Proof. We simplify the notation a little further to make the proof readable. Define \(a = v(X_i \setminus S_i)\), \(b = v(X_j \setminus S_j)\), \(c = v(S_j)\) and \(d = v(S_i)\). The lemma requires that \(a \ge b\) and \(c \ge d\). \[\begin{align} v(Y_i)v(Y_j) &= (v(X_i \setminus S_i) + v(S_j))(v(X_j \setminus S_j) + v(S_i)) \\ &= (a + c)(b + d) \\ &= (a + d)(b + c) + (a-b)(d-c) \\ &\le (a+d)(b+c) \\ &= v(X_i)v(X_j). \end{align}\] In the inequality, we use the fact that \((a - b)(d -c) \le 0\) since \(a \ge b\) and \(c \ge d\). Note that equality holds if and only if \((a-b)(d-c) = 0\); that is either \(a = b\) or \(c = d\) or both. ◻

Proof. The proof follows using Jensen’s inequality. \[\mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{NSW}}(X)] = \mathop{\mathrm{\mathbb{E}}}[e^{\normalfont{\texttt{logNSW}}(X)}] \ge e^{\mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{logNSW}}(X)]} \ge e^{t}. \qedhere\] ◻

Proof. [1] shows that when agents have identical valuations, any envy-free up to one good allocation is an \(e^{1/e}\)-approximation of the max Nash welfare. By Fact 8, \(W\) is envy-free up to one good. ◻

Proof. Let \(X^*\) be the Nash optimal allocation in this instance. We first show that any agent in \(X^*\) who receives a large good does not receive any other positively valued good. Assume for contradiction that an agent \(i\) who receives the large good \(g\) receives a set of other goods \(S_i\) such that \(v(S_i) > 0\). Consider the agent \(j\) who is the worst off among the agents who do not receive a large good; that is, \(j\) minimizes \(v(X^*_j)\) among the agents who do not receive a large good. Since \(\ell \le \Delta - 1\), such a \(j\) must exist. This agent \(j\) receives utility at most \(\frac{v(G \setminus L)}{\Delta - \ell} < v(g)\). Therefore, moving the bundle \(S_i\) from agent \(i\) to agent \(j\) strictly increases Nash welfare (using Lemma 1). This contradicts the optimality of \(X^*\).

Let \(N_L\) be the set of agents who receive a large good in \(X^*\). Let \(N_S\) be the set of all the other agents. Since each agent in \(N_L\) receives exactly one good of positive value, \[\begin{align} \prod_{i \in N_L} v(X^*_i) = \prod_{g \in L} v(g). \label{eq:nash-upper-bound-1} \end{align}\tag{5}\]

We can upper bound the product of all other agents’ utilities using the AM-GM inequality: \[\begin{align} \prod_{i \in N_S} v(X^*_i) \le \left ( \frac{v(G \setminus L)}{\Delta - \ell}\right )^{\Delta - \ell}. \label{eq:nash-upper-bound-2} \end{align}\tag{6}\]

Combining 5 and 6 proves the first statement of the lemma. The second statement follows from applying a logarithm on both sides of the first statement, and using Fact 2. ◻

Proof. The set of small goods \(G \setminus L\) is the set \(\{g_{\ell + 1}, \dots, g_{m}\}\). Therefore, the allocation of small goods \((S_1, \dots, S_{\Delta})\) is equivalent to the round robin allocation of the small goods \(G \setminus L\) with picking sequence \((\ell +1, \ell + 2, \dots, \Delta, 1, 2, \dots, \ell)\). Therefore, the observation follows from Fact 7. ◻

Proof. To prove this result, we lower bound \(v(W_{\Delta})\) using the following relation:

\[\begin{align} \mu \Delta = v(G \setminus L) = \sum_{i \in [\Delta]} v(S_i) \end{align}\]

We upper bound \(\sum_{i \in [\Delta]} v(S_i)\) using the grouping of the agents we constructed earlier. For all the agents \(i \in N_L\), \(v(S_i) \le v(W_{\Delta})\) from Observation 10. For all the agents \(i \in N_3 \cup N_4\), \(v(S_i) \le \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\) using Fact 8. For the agents \(i \in N_4\), we additionally have \(v(S_i) \le (1 + \gamma^2)\frac{\Delta \mu}{\Delta - \ell}\). For the remaining agents in \(N_5\), we have \(\sum_{i \in N_5} v(S_i) = \sum_{i \in N_5} v(W_i) = \alpha\frac{\Delta \mu}{\Delta - \ell} + (|N_5| - \alpha)v(W_{\Delta})\). Combining all of these inequalities, we get:

\[\begin{align} \mu \Delta &= \sum_{i \in [\Delta]} v(S_i) \notag \\ &= \sum_{i \in N_L} v(S_i) + \sum_{i \in N_3} v(S_i) + \sum_{i \in N_4}v(S_i) + \sum_{i \in N_5} v(S_i) \notag\\ &\le |N_L| v(W_{\Delta}) + |N_3| \left ( \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\right ) + |N_4| \min\left \{\left ( \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\right ), (1 + \gamma^2)\frac{\Delta \mu}{\Delta - \ell} \right \} \notag\\ &\qquad \qquad + \alpha\frac{\Delta \mu}{\Delta - \ell} + (|N_5| - \alpha)v(W_{\Delta}) \label{eq:w-delta-lower-bound-1}. \end{align}\tag{8}\]

Depending on how we upper bound the \(\min\{\}\) function, we get two different lower bounds on \(v(W_{\Delta})\). We first use \(\min\left \{\left ( \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\right ), (1 + \gamma^2)\frac{\Delta \mu}{\Delta - \ell} \right \} \le \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\). This simplifies 8 to: \[\begin{align} \mu \Delta \le |N_L| v(W_{\Delta}) + (|N_3| + |N_4|)\left ( \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\right ) + \alpha\frac{\Delta \mu}{\Delta - \ell} + (|N_5| - \alpha)v(W_{\Delta}) \end{align}\]

Re-arranging terms and using the facts that \(\Delta = |N_L| + |N_3| + |N_4| + |N_5|\) and \(\Delta - \ell = |N_S| = |N_3| + |N_4| + |N_5|\), we get \[\begin{align} \frac{v(W_{\Delta})(\Delta - \ell)}{\Delta \mu} \ge \frac{|N_5| - \alpha}{\Delta - \alpha}. \end{align}\]

This implies \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_\Delta)(\Delta-\ell)}{\Delta \mu} \right) &\ge \frac{(|N_5| - \alpha)}{\Delta}\ln \left ( \frac{|N_5| - \alpha}{\Delta - \alpha} \right ) \notag \\ & = \frac{(|N_5| - \alpha)}{\Delta}\ln \left ( \frac{|N_5| - \alpha}{\Delta} \right ) + \frac{(|N_5| - \alpha)}{\Delta} \ln \left (\frac{\Delta}{\Delta - \alpha} \right ). \label{eq:w-delta-lower-bound-2} \end{align}\tag{9}\]

The first term is minimized when \(|N_5| - \alpha = \frac{\Delta}{e}\) and achieves a minimum value of \(-\frac{1}{e}\) (Fact 2). The second term is non-negative. This shows that \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge -\frac{1}{e}. \end{align}\]

This proves the second part of the lemma. Additionally, when \(\frac{|N_5| - \alpha}{\Delta}\) is not in the interval \(\left [\frac{1}{e} - 10^{-4}\gamma, \frac{1}{e} + 10^{-4}\gamma \right]\), there is some constant \(c'_1\) such that \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge -\frac{1}{e} + c'_1 + \frac{(|N_5| - \alpha)}{\Delta} \ln \left (\frac{\Delta}{\Delta - \alpha} \right ) \\ &\ge -\frac{1}{e} + c'_1. \end{align}\]

This shows that if condition (i) is satisfied, then we achieve our desired result. So from here on we assume condition (i) is not satisfied. Consider the case where condition (ii) is satisfied. In this case, 9 reduces to \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge -\frac{1}{e} + \frac{(|N_5| - \alpha)}{\Delta} \ln \left (\frac{\Delta}{\Delta - \alpha} \right ) \\ &\ge -\frac{1}{e} + \frac{1}{3} \ln \left (\frac{1}{1 - 10^{-4}\gamma^4} \right ). \end{align}\] The final inequality uses our assumptions that condition (i) is not satisfied but condition (ii) is satisfied. Therefore, if condition (ii) is satisfied, then for \(c'_2 = \frac{1}{3} \ln \left (\frac{1}{1 - 10^{-4}\gamma^4} \right )\), we have \(\frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) \ge -\frac{1}{e} + c'_2\). This is our desired result. So from here on we assume condition (ii) is not satisfied.

To prove our result for condition (iii), we return to 8 and upper bound \(\min\left \{\left ( \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta})\right ), (1 + \gamma^2)\frac{\Delta \mu}{\Delta - \ell} \right \}\) using \((1 + \gamma^2)\frac{\Delta \mu}{\Delta - \ell}\). Using a similar analysis, we get \[\begin{align} \frac{v(W_{\Delta})(\Delta - \ell)}{\mu \Delta} \ge \frac{|N_5| - \alpha - \gamma^2 |N_4|}{\Delta - \alpha - |N_4|} &\ge \frac{|N_5| - \alpha - \gamma^2 |N_4|}{\Delta- |N_4|}. \end{align}\]

The right hand side of the above inequality can be simplified as follows using basic arithmetic operations and using \(|N_5| - \alpha \ge \frac{\Delta}{3}\) (from condition (i) not being satisfied): \[\begin{align} \frac{v(W_{\Delta})(\Delta - \ell)}{\mu \Delta} &\ge \frac{|N_5| - \alpha - \gamma^2 |N_4|}{\Delta- |N_4|} \\ &\ge \frac{|N_5| - \alpha}{\Delta} \left [ \frac{1 - \frac{\gamma^2 |N_4|}{|N_5| - \alpha}}{1 - \frac{|N_4|}{\Delta}} \right ] \\ &\ge \frac{|N_5| - \alpha}{\Delta} \left [ \frac{1 - \frac{3\gamma^2 |N_4|}{\Delta}}{1 - \frac{|N_4|}{\Delta}} \right ] \\ &\ge \left (\frac{|N_5| - \alpha}{\Delta} \right ) e^{\frac{|N_4|}{\Delta}(1 - 6\gamma^2)}. \end{align}\]

This implies \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge \frac{(|N_5| - \alpha)}{\Delta} \ln \left ( \frac{|N_5| - \alpha}{\Delta} \right ) + \left (\frac{|N_5| - \alpha}{\Delta} \right )\left (\frac{|N_4|}{\Delta}(1 - 6\gamma^2) \right ) \\ &\ge -\frac{1}{e} + \frac{1}{3} \left (\frac{|N_4|}{\Delta}(1 - 6\gamma^2) \right ). \end{align}\]

Therefore, if \(|N_4| \ge 10^{-4}\gamma^2 \Delta\) (condition (iii) is satisfied), then there is some positive constant \(c'_3\) such that \(\frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) \ge - \frac{1}{e} + c'_3\).

Finally, to prove our result for condition (iv), we directly plug in the lower bound on \(v(W_{\Delta})\). This gives us: \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{(1 + 10^{-4}\gamma^2)(\Delta-\ell)}{\Delta} \right) \\ &\ge \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{(\Delta-\ell)}{\Delta} \right ) + \frac{(|N_5| - \alpha)}{\Delta}\ln(1 + 10^{-4}\gamma^2). \end{align}\]

To simplify this further, we use the fact that \(|N_5| - \alpha\) is lowerbounded by \(\frac{\Delta}{3}\) (from condition (i) not being satisfied) and upper bounded by \(\Delta - \ell\). This gives us \[\begin{align} \frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) &\ge \frac{(\Delta - \ell)}{\Delta}\ln \left (\frac{(\Delta-\ell)}{\Delta} \right )+ \frac{1}{3}\ln(1 + 10^{-4}\gamma^2) \\ &\ge -\frac{1}{e} + \frac{1}{3}\ln(1 + 10^{-4}\gamma^2). \end{align}\]

This shows that if condition (iv) is satisfied, we prove our desired result with constant \(c'_4 = \frac{1}{3}\ln(1 + 10^{-4}\gamma^2)\). In conclusion, the lemma is proved with constant \(c_1 = \min\{c'_1, c'_2, c'_3, c'_4\}\). ◻

Proof. We return to 7 . Lemma 4 shows that \(\frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) \ge -\frac{1}{e}\). Using this lower bound, 7 simplifies to \[\begin{align} \normalfont{\texttt{logNSW}}(W) &\ge \frac{1}{\Delta} \left [\sum_{g \in L} \ln v(g) + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta - \ell} \right ] + \frac{(|N_2| + |N_3|)}{\Delta}\ln(1 + \gamma^2) -\frac{1}{e}. \end{align}\] The above inequality immediately proves the second part of the lemma. Additionally, if either (a) or (b) holds, the above inequality further simplifies to \[\begin{align} \normalfont{\texttt{logNSW}}(W) &\ge \frac{1}{\Delta} \left [\sum_{g \in L} \ln v(g) + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta - \ell} \right ] + 10^{-4}\gamma^2\ln(1 + \gamma^2) -\frac{1}{e}. \end{align}\]

This proves our desired result for the conditions (a) and (b). If any of the remaining four conditions hold, Lemma 4 shows that \(\frac{(|N_5| - \alpha)}{\Delta}\ln \left (\frac{v(W_{\Delta})(\Delta-\ell)}{\Delta \mu} \right) \ge -\frac{1}{e} + c_1\). Plugging this into 7 gives us \[\begin{align} \normalfont{\texttt{logNSW}}(W) &\ge \frac{1}{\Delta} \left [\sum_{g \in L} \ln v(g) + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta - \ell} \right ] - \frac{1}{e} + c_1. \end{align}\]

This proves our desired result for the conditions (c), (d), (e) and (f). ◻

Proof. Note that \(\ell = |N_L| = \Delta - |N_3| - |N_4| - |N_5|\). If [prop:a] is violated, one of the following conditions must hold:

(a) \(|N_3| \ge 0.01\gamma \Delta\),

(b) \(|N_4| \ge 0.01\gamma \Delta\),

(c) \(\frac{|N_5| - \alpha}{\Delta} \notin \left [\frac{1}{e} - 0.01\gamma, \frac{1}{e} + 0.01\gamma \right]\),

(d) \(\alpha \ge 0.01\gamma\Delta\).

If any of these conditions are true, Lemma 5 shows that \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \frac{1}{\Delta} \left [\sum_{g \in L} \ln v(g) + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta - \ell} \right ] -\frac{1}{e} + c_2. \end{align}\]

The result follows by combining the above inequality with Lemma 3. ◻

Proof. [prop:c] is violated if and only if \(|N_2| \ge \gamma^2 \Delta\). In this case, Lemma 5 shows that \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \frac{1}{\Delta} \left [\sum_{g \in L} \ln v(g) + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta - \ell} \right ] -\frac{1}{e} + c_2. \end{align}\]

The result follows by combining the above inequality with Lemma 3. ◻

Proof. In this proof, we assume for contradiction that none of the conditions in Lemma 5 are satisfied. Note that this also implies [prop:a] and [prop:c] are satisfied by the instance. We will show that if [prop:b] is violated, then one of the conditions of Lemma 5 is satisfied. This then implies the lemma via Lemma 3.

Assume [prop:b] is violated such that there are at least \(\frac{\gamma \Delta}{2}\) agents \(i\) with \(v(S_i) \le (1 - \gamma)\mu\). Let \(N'\) be the set of \(i\) such that \(i \le \ell\) and \(v(S_i) \le (1 - \gamma)\mu\). Note that \(|N'| \ge \frac{\gamma \Delta}{2}\) using Observation 10 and the fact that \(\ell \ge \frac{\Delta}{2}\) (assuming Property A is satisfied). Recall that \(\Delta \mu = \sum_{i \in [\Delta]} v(S_i)\). Let \(\mu^*\) denote the mean of \(v(S_i)\) among all the agents in \([\Delta] \setminus N'\).

\[\begin{align} \mu^* = \frac{1}{\Delta - |N'|} \sum_{i \in [\Delta] \setminus N'} v(S_i) &\ge \frac{1}{\Delta - |N'|} \left (\Delta \mu - |N'|(1- \gamma) \mu\right ) \\ &\ge \frac{1}{\Delta - \frac{\gamma \Delta}{2}} \left (\Delta \mu - \frac{\gamma \Delta}{2} (1 - \gamma) \mu \right )\\ &\ge \mu \left ( 1 + \frac{\gamma^2}{2} \right ). \end{align}\]

From Observation 10, the bundles \(\{S_{\ell+1}, \dots, S_\Delta\}\) are the \(\Delta-\ell\) highest valued small bundles. Therefore, \[\begin{align} \sum_{i \in N_S} v(W_i) \ge \mu^* |N_S| \ge \mu |N_S| \left (1 + \frac{\gamma^2}{2} \right ). \end{align}\]

Moreover, using Fact 8, for any agent \(i \in N_S\), \[\begin{align} v(W_i) \le \max_{g \in W_i}v(g) + v(W_{\Delta}) \le \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta}) \le 3\mu + (1 + 10^{-4}\gamma^2)\mu \le 5\mu. \end{align}\] In this inequality, we assume [prop:a] is satisfied and \(v(W_{\Delta}) \le (1+10^{-4}\gamma^2) \mu\) (Lemma 5[condition (f)]).

