### Archive

Posts Tagged ‘submodular’

## 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 $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^{ and $O_i^{. We can write:

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

if we added $j$ to set $S_i$ it means that $v_i(j \vert S_i^{ 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^{

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^{

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: