Submodular Allocation Problem
I am in Israel for the Algorithmic Game Theory Semester in the Center for the Study of Rationality. It is great to both explore Jerusalem and learn about games and algorithms. I think it is a great opportunity to start blogging again. To start, I decided to write about simple and beautiful algorithm by Lehman, Lehman and Nisan on the allocation problem when players have submodular valuations.
Consider a set of items and agents. Each agent has a monotone submodular valuation over the items, i.e., s.t. for any subsets of and for T. Now, the goal is to partition the items in sets in order to maximize .
This problem is clearly NP-hard (for example, we can reduce from Maximum Coverage or any similar problem), but is has a very simples Greedy Approximation. The approximation goes as follows: start with all sets being empty, i.e., start with then for each item , find the player with maximum and add to this player. This is a -approximation algorithm. The proof is simple:
Let be the sets returned by the algorithm and the optimal solution. Let also and . We can write:
if we added to set it means that by the Greedy rule. Therefore we can write:
where the first inequality follows from the Greedy rule and the second follows from submodularity. Now, we can simply write:
An improved algorithm was given by Dobzinski and Shapira achieving an approximation using demand queries – that are used as a separation oracle for a suitable linear program.