Using a simple counting argument, at least \(\frac{\gamma^2 |N_S|}{20} \ge \frac{\gamma^2 \Delta}{60}\) agents \(i \in N_S\) have \(v(W_i) \ge \left (1 + \frac{\gamma^2}{4} \right ) \mu\). Let \(\widetilde{N}\) denote the set of these agents.

Since \(\widetilde{N}\) only contains agents who do not receive a large good, one of \(N_3 \cap \widetilde{N}, N_4 \cap \widetilde{N}\) and \(N_5 \cap \widetilde{N}\) must have size at least \(\frac{\gamma^2 \Delta}{200}\). If \(N_3\) or \(N_4\) have size at least \(\frac{\gamma^2 \Delta}{200}\), then one of conditions (b) and (e) in Lemma 5 must be satisfied — a contradiction. Therefore, it must be that \(|N_5 \cap \widetilde{N}| \ge \frac{\gamma^2 \Delta}{200}\). In this case, we lower bound \(\alpha\).

To lower bound \(\alpha\), we lower bound the \(\alpha_i\) values. For any agent \(i \in \widetilde{N} \cap N_5\), we have \(\alpha_i \ge \frac{\gamma^2}{24}\). This follows from the following sequence of inequalities. \[\begin{align} v(W_i) \ge \left (1 + \frac{\gamma^2}{4} \right )\mu = \frac{\gamma^2}{24} (3\mu) + \left (1 + \frac{\gamma^2}{8} \right )\mu \ge \frac{\gamma^2}{24} \frac{\Delta \mu}{\Delta - \ell} + v(W_{\Delta}). \end{align}\] In the final inequality we use both Property A and Lemma 5[condition (f)].

Summing over all \(i \in \widetilde{N} \cap N_5\), we get \(\alpha \ge \sum_{i \in \tilde{N} \cap N_5} \alpha_i \ge 10^{-4} \gamma^4 \Delta\). This implies that condition (d) of Lemma 5 is satisfied — another contradiction. This shows that when \(\frac{\gamma \Delta}{2}\) agents \(i\) have \(v(S_i) \le (1 - \gamma)\mu\), the lemma holds.

The proof for the other case, where there are \(\frac{\gamma \Delta}{2}\) agents \(i \in N_S\) with \(v(W_i) \ge (1 + \gamma)\mu\) follows using a similar argument. In summary, if [prop:b] is not satisfied, one of the conditions of Lemma 5 must be satisfied, which implies \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \normalfont{\texttt{logNSW}}(\mathcal{I}) -\frac{1}{e} + c_2. \end{align}\] This proves the lemma. ◻

Proof. We define \(G' \subseteq G\) as the set of goods with value at least \(0.99\mu\). All the large goods trivially fall into \(G'\) since each large good has value of at least \(\frac{\Delta \mu}{\Delta - \ell}\) and \(\ell \ge \left (1 - 1/e - \gamma \right )\Delta\) ([prop:a]).

Consider the small bundle of an agent \(i\) who receives a large good; that is, \(i \le \ell\). By our construction, \(S_i = \{g_{\Delta + i}, g_{2\Delta + i}, \dots\}\). The bundle \(S_i \setminus \{g_{\Delta + i}\} = \{g_{2\Delta + i}, g_{3\Delta + i}, \dots\}\) is at most as valuable as \(S_{\ell} = \{g_{\Delta + \ell}, g_{2\Delta + \ell}, \dots\}\). This has two implications. First, the only good in \(S_i\) which can be in \(G'\) is \(g_{\Delta + i}\). Second, we can lower bound \(v(g_{\Delta + i})\) using \(v(S_{\ell})\) as follows: \[\begin{align} v(S_i) = v(g_{\Delta + i}) + v(S_i \setminus \{g_{\Delta + i}\}) \le v(g_{\Delta + i}) + v(S_\ell) \le v(g_{\Delta + i}) + 10^{-4}\mu. \end{align}\] Re-arranging the terms of this inequality, we get for all agents \(i \in [\ell]\) \[\begin{align} v(g_{\Delta + i}) \ge v(S_i) - 10^{-4}\mu. \label{eq:large-small-bundle} \end{align}\tag{10}\]

We can make a similar argument about agents who do not receive a large good. If an agent \(i\) does not receive a large good, \(S_i = \{g_i, g_{\Delta + i}, \dots\}\). The bundle \(S_i \setminus \{g_{i}\} = \{g_{\Delta + i}, g_{2\Delta + i}, \dots\}\) is at most as valuable as \(S_{\ell} = \{g_{\Delta + \ell}, g_{2\Delta + \ell}, \dots\}\). Using a similar argument, we get that the only good from \(G'\) in \(S_i\) is the good \(g_i\), and we get for all agents \(i > \ell\), \[\begin{align} v(g_i) \ge v(S_i) - 10^{-4}\mu. \label{eq:small-small-bundle} \end{align}\tag{11}\]

By [prop:b], all but \(\gamma \Delta\) agents satisfy \(v(S_i) \ge (1 - \gamma)\mu\). Let \(N'\) be the set of these agents \(i \in [\Delta]\) such that \(v(S_i) \ge (1 - \gamma)\mu\). For all the agents \(i \in N'\), from 10 and 11 , there is exactly one good in each small bundle \(S_i\) with value at least \(0.99\mu\). Using this, we can upper bound the total value of \(G \setminus G'\) as follows: \[\begin{align} v(G \setminus G') &\le v(\{g_{\Delta + \ell}, g_{\Delta + \ell + 1}, \dots, g_m\})+\sum_{i \in [\Delta] \setminus N'} v(S_i) \notag\\ &\le \Delta v(S_{\ell}) + \sum_{i \in [\Delta] \setminus N'} v(S_i) \notag \\ &\le \Delta v(S_{\ell}) + \gamma \Delta (1 - \gamma) \mu \notag\\ &\le 2 \cdot 10^{-4} \Delta \mu. \label{eq:g-minus-gprime} \end{align}\tag{12}\] Additionally, \(|G'| \in [\Delta + \ell - \gamma \Delta, \Delta + \ell]\) since each small bundle \(S_i\) has at most one good in \(G'\) and at least \(\Delta - \gamma \Delta\) small bundles have one good in \(G'\).

Let \(X^*\) denote the optimal Nash allocation of \(\mathcal{I}\). To upper bound the Nash welfare of \(X^*\), we consider the optimal Nash allocation where the goods in \(G'\) are allocated integrally and all the other goods are allocated fractionally. Formally, this is a fractional allocation with the constraint that the goods in \(G'\) are allocated integrally. It is easy to see that the optimal Nash welfare of such an allocation upper bounds the Nash welfare of any fully integral allocation in this instance. We denote this allocation using \((Z^*, p)\) where \(Z^*_i\) denotes the goods allocated from \(G'\) to agent \(i\), and \(p_i\) denotes the total value allocated from the goods in \(G \setminus G'\) to agent \(i\). Note that \(\sum_{i \in [\Delta]} p_i = v(G \setminus G') \le 2\cdot 10^{-4} \Delta \mu\) (from 12 ). In this allocation, the utility of agent \(i\) is given by \(v(Z^*_i) + p_i\). For all agents \(i\), we denote \(g^*_i\) as the highest valued good in the bundle \(Z^*_i\).

We may assume, without loss of generality, \(Z^*_i\) is non-empty for each agent \(i \in [\Delta]\). This holds due to the following swapping argument. Assume that \(Z^*_i = \emptyset\). There must be some other agent \(j\) such that \(|Z^*_j| \ge 2\). Let \(g\) be some good in \(Z^*_j \setminus \{g^*_j\}\). If \(p_i < v(g^*_j)\), then moving \(g\) from \(Z^*_j\) to \(Z^*_i\) strictly increases the Nash welfare of the allocation (using an argument similar to Lemma 1). If \(p_i \ge v(g^*_j)\), we add \(g\) to \(Z^*_i\) and deduct \(p_i\) by the value \(v(g)\). We add this deducted value to agent \(j\) by increasing \(p_j\) by \(v(g)\). This swap does not change the utility of any agent but reduces the number of agents with empty bundles by \(1\). Applying this swap repeatedly, we end up with an optimal Nash allocation \((Z^*, p)\) where each \(Z^*_i\) is non-empty.

Additionally, we can assume that if there is some large good \(g\) in the bundle \(Z^*_i\), then \(Z^*_i = \{g\}\) and \(p_i = 0\). This follows from the definition of the large goods. There are at least \(\Delta - \ell\) agents who do not receive any large goods, which implies there is at least one agent \(j\) who receives a utility of at most \(\frac{v(G \setminus L)}{\Delta - \ell} < v(g)\) for any large good \(g\). Therefore, if \(p_i \ne 0\) or \(Z^*_i \setminus \{g\} \ne \emptyset\), moving all of this value from \(i\) to \(j\) strictly improves the Nash welfare (from Lemma 1).

Let \(N_L^*\) denote the set of agents who receive a large good in the allocation \(Z^*\) and let \(N_S^*\) denote all the other agents. Since each agent in \(N_L^*\) receives only one good: \[\begin{align} \prod_{i \in N_L^*} (v(Z^*_i) + p_i) = \prod_{g \in L} v(g) = \prod_{i = 1}^{\ell} v(g_i). \label{eq:z-star-large-product} \end{align}\tag{13}\]

For all the other agents: \[\begin{align} \prod_{i \in N_S^*} (v(Z^*_i) + p_i) &\le \prod_{i \in N_S^*} |Z^*_i|v(g^*_i)\left (1 + \frac{p_i}{v(g^*_i)} \right ) \\ &= \left ( \prod_{i \in N_S^*} |Z^*_i| \right ) \left ( \prod_{i \in N_S^*} v(g^*_i) \right ) \prod_{i \in N_S^*} \left (1 + \frac{p_i}{v(g^*_i)} \right ) \end{align}\]

We upper bound each of these three terms separately. For the third term, \(v(g^*_i) \ge 0.99\mu\) by definition of \(G'\) and \(\sum_{i \in [\Delta]} p_i \le 2 \cdot 10^{-4} \Delta \mu\). Therefore, we can use the AM-GM inequality to get the following upper bound:

\[\begin{align} \prod_{i \in N_S^*} \left (1 + \frac{p_i}{v(g^*_i)} \right ) &\le \left (1 + \frac{\sum_{i\in [\Delta]} p_i}{|N_S^*| \cdot 0.99\mu} \right )^{|N_S^*|} \\ &\le \left (1 + \frac{2\cdot 10^{-4} \Delta \mu}{|N_S^*| \cdot 0.99 \mu} \right )^{|N_S^*|} \\ &\le \left (1 + 10^{-3} \right )^{|N_S^*|}. \end{align}\] In the last inequality, we use [prop:a] which implies that \(|N_S^*| = \Delta - \ell \ge \Delta \left (\frac{1}{e} - \gamma \right )\ge \frac{\Delta}{3}\). The second term is maximized when the \(|N_S^*|\) goods of the form \(g^*_i\) are the highest valued small goods in the instance. That is \(\prod_{i \in N_S^*} v(g^*_i) \le \prod_{i = \ell + 1}^{\Delta} v(g_i)\).

For the first term, we need to upper bound \(\prod_{i \in N_S^*} |Z^*_i|\) subject to each \(|Z^*_i|\) being an integer and \(\sum_{i \in N_S^*} |Z^*_i| \le \Delta\), since there are at most \(\Delta\) small goods in \(G'\). Since \(\frac{|N_S^*|}{\Delta} \in [\frac{1}{e} - \gamma, \frac{1}{e} + \gamma]\) ([prop:a]), \(\prod_{i \in [\Delta]} |Z^*_i|\) is maximized when some agents receive three goods and all the remaining agents receive two goods. Therefore,

\[\begin{align} \prod_{i \in N_S^*} |Z^*_i| \le 3^{\beta} 2^{|N_S^*| - \beta} = \left ( \frac{3}{2} \right )^{\beta} 2^{|N_S^*|}, \end{align}\] where \(\beta\) is such that \(3\beta + 2(|N_S^*| - \beta) \le \Delta\). Re-arranging this inequality and applying \(|N_S^*| \ge \left (\Delta(\frac{1}{e} - \gamma) \right )\), we get \(\beta \le \frac{e - 2 + 2e\gamma}{e}\Delta\). When \(\gamma = 10^{-10}\), we can calculate \(\beta \le 0.265 \Delta\) and \(|N_S^*| \le 0.368\Delta\). Therefore, \[\begin{align} \prod_{i \in N_S^*} |Z^*_i| \le \left ( \frac{3}{2} \right )^{0.265 \Delta} 2^{0.368\Delta} \le 1.437^{\Delta}. \end{align}\]

Using these three inequalities, we get the following upper bound on \(\prod_{i \in N_S^*} (v(Z^*_i) + p_i)\). \[\begin{align} \prod_{i \in N_S^*} (v(Z^*_i) + p_i) \le (1.437)^{\Delta} \left (\prod_{i = \ell + 1}^{\Delta} v(g_i) \right ) \left (1 + 10^{-3} \right )^\Delta \le (1.439)^{\Delta} \left (\prod_{i = \ell + 1}^{\Delta} v(g_i) \right ). \label{eq:z-star-small-product} \end{align}\tag{14}\]

Putting 13 and 14 together, we get:

\[\begin{align} \prod_{i \in [\Delta]} v(X^*_i) \le \prod_{i \in [\Delta]} (v(Z^*_i) + p_i) \le (1.439)^{\Delta} \prod_{i \in [\Delta]} v(g_i) \le \left (e^{1/e} - 0.001 \right )^{\Delta} \prod_{i \in [\Delta]} v(g_i). \end{align}\]

The lemma follows from noting that \(v(W_i) \ge v(g_i)\) for each agent \(i \in [\Delta]\). Therefore, \[\begin{align} \normalfont{\texttt{NSW}}(W) \ge \frac{1}{e^{1/e} - 0.001}\normalfont{\texttt{NSW}}(\mathcal{I}). \end{align}\]

Applying a logarithm on both sides completes the proof. ◻

Proof. If any of properties A, B and C are not satisfied, Lemmas 6, 8 and 7 prove the theorem. If [prop:e] is not satisfied, Lemma 9 proves the theorem since \(S_\ell\) is the least valuable small bundle (Observation 10).

Finally, note that [prop:c] and [prop:e] imply [prop:d], because all agents \(i\) who receive a large good and satisfy \(\gamma^2 v(g_i) > v(S_i)\) also satisfy \(\gamma v(g_i) > \mu\) since [prop:e] implies that \(v(S_i) \ge 10^{-4} \mu\). Therefore [prop:c] and [prop:e] together imply that for all but at most \(\gamma^2\Delta\) agents \(i\) who receive a large good, \(v(g_i) > \frac{\mu}{\gamma}\), which implies that [prop:d] is satisfied. ◻

Proof. We note that \(\mathcal{I}^{mod}\) might have a different set of large goods than \(\mathcal{I}\). However, to avoid any confusion, we only refer to the large goods of \(\mathcal{I}\) when we refer to the set of large goods \(L\). This proof does not explicitly use the large goods of the instance \(\mathcal{I}^{mod}\). In the same vein, when we use the value \(\mu\), we mean the value \(\frac{v(G \setminus L)}{\Delta}\), where \(L\) is the set of large goods in the instance \(\mathcal{I}\). In the allocation \(W^{mod}\), we use \(S^{mod}_i\) to denote for each agent \(i\) the set of small goods in \(W^{mod}_i\) — again, note that these small goods are defined with respect to the original instance \(\mathcal{I}\).

We lower bound the Nash welfare of \(W^{mod}\) the same way we did in Theorem [thm:round-robin-nash-lower-bound]. Let \(N_L\) be the set of agents who receive a large good or a good from \(A\) in \(W^{mod}\). Since each good in \(A\) has value strictly greater than \(\frac{\Delta\mu}{\Delta - \ell}\), we must have \(N_L = \{1, \dots, \ell + |A|\}\). We let \(N_S\) denote the remaining agents. This set of remaining agents must be non-empty since \(\ell + |A| \le (1 - 1/e + \gamma)\Delta + 0.01\Delta \le 0.7\Delta\) ([prop:a]). Within the set \(N_S\), we use \(N_1\) to denote the set of agents \(i\) such that \(v(W^{mod}_i) \ge \frac{\Delta \mu}{\Delta - \ell}\). We use \(N_2\) to denote the set of all other agents in \(N_S\). Note that all agents in \(N_2\) have utility between \(v(W^{mod}_{\Delta})\) and \(\frac{\Delta \mu}{\Delta - \ell}\).

For each \(i \in N_2\) we define the value \(\alpha_i \in [0, 1]\) as the value which satisfies \(v(W^{mod}_i) = \alpha_i \frac{\Delta \mu}{\Delta - \ell} + (1 - \alpha_i)v(W^{mod}_{\Delta})\). We define \(\alpha = \sum_{i \in N_2} \alpha_i\). Similar to Theorem [thm:round-robin-nash-lower-bound], we can lower bound the log Nash welfare of the allocation \(W^{mod}\):

\[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L \cup A}\ln{v(g)} + \sum_{i \in N_1}\ln\frac{\Delta \mu}{\Delta -\ell} + \sum_{i \in N_2} \ln v(W^{mod}_i) \right ]. \end{align}\]

This can be simplified in the same way using the concavity of the log function and the definition of each agent part:

\[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L}\ln{v(g)} + \sum_{g \in A}\ln{v(g)} + (|N_1| + \alpha)\ln\frac{\Delta \mu}{\Delta -\ell} + (|N_2| - \alpha) \ln v(W^{mod}_{\Delta}) \right ] \\ &\ge \frac{1}{\Delta} \left [\sum_{g \in L}\ln{v(g)} + |A|\ln{\frac{\mu}{\gamma}} + (|N_1| + \alpha)\ln\frac{\Delta \mu}{\Delta -\ell} + (|N_2| - \alpha) \ln v(W^{mod}_{\Delta}) \right ]. \end{align}\]

By definition, \(|N_1| + |N_2| + |A|= \Delta - \ell\). We can therefore re-arrange the above expression to bring it closer to the upper bound of \(\normalfont{\texttt{logNSW}}(\mathcal{I})\) in Lemma 3.

\[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L}\ln{v(g)} + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta -\ell} \right ] + \frac{|A|}{\Delta}\ln\frac{\Delta - \ell}{\Delta \gamma} + \frac{(|N_2| - \alpha)}{\Delta}\ln\frac{(\Delta - \ell)v(W^{mod}_{\Delta})}{\Delta\mu}. \end{align}\]

