Submodular Max-Min Allocation Under Identical Valuations

Additivity is one of the simplest assumptions on the valuation functions of the players. In the general version where players may have non-identical additive valuation functions, the state-of-the-art algorithm by Chakrabarty, Chuzhoy and Khanna [7] achieves an approximation factor of $𝒪(n^{\epsilon })$. Interestingly, the best-known lower bound, shown by Bezáková and Dani [6], only rules out a factor better than $2$.

A well-studied special case is the so-called restricted assignment case, where players have identical valuations, but a bipartite graph between items and players restricts the allowed allocations. To tackle this problem, Bansal and Sviridenko [4] introduced the configuration LP, and subsequent work [4, 2, 22, 1] led to the current best approximation factor of $\frac{1}{4}-\epsilon$ for the problem [10]. Recently, the integrality gap of the configuration LP for restricted assignment was shown to be at most $3.53$ [15]. For identical valuations, Woeginger designed a polynomial-time approximation scheme (PTAS) [30].

The first approximation algorithm for general submodular valuations was given in [14], and even though improvements have been made [13], the best-known approximation factor remains polynomial in the input. For a constant number of players, Chekuri, Vondrák and Zenklusen [8] gave a $1-1/e$-approximation.

For max-sum, Vondrak gave a $1-1/e$-approximation [29], which was shown to be optimal [17, 21]. In the restricted assignment case, Bamas, Morell and Rohwedder [3] generalized the techniques from Bansal and Sviridenko to obtain a $𝒪(\log \log n)$-approximation. Under identical valuations, Krause, Rajagopal, Gupta and Guestrin [18] gave the first constant-factor approximation algorithm, which uses an algorithm for max-sum as a subroutine. Plugging in Vondrak’s optimal algorithm, their method achieves a $\frac{e-1}{3e}\approx 0.21$-approximation.

More recently, another line of research has studied the problem of finding an allocation which approximates the maximin share of all players, which is the largest value a player can ensure by proposing an allocation and receiving the bundle which is worst for them. Under identical valuations, this problem is equivalent to submodular max-min allocation. Barman and Krishnamurthy [5] gave a different algorithm with the same guarantee as Krause et al. [18]. Ghodsi, Hajiaghayi, Seddighin, Seddighin and Yami [12] improved this factor to $\frac{1}{3}$. Finally, Uziahu and Feige [28] gave a $\frac{10}{27}$-approximation by analyzing a bidding procedure which uses a truncated version of the valuation function.

If we reverse the roles of max and min, we obtain the classical makespan minimization setting, where we try to assign jobs to machines so as to minimize the latest completion time. As its max-min counterpart, it admits a PTAS for identical additive valuations [16]. The submodular variant of makespan minimization, sometimes called submodular load balancing, is not $o\left(\sqrt{\frac{n}{\log n}}\right)$-approximable [27]. This stands in stark contrast to its “dual” max-min variant.

Khot, Lipton, Markakis and Mehta [17] showed that when players have identical valuations, it is NP-hard to distinguish between the case where all players can achieve value $1$ and the case where a player achieves at most value $1-\frac{1}{e}+\epsilon$ on average. Since the average value is always at least as big as the min value, their hardness result, while originally designed for max-sum, immediately translates to our setting:

Removing $k$ players and all items in ${\bigcup }_{i=1}^k{A}_{p_i}$ from the instance leads to a smaller counter-example: The greedy algorithm still behaves identically on all other players, including $q$, so there is a valid greedy allocation $A^{\prime }$ on the instance with $f_{\mathrm{𝗆𝗂𝗇}}(A^{\prime })\le 2$. On the other hand, since all removed items only belonged to $k$ players in the optimal solution, removing these $k$ players gives a solution $A^{\ast \ast }$ with $f(A_p^{\ast \ast })\ge 5$ for all remaining players $p$. $◀$

The above lemma allows us to prove the existence of a “fixed” item for each player:

Consider the bipartite graph $G=(P\cup P^{\prime },E)$ with the set of players $P$ on the left side and a copy $P^{\prime }$ of the set of players on the right side, and edges $(p,p^{\prime })$ if $A_p\cap A_{p^{\prime }}^{\ast }\ne \mathrm{\varnothing }$. Let $N(Q)={\bigcup }_{q\in Q}\{v\in V\mid (q,v)\in E\}$ be the neighbourhood of $Q$. Consider an arbitrary non-empty subset $Q\subseteq P-\{q\}$. By Lemma 3.6, $|N(Q)|\ge |Q|+1$. For the set $\{q\}$, we have $|N(\{q\})|\ge 1$ since $A_q\ne \mathrm{\varnothing }$ and each item in $q$ must be allocated somewhere in the optimal solution. For the set $\mathrm{\varnothing }$, we have $|N(\mathrm{\varnothing })|\ge 0=|\mathrm{\varnothing }|$. For any other set $\{q\}\subset Q\subseteq P$, we know that $|N(Q)|\ge |N(Q-\{q\})|\ge |Q-\{q\}|+1=|Q|$. Altogether, we obtain that for any subset $Q\subseteq P$, $|N(Q)|\ge |Q|$. We can hence apply Hall’s Marriage Theorem to conclude that $G$ contains a perfect matching. This matching defines exactly the desired permutation $\varphi$. $◀$ To simplify notation, we consider an optimal solution such that $\varphi$ is the identity function, by just permuting the allocations of the players in the optimal solution. We now define the reallocation digraph $G=(P,E)$: Each pair of players $(p,r)\in P^2$ is associated to a set $A_{p\to r}=A_p\cap A_r^{\ast }$. An arc $(p,r)$ exists if $A_{p\to r}\ne \mathrm{\varnothing }$. By Lemma 3.7, each vertex has a self-loop.

