Archive

Posts Tagged ‘submodular’

Submodular Allocation Problem

April 6th, 2011 No comments

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 m items and n agents. Each agent has a monotone submodular v_i valuation over the items,  i.e., v_i:2^{[m]} \rightarrow \mathbb{R} s.t. v_i(S) + v_i(T) \geq v_i(S \cap T) + v_i(S \cup T) for any subsets S,T of [m] and f(S) \leq f(T) for S \subseteq T. Now, the goal is to partition the items in n sets S_1, \hdots, S_n in order to maximize \sum_i v_i(S_i).

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 S_i = \emptyset, \forall i then for each item j, find the player i with maximum v_i(j \vert S_i) = v_i(S_i \cup \{j\}) - v_i(S_i) and add j to this player. This is a 2-approximation algorithm. The proof is simple:

Let S_1, \hdots, S_n be the sets returned by the algorithm and O_1, \hdots, O_n the optimal solution. Let also S_i^{<j} = S_i \cap \{1, 2, \hdots, j-1\} and O_i^{<j} = O_i \cap \{1, 2, \hdots, j-1\}. We can write:

\sum_i v_i(S_i) = \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j})

if we added j to set S_i it means that v_i(j \vert S_i^{<j}) \geq v_k(j \vert S_k^{<j}) by the Greedy rule. Therefore we can write:

\sum_i v_i(S_i) \geq \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j}) \geq \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j})

where the first inequality follows from the Greedy rule and the second follows from submodularity. Now, we can simply write:

\begin{aligned} \sum_i v_i(S_i) & \geq \frac{1}{2} \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j}) + \frac{1}{2} \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j}) \\ & \geq \frac{1}{2} \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j} \cup O_i^{<j}) + \frac{1}{2} \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j}) \\ & \geq \frac{1}{2} \sum_i \sum_{j \in S_i \cup O_i} v_i(j \vert S_i^{<j} \cup O_i^{<j}) \\ & = \frac{1}{2} \sum_i v_i(S_i \cup O_i) \geq \frac{1}{2} \sum_i v_i(O_i) \end{aligned}

An improved algorithm was given by Dobzinski and Shapira achieving an 1 -\frac{1}{e} approximation using demand queries – that are used as a separation oracle for a suitable linear program.

Categories: theory Tags: ,