Using [prop:a], \(\frac{\Delta - \ell}{\Delta \gamma} \ge 10^{9}\). This simplifies the above expression to:

\[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L}\ln{v(g)} + (\Delta - \ell)\ln\frac{\Delta \mu}{\Delta -\ell} \right ] + \frac{10|A|}{\Delta} + \frac{(|N_2| - \alpha)}{\Delta}\ln\frac{(\Delta - \ell)v(W^{mod}_{\Delta})}{\Delta\mu}. \label{eq:small-good-removal-large-good-addition-1} \end{align}\tag{15}\]

The key to proving this theorem is analyzing the term \(\frac{(|N_2| - \alpha)}{\Delta}\ln\frac{(\Delta - \ell)v(W^{mod}_{\Delta})}{\Delta\mu}\) in the above expression. We do this the same way as Theorem [thm:round-robin-nash-lower-bound]. We require the following observations to make our analysis simpler.

We return to 15 and simplify it using our observations. Specifically, we plug in Observation 14 and Lemma 3 to get

\[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \normalfont{\texttt{logNSW}}(\mathcal{I}) + \frac{10|A|}{\Delta} + \frac{(|N_2| - \alpha)}{\Delta}\ln\frac{|N_2| - \alpha}{\Delta} - \frac{2|R|}{\Delta}. \end{align}\]

This can be further simplified by noting that \(\frac{(|N_2| - \alpha)}{\Delta}\ln\frac{|N_2| - \alpha}{\Delta} \ge -\frac{1}{e}\). This gives us our final result: \[\normalfont{\texttt{logNSW}}(W^{mod}) \ge \normalfont{\texttt{logNSW}}(\mathcal{I}) -\frac{1}{e} + \frac{10|A|}{\Delta} - \frac{2|R|}{\Delta}. \qedhere\] ◻

Proof. The corollary follows from Theorem 11 and the fact that adding the goods \(A \setminus A'\) can only improve the Nash welfare of the allocation. ◻

Proof. To upper bound the Nash welfare of \(Y\), we modify it slightly to make it easier to analyze. We first assume without loss of generality that \(Y\) allocates all the goods. If not, we can allocate the unallocated goods arbitrarily in a way that satisfies the class constraints. This only improves the log Nash welfare of the allocation \(Y\).

In the allocation \(Y\), let \(g^*_i\) denote the highest valued large good that agent \(i\) is allocated (if \(i\) is allocated a large good).

If there is some agent who has two (or more) large goods in \(Y\), we move one of the large goods to another agent in a way that increases the Nash welfare of \(Y\). Specifically, consider an agent \(i\) with at least two large goods. Let \(\tilde{g}_i\) be the least valued large good in \(Y_i\). Since \(\tilde{g}_i\) is not the highest valued good of \(i\), we have \[\begin{align} \frac{v(Y_i \setminus \{\tilde{g}_i\})}{v(Y_i)} \ge \frac{1}{2}. \end{align}\]

By the definition of large goods, this good \(\tilde{g}_i\) has value strictly greater than \(\frac{\Delta \mu}{\Delta - \ell}\). Since the total value of the small goods is \(\Delta \mu\) and there are at least \(\Delta - \ell\) agents who do not receive a large good, there is at least one agent who does not receive a large good and receives utility at most \(\frac{\Delta \mu}{\Delta - \ell}\). Let \(j\) denote one such agent. Adding \(\tilde{g}_i\) to \(Y_j\) at least doubles the utility of \(j\). Therefore, \[\begin{align} \frac{v(Y_j \cup \{\tilde{g}_i\})}{v(Y_j)} > 2. \end{align}\]

Combining these two inequalities, we get that moving \(\tilde{g}_i\) from agent \(i\) to \(j\) strictly improves the Nash welfare of \(Y\), and strictly increases the number of agents who receive a large good. We can repeat this transfer whenever there is an agent who has two large goods. Let \(Y'\) denote the resulting allocation where \(\ell\) agents receive a large good. Note that \(\normalfont{\texttt{NSW}}(Y') \ge \normalfont{\texttt{NSW}}(Y)\). Moreover, \(Y'\) still allocates at most one good from each class to every agent since we only modified the allocations of the large goods.

Let \(L^*\) be the set of large goods in the instance with value at least \(\frac{\mu}{\gamma}\), and \(N_{L^*}\) be the set of agents who receive goods in \(L^*\). Since the instance is well-behaved, there are at least \((1 - 1/e - 2\gamma)\Delta\) large goods in \(L^*\) ([prop:a] and [prop:d]). Let \(G_1, \dots, G_t\) denote the set of classes of goods such that \(|G_j| > 0.5\Delta\) for each \(j \in [t]\). Via a simple counting argument, at least \(0.1\Delta\) goods from \(G_j\) for each \(j \in [t]\) are allocated to the agents in \(N_{L^*}\) in the allocation \(Y'\). Therefore, the total value of small goods allocated to agents in \(N_{L^*}\) is at least \[\begin{align} \sum_{j = 1}^t 0.1\Delta \frac{v(G_j)}{|G_j|} \ge \sum_{j = 1}^t 0.1v(G_j) \ge 0.1\gamma v(G \setminus L). \end{align}\]

For each agent \(i\), let \(s_i\) denote the total value that agent \(i\) receives from small goods. From our discussion above, we have \[\begin{align} \sum_{i \in N_{L^*}} s_i \ge 0.1\gamma v(G \setminus L) = 0.1 \gamma \Delta \mu. \label{eq:suboptimal-0} \end{align}\tag{18}\]

Let \(N_L\) denote the set of agents who receive a large good in \(Y'\). For any agent \(i \in N_L\), let \(g^*_i\) denote the large good allocated to agent \(i\). Partitioning the agents in \(N_{L^*}\), \(N_{L} \setminus N_{L^*}\) and \([\Delta] \setminus N_L\), we can upper bound the log Nash welfare of \(Y'\): \[\begin{align} \normalfont{\texttt{logNSW}}(Y') &= \frac{1}{\Delta} \left [ \sum_{i \in N_{L^*}}\ln(v(g^*_i) + s_i) + \sum_{i \in N_{L} \setminus N_{L^*}}\ln(v(g^*_i) + s_i) + \sum_{i \in [\Delta] \setminus N_L} \ln(s_i) \right ] \notag \\ &\le \frac{1}{\Delta} \left [ \sum_{i \in N_{L^*}}\ln \left (v(g^*_i) \left (1 + \frac{\gamma s_i}{\mu} \right ) \right ) + \sum_{i \in N_{L} \setminus N_{L^*}}\ln \left (v(g^*_i)\left (1 + \frac{(\Delta - \ell)s_i}{\Delta\mu} \right ) \right ) + \sum_{i \in [\Delta] \setminus N_L} \ln(s_i) \right ] \notag\\ &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + \sum_{i \in [\Delta] \setminus N_L} \ln(s_i) \right ] \notag \\ &\qquad \qquad + \frac{1}{\Delta} \sum_{i \in N_{L^*}}\ln \left (1 + \frac{\gamma s_i}{\mu} \right ) + \frac{1}{\Delta}\sum_{i \in N_{L} \setminus N_{L^*}}\ln \left (1 + \frac{(\Delta - \ell)s_i}{\Delta\mu} \right )\label{eq:suboptimal} \end{align}\tag{19}\]

In the first inequality, we use the lower bound on \(v(g^*_i)\) given by the group each agent in \(N_L\) belongs to. If \(i \in N_{L^*}\), \(v(g^*_i) \ge \frac{\mu}{\gamma}\), and if \(i \in N_L\), \(v(g^*_i) \ge \frac{\Delta\mu}{\Delta - \ell}\).

Next, we upper bound \(\sum_{i \in [\Delta] \setminus N_L} s_i\). We do this using the AM-GM inequality. \[\begin{align} \sum_{i \in [\Delta]\setminus N_L} \ln(s_i) &\le (\Delta - \ell)\ln \left ( \frac{\sum_{i \in [\Delta]\setminus N_L} s_i}{\Delta - \ell} \right ) \\ &\le (\Delta - \ell)\ln \left ( \frac{\Delta \mu - \sum_{i \in N_L} s_i}{\Delta - \ell} \right ) \\ &\le (\Delta - \ell)\ln \left (\frac{\Delta \mu}{\Delta - \ell}\right ) + (\Delta - \ell)\ln \left (1 - \frac{\sum_{i \in N_L} s_i}{\Delta \mu} \right ). \end{align}\]

Plugging this upper bound into 19 , we get \[\begin{align} \normalfont{\texttt{logNSW}}(Y') &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + (\Delta - \ell) \ln\left (\frac{\Delta\mu}{\Delta - \ell} \right) \right ] \\ &\qquad + \frac{1}{\Delta} \sum_{i \in N_{L^*}}\ln \left (1 + \frac{\gamma s_i}{\mu} \right ) + \frac{1}{\Delta}\sum_{i \in N_{L} \setminus N_{L^*}}\ln \left (1 + \frac{(\Delta - \ell)s_i}{\Delta\mu} \right ) + \frac{(\Delta - \ell)}{\Delta}\ln \left (1 - \frac{\sum_{i \in N_L} s_i}{\Delta \mu} \right ). \end{align}\]

We now apply AM\(\ge\)GM once more to simplify the right hand side. \[\begin{align} \normalfont{\texttt{logNSW}}(Y') &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + (\Delta - \ell) \ln\left (\frac{\Delta\mu}{\Delta - \ell} \right) \right ] \\ & \qquad \qquad + \ln \left (1 - \sum_{i \in N_{L^*}} s_i \left (\frac{\Delta - \ell}{\Delta^2 \mu} - \frac{\gamma}{\Delta\mu} \right ) \right ) \\ &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + (\Delta - \ell) \ln\left (\frac{\Delta\mu}{\Delta - \ell} \right) \right ] + \ln \left (1 - \sum_{i \in N_{L^*}} \frac{s_i}{3\Delta \mu} \right ) \\ &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + (\Delta - \ell) \ln\left (\frac{\Delta\mu}{\Delta - \ell} \right) \right ] + \ln \left (1 - \frac{0.1\gamma\Delta\mu}{3\Delta \mu} \right ) \\ &\le \frac{1}{\Delta} \left [ \sum_{g \in L}\ln v(g) + (\Delta - \ell) \ln\left (\frac{\Delta\mu}{\Delta - \ell} \right) \right ] -\gamma^2. \end{align}\]

The second inequality uses [prop:a]. The third inequality uses 18 . The final inequality uses \(1 + x \le e^x\). Since \(\normalfont{\texttt{NSW}}(Y') \ge \normalfont{\texttt{NSW}}(Y)\), this completes the proof. ◻

Proof. Let \(M_{\mathcal{G}(\mathbf{x})}\) be the integral matching constructed by the ST rounding algorithm applied to allocation \(\mathbf{x}\). For each matching \(M'\) in the support of \(M_{\mathcal{G}(\mathbf{x})}\), we define a bundle \(S(M') \subseteq G'\), where \(G'\) is the set of goods of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). The bundle \(S(M')\) consists of one copy of the good \(g\) matched to bucket \(b\) (in \(M'\)) from the set \(G_{b}\), for each bucket \(b \in B_i\).

We define an allocation \(Z\) in the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) as one where \(\Delta \Pr[M_{\mathcal{G}(\mathbf{x})} = M']\) agents receive the bundle \(S(M')\), for each \(M'\) in the support of \(M_{\mathcal{G}(\mathbf{x})}\). This is a valid allocation because the number of copies of good \(g\) from set \(G_b\) it allocates is exactly \(\Delta \Pr[g \text{ is matched to } b] = \Delta b_g\) for each good \(g \in G\) and bucket \(b \in B_i\). Using the Cardinality property of the allocation \(X\), we know that each of the first \(k_i - 1\) buckets is matched to a good. Therefore, each bundle in the allocation \(Z\) must have exactly one good from \(G_{b^1}, \dots G_{b^{k_i - 1}}\), and at most one good from the set \(G_{b^{k_i}}\).

The proof has two steps. We first show that \(\normalfont{\texttt{logNSW}}(Z) \ge \normalfont{\texttt{logNSW}}(W)\). Then, we show that \(\normalfont{\texttt{logNSW}}(Z) = \mathop{\mathrm{\mathbb{E}}}[\ln(v_i(X_i))]\).

Assume that \(Z\) and \(W\) are not identical allocations. We start at the allocation \(Z\) and change it using a series of steps till we reach the allocation \(W\). We show that each of these steps weakly reduces the Nash welfare of the allocation. This shows that the Nash welfare of \(W\) is upper bounded by the Nash welfare of \(Z\). To make the rest of this proof more readable, we say good \(g\) is from bucket \(b\) instead of saying good \(g\) is from the set \(G_b\).

Let \(g'_k\) be the good with the smallest \(k\) such that it is allocated to different agents in \(Z\) and \(W\). Let \(k = (t-1)\Delta + j\) for positive integer \(t\) and positive integer \(j\) with \(j \le \Delta\); this means \(g'_k\) is from the \(t\)-th bucket \(b^t\) and is allocated to agent \(j\) in \(W\). Assume \(g'_k\) is allocated to agent \(j'\) in \(Z\).

If \(j' < j\), then the good that \(Z_{j'}\) receives from bucket \(b^t\) is \(g'_k\). Since \(Z_{j'}\) receives at most one good from bucket \(b^t\), this implies that \(g'_{(t-1)\Delta + j'}\) is allocated to different agents in both \(W\) and \(Z\), contradicting our assumption about \(k\). Therefore \(j' > j\).

Let the set of goods in \(Z_j\) from bucket \(b^t\) be \(S_j\). Note that \(|S_j| \le 1\); \(S_j\) could be empty if \(t = k_i\). Since all goods \(\{g'_1, \dots, g'_{k-1}\}\) are allocated to the same agents in \(Z\) and \(W\), it must be that \(g'_k\) is more valuable than the singleton good in \(S_j\) (if one exists); specifically, we have \(v_i(g'_k) \ge v_i(S_j)\).

We define \(Z^{<t}_j\) as the set of goods in \(Z_j\) from the buckets with index \(< t\). We similarly define \(Z^{> t}_j, W^{< t}_j\) and \(W^{>t}_j\). Note that \(Z^{<t}_j\) and \(W^{<t}_j\) are identical by assumption and \(v_i(W^{<t}_j) \ge v_i(W^{<t}_{j'})\) since \(j' > j\). We have two cases in our proof.

Case 1: \(v_i(Z_{j}^{> t}) \ge v_i(Z_{j'}^{> t})\). We convert \(Z\) into a new allocation \(\widetilde{Z}\) by swapping \(g'_k\) and \(S_j\); that is, we allocate \(g'_k\) to agent \(j\) and \(S_j\) to agent \(j'\) leaving everything else unchanged. This swap reduces the Nash welfare of allocation \(Z\) due to Lemma 1. Additionally, \(\widetilde{Z}\) and \(W\) do not differ in the allocations of the first \(k\) goods \(g'_1, \dots, g'_k\).

Case 2: \(v_i(Z_{j}^{> t}) < v_i(Z_{j'}^{> t})\). We convert \(Z\) into a new allocation \(\widetilde{Z}\) by swapping \(Z_{j'}^{> t} \cup \{g'_k\}\) and \(Z_{j}^{> t} \cup S_j\); that is, we allocate \(Z_{j'}^{> t} \cup \{g'_k\}\) to agent \(j\) and \(Z_{j}^{> t} \cup S_j\) to agent \(j'\) leaving the rest of the allocation unchanged. This swap reduces the Nash welfare of allocation \(Z\) due to Lemma 1. Once again, \(\widetilde{Z}\) and \(W\) do not differ in the allocations of the first \(k\) goods \(g'_1, \dots, g'_k\).

What we have ensured above is that given an allocation \(Z\) that agrees with \(W\) on the allocation of the first \(k-1\) goods, we can convert it into an allocation \(\widetilde{Z}\) that agrees with \(W\) on the allocation of the first \(k\) goods and has weakly lower Nash welfare. Moreover, \(\widetilde{Z}\) allocates to each agent, exactly one good from the first \(k_i - 1\) buckets and at most one good from the last bucket. Repeating this step at most \(m'\) times, we reach the allocation \(W\). This proves that \(W\) has a lower Nash welfare than \(Z\).

Finally, we recall the definition of \(Z\) as an allocation where \(\Delta \Pr[M_{\mathcal{G}(\mathbf{x})} = M']\) agents receive the bundle \(S(M')\) for each \(M'\) in the support of \(M_{\mathcal{G}(\mathbf{x})}\). Assuming \(X\) is the final allocation output by ST rounding, we have \[\begin{align} \normalfont{\texttt{logNSW}}(Z) = \frac{1}{\Delta}\sum_{j \in [\Delta]}\ln(v_i(Z_j)) &= \frac{1}{\Delta} \sum_{M' \in supp(M_{\mathcal{G}(\mathbf{x})})} \Delta \Pr[M_{\mathcal{G}(\mathbf{x})} = M']\ln(v_i(S(M'))) \\ &= \mathop{\mathrm{\mathbb{E}}}[\ln(v_i(X_i))] = \texttt{ST}(\mathbf{x}, i). \end{align}\] The penultimate equality holds because \(S(M')\) is exactly \(X_i\) when \(M' = M_{\mathcal{G}(\mathbf{x})}\) (more pedantically, \(S(M')\) contains one copy of each good in \(X_i\) when \(M' = M_{\mathcal{G}(\mathbf{x})}\)). ◻

Proof. This follows from the condition 3 that configuration LP solutions satisfy. This condition states that \(\sum_{i \in N}\sum_{S\subseteq G: g \in S} y_{i, S} = 1\) for all \(g \in G\). The observation follows from noting, by the definition of \(\mathbf{x}\), that \(\sum_{i \in N} x_{ig} = \sum_{i \in N}\sum_{S\subseteq G: g \in S} y_{i, S} = 1\). ◻

Proof. We assume that \(y\) has a well-defined objective value. This means for every \(S \subseteq G\) such that \(y_{i, S} > 0\), the value \(v_i(S)\) is positive. This implies there is at least one good in \(S\) with positive value for agent \(i\). Let \(G^+\) be the set of goods that agent \(i\) has positive value for. By our discussion, each set \(S\) with \(y_{i, S} > 0\) has at least one good from \(G^+\). Therefore, \[\begin{align} \sum_{g \in G^+} x_{ig} = \sum_{g \in G^+} \sum_{S \subseteq G: g \in S} y_{i, S} \ge \sum_{S \subseteq G} y_{i, S} = 1. \end{align}\]

The final equality holds since \(y\) satisfies 2 . Therefore, the number of goods with positive value in \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is at least \(\Delta \sum_{g \in G^+} x_{ig} \ge \Delta\). This means that Assumption 9 is satisfied. ◻

Proof. In the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\), we define the allocation \(Y\) as one where \(\Delta y_{i, S}\) agents receive the bundle \(S\) for each \(S\subseteq G\). This is a valid allocation since the number of copies of good \(g\) it allocates is exactly \(\sum_{S \subseteq G: g \in S} \Delta y_{i, S} = \Delta x_{i, g}\) for each good \(g \in G\). This implies \[\begin{align} \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) \ge \normalfont{\texttt{logNSW}}(Y). \end{align}\] The proof is completed by using the definition of \(Y\) to measure its log Nash welfare: \[\normalfont{\texttt{logNSW}}(Y) = \frac{1}{\Delta} \sum_{j \in [\Delta]} \ln{v_i(Y_j)} = \frac{1}{\Delta} \sum_{S \subseteq G} \Delta y_{i, S} \ln{v_i(S)} = \sum_{S \subseteq G} y_{i, S} \ln{v_i(S)}. \qedhere\] ◻

Proof. Fix an agent \(i\). We first construct a set \(L_i\) satisfying the properties of Definition 5. This set can be constructed iteratively. We start by initializing \(L_i\) as the empty set, and while there is some good \(g' \in G \setminus L_i\) such that \(x_{ig'} > 0\) and \(v_i(g') > \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}}\), we add this \(g'\) to \(L_i\). It is easy to see that this process always terminates and it does so in time polynomial in the number of goods \(m\). Additionally, by definition, it satisfies property (ii) of Definition 5 when it terminates.

We show that this process satisfies property (iii) next. If for some \(g'\), we have \(x_{ig'} \ge 1 - \sum_{g \in L_i} x_{ig}\), then \[\begin{align} \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}} \ge \frac{x_{ig'} v_i(g')}{1 - \sum_{g \in L_i} x_{ig}} \ge \frac{x_{ig'} v_i(g')}{x_{ig'}} = v_i(g'). \end{align}\] This implies \(g'\) will never get added to \(L_i\) which implies that our addition process will never violate property (iii) of Definition 5.

Moreover, the addition of \(g'\) to \(L_i\) reduces the value of \(\frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}}\) due to the following inequalities:

\[\begin{align} \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g) - x_{ig'}v_i(g')}{1 - \sum_{g \in L_i} x_{ig} - x_{ig'}} &< \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g) - x_{ig'}\frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}}}{1 - \sum_{g \in L_i} x_{ig} - x_{ig'}} \\ &= \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}}. \end{align}\] Therefore adding \(g'\) to \(L_i\) does not violate the largeness of the goods already in \(L_i\). In conclusion, we have presented a polynomial time algorithm which outputs a set of large goods \(L_i\) satisfying Definition 5.

We show uniqueness next. Assume there are two different sets of large goods \(L_i\) and \(L'_i\) satisfying the properties of Definition 5. Note that if any good \(g\) is in \(L_i\) (resp. \(L'_i\)), all goods \(g'\) with \(x_{ig'} > 0\) and value at least \(v_i(g)\) must also be in \(L_i\) (resp. \(L'_i\)). Therefore, one of the two sets \(L_i\) and \(L'_i\) must be contained in the other. Assume \(L_i \subset L'_i\). By applying the properties of large goods with the set \(L_i\), we get for any \(g \in L'_i \setminus L_i\), \[\begin{align} v_i(g) \le \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}} = \frac{v_i(\mathbf{x}_i) - \sum_{g \in L'_i} x_{ig} v_i(g) + \sum_{g \in L'_i \setminus L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}}. \end{align}\]

Adding the above inequality up for all \(g \in L'_i \setminus L_i\), we get \[\begin{align} \sum_{g \in L'_i \setminus L_i} x_{ig} v_i(g) \le \left (\frac{\sum_{g \in L'_i \setminus L_i} x_{ig}}{1 - \sum_{g \in L_i}x_{ig}} \right ) \left (v_i(\mathbf{x}_i) - \sum_{g \in L'_i} x_{ig} v_i(g) + \sum_{g \in L'_i \setminus L_i} x_{ig} v_i(g) \right ). \end{align}\]

Re-arranging terms, we get \[\begin{align} \frac{\sum_{g \in L'_i \setminus L_i} x_{ig} v_i(g)}{ \sum_{g \in L'_i \setminus L_i} x_{ig}} \le \frac{ \left ( v_i(\mathbf{x}_i) - \sum_{g \in L'_i} x_{ig} v_i(g) \right )}{1 - \sum_{g \in L'_i}x_{ig}}. \end{align}\]

This contradicts the set \(L'_i\) being a set of large goods since each good \(g \in L'_i\setminus L_i\) satisfies \(x_{ig} > 0\) and \[\begin{align} v_i(g) > \frac{\left ( v_i(\mathbf{x}_i) - \sum_{g \in L'_i} x_{ig} v_i(g) \right )}{1 - \sum_{g \in L'_i}x_{ig}}, \end{align}\] by the definition of being a large good. Therefore, the set of large goods must be unique and the proof is complete. ◻

Proof. Let \(L_i\) be the set of large goods for agent \(i\) in the allocation \(\mathbf{x}\). The instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is constructed by creating \(\Delta x_{ig}\) copies of each good \(g\). We use \(G^i\) to denote the set of goods in instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\).

Let \(L\) (with \(|L| = \ell\)) be the set of all copies of each good in \(L_i\). From the definition of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\), \(v_i(G^i) = \sum_{g \in G}\Delta x_{ig} v_i(g)\), \(v_i(L) = \Delta \sum_{g \in L_i} x_{ig} v_i(g)\) and \(\ell = \Delta \ell_i\).

We show that this set \(L\) satisfies Definition 1. For each good \(g \in L_i\), we have by the properties of \(L_i\),

\[\begin{align} v_i(g) > \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}} = \frac{v_i(G^i \setminus L)}{\Delta - \ell}. \end{align}\] This shows that all copies of \(g\) in the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) satisfy the first property of Definition 1. To prove the second property, consider any \(g \notin L_i\) with \(x_{ig} > 0\). We have \[\begin{align} v_i(g) \le \frac{v_i(\mathbf{x}_i) - \sum_{g \in L_i} x_{ig} v_i(g)}{1 - \sum_{g \in L_i} x_{ig}} = \frac{v_i(G^i \setminus L)}{\Delta - \ell}, \end{align}\] which shows that all copies of \(g\) in the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) satisfy the second property of Definition 1. Since the set of large goods in the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is unique (Observation [obs:large-goods-unique]), this proves that \(L\) must be the set of large goods of the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). This implies the number of large goods is equal to \(\Delta \ell_i\).

Finally, we compute the mean value \(\mu = \frac{v_i(G^i \setminus L)}{\Delta}\). From the above discussion, this is equal to \[\mu = \frac{v_i(G^i \setminus L)}{\Delta} = \frac{\Delta \left (\sum_{g \in G \setminus L_i} x_{ig} v_i(g) \right )}{\Delta} = \sum_{g \in G \setminus L_i} x_{ig} v_i(g) = \mu^i. \qedhere\] ◻

Proof. Fix an agent \(i \in N\). Both claims of the lemma follow from a simple observation: each of the five properties [prop:a]–[prop:e] defining a well-behaved instance can be rephrased as a statement about the fraction of the \(\Delta\) agents that satisfy a certain condition, where neither the condition nor the thresholds involved depend on \(\Delta\).

Fix any feasible \(\Delta\), and let the artificial instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) have large good set \(L\) (with \(|L| = \ell\)), mean value \(\mu\), and round robin allocation \(W\) with small bundles \((S_1, \dots, S_{\Delta})\).

Recall that [prop:a] asks that \(\frac{\ell}{\Delta} \in \left [1 - \frac{1}{e}-\gamma, 1 - \frac{1}{e} + \gamma \right ]\). By Lemma 15, \(\frac{\ell}{\Delta} = \ell_i\), a quantity of the fractional bundle \(\mathbf{x}_i\) alone that does not depend on \(\Delta\). Hence [prop:a] is equivalent to the \(\Delta\)-independent condition \(\ell_i \in \left [1 - \frac{1}{e}-\gamma, 1 - \frac{1}{e} + \gamma \right ]\); in particular it holds either for all feasible \(\Delta\) or for none. Since \(\ell_i = \sum_{g \in L_i} x_{ig}\) can be computed from \(L_i\) in polynomial time, this condition can be verified in polynomial time.⁵

The four remaining properties [prop:b]–[prop:e] are statements about the small bundles and large goods that agents receive in the round robin allocation \(W\). Since \(\Delta\) can be exponentially large, we cannot compute each agent’s allocated bundle in \(W\) efficiently. We get around this by exploiting the fact that \(W\) contains only a few distinct bundles, which lets us describe \(W\) compactly and, crucially, without any reference to \(\Delta\).

Let \(G = \{g_1, \dots, g_m\}\) denote the set of goods of the original instance, ordered so that \(v_i(g_1) \ge v_i(g_2) \ge \dots \ge v_i(g_m)\). We assume the round robin algorithm breaks ties in favor of goods with an earlier index; that is, the copies of \(g_1\) are allocated before the copies of \(g_2\), and so on, even if two goods in \(G\) have identical value. This is without loss of generality: for each agent \(j\), the values \(v_i(W_j)\) and \(v_i(S_j)\) do not depend on how these ties are broken, so the tie-breaking rule does not affect whether \(W\) satisfies the properties of a well-behaved instance.

Our succinct representation of \(W\) has the form \(\{(X_j, a_j, b_j)\}_{j \in [k]}\), where each \(X_{j} \subseteq G\) and \(a_j, b_j \in [0, 1]\). Its interpretation is that, in the allocation \(W\), the agents \(\{\Delta a_j + 1, \Delta a_j + 2, \dots, \Delta b_j\}\) all receive the bundle \(X_j\) (more pedantically, they each receive a bundle consisting of one copy of each good in \(X_j\)). To ensure that this is a complete description of the allocation, we require that \(a_1 = 0\), \(b_k = 1\), and that \(a_{j} < b_j\) and \(a_{j+1} = b_j\) for all \(j \in [k]\). This ensures the index intervals \((a_j\Delta, b_j\Delta]\) partition the agent set \([\Delta]\). It is easy to see that any allocation (not just \(W\)) can be represented using this form. We will exploit this representation form by showing that \(W\) can be represented in this form with \(k \le m+1\). Moreover, the fraction of agents receiving the bundle \(X_j\) will be independent of \(\Delta\); that is the value \((b_j - a_j)\) will be a function of \(\mathbf{x}_i\) that does not depend on \(\Delta\).

We construct this representation iteratively by simulating the round robin algorithm. We simulate the round robin algorithm in blocks: in the first block we allocate all copies of \(g_1\), then in the next block we allocate all copies of \(g_2\), and so on. There are \(m\) such blocks. To simulate the \(t\)-th block (the allocation of the copies of \(g_t\)) we require an allocation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) that corresponds to the round robin allocation at the end of the first \(t-1\) blocks and a starting pointer that points to the agent who should receive the first good in the \(t\)-th block.