We subdivide the players of our instance into two categories $P=B\cup S$. The set $B$ of big players consists of all players $b$ such that $f(A_b)>4-\beta$. The set $S$ of small players consists of all players $p$ with $f(A_p)\le 4-\beta$.

Notice that $q\in S$. This partition is mainly motivated by the following observation:

Any player $p\in B$ cannot be allocated just one item $j$ since . If $p$ was allocated $k$ items for $k>2$, then must hold in order for the greedy algorithm to allocate $a_p^k$ to $p$. But since $f(a_p^1)\ge \beta$, we must have ${\mathrm{\Delta }}_f(a_p^k\mid \{a_p^1,\mathrm{\dots },a_p^{k-1}\})\le {\mathrm{\Delta }}_f(a_p^2\mid \{a_p^1\})\le 2-\beta$. So we have

contradicting our assumption $k>2$. $◀$

For each $p\in B$, denote by $x_p$ the item in $A_{p\to p}$ and denote by $y_p$ the other item of $A_p$. Lemma 3.7 guarantees the existence of the first item and Observation 3.8 implies that there is exactly one other item. Lemma 3.6 guarantees that the other item is not in $A_{p\to p}$.

Suppose for contradiction that $A_{b\to c}\ne \mathrm{\varnothing }$, where $y_b\in A_{b\to c}$. Let $p\in P$ be the player such that $y_c\in A_p^{\ast }$. Consider a modified instance where we remove player $c$ as well as items $\{y_b,x_c,y_c\}$ and add an item $z$ which contributes an additive factor of $t:=\max (f(y_b),{\mathrm{\Delta }}_f(y_c\mid A_p^{\ast }-\{y_c\}))$ to every set. This function is submodular and monotone. Notice that this addition of $z$ does not change any marginal contribution, i.e. for $j\ne z$ we have ${\mathrm{\Delta }}_f(j\mid S)={\mathrm{\Delta }}_f(j\mid S\cup \{z\})$.

The greedy algorithm on the new instance may allocate all items that give marginal contribution larger than $t$ in the original run as before. As soon as all remaining items give marginal contribution $\le t$, it may choose to allocate item $z$ to player $b$ (since $z$ contributes the same to each player, and greedy considers $b$ as or ).

Since $b\in B$, we have $f(A_b)>4-\beta \ge 2$. Furthermore, $f(\{x_b,z\})\ge f(x_b)+f(y_b)\ge f(A_b)\ge 2$. Consider the moment in the greedy algorithm after $z$ was allocated to $b$. If $x_b$ had already been allocated, then $b$ has reached the threshold of $2$ and will be thus ignored by the greedy algorithm. Therefore, all following items can be allocated to the same players as in the original run of the greedy algorithm. Now suppose $x_b$ had not yet been allocated. Since the addition of $z$ to player $b$ does not influence the marginal contributions and , the greedy algorithm can allocate all items up to $x_b$ in the same way (including $x_b$). After allocating $x_b$, player $b$ has reached the threshold of $2$ and thus again the greedy algorithm can allocate in the same way as in the original run. Thus, we again obtain $f_{\mathrm{𝗆𝗂𝗇}}(A_q^{\prime })\le 2$, for the new allocation $A^{\prime }$.

On the other hand, we can modify our old optimal allocation, by just replacing item $y_c$ by item $z$. Call the new optimal allocation $A^{\ast \ast }$. We have

We obtained a counterexample with less players, a contradiction. $◀$ Thus, in fact, $G[B]$ is an independent set. We now argue that $B$ cannot be too large. To this end, we first prove the following two helpful lemmata. For a player $p$, let us define $V_p:={\bigcup }_{(r,p)\in E}{A}_{r\to p}$ the set of items reallocated to $p$ and $W_p:={\bigcup }_{(p,r)\in E}{A}_{p\to r}$ the set of items reallocated from $p$.

Recall that $A^{(j)}$ denotes the partial greedy allocation exactly before item $j$ is allocated. Let $\mathrm{\ell }$ be the last item allocated to $A_p$. By Lemma 3.7, there exists an item $k\in A_{p\to p}$. Therefore, $W_p\subseteq A_p-\{k\}$ and we can write

The third inequality is because the items were allocated to $p$ and not $q$. The fourth inequality comes from $A_p^{(\mathrm{\ell })}\supseteq A_p^{(k)}$, then we use that at the partial allocation $A^{(k)}$, greedy prefered $k$ over $\mathrm{\ell }$. Finally, the strict inequality holds because otherwise $p$ would have achieved the $\alpha \cdot \mathrm{𝖮𝖯𝖳}$ threshold and not received any more items. $◀$