Initially, the allocation is empty and the first agent is due to pick a good. Therefore, we initialize our allocation using the tuple \(\{(\emptyset, 0, 1)\}\) and initialize a starting pointer \(p_1 = 0\), which denotes which agent should pick a good next; the value of the starting pointer \(p_1\) is set such that the agent \(p_1\Delta + 1\) is due to receive the next good. Simulating the first block, we allocate the \(\Delta x_{ig_1}\) copies of good \(g_1\); these goods are allocated to the first \(\Delta x_{ig_1}\) agents. We can update our allocation by splitting the initial tuple \(\{(\emptyset, 0, 1)\}\) into two tuples \(\{(\{g_1\}, 0, x_{ig_1}), (\emptyset, x_{ig_1}, 1)\}\), and then updating our starting pointer to \(p_2 = x_{ig_1}\). This is the allocation of the round robin algorithm after \(\Delta x_{ig_1}\) iterations, and the starting pointer \(p_2\) denotes that the agent \(\Delta x_{ig_1} + 1\) should receive the next good.

More generally, assume we have simulated the first \(t-1\) blocks and would like to simulate the allocation of the copies of \(g_t\). Given a starting pointer \(p_t\), the good \(g_t\) is allocated to all the agents \(\{\Delta p_t + 1, \dots, \Delta (p_t + x_{ig_t})\}\) if \((p_t + x_{ig_t}) \le 1\) and the set of agents \(\{\Delta p_t + 1, \dots, \Delta, 1, \dots, \Delta (p_t + x_{ig_t} - 1)\}\) otherwise. We can use this information to update our allocation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\), which we constructed by simulating the first \(t-1\) blocks. As we show, this can be done without knowing the value of \(\Delta\).

For all the tuples \((X_{j}, a_j, b_j)\) where the interval \([a_j, b_j]\) is contained in \([p_t, \min\{1, p_t + x_{ig_t}\}]\) or \([0, \max\{p_t + x_{ig_t} - 1, 0\}]\) we update \(X_j\) to \(X_j \cup \{g_t\}\) since all of the agents in this interval receive a copy of \(g_t\). For all the tuples \((X_{j}, a_j, b_j)\) where the interval \([a_j, b_j]\) is completely disjoint from \([p_t, \min\{1, p_t + x_{ig_t}\}]\) or \([0, \max\{p_t + x_{ig_t} - 1, 0\}]\), we leave \(X_j\) unchanged since none of the agents in this interval receive a copy of \(g_t\).

Next, consider the tuple \((X_{j}, a_j, b_j)\) where the interval \((a_j, b_j)\) contains the endpoint \((p_t + x_{ig_t})\) or \((p_t + x_{ig_t} - 1)\). In this case, some of the agents in \(\{\Delta a_j + 1, \dots, \Delta b_j\}\) receive the good \(g_t\) and some agents do not. Specifically, if the interval contains the endpoint \(p_t + x_{ig_t}\) and does not contain \(p_t\), the set of agents \(\{\Delta a_j + 1, \dots, \Delta (p_t + x_{ig_t})\}\) receive the good \(g_t\) and the remaining agents do not. Therefore, to update the allocation, we split \((X_j, a_j, b_j)\) into \((X_{j} \cup \{g_t\}, a_j, p_t + x_{ig_t})\) and \((X_{j}, p_t + x_{ig_t}, b_j)\). We can do something similar if the interval contains \((p_t + x_{ig_t} - 1)\). We will show that no interval contains \(p_t\), so there is no other case to worry about.

Finally, we update the starting pointer \(p_{t+1}\) to be \(p_t + x_{ig_t}\) if \(p_t + x_{ig_t} < 1\) and \(p_t + x_{ig_t} - 1\) otherwise. Note that this update step also means the allocation at the beginning of the \((t+1)\)-th block will not have any tuple \((X_j, a_j, b_j)\) such that \((a_j, b_j)\) contains \(p_{t+1}\). If it did, we would have split it in the simulation of the \(t\)-th block itself. More generally, for any block \(t\), \(p_t\) will not be present in the interval \((a_j, b_j)\) for any tuple \((X_j, a_j, b_j)\).

Using this procedure, we compute a succinct representation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) of the allocation \(W\). To see why it is succinct, note that at each iteration, we split at most one tuple \((X_j, a_j, b_j)\) — this is the tuple that contains either \(p_t + x_{ig_t}\) or \(p_t + x_{ig_t} - 1\) (only one of these will be in the range \((0, 1)\)). Since we start with an allocation represented by one tuple and each tuple is split into two tuples (if it is split), we terminate with an allocation represented by at most \(m+1\) tuples. Moreover, all the \(a_j\) and \(b_j\) values are functions of the fractional bundle \(\mathbf{x}_i\). Therefore, this is a representation that only takes up polynomial space. Additionally this construction is independent of the value of \(\Delta\) since all the steps can be carried out without knowing \(\Delta\). Therefore, we can construct this representation of \(W\) in polynomial time, and this allocation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) represents the round robin allocation of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) for any feasible value of \(\Delta\).

We now use the representation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) of the allocation \(W\) to express the four remaining properties. Consider the group of agents that receive the bundle \(X_j\). Since every agent in this group receives the same set of goods, the following two quantities are common to the whole group, and both depend only on \(\mathbf{x}_i\) (not on \(\Delta\)):

• the value of the small goods in the bundle \(\sigma_j := v_i(X_j \setminus L_i)\), which equals \(v_i(S_{j'})\) for every agent \(j'\) in the group; and

• if the group receives a large good, the value \(\lambda_j := v_i(g)\) of that large good, where \(g\) is the unique element of \(X_j \cap L_i\).

Here we used that each agent who receives a large good receives exactly one of them: by property (iii) of Definition 5, \(\ell_i = \sum_{g \in L_i} x_{ig} < 1\), so there are \(\ell = \Delta\ell_i < \Delta\) copies of large goods in total; since the large goods are the most valuable goods, they are all allocated in the first round of the round robin algorithm, one to each of the agents \(\{1, \dots, \ell\}\). Consequently, group \(j\) receives a large good if and only if \(X_j \cap L_i \neq \emptyset\), in which case \(|X_j \cap L_i| = 1\).

Using \(\sigma_j\), \(\lambda_j\), \(\mu^i\), and the group fractions \(b_j - a_j\), each remaining property becomes a statement about the allocation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) that does not involve \(\Delta\):

[prop:b]

holds if and only if the fraction of agents whose small bundle has value outside \(\left [(1-\gamma)\mu^i, (1+\gamma)\mu^i \right ]\) is at most \(\gamma\); that is, \(\sum_{j:\, \sigma_j \notin [(1-\gamma)\mu^i,\, (1+\gamma)\mu^i]} (b_j - a_j) \le \gamma\).

[prop:c]

holds if and only if the fraction of agents who receive a large good and a small bundle of comparable value is at most \(\gamma^2\); that is, \(\sum_{j:\, X_j \cap L_i \neq \emptyset,\;\sigma_j \ge \gamma^2 \lambda_j} (b_j - a_j) \le \gamma^2\).

[prop:d]

holds if and only if the fraction of agents who receive a large good with value less than \(\frac{\mu^i}{\gamma}\) is at most \(\gamma^2\); that is, \(\sum_{j:\, X_j \cap L_i \neq \emptyset,\;\lambda_j \le \mu^i/\gamma} (b_j - a_j) \le \gamma^2\).

[prop:e]

holds if and only if \(\sigma_j \ge 10^{-4}\mu^i\) for every group; that is, \(\sum_{j:\, \sigma_j < 10^{-4}\mu^i} (b_j - a_j) = 0\).

Each of these conditions is expressed purely in terms of \(b_j - a_j\), \(\sigma_j\), \(\lambda_j\), and \(\mu^i\), none of which depend on \(\Delta\). Hence each of [prop:b]–[prop:e] holds either for all feasible \(\Delta\) or for no feasible \(\Delta\). Together with the analogous conclusion for [prop:a], this shows that the well-behavedness of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) does not depend on the choice of feasible \(\Delta\), proving the first claim of the lemma. Finally, the representation \(\{(X_j, a_j, b_j)\}_{j \in [k]}\) of \(W\), the set \(L_i\) and the value \(\mu^i\) are all computable in polynomial time. Therefore all of the properties can be verified in polynomial time, proving the second claim of the lemma. ◻

Proof. Using Lemma 14, we can find the set \(L_i\) for each agent \(i\) in polynomial time. Using this set, it is easy to check if an agent \(i\) satisfies the small good fraction property. Using Lemma 16, we can check in polynomial time if \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is well-behaved for all feasible \(\Delta\) with respect to \(\mathbf{x}\). Therefore, we can decide in polynomial time if an agent \(i\) is well-behaved, and the corollary follows. ◻

Proof. Let \(\Delta\) be any integer that is feasible with respect to both \(y\) and \(\mathbf{x}\). Consider the artificial instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) for agent \(i\). Note that \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is well-behaved by the assumption in the lemma. Define the allocation \(Y\) as one where \(\Delta y_{i, S}\) agents receive the bundle \(S\) for each \(S \subseteq G\). This is the same allocation constructed in the proof of Lemma 13. The goal of this proof is to invoke Lemma 10 with the allocation \(Y\). Note that the allocation \(Y\) has positive Nash welfare since the objective value of the configuration LP solution \(y\) is well-defined; therefore, if \(y_{i, S} > 0\), the value \(v_i(S)\) is positive.

Let \(G^i\) denote the set of goods of this instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). This set of goods \(G^i\) can be naturally partitioned based on which good in \(G\) it is a copy of. Let \(g'_1, g'_2, \dots, g'_k\) be the set of small goods for agent \(i\), and let \(G_1, G_2, \dots G_k\) be a partition of the small goods of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) where each \(G_j\) consists of all the copies of good \(g'_j\). Using Lemma 15, the set of small goods of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is exactly the set of copies of \(g'_1, \dots, g'_k\). Therefore, \(G_1, \dots G_k\) partition the set of small goods of \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) into classes where all goods in each class have the same value.

Finally, note that for each small good \(g\), there are \(\Delta x_{ig}\) copies of \(g\) in the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). Therefore, \[\begin{align} \sum_{j = 1}^k \mathbb{1}\{|G_j| > 0.5\Delta\} v_i(G_j) = \sum_{j = 1}^k \mathbb{1}\{x_{ig'_j} > 0.5\} \Delta x_{ig'_j} v_i(g'_j) \ge \gamma \Delta \mu^i = \gamma \Delta \mu. \end{align}\]

The final equality holds due to Lemma 15. Additionally note that in the allocation \(Y\), no agent gets two copies of a good in \(G\) since each agent’s allocation is a subset of \(G\). We can therefore apply Lemma 10 to conclude that \[\begin{align} \normalfont{\texttt{logNSW}}(Y) < \frac{1}{\Delta} \left [\sum_{g \in L}\ln v(g) + (\Delta - \ell)\ln \left (\frac{\Delta \mu}{\Delta - \ell} \right ) \right ] - \gamma^2. \label{eq:small-good-fraction-1} \end{align}\tag{21}\]

Let \(W\) be the round robin allocation of this instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). Using Theorem [thm:round-robin-nash-lower-bound], we have: \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \frac{1}{\Delta} \left [\sum_{g \in L}\ln v(g) + (\Delta - \ell)\ln \left (\frac{\Delta \mu}{\Delta - \ell} \right ) \right ] - \frac{1}{e}. \label{eq:small-good-fraction-2} \end{align}\tag{22}\]

Combining 21 and 22 , we get \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \normalfont{\texttt{logNSW}}(Y) - \frac{1}{e} + \gamma^2. \end{align}\] Using Lemma 11, we have \(\texttt{ST}(\mathbf{x}, i) \ge \normalfont{\texttt{logNSW}}(W)\). Further, using the arguments of Lemma 13, we have \(\normalfont{\texttt{logNSW}}(Y) = \sum_{S \subseteq G}y_{i, S} \ln v_i(S)\). Using these two observations, we can simplify the above inequality to conclude that \[\texttt{ST}(\mathbf{x}, i) \ge \sum_{S \subseteq G} y_{i, S} \ln(v_i(S)) - \frac{1}{e} + \gamma^2. \qedhere\] ◻

Proof. Let \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) be the artificial instance of agent \(i\) for some \(\Delta\) that is feasible with respect to \(\mathbf{x}\) and \(y\). If \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is well-behaved but \(i\) does not satisfy the small good fraction property, the lemma holds due to Lemma 17. We therefore assume the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is not well-behaved.

Let \(W\) be the round robin allocation of this instance. Since the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) is not well-behaved, Theorem [thm:non-well-behaved-instance-improvement] proves the following: \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) - \frac{1}{e} + c, \end{align}\] for some constant \(c > 0\). The lemma follows by noting that \(\texttt{ST}(\mathbf{x}, i) \ge \normalfont{\texttt{logNSW}}(W)\) (Lemma 11) and \(\normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) \ge \sum_{S \subseteq G} y_{i, S}\ln v_i(S)\) (Lemma 13). ◻

Proof. Let \(\Delta\) be an integer feasible with respect to both \(\mathbf{x}\) and \(y\). Let \(N_1\) be the set of agents \(i\) such that \(\mathbf{x}\) is not well-behaved for agent \(i\). By the theorem statement, \(|N_1| \ge \gamma^3 n\).

For each agent \(i \in N_1\), the following holds due to Lemma 18: \[\begin{align} \texttt{ST}(\mathbf{x}, i) \ge \sum_{S \subseteq G}y_{i, S}\ln v_i(S) - \frac{1}{e} + c. \label{eq:n1-bound} \end{align}\tag{23}\]

For all the other agents \(i \in N \setminus N_1\), the following holds due to Lemma [lem:fractional-nash-lower-bound]: \[\begin{align} \texttt{ST}(\mathbf{x}, i) \ge \sum_{S \subseteq G} y_{i, S} \ln(v_i(S)) - \frac{1}{e} \label{eq:n-bound}. \end{align}\tag{24}\]

Adding up 23 and 24 , we get \[\begin{align} \texttt{ST}(\mathbf{x}) &\ge \frac{1}{n} \sum_{i \in N, S \subseteq G} y_{i, S}\ln v_i(S) -\frac{1}{e} + \frac{|N_1|c}{n} \\ &\ge \frac{1}{n} \sum_{i \in N, S \subseteq G} y_{i, S} \ln v_i(S) - \frac{1}{e} + \gamma^3 c \end{align}\] Therefore the theorem holds with \(c^*_1\) defined as the value \(\gamma^3 c\). ◻

Proof. This is trivial for each good not in \(G'\) since their fractional allocations are the same in both \(\mathbf{x}\) and \(\mathbf{z}\). Consider any good \(g \in G'\). We use the notation \(L(g)\), \(S(g)\), \(\zeta(g)\) and \(s(g)\) as defined in the above procedure.

\[\begin{align} \sum_{i \in N} z_{ig} &= \sum_{i \in L(g)} z_{ig} + \sum_{i \in S(g)} z_{ig} + \sum_{i \in N \setminus (L(g) \cup S(g))} z_{ig} \\ &= \sum_{i \in L(g)} x_{ig}(1 + \gamma^2) + \sum_{i \in S(g)} x_{ig}\left ( 1- \frac{\gamma^2 \zeta(g)}{s(g)}\right ) + \sum_{i \in N \setminus (L(g) \cup S(g))} x_{ig} \\ &= \sum_{i \in N}x_{ig} + \sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\}\gamma^2 x_{ig} - \frac{\gamma^2\zeta(g)}{s(g)} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \\ &= \sum_{i \in N} x_{ig} + \gamma^2 \zeta(g) - \frac{\gamma^2\zeta(g)}{\sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}x_{ig}} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \\ &= \sum_{i \in N} x_{ig}. \end{align}\]

To show that each \(z_{ig}\) is non-negative, we only need to consider the cases where \(z_{ig} < x_{ig}\). These are the cases where we set \(z_{ig} \gets x_{ig}\left ( 1- \frac{\gamma^2 \zeta(g)}{s(g)}\right )\). In this case, from the definition of goods in \(G'\), \(s(g) \ge \frac{\gamma}{2}\) and we trivially have \(\zeta(g) \le 1\). Therefore, \[\begin{align} \left ( 1- \frac{\gamma^2 \zeta(g)}{s(g)}\right ) \ge (1 - 2\gamma) > 0. \end{align}\] This proves that \(z_{ig}\) is always non-negative. ◻

Proof. We add \(\gamma^2\Delta x_{ig}\) copies of each good \(g \in G'\) which is a large good for the agent \(i\). Therefore, the first statement holds. To prove the second statement, let \(\widetilde{G} \subseteq G'\) be the set of large goods in \(G'\) such that for each \(g \in \widetilde{G}\), we have \(v_i(g) \le \frac{\mu}{\gamma}\). By [prop:d] of the well-behaved instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\), we have \(\Delta \sum_{g \in \widetilde{G}} x_{ig} \le \gamma^2 \Delta\). This implies the number of copies of goods in \(\widetilde{G}\) that we add is at most \(\gamma^4 \Delta\). ◻

Proof. Each good \(g \in G'' \setminus \widetilde{G}\) satisfies \(\sum_{i \in N_{nwb}} f_{ig} > \frac{\gamma}{4}\). This implies

\[\begin{align} |N_{nwb}| \ge \sum_{i \in N_{nwb}} \sum_{g \in G} f_{ig} \ge \sum_{i \in N_{nwb}} \sum_{g \in G'' \setminus \widetilde{G}} f_{ig} > \frac{\gamma}{4} |G'' \setminus \widetilde{G}|. \end{align}\]

Combining this with the fact that \(|N_{nwb}| \le \gamma^3 n\), we get \(|G'' \setminus \widetilde{G}| \le 4\gamma^2 n < \gamma n\). Using this, we can upper bound \(\zeta(G'')\) as \[\begin{align} \zeta(G'') = \zeta(\widetilde{G}) + \zeta(G'' \setminus \widetilde{G}) &\le \zeta(\widetilde{G}) + |G'' \setminus \widetilde{G}| \\ &\le \zeta(\widetilde{G}) + \gamma n. \end{align}\]

Noting that \(\zeta(G'') \ge 9\gamma n\), we can re-arrange the terms of the above inequality to infer that \(\zeta(\widetilde{G}) \ge 8\gamma n\). ◻

Proof. We restrict our attention to goods in \(\widetilde{G}\). Goods outside of \(\widetilde{G}\) are allocated the same way in both allocations. Fix a good \(g \in \widetilde{G}\). We need to show that the amount of \(g\) we add to well-behaved agents is less than the amount of \(g\) we remove from non-well-behaved agents. The total amount of \(g\) we add to well-behaved agents is at most \[\begin{align} \sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\} \gamma^2 x_{ig} \le \gamma^2 \sum_{i \in N} x_{ig} \le \gamma^2. \end{align}\]

The amount we remove from non-well-behaved agents is at least \[\begin{align} \sum_{i \in N_{nwb}} \frac{x_{ig} - f_{ig}}{2} = \sum_{i \in N_{nwb}} \frac{x_{ig}}{2} - \sum_{i \in N_{nwb}} \frac{f_{ig}}{2} \ge \frac{\gamma}{4} - \frac{\gamma}{8} \ge \frac{\gamma}{8}. \end{align}\] Here, we use the fact that \(g\) is in both \(G''\) and \(\widetilde{G}\). Therefore, \(\sum_{i \in N_{nwb}} x_{ig} \ge \frac{\gamma}{2}\) and \(\sum_{i \in N_{nwb}} f_{ig} \le \frac{\gamma}{4}\). \(\gamma/8\) is clearly greater than \(\gamma^2\). This proves the first statement.

The second statement is easy to see. Every time we set \(z_{ig}\) such that \(z_{ig} < x_{ig}\), we set \(z_{ig} \gets \frac{x_{ig} + f_{ig}}{2}\) which is clearly at least \(0\). ◻

Proof. From Lemma [lem:fractional-property-a], we have for each \(i \in N_{wb}\), \(\sum_{g \in G}\mathbb{1}\{g \in L_i\}x_{ig} \ge 1 - \frac{1}{e} - \gamma\). There are at least \(n - \gamma^3 n\) well-behaved agents. Therefore, \[\begin{align} \sum_{i \in N_{wb}}\sum_{g \in G}\mathbb{1}\{g \in L_i\}x_{ig} \ge \left (1 - \frac{1}{e} - \gamma \right )(1 - \gamma^3)n. \end{align}\]

The set \(G\) can be split into \(G_{wb}\) and \(G_{nwb}\). Using this, \[\begin{align} \sum_{i \in N_{wb}}\sum_{g \in G_{wb}}\mathbb{1}\{g \in L_i\}x_{ig} \ge \left (1 - \frac{1}{e} - \gamma \right )(1 - \gamma^3)n - \sum_{i \in N_{wb}}\sum_{g \in G_{nwb}}\mathbb{1}\{g \in L_i\}x_{ig}. \end{align}\]

The term \(\sum_{i \in N_{wb}}\sum_{g \in G_{nwb}}\mathbb{1}\{g \in L_i\}x_{ig}\) is at most \(10\gamma n\) via the large good consistency property. Additionally, the term \(\sum_{i \in N_{wb}}\sum_{g \in G_{wb}}\mathbb{1}\{g \in L_i\}x_{ig}\) is at most \(|G_{wb}|\) since \(\mathbf{x}\) is a valid fractional allocation. Therefore: \[\begin{align} |G_{wb}| &\ge \left (1 - \frac{1}{e} - \gamma \right )(1 - \gamma^3)n - 10\gamma n\\ &\ge \left ( 1 - \frac{1}{e} - 12\gamma \right )n. \end{align}\] This completes the proof. ◻

Proof. We can re-write the left hand side of the desired inequality as follows: \[\begin{align} \sum_{i \in N_{wb}}\sum_{g \in G \setminus L_i}x_{ig} \sum_{j \in N_{wb}}\mathbb{1}\{g \in L_j\}x_{jg} &= \sum_{g \in G} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} \notag \\ &= \sum_{g \in G_{wb}} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} \notag \\ &\qquad + \sum_{g \in G_{nwb}} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg}. \label{eq:weird-upper-bound-0} \end{align}\tag{31}\]