First, notice that

Since $V_p=A_p^{\ast }-(A_p-W_p)$, $A_p-W_p\subseteq A_p^{\ast }$, and $W_p\subseteq A_p$, we can write

Now, the result follows by using (7) and (1). $◀$

Let $S_0$ be the set of small players that do not receive any item from big players, let $S_1$ be the set of small players that receive one item from one big player and let $S_{\ge 2}$ be the set of small players that receive items from multiple big players. If we can show $S_{\ge 2}=\mathrm{\varnothing }$, this means that no two big players have an edge towards the same small player. But since every big player has an edge towards a small player by Lemma 3.9, by pigeonhole principle this would imply the desired $|B|\le |S|$.

Associate with each player $p$ the quantity

Note that ${\sum }_{p\in P}g(p)=0$, as ${\bigcup }_{p\in P}{W}_p={\bigcup }_{p\in P}{V}_p$. We can decompose the set of players as

where $b_i(p)$ denotes the $i$-th big player that gives an item to $p$, in an arbitrary order. Therefore,

Since ${\sum }_{p\in P}g(p)=0$, to prove $S_{\ge 2}=\mathrm{\varnothing }$, it is enough to show that all terms of (8) are $\le 0$, and that terms of the last sum are . This is the purpose of the rest of the proof.

1. 1.

   $g(p)\le 0$ for $p\in S_0$. This follows directly from Lemma 3.11 and $f(A_p)\le 4-\beta \le 3$.

2. 2.

   $g(s)+g(b)\le 0$ for $s\in S_1$ and $b=b_1(s)$. Since $s$ is a small player, we have $f(A_s)\le 4-\beta$, and by Lemma 3.11, we get $g(s)\le 1-\beta$. If we can show $g(b)\le \beta -1$, then this implies $g(s)+g(b)\le 0$. Recall that $W_b=\{y_b\}$.

   As the second item allocated to $b$ contributes at most $\beta$, we have ${\mathrm{\Delta }}_f(x_b\mid A_q)+{\mathrm{\Delta }}_f(y_b\mid A_q)\le 2+\beta$. By the facts $f(A_b^{\ast })-f(A_q)\ge 3$ and $A_b^{\ast }=V_b\cup (A_b-W_b)$, we get

   	${\displaystyle \sum _{j\in V_b}}{\mathrm{\Delta }}_f(j\mid A_q)$	$\ge {\mathrm{\Delta }}_f(V_b\cup (A_b-W_b)\mid (A_b-W_b)\cup A_q)$
   		$={\mathrm{\Delta }}_f(A_b^{\ast }\mid (A_b-W_b)\cup A_q)$
   		$\ge f(A_b^{\ast })-{\mathrm{\Delta }}_f(A_b-W_b\mid A_q)-f(A_q)$
   		$\ge 3-{\mathrm{\Delta }}_f(x_b\mid A_q)$

   In total, $g(b)\le {\mathrm{\Delta }}_f(y_b\mid A_q)-{\sum }_{j\in V_b}{\mathrm{\Delta }}_f(j\mid A_q)\le {\mathrm{\Delta }}_f(y_b\mid A_q)-3+{\mathrm{\Delta }}_f(x_b\mid A_q)\le \beta -1.$

3. 3.

   for $s\in S_{\ge 2}$, $b=b_1(s)$ and $c=b_2(s)$. We have $f((A_b-W_b)\cup A_q)\le f(A_b-W_b)+f(A_q)\le 4$, but since $f(A_b^{\ast })\ge 5$, we must have

   $$\sum _{j\in V_b}{\mathrm{\Delta }}_f(j\mid A_q)\ge {\mathrm{\Delta }}_f(V_b\cup (A_b-W_b)\mid (A_b-W_b)\cup A_q)\ge 1.$$

   The same holds for player $c$. By Lemma 3.10, we also know . Therefore

$◀$ We can conclude as follows:

where the last inequality is because $2+\beta \ge 4-\beta$, and $|B|\le |S|$ by Lemma 3.12. This contradicts $\mathrm{𝖺𝗏𝗀}>3$, as stated in the beginning. This finishes the proof of Theorem 1.1.

We discuss the (close-to-) tightness of this analysis in the full paper version. In particular, we show that no value of $\alpha$ can lead to an approximation factor better than $\frac{2+S}{4+3S}\approx 0.4068$, where $S={\sum }_{i=1}^{\mathrm{\infty }}\frac{1}{s_i-1}$ with $s_k=1+{\prod }_{i=1}^n{s}_i$ is a constant related to the Sylvester sequence or Salzer sequence and was already used in [20, 24] for other packing problems.

Since $y_{j^{\ast }}$ is not involved in any tight constraint, we can lower its value by a sufficiently small amount, satisfying the value constraint while keeping all configuration constraints satisfied. $◀$

Fix an arbitrary player $p\in P$. For an optimal solution $x$ to (P), we have