Essentially, we split the set of goods \(G\) into \(G_{wb}\) and \(G_{nwb}\). We upper bound each term separately. By the definition of well-behaved large goods, \[\begin{align} \sum_{g \in G_{wb}} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} &\le \sum_{g \in G_{wb}}\gamma \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} \notag \\ &= \gamma \sum_{j \in N_{wb}} \sum_{g \in G_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} \notag \\ &\le \gamma \sum_{j \in N_{wb}} \ell_j \notag\\ &\le \gamma n. \label{eq:weird-upper-bound-1} \end{align}\tag{32}\]

In the final inequality we use the fact that \(\ell_j \le 1\) for all agents. Next, by the definition of the large good consistency property, \[\begin{align} \sum_{g \in G_{nwb}} \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} &\le \sum_{g \in G_{nwb}} \sum_{j \in N_{wb}} \mathbb{1}\{g \in L_j\} x_{jg} \notag \\ &\le 10\gamma n. \label{eq:weird-upper-bound-2} \end{align}\tag{33}\]

In the first inequality, we upper bound \(\sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\} x_{ig}\) using \(1\). Plugging in 32 and 33 into 31 , we prove the result. ◻

Proof. This follows from combining Lemma [lem:dependent-rounding-expectation] with Lemma [lem:fractional-property-a]. ◻

Proof. Consider some good \(g\) and some iteration \(k\). The only way \(\sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\}z_{ig, k}\) changes during iteration \(k\) is if \(g\) is at the end of the maximal path \(P\) chosen at iteration \(k\). However, by the rules of the edge fixing phase, all goods \(g\) either have zero variable edges incident on it or at least two variable edges incident on it. This implies \(g\) can never be at the end of a maximal path of variable edges. Therefore, \(\sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\}z_{ig, k}\) remains unchanged during iteration \(k\). Since \(k\) was chosen arbitrarily, it must hold that for all goods \(g\), \(\sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}z_{ig, \infty} = \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}z_{ig,1} = \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}x_{ig}\). ◻

Proof. Let \(G_{wb}\) denote the set of well-behaved large goods of the instance. Recall that a large good is well-behaved if \(\sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\}x_{ig} \ge 1 - \gamma\). There are at least \((1 - 1/e - 12\gamma)n\) well-behaved large goods \(|G_{wb}|\) in the instance since it satisfies the large good consistency property (Corollary 26). We define a good \(g\) as desirable at the start of iteration \(k\) if \[\begin{align} \sum_{i \in N_{wb}} \mathbb{1}\{g \in L_i\} \mathbb{1}\{\text{the (i, g) edge is variable at the start of iteration k}\}z_{ig} \ge 1 - \gamma. \end{align}\]

Each well-behaved agent \(i\) has \(\ell^{\mathbf{x}}_i \le (1 - 1/e + \gamma)\) (Lemma [lem:fractional-property-a]). This implies that each well-behaved large good has a degree of at least \(2\), and is therefore desirable at the start of the algorithm. Since no good is desirable at the end of the algorithm (no edge is variable), there is a point during the algorithm for each well-behaved large good \(g\) where it stops being desirable.

For each well-behaved large good \(g\), we pair it with a unique well-behaved agent \(i\) such that \(\ell^{\mathbf{z}}_{i, \infty} \ge (1 - \gamma)\). This implies \[\begin{align} \sum_{i \in N_{wb}} \left (\ell^{\mathbf{z}}_{i, \infty} \right )^2 \ge |G_{wb}|(1-\gamma)^2 \ge \left (1 - \frac{1}{e} - 12\gamma \right )n(1 -\gamma)^2 \ge \left (1 - \frac{1}{e} - 15\gamma \right )n, \end{align}\] which proves the lemma.

In the remainder of this proof, we describe our agent-good pairing process. Consider the point in the algorithm where the well-behaved large good \(g\) stops being desirable. The exact point where the good \(g\) stops being desirable must correspond to the point where some variable edge incident on \(g\) is fixed. This must either be because some agent \(i\) has \(\ell^{\mathbf{z}}_i\) set to \(1\) during the iteration, or the good \(g\) has exactly one variable edge incident to it at some point in the algorithm.

Consider the first case where \(g\) stops being desirable because a well-behaved agent \(i\) has \(\ell^{\mathbf{z}}_i\) set to \(1\) during the \(k\)-th iteration, and the \((i, g)\) edge has positive weight at the end of the \(k\)-th iteration. We pair \(g\) with this agent \(i\). It clearly satisfies our criteria since \(\ell^{\mathbf{z}}_{i, \infty} = \ell^{\mathbf{z}}_{i, k+1} = 1\). To show uniqueness, we observe that \(i\) must be an endpoint of the path \(P\) chosen by the algorithm during the \(k\)-th iteration. Since all paths are maximal, this must mean that the agent \(i\) has exactly one variable edge incident to it and this must correspond to the \((i, g)\) edge that gets fixed at the end of this iteration. This implies that the only edge fixed by \(\ell^{\mathbf{z}}_{i, k+1}\) being set to \(1\) is the \((i, g)\) edge.

Next, consider the case where \(g\) stops being desirable because it has one variable edge \((i, g)\) incident to it during the edge fixing phase of some iteration \(k\), and this edge gets fixed. Let \(i\) be the agent that this singular variable edge is incident on. This must mean that \(z_{ig, k+1} \ge 1 - \gamma\) since the good \(g\) was desirable at the end of the weight update phase of the \(k\)-th iteration. We pair \(g\) with the agent \(i\). We need to show two things to complete this proof: first, \(\ell^{\mathbf{z}}_{i, \infty} \ge 1-\gamma\), and second, no other good is paired with agent \(i\). Both of these follow from the observation that \(\ell^{\mathbf{z}}_{i, k+1} \ge 1 - \gamma\) and \(\ell^{\mathbf{z}}_{i, 1} \le (1 - 1/e + \gamma)\); this implies that \(\ell^{\mathbf{z}}_{i, k+1} > \ell^{\mathbf{z}}_{i, 1}\). That is, the large good amount of agent \(i\) increased from its initial value of \(\ell^{\mathbf{z}}_{i, 1}\). This is only possible if at some iteration, the algorithm chose a path \(P\) in the bipartite graph \(\mathcal{H}\) with the agent \(i\) as one of its endpoints during some iteration \(k' \le k\). Since paths are chosen maximally, this implies that the agent \(i\) has at most one variable edge incident to it at the end of the weight update phase of iteration \(k\). This edge is the edge \((i, g)\) that gets fixed at the end of this iteration. Therefore, once the edge is fixed, \(i\) no longer has any incident variable edges and will not be updated in future iterations. We can therefore, conclude that \(\ell^{\mathbf{z}}_{i, \infty} = \ell^{\mathbf{z}}_{i, k+1} \ge 1- \gamma\).

In both cases, when we pair a good \(g\) with an agent \(i\), the agent \(i\) has exactly one variable edge (the \((i,g)\) edge) incident on it at the moment before \(g\) stops being desirable, and this edge is fixed when \(g\) stops being desirable. Therefore, it cannot be that two goods get paired with the same agent. This completes the proof. ◻

Proof. Fix a good \(g \in G\). We can compute \(\sum_{i \in N}z_{ig}\) by partitioning it into three parts. \[\begin{align} \sum_{i \in N}z_{ig} = \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}z_{ig} + \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}z_{ig} + \sum_{i \in N_{nwb}}z_{ig}. \label{eq:valid-1} \end{align}\tag{34}\]

In the right hand side, the first term is decided by Step 1 (Section 8.1), the second term is decided by Step 3 (Section 8.3) and the third term is decided by Step 2 (Section 8.2). From the Preservation property [d3] of Step 1, we have: \[\begin{align} \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}z_{ig} = \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}x_{ig}.\label{eq:valid-2} \end{align}\tag{35}\]

From the modifications carried out in Step 2, we have: \[\begin{align} \sum_{i \in N_{nwb}}z_{ig} = \sum_{i \in N_{nwb}} \frac{x_{ig} + f^{\mathbf{x}}_{ig}}{2}. \label{eq:valid-3} \end{align}\tag{36}\]

Finally, from the modification carried out in Step 3, we have: \[\begin{align} \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}z_{ig} &= \sum_{i \in N_{wb}} \mathbb{1}\{g \notin L_i\}x_{ig} \left [1 - \max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \} \right . \notag \\&\qquad \qquad \left .+ \sum_{j \in N_{wb}}\max \left \{\frac{\ell^{\mathbf{z}}_j}{100} - \gamma, 0 \right \}\mathbb{1}\{g \notin L_j\}x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} \right ] \notag \\ &\le \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}x_{ig} - \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\} \max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \}x_{ig} \notag \\ &\qquad \qquad + \sum_{j \in N_{wb}}\max \left \{\frac{\ell^{\mathbf{z}}_j}{100} - \gamma, 0 \right \}\mathbb{1}\{g \notin L_j\}x_{jg} + \sum_{j \in N_{nwb}}\frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} \notag \\ &= \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}x_{ig} + \sum_{j \in N_{nwb}}\frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2}. \label{eq:valid-4} \end{align}\tag{37}\]

Plugging in 35 , 36 and 37 into 34 , we get \[\begin{align} \sum_{i \in N}z_{ig} &= \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}z_{ig} + \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}z_{ig} + \sum_{i \in N_{nwb}}z_{ig} \\ &\le \sum_{i \in N_{wb}}\mathbb{1}\{g \in L_i\}x_{ig} + \sum_{i \in N_{wb}}\mathbb{1}\{g \notin L_i\}x_{ig} + \sum_{j \in N_{nwb}}\frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} + \sum_{i \in N_{nwb}} \frac{x_{ig} + f^{\mathbf{x}}_{ig}}{2} \\ &= \sum_{i \in N}x_{ig}. \end{align}\]

Finally, we show that \(z_{ig} \ge 0\) for all \(i \in N\) and \(g \in G\). This is easy to see if \(i \in N_{wb}\) and \(g \in L_i\) since the dependent partial rounding scheme ensures that \(z_{ig}\) remains non-negative. If \(i \in N_{nwb}\), then by Step 2, \(z_{ig} = \frac{x_{ig} + f^{\mathbf{x}}_{ig}}{2} \ge 0\). If \(i \in N_{wb}\) and \(g \notin L_i\), then \[\begin{align} z_{ig} &= x_{ig}\left [1 - \max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \} + \sum_{j \in N_{wb}}\max \left \{\frac{\ell^{\mathbf{z}}_j}{100} - \gamma, 0 \right \}\mathbb{1}\{g \notin L_j\}x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2}\right ] \\ &\ge x_{ig} \left [1 - \max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \} \right ] \\ &\ge 0. \end{align}\] The last inequality follows from \(\ell^{\mathbf{z}}_i \in [0, 1]\). Therefore, the allocation \(\mathbf{z}\) is valid. ◻

Proof. \(R^i\) consists of \(\Delta x_{ig} \max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \}\) copies of each good \(g \in G \setminus L_i\). Therefore, \[\begin{align} v_i(R^i) = \sum_{g \in G \setminus L_i} \Delta x_{ig} v_i(g)\max \left \{\frac{\ell^{\mathbf{z}}_i}{100} - \gamma, 0 \right \} \le \frac{\ell^\mathbf{z}_i \Delta}{100} \sum_{g \in G \setminus L_i} x_{ig}v_i(g) = \frac{\ell^{\mathbf{z}}_i\mu^i \Delta}{100}. \end{align}\]

The observation follows from noting that \(\ell^{\mathbf{z}}_i\Delta = |L^*|\) and \(\mu^i = \mu\) (Lemma 15). ◻

Proof. \(A^i\) consists of \(\Delta x_{ig}\left [\sum_{j \in N_{wb}}\max \left \{\frac{\ell^{\mathbf{z}}_j}{100} - \gamma, 0 \right \}\mathbb{1}\{g \notin L_j\}x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} \right ]\) copies of each good \(g \in G \setminus L_i\). Therefore, \[\begin{align} \frac{v_i(A^i)}{\Delta\mu^i} &= \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb}}\max \left \{\frac{\ell^{\mathbf{z}}_j}{100} - \gamma, 0 \right \}\mathbb{1}\{g \notin L_j\}x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} \right ] \\ &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb} \setminus \{i\}}\left (\frac{\ell^{\mathbf{z}}_j}{100} - \gamma \right )x_{jg} - \sum_{j \in N_{wb}}\left (\frac{\ell^{\mathbf{z}}_j}{100} - \gamma \right ) \mathbb{1}\{g \in L_j\} x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg} - f^{\mathbf{x}}_{jg}}{2} \right ] \\ \end{align}\]

To simplify this expression, we separate the terms with negative coefficients and upper bound them. \[\begin{align} \frac{v_i(A^i)}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb} \setminus \{i\}}\left (\frac{\ell^{\mathbf{z}}_j}{100}\right )x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg}}{2} -\gamma \right ] \\ & \qquad \qquad - \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i} \left [\sum_{j \in N_{wb}} \left (\frac{\ell^{\mathbf{z}}_j}{100} \right )\mathbb{1}\{g \in L_j\}x_{jg} + \sum_{j \in N_{nwb}} \frac{f^{\mathbf{x}}_{jg}}{2} \right ] \end{align}\]

We use the fact that \(v_i(g) \le \frac{\mu^i}{1-\ell^{\mathbf{x}}_i} \le 3\mu^i\) for all small goods \(g\) since \(i\) is well-behaved and Lemma [lem:fractional-property-a] holds. This yields \[\begin{align} \frac{v_i(A^i)}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb} \setminus \{i\}}\left (\frac{\ell^{\mathbf{z}}_j}{100}\right )x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg}}{2} - \gamma \right ] \\ & \qquad \qquad - \sum_{g \in G \setminus L_i} 3x_{ig} \left [\sum_{j \in N_{wb}} \frac{\mathbb{1}\{g \in L_j\}x_{jg}}{100} + \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg}\right ]. \\ &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb} \setminus \{i\}}\left (\frac{\ell^{\mathbf{z}}_j}{100}\right )x_{jg} + \sum_{j \in N_{nwb}} \frac{x_{jg}}{2} -\gamma\right ] \\ & \qquad \qquad - \sum_{g \in G \setminus L_i} x_{ig} \sum_{j \in N_{wb}} \frac{\mathbb{1}\{g \in L_j\}x_{jg}}{30} - 3 \sum_{g \in G \setminus L_i} x_{ig} \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg}. \end{align}\]

We use \(C\) to denote the term \(\sum_{g \in G \setminus L_i} x_{ig} \sum_{j \in N_{wb}} \frac{\mathbb{1}\{g \in L_j\}x_{jg}}{30} + 3 \sum_{g \in G \setminus L_i} x_{ig} \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg}\). Note that \(C\) is independent of the randomness of Step 1. If we multiply both sides of the above inequality by \((1-\ell^{\mathbf{z}}_i)\) and take an expectation, we get \[\begin{align} \frac{\mathop{\mathrm{\mathbb{E}}}[(1-\ell^{\mathbf{z}}_i) v_i(A^i)]}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N_{wb} \setminus \{i\}}\left (\frac{\mathop{\mathrm{\mathbb{E}}}[(1-\ell^{\mathbf{z}}_i)\ell^{\mathbf{z}}_j]}{100}\right )x_{jg} + \sum_{j \in N_{nwb}} \frac{\mathop{\mathrm{\mathbb{E}}}[1-\ell^{\mathbf{z}}_i]x_{jg}}{2} - \mathop{\mathrm{\mathbb{E}}}[1-\ell^{\mathbf{z}}_i] \gamma\right ] \\ &\qquad \qquad - \mathop{\mathrm{\mathbb{E}}}[1-\ell^{\mathbf{z}}_i]C \end{align}\]

Here, we use Negative Correlation [d2] to upper bound \(\mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_i \ell^{\mathbf{z}}_j]\) and we use Corollary 29 to bound \(\mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_i]\). This simplifies our expression to

\[\begin{align} \frac{\mathop{\mathrm{\mathbb{E}}}[(1-\ell^{\mathbf{z}}_i) v_i(A^i)]}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}v_i(g)}{\mu^i}\left [\sum_{j \in N \setminus \{i\}}\frac{x_{jg}}{1000} - \gamma\right ] - C \end{align}\]

We separate out the \(\gamma\) term and write \(\sum_{j \in N \setminus \{i\}}x_{jg} = 1 - x_{ig}\), which holds due to Observation 16. Using \(\mu^i = \sum_{g \in G \setminus L_i}x_{ig}v_i(g)\), we get

\[\begin{align} \frac{\mathop{\mathrm{\mathbb{E}}}[(1-\ell^{\mathbf{z}}_i) v_i(A^i)]}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \frac{x_{ig}(1-x_{ig})v_i(g)}{1000\mu^i} - \gamma - C \end{align}\]

We complete our analysis by only considering goods in \(G \setminus L_i\) where \(x_{ig} \le 0.5\). For all of these goods \(g\), \((1 - x_{ig}) \ge 1/2\). Moreover, \(\sum_{g \in G\setminus L_i}\mathbb{1}\{x_{ig} \le 0.5\} x_{ig}v_i(g) \ge (1-\gamma)\mu^i\) via the small good fraction property (Definition 8). Therefore,

\[\begin{align} \frac{\mathop{\mathrm{\mathbb{E}}}[(1-\ell^{\mathbf{z}}_i) v_i(A^i)]}{\Delta \mu^i} &\ge \sum_{g \in G \setminus L_i} \mathbb{1}\{x_{ig} \le 0.5\}\frac{x_{ig}(1-x_{ig})v_i(g)}{1000\mu^i} - \gamma - C \\ &\ge \sum_{g \in G \setminus L_i} \mathbb{1}\{x_{ig} \le 0.5\}\frac{x_{ig}v_i(g)}{2000\mu^i} -\gamma- C \\ &\ge \frac{(1-\gamma)}{2000} - \gamma - C \\ &\ge 10^{-4} - C. \end{align}\] This completes the proof. ◻

Proof. This holds essentially due to the High Variance property [d4] and Corollary 29. \[\begin{align} \sum_{i \in N_{wb}}\frac{\mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_i(1 - \ell^{\mathbf{z}}_i)]}{30 n} &\le \frac{1}{30 n}\mathop{\mathrm{\mathbb{E}}}\left [ \sum_{i \in N_{wb}}\ell^{\mathbf{z}}_i - \sum_{i \in N_{wb}}\left (\ell^{\mathbf{z}}_i \right)^2 \right ] \\ &\le \frac{1}{30 n}\left [ \left (1 - \frac{1}{e} + \gamma \right )n - \left (1-\frac{1}{e} - 15\gamma \right )n \right ] \\ &\le \gamma. \end{align}\] In the second inequality, we use the High Variance property [d4] and Corollary 29. ◻

Proof. The lemma holds because \(|N_{nwb}| \le \gamma^3 n\) and the following sequence of inequalities. \[\begin{align} \frac{3}{n} \sum_{i \in N_{wb}} \sum_{g \in G \setminus L_i} x_{ig} \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg} &\le \frac{3}{n} \sum_{g \in G} \sum_{i \in N_{wb}} x_{ig} \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg} \\ &\le \frac{3}{n} \sum_{g \in G} \sum_{j \in N_{nwb}} f^{\mathbf{x}}_{jg} \\ &\le \frac{3}{n} |N_{nwb}| \le \gamma. \end{align}\] In the second inequality we upper bound \(\sum_{i \in N_{wb}} x_{ig}\) using \(1\). In the third inequality, we use the fact that the first bucket has size at most \(1\) for any agent \(i\). In the final inequality, we use \(|N_{nwb}| \le \gamma^3 n\). ◻

Proof. Let \(\varepsilon> 0\) be some constant that we will decide later. Let \(\mathcal{I}\) be an instance of the fair allocation problem with additive valuations. Given the instance \(\mathcal{I}\), let \(y\) be a rational configuration LP solution which is optimal up to a \(\ln{(1 + \varepsilon)}\) additive error (computed using Theorem 4). We can assume that this solution \(y\) has a well-defined objective value due to Remark 6. Let \(\mathbf{x}\) be its corresponding fractional allocation.

We compute a fractional allocation \(\mathbf{z}\) such that for some constant \(c^* > 0\), \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\texttt{ST}(\mathbf{z})] &\ge \frac{1}{n} \sum_{i \in N, S\subseteq G} y_{i, S} \ln v_i(S) - \frac{1}{e} + c^*, \\ &\ge \normalfont{\texttt{logNSW}}(\mathcal{I}) - \ln(1 + \varepsilon) - \frac{1}{e} + c^*. \end{align}\] If more than \(\gamma^3 n\) agents are not well-behaved in \(\mathbf{x}\), then \(\mathbf{z}= \mathbf{x}\) (Theorem 19). If at most \(\gamma^3 n\) agents are not well-behaved in \(\mathbf{x}\) but \(\mathbf{x}\) does not satisfy the large good consistency, we compute \(\mathbf{z}\) using Theorem 20. If at most \(\gamma^3 n\) agents are not well-behaved in \(\mathbf{x}\) and \(\mathbf{x}\) satisfies the large good consistency property, we compute \(\mathbf{z}\) using Theorem 28.

Then we round \(\mathbf{z}\) using the ST rounding procedure to create an integral allocation \(X\). Via Fact 1,

\[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{NSW}}(X)] \ge e^{\mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{logNSW}}(X)]} = e^{\mathop{\mathrm{\mathbb{E}}}[\texttt{ST}(\mathbf{z})]} \ge \exp\left \{\normalfont{\texttt{logNSW}}(\mathcal{I}) - \ln(1 + \varepsilon) - \frac{1}{e} + c^*\right \}. \end{align}\]

Setting \(\varepsilon= \frac{c^*}{2}\) and upper bounding \(\ln(1 + \varepsilon)\) by \(\varepsilon\), we get: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{NSW}}(X)] \ge e^{\mathop{\mathrm{\mathbb{E}}}[\normalfont{\texttt{logNSW}}(X)]} \ge \exp\left \{\normalfont{\texttt{logNSW}}(\mathcal{I}) - \frac{1}{e} + \frac{c^*}{2} \right \} = \frac{\normalfont{\texttt{NSW}}(\mathcal{I})}{e^{\frac{1}{e} - \frac{c^*}{2}}}. \end{align}\]

Every single step of the above process can be implemented in polynomial time. We start by finding a configuration LP solution using Theorem 4 and its corresponding fractional allocation \(\mathbf{x}\). Then, we decide which algorithm to use to compute \(\mathbf{z}\) — this can be done in polynomial time since the set of well-behaved agents can be found in polynomial time (Corollary 18) and the large good consistency property can be verified in polynomial time. Then we compute \(\mathbf{z}\); all the algorithms we present for computing \(\mathbf{z}\) are polynomial time algorithms. Finally, Shmoys-Tardos rounding can be implemented in polynomial time using any of the standard techniques [10], [20]. ◻

Proof. We first show that there always exists a set \(L\) satisfying the properties of Definition 1. This set \(L\) can be constructed iteratively. We start by initializing \(L\) as the empty set, and while there is some good \(g \in G \setminus L\) such that \(v(g) > \frac{v(G \setminus L)}{\Delta - \ell}\) (where \(\ell = |L|\)), we add this \(g\) to \(L\). Note that this addition only reduces the value of \(\frac{v(G \setminus L)}{\Delta - \ell}\) and therefore, does not violate the largeness of the goods already in \(L\).

\[\begin{align} \frac{v(G \setminus (L \cup \{g\}))}{\Delta - \ell - 1} = \frac{v(G \setminus L) - v(g)}{\Delta - \ell - 1} < \frac{v(G \setminus L) - \frac{v(G \setminus L)}{\Delta - \ell}}{\Delta - \ell - 1} = \frac{v(G \setminus L)}{\Delta - \ell}. \end{align}\]

This iterative procedure stops when \(|L| = \Delta - 1\) because \(v(g) \le v(G \setminus L)\) for any \(g \in G \setminus L\). Therefore, \(L\) satisfies Definition 1.

We show uniqueness next. Assume there are two different sets of large goods \(L\) and \(L'\) satisfying the properties of Definition 1. Note that if any good \(g\) is in \(L\) (resp. \(L'\)), all goods with value at least \(v(g)\) must also be in \(L\) (resp. \(L'\)). Therefore, let \(L = \{g_1, \dots, g_{\ell}\}\) and let \(L' = \{g_1, \dots, g_{\ell'}\}\), and assume \(\ell < \ell'\). By applying the properties of large goods with the set \(L\), we get for any \(g \in L' \setminus L\), \[\begin{align} v(g) \le \frac{v(G \setminus L)}{\Delta - \ell} = \frac{v(G \setminus L') + v(L' \setminus L)}{\Delta - \ell}. \end{align}\]

Adding the above inequality up for all \(g \in L' \setminus L\), we get \[\begin{align} v(L' \setminus L) \le \left (\frac{\ell' - \ell}{\Delta - \ell} \right ) (v(G \setminus L') + v(L' \setminus L)). \end{align}\]

Re-arranging terms gives us \[\begin{align} v(L' \setminus L) \le \frac{(\ell' - \ell)v(G \setminus L')}{\Delta - \ell'}. \end{align}\]

This contradicts the set \(L'\) being a set of large goods since each good \(g \in L'\setminus L\) satisfies \[v(g) > \frac{v(G \setminus L')}{\Delta - \ell'}. \qedhere\] ◻

Proof. Similar to the previous proof, this proof does not explicitly use the large goods of the instance \(\mathcal{I}^{mod}\). When we use the value \(\mu\), we mean the value \(\frac{v(G \setminus L)}{\Delta}\), where \(L\) is the set of large goods in the instance \(\mathcal{I}\). In the allocation \(W^{mod}\), we use \(S^{mod}_i\) to denote the set \(W^{mod}_i \setminus L'\) for each agent \(i\).

Like all the previous proofs, we partition the agents to lower bound the log Nash welfare. Let \(N_{L'}\) be the set of agents who receive a good in \(L'\) in the allocation \(W^{mod}\). Each of the large goods in the new set \(L'\) is more valuable than all the small goods of the instance. Therefore, the set \(N_{L'} = \{1, 2, \dots, |L'|\}\). Let \(N_S\) denote the remaining agents. Of the agents in \(N_S\), let \(N_1\) denote the set of agents \(i\) such that \(v(W^{mod}_i) \ge (1-\gamma)\mu\). Let \(N_2\) denote the remaining agents \(i\) where \(v(W^{mod}_i) < (1-\gamma)\mu\).

If \(N_S\) is empty (or equivalently \(|L'| = \Delta\)), then the theorem trivially follows because \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) \ge \frac{1}{\Delta} \left [\sum_{g \in L'}\ln v(g) \right ], \end{align}\] which proves the theorem for the special case where \(\Delta = |L'|\). From here on, we assume \(|L'| < \Delta\); that is, \(N_S\) is non-empty.

If all agents \(i\) in \(N_S\) satisfy \(v(W^{mod}_i) \ge 2\mu\), then the log Nash welfare of \(W^{mod}\) can be easily lower bounded as follows: \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L'} \ln v(g) + (\Delta - |L'|) \ln(2\mu)\right ] \\ &\ge \frac{1}{\Delta} \left [\sum_{g \in L'} \ln v(g) + (\Delta - |L'|) \ln\left (\mu \left (1 + \frac{v(A)}{\Delta \mu} \right )\right )\right ] \\ &\ge \frac{1}{\Delta} \left [\sum_{g \in L'} \ln v(g) + (\Delta - |L'|) \ln\mu \right ] + \frac{(\Delta - |L'|)v(A)}{2\Delta^2\mu}. \end{align}\] In the final inequality, we use Fact 3. This proves the theorem. So from here on, we assume \(v(W^{mod}_{\Delta}) < 2\mu\). That is, the worst bundle of the allocation has utility at most \(2\mu\). We make the following observations.

Since \(\mathcal{I}\) is well-behaved, the above observation implies that the set \(N_2\) has size at most \(\gamma \Delta\) ([prop:b]), and each agent \(i\) in \(N_2\) satisfies \(v(W^{mod}_i) \ge 10^{-4}\mu\) ([prop:e]). For each agent \(i \in N_1\), \(v(W^{mod}_i) \in [(1-\gamma)\mu, 5\mu]\) (using Observation 32). We can therefore define a value \(\alpha_i \in [0, 1]\) for each \(i \in N_1\) that satisfies \(v(W^{mod}_i) = \alpha_i (5\mu) + (1-\alpha_i)\mu(1-\gamma)\). Define \(\alpha = \sum_{i \in N_1} \alpha_i\).

We can lower bound the log Nash welfare of \(W^{mod}\) using the concavity of the \(\log\) function. \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \sum_{i \in N_1} \ln v(W^{mod}_i) + \sum_{i \in N_2} \ln v(W^{mod}_i)\right ] \\ &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \alpha\ln(5\mu) + (|N_1| - \alpha)\ln((1-\gamma)\mu) + |N_2| \ln(10^{-4} \mu)\right ] \\ &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + (\Delta - |L'|)\ln(\mu) \right ] + \frac{\alpha}{\Delta}\ln(5) + \frac{|N_1|}{\Delta}\ln(1-\gamma) + \frac{|N_2|}{\Delta} \ln(10^{-4}) \end{align}\]

We can simplify this further using \(|N_1| \le \Delta\) and \(|N_2| \le \gamma \Delta\). \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + (\Delta - |L'|)\ln(\mu) \right ] + \frac{\alpha}{\Delta} - 12\gamma. \label{eq:small-good-addition-large-good-removal-0} \end{align}\tag{44}\]

To complete this proof, we need to lower bound \(\alpha\). By the definition of the round robin algorithm, \(\{S^{mod}_{|L'|+1}, \dots, S^{mod}_{\Delta}\}\) are the \(\Delta - |L'|\) highest valued small bundles in the allocation. Therefore,

\[\begin{align} \sum_{i = |L'| + 1}^{\Delta} v(W^{mod}_{i}) \ge \frac{\Delta - |L'|}{\Delta} \sum_{i = 1}^{\Delta} v(S^{mod}_i) = (\Delta - |L'|) \mu + \frac{(\Delta - |L'|)v(A)}{\Delta}. \label{eq:small-good-addition-large-good-removal-1} \end{align}\tag{45}\]

We upper bound the left hand side by partitioning the agents into \(N_1\) and \(N_2\). \[\begin{align} \sum_{i = |L'| + 1}^{\Delta} v(W^{mod}_{i}) &= \sum_{i \in N_1} v(W^{mod}_i) + \sum_{i \in N_2}v(W^{mod}_i) \\ &\le \alpha (5\mu) + (|N_1| - \alpha)\mu(1-\gamma) + |N_2|\mu(1-\gamma) \\ &\le 5\alpha\mu + (\Delta - |L'|)\mu. \end{align}\]

Plugging this back into 45 , we get: \[\begin{align} 5\alpha\mu + (\Delta - |L'|)\mu \ge (\Delta - |L'|) \mu + \frac{(\Delta - |L'|)v(A)}{\Delta}. \end{align}\]

Re-arranging this inequality gives us \(\alpha \ge \frac{(\Delta - |L'|)v(A)}{5\Delta \mu}\). Plugging this back into 44 , we conclude that \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + (\Delta - |L'|)\ln(\mu) \right ] + \frac{(\Delta - |L'|)v(A)}{5\Delta^2 \mu} - 12\gamma, \end{align}\] which proves the theorem. ◻

Proof. Similar to the previous proof, this proof does not explicitly use the large goods of the instance \(\mathcal{I}^{mod}\). When we use the value \(\mu\), we mean the value \(\frac{v(G \setminus L)}{\Delta}\), where \(L\) is the set of large goods in the instance \(\mathcal{I}\). Like all previous proofs, this one also partitions the agents and uses the concavity of the log function to lower bound the log Nash welfare of \(W^{mod}\). However, because small goods are both added and removed, we analyze this in two phases: in the first phase, we analyze the effect of removing small goods, and in the second phase, we analyze the effect of adding small goods.

Formally, let \(\mathcal{I}^{int}\) be an intermediate instance that results from replacing \(L\) with \(L'\) and removing the small goods \(R\) from the instance \(\mathcal{I}\). Let \(W^{int}\) denote the round robin allocation of this instance. We also use \(S^{int}_i\) to denote for each agent \(i\), the set \(W^{int}_i \setminus L'\). Define \(N_{L'}\) to be the set of agents who receive a good from the set \(L'\) in \(W^{int}\). Since \(L'\) are the highest value goods of the instance, \(N_{L'} = \{1, \dots, |L'|\}\). Let \(N_S\) denote the remaining agents. We first show that if \(N_S\) is non-empty, \[\begin{align} \frac{1}{\Delta}\sum_{i \in N_S} \ln v(W^{int}_i) \ge \frac{(\Delta - |L'|)}{\Delta} \ln \mu - \frac{2(\Delta - |L'|)v(R)}{\Delta^2 \mu} - 12\gamma. \label{eq:general-add-removal-phase-1} \end{align}\tag{46}\]

The above inequality is true when each agent \(i \in N_S\) satisfies \(v(W^{int}_i) \ge (1 + \gamma)\mu\). Therefore, we assume \(v(W^{int}_{\Delta})\) is strictly less than \((1 + \gamma)\mu\). Using this, we partition the agents in \(N_S\) further. We define \(N_1\) to be the set of agents \(i\) that satisfy \(v(W^{int}_i) > (1 + \gamma)\mu\). We define \(N_2\) to be the remaining agents. Note that each agent \(i \in N_2\) satisfies \(v(W^{int}_i) \in [v(W^{int}_{\Delta}), (1 + \gamma)\mu]\). We therefore define \(\alpha_i \in [0, 1]\) for each \(i \in N_2\) where \(v(W^{int}_i) = (1 - \alpha_i)((1 + \gamma) \mu) + \alpha_i v(W^{int}_{\Delta})\). We define \(\alpha = \sum_{i \in N_2} \alpha_i\).

We can lower bound \(\frac{1}{\Delta}\sum_{i \in N_S} \ln v(W^{int}_i)\) as follows:

\[\begin{align} \frac{1}{\Delta}\sum_{i \in N_S} \ln v(W^{int}_i)&\ge \frac{1}{\Delta} \left [|N_1|\ln(\mu) + \sum_{i \in N_2} \ln v(W^{int}_i) \right ]\notag \\ &\ge \frac{1}{\Delta} \left [|N_1|\ln(\mu) + (|N_2| - \alpha)\ln \mu + \alpha \ln v(W^{int}_{\Delta})\right ] \notag \\ &= \frac{1}{\Delta} \left [(\Delta - |L'|)\ln(\mu)\right ] + \frac{\alpha}{\Delta}\ln \left (\frac{v(W^{int}_{\Delta})}{\mu} \right ) \label{eq:general-add-removal-1} \end{align}\tag{47}\]

The key part left to analyze is the term \(\frac{\alpha}{\Delta}\ln \left (\frac{v(W^{int}_{\Delta})}{\mu} \right )\). This is done using the following observations.

Plugging in Observation 35 into 47 proves 46 .

We now move from \(\mathcal{I}^{int}\) to \(\mathcal{I}^{mod}\) by adding the set of small goods \(A\) to the instance. For each agent \(i\), we define \(S^{mod}_i\) as the set of goods \(W^{mod}_i \setminus L'\). By adding the set of small goods \(A\), the value of each agent’s bundle can only increase. Exploiting this, we define the value \(\beta_i \ge 0\) for each agent \(i \in N_S\) as the value \(v(W^{mod}_i) - v(W^{int}_i)\).

First, consider the case when \(|L'| = \Delta\); that is, \(N_S\) is empty. Then the log Nash welfare of \(W^{mod}\) can be lower bounded as \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) \ge \frac{1}{\Delta} \left [\sum_{g \in L'} \ln v(g) \right ]. \end{align}\] This proves the theorem for the case where \(|L'| = \Delta\). We therefore assume that \(|L'| < \Delta\).

If \(v(W^{mod}_{\Delta}) \ge 2\mu\), then each agent who does not receive a good in \(L'\) receives a utility of at least \(2\mu\). This allows us to lower bound the Nash welfare as \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L'}\ln v(g) + (\Delta - |L'|)\ln(2\mu) \right ] \\ &\ge \frac{1}{\Delta} \left [\sum_{g \in L'}\ln v(g) + (\Delta - |L'|)\ln(\mu) \right ] + \frac{\Delta - |L'|}{2\Delta}. \end{align}\]

Note that \(v(A) \le \Delta \mu\), which implies \(1 \ge \frac{v(A) - v(R)}{\Delta \mu}\). Therefore, the above inequality can be further lower bounded as \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [\sum_{g \in L'}\ln v(g) + (\Delta - |L'|)\ln(\mu) \right ] + \frac{(\Delta - |L'|)(v(A)-v(R))}{4\Delta^2 \mu}, \end{align}\] which proves the Theorem. We therefore assume \(v(W^{mod}_{\Delta}) < 2\mu\). Using this assumption, we make a simple observation.

We can now lower bound the log Nash welfare of \(W^{mod}\). \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \sum_{i \in N_S} \ln (v(W^{mod}_i))\right ] \\ &= \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \sum_{i \in N_S} \ln (v(W^{int}_i) + \beta_i)\right ] \\ &\ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \sum_{i \in N_S} \ln \left (v(W^{int}_i) \left (1+ \frac{\beta_i}{5\mu}\right ) \right )\right ]. \end{align}\]

In the last inequality, we use \(v(W^{int}_i)\le 5\mu\) (Observation 34). Since \(\beta_i \le 5\mu\), we can lower bound \(\ln \left (1 + \frac{\beta_i}{5\mu} \right )\) using \(\frac{\beta_i}{10\mu}\) (Fact 3). This simplifies the above expression to: \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) \ge \frac{1}{\Delta} \left [ \sum_{g \in L'} \ln v(g) + \sum_{i \in N_S} \ln \left (v(W^{int}_i) \right )\right ] + \frac{\sum_{i \in N_S} \beta_i}{10\Delta\mu}. \label{eq:general-add-removal-phase-2} \end{align}\tag{48}\]

46 lowerbounds \(\sum_{i \in N_S} \ln \left (v(W^{int}_i) \right )\). The following observation lower bounds \(\sum_{i \in N_S} \beta_i\).

Plugging in Observation 37 and 46 into 48 , we prove the Theorem. ◻

Proof. Let \(W\) be the round robin allocation in the instance \(\mathcal{I}\). We show that \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) \ge \normalfont{\texttt{logNSW}}(W) - 2. \end{align}\]

Combining this with the fact that \(\frac{\normalfont{\texttt{NSW}}(\mathcal{I})}{\normalfont{\texttt{NSW}}(W)} \le e^{1/e}\) (Lemma 2), this proves the theorem.

Let the goods of \(\mathcal{I}^{mod}\) be the set \(\{g'_1, g'_2, \dots, g'_{m'}\}\). Let the classes of goods \(G_1, \dots, G_{k'}\) be ordered such that each good in \(G_1\) has value weakly greater than each good in \(G_2\), and so on. To compare the allocation \(W^{mod}\) and \(W\), we compare the allocated bundles for each agent. Fix some agent \(i \in [\Delta]\). We have \(W_i = \{g_i, g_{\Delta + i}, g_{2\Delta + i}, \dots\}\) for each agent \(i\) by our notation that \(G = \{g_1, \dots, g_m\}\) is the set of goods of the original instance \(\mathcal{I}\). Similarly, assuming \(v(g'_1) \ge v(g'_2) \ge \dots \ge v(g'_{m'})\), we have \(W^{mod}_i = \{g'_{i}, g'_{\Delta + i}, g'_{2\Delta + i} \dots\}\) for each agent \(i\) by the definition of the round robin allocation (assuming ties are broken in favor of lower index). We prove the following claims to relate the two bundles.

We can use Observations 38 and 39 to upper bound \(v(W_i)\). Using the observations, we can lower bound \(v(W^{mod}_i)\) as follows: \[\begin{align} v(W_i) &= v(g_i) + v(g_{\Delta + i}) + v(g_{2\Delta + i}) + \dots \\ &\le v(g'_i) + v(g_{\Delta + i}) + v(g_{2\Delta + i}) + \dots \\ &= v(g'_i) + \left ( v(g_{\Delta + i}) + v(g_{2\Delta + i}) \right ) + \left ( v(g_{3\Delta + i}) + v(g_{4\Delta + i}) \right ) + \left ( v(g_{5\Delta + i}) + v(g_{6\Delta + i}) \right ) + \dots \\ &\le v(g'_i) + \left (v(g'_i) + v(g'_i) \right ) + \left (v(g'_{\Delta + i}) + v(g'_{\Delta + i}) \right ) +\left (v(g'_{2\Delta + i}) + v(g'_{2\Delta + i}) \right ) + \dots \\ &\le 3v(g'_i) + 3v(g'_{\Delta + i}) + 3v(g'_{2\Delta + i}) + \dots \\ &\le 3v(W^{mod}_i) \end{align}\] In the first inequality, we used Observation 38 and in the second inequality, we used Observation 39.

We have shown that for each agent \(i\), \(v(W_i)\le 3v(W^{mod}_i)\). This immediately gives us \[\begin{align} \normalfont{\texttt{logNSW}}(W^{mod}) = \frac{1}{\Delta} \sum_{i \in [\Delta]} \ln(v(W^{mod}_i)) \ge \frac{1}{\Delta} \sum_{i \in [\Delta]} \left (\ln v(W_i) - \ln(3) \right ) \ge \frac{1}{\Delta} \sum_{i \in [\Delta]} \ln v(W_i) - 2. \end{align}\] This completes the proof. ◻

Proof. Let \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) be the artificial instance of agent \(i\) for some \(\Delta\) that is feasible with respect to both \(\mathbf{x}\) and \(y\). Let \(W\) be the round robin allocation of this instance. Theorem [thm:round-robin-nash-lower-bound] proves the following: \[\begin{align} \normalfont{\texttt{logNSW}}(W) \ge \frac{1}{\Delta}\left [ \sum_{g \in L} \ln{v_i(g)} + (\Delta - \ell) \ln\left ( \frac{\Delta\mu}{\Delta - \ell} \right ) \right ] - \frac{1}{e}. \end{align}\]

Combining this with Lemma 11, we get: \[\begin{align} \texttt{ST}(\mathbf{x}, i) \ge \frac{1}{\Delta}\left [ \sum_{g \in L} \ln{v_i(g)} + (\Delta - \ell) \ln\left ( \frac{\Delta\mu}{\Delta - \ell} \right ) \right ] - \frac{1}{e}. \label{eq:fractional-nash-lower-bound-1} \end{align}\tag{49}\]

We use Lemma 15 which states that \(\ell = \Delta \ell_i\), \(\mu^i = \mu\) and \(L\) consists of \(\Delta x_{ig}\) copies of each \(g \in L_i\). This simplifies 49 to \[\begin{align} \texttt{ST}(\mathbf{x}, i) \ge \sum_{g \in L_i} x_{ig}\ln{v_i(g)} + (1 - \ell_i) \ln\left ( \frac{\mu^i}{1 - \ell_i} \right ) - \frac{1}{e}. \end{align}\]

This proves the first inequality. To prove the second inequality, we use Lemma 3 which states that \[\begin{align} \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) \le \frac{1}{\Delta}\left [ \sum_{g \in L} \ln{v_i(g)} + (\Delta - \ell) \ln\left ( \frac{\Delta\mu}{\Delta - \ell} \right ) \right ] \end{align}\]

Plugging this into 49 gives us \[\begin{align} \texttt{ST}(\mathbf{x}, i) \ge \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) - \frac{1}{e}. \end{align}\]

Finally we use Lemma 13 to lower bound \(\normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta))\) using \(\sum_{S \subseteq G} y_{i, S}\ln v_i(S)\). This proves the lemma. ◻

Proof. Let \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) be the artificial instance for agent \(i\) for some \(\Delta\) feasible with respect to \(\mathbf{x}\). Let \(\ell\) be the number of large goods of the instance \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\). Since \(i\) is well-behaved in \(\mathbf{x}\), \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) must be well-behaved, which implies \(\frac{\ell}{\Delta} \in \left [1 - \frac{1}{e} - \gamma, 1 - \frac{1}{e}+\gamma \right ]\) ([prop:a]). The lemma follows by noting that \(\ell_i = \frac{\ell}{\Delta}\) (Lemma 15). ◻

Proof. Let \(\mathcal{I}^{i, \mathbf{x}}(\Delta)\) be the artificial instance of agent \(i\) for some \(\Delta\) that is feasible with respect to \(\mathbf{x}\) and \(y\). Lemma 3 shows the following \[\begin{align} \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) \le \frac{1}{\Delta} \left [\sum_{g \in L}\ln v_i(g) + (\Delta - \ell)\ln \mu \right ] + \frac{1}{e}. \end{align}\]

We use Lemma 15 which states that \(\ell = \Delta \ell_i\), \(\mu^i = \mu\) and \(L\) consists of \(\Delta x_{ig}\) copies of each \(g \in L_i\). This simplifies the above inequality to \[\begin{align} \normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta)) \le \sum_{g \in L_i} x_{ig}\ln{v_i(g)} + (1 - \ell_i) \ln \mu^i + \frac{1}{e}. \end{align}\]

Finally, we use Lemma 13 to lower bound \(\normalfont{\texttt{logNSW}}(\mathcal{I}^{i, \mathbf{x}}(\Delta))\) using \(\sum_{S \subseteq G} y_{i, S}\ln v_i(S)\), and prove the lemma. ◻

Proof. We show that \(\mathop{\mathrm{\mathbb{E}}}[z_{ig, k+1}] = \mathop{\mathrm{\mathbb{E}}}[z_{ig, k}]\) for all \(k \ge 1\). This implies that \(\mathop{\mathrm{\mathbb{E}}}[z_{ig, \infty}] = \mathop{\mathrm{\mathbb{E}}}[z_{ig, 1}]\) and since \(\mathop{\mathrm{\mathbb{E}}}[z_{ig, 1}] = x_{ig}\), the lemma is proved.

We consider two events at iteration \(k\).

Event A: The edge \((i, g)\) is not in the path \(P\) or the cycle \(C\) chosen by the algorithm. In this case, \(\mathop{\mathrm{\mathbb{E}}}[z_{ig, k+1}] = \mathop{\mathrm{\mathbb{E}}}[z_{ig, k}]\) since it remains unchanged during iteration \(k\).

Event B: The edge \((i, g)\) is in the path \(P\) or cycle \(C\) chosen by the algorithm. In this case, assume without loss of generality that \((i, g) \in M_1\). The proof for the other case is similar. We can compute \(\mathop{\mathrm{\mathbb{E}}}[z_{ig, k+1}]\) using the definition of our update rule:

\[\begin{align} \mathop{\mathrm{\mathbb{E}}}[z_{ig, k+1}] = \mathop{\mathrm{\mathbb{E}}}\left [ \frac{\beta^*}{\beta^* + \alpha^*}(z_{ig, k} + \alpha^*) + \frac{\alpha^*}{\beta^* + \alpha^*}(z_{ig, k} - \beta^*) \right ] = \mathop{\mathrm{\mathbb{E}}}[z_{ig, k}]. \end{align}\]

Since the two events \(A\) and \(B\) cover all possible cases, this proves the lemma. ◻

Proof. This proof is similar to the previous lemma. We show that for all \(k \ge 1\), \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left [\prod_{i \in S} \ell^{\mathbf{z}}_{i, k+1} \right ] \le \mathop{\mathrm{\mathbb{E}}}\left [\prod_{i \in S} \ell^{\mathbf{z}}_{i, k} \right ]. \label{eq:negative-correlation} \end{align}\tag{50}\]

This implies that \(\mathop{\mathrm{\mathbb{E}}}\left [\prod_{i \in S} \ell^{\mathbf{z}}_{i, \infty} \right ] \le \mathop{\mathrm{\mathbb{E}}}\left [\prod_{i \in S} \ell^{\mathbf{z}}_{i, 1} \right ]\) and the lemma is proved due to \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left [\prod_{i \in S} \ell^{\mathbf{z}}_{i, 1} \right ] = \prod_{i \in S} \ell^{\mathbf{x}}_{i}\le \left (1 - \frac{1}{e} + \gamma \right )^{|S|}. \end{align}\] The final inequality holds due to Lemma [lem:fractional-property-a].

Let us consider iteration \(k\) (for some \(k\)). In this iteration, if a cycle \(C\) is chosen by the algorithm, \(\ell^{\mathbf{z}}_{i, k+1} = \ell^{\mathbf{z}}_{i, k}\) for all agents \(i\) since no agent sees their large good amount modified. Therefore, 50 holds. If a maximal path \(P\) is chosen by the algorithm, only agents at the endpoints of the path see a change in their \(\ell^{\mathbf{z}}_i\) values.

Let \(i_1, i_2\) be the two agents at the endpoint of the path \(P\) chosen by the algorithm at iteration \(k\). Note that for all agents \(i \in S \setminus \{i_1, i_2\}\), we have \(\ell^{\mathbf{z}}_{i, k+1} = \ell^{\mathbf{z}}_{i, k}\). Therefore, if neither \(i_1\) nor \(i_2\) are in \(S\), then 50 holds. If both \(i_1\) and \(i_2\) are in \(S\), 50 holds if \(\mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_{i_1, k+1} \ell^{\mathbf{z}}_{i_2, k+1}] \le \mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_{i_1, k} \ell^{\mathbf{z}}_{i_2, k}]\). This is true because

\[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_{i_1, k+1} \ell^{\mathbf{z}}_{i_2, k+1}] &= \mathop{\mathrm{\mathbb{E}}}\left [\frac{\beta^*}{\beta^* + \alpha^*}(\ell^{\mathbf{z}}_{i_1, k} + \alpha^*)(\ell^{\mathbf{z}}_{i_2, k} - \alpha^*) + \frac{\alpha^*}{\beta^* + \alpha^*}(\ell^{\mathbf{z}}_{i_1, k} - \beta^*)(\ell^{\mathbf{z}}_{i_2, k} + \beta^*)\right ] \\ &\le \mathop{\mathrm{\mathbb{E}}}\left [\ell^{\mathbf{z}}_{i_1, k}\ell^{\mathbf{z}}_{i_2, k} - \alpha^* \beta^* \right ] \\ &\le \mathop{\mathrm{\mathbb{E}}}\left [\ell^{\mathbf{z}}_{i_1, k}\ell^{\mathbf{z}}_{i_2, k} \right ]. \end{align}\] The above proof assumes that the edges of \(P\) incident on \(i_1\) and \(i_2\) fall into different matchings. Note that this holds because the graph is bipartite; therefore, if the two endpoints of a path are two agents, then the path must have even length. This implies the two edges at either end of the path must fall into different matchings.

If one agent (say \(i_1\)) at the endpoint of the path \(P\) is in the set \(S\), then using the arguments of Lemma [lem:dependent-rounding-expectation], we can show that \(\mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_{i_1, k+1}] = \mathop{\mathrm{\mathbb{E}}}[\ell^{\mathbf{z}}_{i_1, k}]\). This proves 50 for this case.

This covers all possible cases, and therefore the lemma holds. ◻