Proof. Let \(\mathcal{A} = (A_1, \dots, A_n)\) be a complete allocation with an acyclic envy graph. There must exist an agent who does not envy any other agent; we call her agent \(i\). Then, for any agent \(j \in N\), we have \(u_i(A_i) \geq u_i(A_j)\). Summing this up over all agents \(j \in N\) gives \(n\cdot u_i(A_i) \geq \sum_{j \in N} u_i(A_j) \geq u_i(M) = 1\), or \(u_i(A_i) \ge 1/n\). Hence, the utilitarian welfare of \(\mathcal{A}\) is at least \(1/n\). ◻

Proof of [prop:strong95price]. We begin by proving the upper bound for the strong utilitarian price. Since the utility functions are normalized, each agent can have a total utility of at most \(1\). Hence, the maximum utilitarian welfare is at most \(n\). On the other hand, by 1, the utilitarian welfare of an ECE allocation is at least \(1/n\). Therefore, the strong utilitarian price is at most \(n/(1/n) = n^2\).

We prove the lower bound for both the strong utilitarian and egalitarian prices using an instance with \(n\) agents, \(m = 2n-1\) goods, and the following utilities:

• \(u_n(g_j) = 1/n\) for each \(j \in \{1, \dots, n\}\).

• For each \(i \in N \setminus \{n\}\), \(u_i(g_{n+i}) = 1\).

• \(u_i(g_j) = 0\) for all other pairs \((i, j)\).

Consider the following ECE allocation: In each round \(r \in \{1, \dots, n\}\), good \(g_r\) is allocated to agent \(r\). There is no envy cycle since in the first \(n-1\) rounds, only agent \(n\) envies other agents, and at the end of round \(n\), agent \(n\) no longer envies any other agent. Next, in each round \(r \in \{{n+1}, \dots, 2n-1\}\), good \(g_r\) is allocated to agent \(r-n+1\). Again, there is no envy cycle since for each \(i \in N \setminus \{n\}\), agent \(i\) only envies agent \(i+1\), and agent \(n\) envies no other agent. In the final allocation, each agent \(i \in N \setminus \{n\}\) gets a utility of \(0\), while agent \(n\) gets a utility of \(1/n\). Hence, the utilitarian welfare of the allocation is \(1/n\), and the egalitarian welfare is \(0\).

Now, observe that for every good, there is a unique agent who values it positively; giving each good to such an agent results in an allocation where every agent gets a utility of \(1\). Thus, the maximum utilitarian welfare of this instance is \(n\) and the maximum egalitarian welfare is \(1\). It follows that the strong utilitarian price of ECE for this instance is \(n/(1/n) = n^2\), and its strong egalitarian price is \(1/0 = \infty\). ◻

Proof. Consider any allocation obtained with the round-robin algorithm. Without loss of generality, assume that the agent ordering in each round⁷ is \((1, 2, \dots, n)\), and that the goods are allocated in the order \(g_1, g_2, \dots, g_m\). In the ECE algorithm, we allocate the goods to the same agents as in the round-robin algorithm, but in reverse order. Let \(k = m - {(\lceil m/n \rceil - 1)n}\) be the number of turns in the last (possibly incomplete) round of the round-robin algorithm. Then, the goods \(g_m, \dots, g_1\) are given to agents \[k, k-1, \dots, 1,\, n, n-1, \dots, 1,\, \dots,\, n, n-1, \dots, 1\] respectively, in that order starting from \(g_m\). To prove that this is indeed a valid allocation produced by the ECE algorithm, it suffices to show that every intermediate allocation (including the final allocation) has an acyclic envy graph, and each good is allocated to an unenvied agent.

We begin my making some observations about the envy graph of any intermediate allocation in this execution of the ECE algorithm. Note that the reverse order of the original round-robin ordering is itself a round-robin ordering, with the ordering \[(a_1, \dots, a_n) \coloneq (k, {k-1}, \dots, 1, n, {n-1}, \dots, {k+1})\] in each round. Furthermore, for each \(i\in\{1,\dots,n\}\), the good allocated to agent \(a_i\) in round \(r\) of the reverse round-robin ordering is the \(r\)-th last good received by agent \(a_i\) in the original round-robin allocation.

Our first claim is that, in any intermediate allocation, if two agents \(a_i, a_j \in N\) have the same number of goods and \(i > j\), then agent \(a_i\) does not envy agent \(a_j\). To see this, observe that in each round \(r \in \{1, \dots, \lceil m/n \rceil\}\) of the reverse round-robin ordering, agent \(a_i\) receives her \(r\)-th good \(g_{m+1-(r-1)n-i}\) after agent \(a_j\) receives her \(r\)-th good \(g_{m+1-(r-1)n-j}\). Since the ordering is reversed in the original round-robin algorithm, agent \(a_i\) must prefer her good \(g_{m+1-(r-1)n-i}\) to the good \(g_{m+1-(r-1)n-j}\) of agent \(a_j\). Since both agents have the same number of goods, agent \(a_i\) does not envy agent \(a_j\).

Next, we claim that if two agents have different numbers of goods, the agent with more goods does not envy the agent with fewer goods. The reasoning is similar to that of the previous claim. In particular, for each \(r\), agent \(a_i\) receives her \((r+1)\)-th good after agent \(a_j\) receives her \(r\)-th good in the reverse round-robin ordering. Since the ordering is reversed in the original round-robin algorithm, agent \(a_i\) must prefer her good to agent \(a_j\)’s good. Therefore, agent \(a_i\) does not envy agent \(a_j\) overall.

Combining the two claims above, it follows that the envy graph is always acyclic. Indeed, we can find a topological ordering of the envy graph as follows. First, sort the agents in increasing order of their bundle size. Then, among agents with bundles of the same size, sort the agents \(a_i \in N\) in increasing order of their indices \(i\). By our two claims, no agent envies an agent placed earlier in the topological order.

Finally, since the reverse of the round-robin ordering is still a round-robin ordering, each good is allocated to an agent with the fewest goods, and among such agents, the agent \(a_i\) with the lowest index \(i\). It therefore follows from our two claims that the agent who receives the good must be unenvied before the allocation of the good. ◻

Proof. Let \(0 < \epsilon < 1/(3n)\). We construct an instance with \(n\) agents, \(m = 2n\) goods, and the following utilities:

Consider the allocation obtained by the ECE algorithm using the heuristic where in round \(r\), good \(g_r\) is allocated to an unenvied agent \(i\) maximizing the utility \(u_i(g_r)\). Assume that any remaining ties are broken by choosing the agent with the lowest index. In the first round, good \(g_1\) must be allocated to agent \(n\), which causes all other agents to envy agent \(n\). For each round \(r \in \{2, \dots, n\}\), there is at least one agent with an empty bundle; such an agent will envy agent \(n\). Hence, good \(g_r\) must be allocated to agent \(r-1\), who is the unenvied agent with the highest utility for it. At the end of round \(r\), the direction of envy between agents \(r-1\) and \(n\) is reversed, so that agent \(n\) envies agent \(r-1\) instead; note that no envy cycle is created. After the first \(n\) rounds, agent \(n\) is no longer envied by any agent but envies every other agent.

Subsequently, good \(g_{n+1}\) must be allocated to agent \(n\)—the only unenvied agent—removing the envy from agent \(n\) to every agent \(i \in N \setminus \{1, n\}\). However, agent \(n\) still envies agent \(1\), who therefore cannot receive a good in round \(n+2\). Hence, good \(g_{n+2}\) must be allocated to agent \(2\), the unenvied agent with the lowest index. This causes agent \(2\) to be envied by agent \(1\). Then, it can be shown by induction that for each round \(r \in \{n+3, \dots, 2n\}\), good \(g_r\) must be allocated to agent \(r-n\), the unenvied agent with the lowest index, causing her to be envied by agent \(r-n-1\). Furthermore, allocating good \(g_{2n}\) to agent \(n\) in round \(2n\) removes agent \(n\)’s envy towards agent \(1\), so no envy cycle is created.

In the final allocation, each agent \(i \in N \setminus \{n\}\) receives a total utility of \(\epsilon\), while agent \(n\) receives a total utility of \(1/n+(n-2)\epsilon\). The utilitarian welfare of this allocation is \(1/n + (2n-3)\epsilon\), and the egalitarian welfare is \(\epsilon\).

On the other hand, consider a different allocation where all the goods \(g_1, \dots, g_{n+1}\) are allocated to agent \(n\), whereas the goods \(g_{n+2}, \dots, g_{2n}\) are allocated to agents \(1, \dots, n-1\) respectively. Note that agent \(n\) receives a utility of \(1-(n-1)\epsilon\) and each agent \(i \in N \setminus \{n\}\) receives a utility of \(1-2\epsilon\). Hence, the utilitarian welfare is \(n-(3n-3)\epsilon\) and the egalitarian welfare is at least \(1-n\epsilon\). Therefore, the strong utilitarian price for this instance is at least \((n-(3n-3)\epsilon)/(1/n+(2n-3)\epsilon)\), which approaches \(n^2\) as \(\epsilon \rightarrow 0\). Furthermore, the strong egalitarian price for this instance is at least \((1-n\epsilon)/\epsilon\), which approaches \(\infty\) as \(\epsilon \rightarrow 0\).

The bound for the strong egalitarian price is obviously tight. For the strong utilitarian price, the tightness of the bound follows from [prop:strong95price], since the set of allocations obtained with the ECE algorithm using any heuristic is a subset of all allocations produced by the ECE algorithm. ◻

Proof. We start with the upper bound for the strong utilitarian price. Let \((A_1, \dots, A_n)\) be an allocation obtained with this heuristic; its utilitarian welfare is denoted by \(\mathrm{UW}= \sum_{i \in N} u_i(A_i)\). Moreover, let \((A^*_1, \dots, A^*_n)\) be an allocation maximizing the utilitarian welfare; its utilitarian welfare is denoted by \(\mathrm{MUW}= \sum_{j \in N} u_j(A^*_j)\). For each bundle \(A_i\) in the ECE allocation, let \(\mathrm{MUW}(A_i) = \sum_{j \in N} u_j(A^*_j \cap A_i)\) be the “portion” of the maximum utilitarian welfare contributed by bundle \(A_i\). Note that \[\begin{align} \mathrm{MUW}= \sum_{j \in N} u_j(A^*_j) \leq \sum_{j \in N} \sum_{i \in N} u_j(A^*_j \cap A_i) = \sum_{i \in N} \sum_{j \in N} u_j(A^*_j \cap A_i) &= \sum_{i \in N} \mathrm{MUW}(A_i). \end{align}\] Let \(k\) be an unenvied agent—such an agent exists by definition of the ECE algorithm. That is, for any \(j \in N\), \(u_j(A_j) \geq u_j(A_k)\). Then, \[\begin{align} \mathrm{MUW}(A_k) = \sum_{j \in N} u_j(A^*_j \cap A_k) \leq \sum_{j \in N} u_j(A_k) \leq \sum_{j \in N} u_j(A_j) = \mathrm{UW}. \end{align}\] Now, let \(i \in N \setminus \{k\}\). We consider three cases depending on the size of bundle \(A_i\).

Case 1: \(|A_i| \geq 2\). Let \(g\) be the last good to be added into the bundle \(A_i\) (due to the envy cycle elimination step, \(A_i\) may belong to a different agent from agent \(i\) when \(g\) is added). By definition of the heuristic, \(g\) must be added into the bundle \(A_i\) after round \(n\). Then, for any agent \(j \in N\), it must hold that \(u_j(A_j) \geq u_j(g_j) \geq u_j(g)\), where \(g_j\) is the good allocated to agent \(j\) in round \(j\). On the other hand, by definition of the ECE heuristic, the owner of the bundle \(A_i \setminus \{g\}\) must be unenvied when \(g\) is added into it. Hence, we also have \(u_j(A_j) \geq u_j(A_i \setminus \{g\})\) for any agent \(j \in N\). As a result, \(u_j(A_i) \leq u_j(A_i \setminus \{g\}) + u_j(g) \leq 2u_j(A_j)\). This implies that \[\begin{align} \mathrm{MUW}(A_i) = \sum_{j \in N} u_j(A^*_j \cap A_i) \leq \sum_{j \in N} u_j(A_i) \leq 2 \sum_{j \in N} u_j(A_j) = 2\cdot\mathrm{UW}. \end{align}\]

Case 2: \(|A_i| = 1\). Then, there is exactly one agent \(j \in N\) such that \(A^*_j \cap A_i \neq \emptyset\), which implies that \(\mathrm{MUW}(A_i) = u_j(A^*_j \cap A_i) \leq 1\).

Case 3: \(|A_i| = 0\). In this case, \(\mathrm{MUW}(A_i) = 0\).

Let \(N_1 = \{i \in N \setminus \{k\} : |A_i| = 1\}\) and \(N_2 = \{i \in N \setminus \{k\} : |A_i| \geq 2\}\). By our analysis of the three cases, \[\begin{align} \mathrm{MUW}\leq \sum_{i \in N} \mathrm{MUW}(A_i) &= \mathrm{MUW}(A_k) + \sum_{i \in N_2} \mathrm{MUW}(A_i) + \sum_{i \in N_1} \mathrm{MUW}(A_i) \\ &\leq \mathrm{UW}+ 2|N_2|\cdot\mathrm{UW}+ |N_1|. \end{align}\] Hence, \[\begin{align} \frac{\mathrm{MUW}}{\mathrm{UW}} \leq 1 + 2|N_2| + \frac{|N_1|}{\mathrm{UW}} &\leq 1 + 2|N_2| + n|N_1| \geq 1/n by \ref{lem:no95envy95cycle}} \\ &\leq 1 + 2|N_2| + n(n-1-|N_2|) ) \setminus N_2} \\ &= n^2 - n + 1 + (2-n)|N_2| \\ &\leq n^2 - n + 1. \end{align}\] Therefore, the strong utilitarian price is at most \(n^2-n+1\).

We continue with the lower bounds. Consider an instance with \(n\) agents, \(m = n\) goods, and the following utilities:

• \(u_1(g_j) = 1/n\) for all \(j\).

• \(u_i(g_{i-1}) = 1\) for each \(i \in N \setminus \{1\}\).

• \(u_i(g_j) = 0\) for all other pairs \((i, j)\).

Consider the allocation obtained with the ECE algorithm using the heuristic where each specified agent is allocated a good that yields the highest utility for her. Assume that any remaining ties are broken by choosing the good with the lowest index. In the first round, agent \(1\) picks good \(g_1\) with utility \(1/n\). In the second round, all remaining goods have the same utility of \(0\) to agent \(2\), so she picks good \(g_2\) which has the lowest index. Then, it can be shown by induction that in each round \(r \in \{3, \dots, n\}\), agent \(r\) values all remaining goods at \(0\) and picks good \(g_r\) which has the lowest index. Note that there is no envy cycle in any round, since each agent \(i \in N \setminus \{1\}\) only envies agent \(i-1\), and agent \(1\) does not envy any agent. In the resulting allocation, agent \(1\) receives a utility of \(1/n\), while every other agent receives a utility of \(0\). Hence, the utilitarian welfare of the allocation is \(1/n\), and the egalitarian welfare is \(0\).

Now, consider a different allocation where each agent \(i \in N \setminus \{1\}\) receives good \(g_{i-1}\) with utility \(1\), and agent \(1\) receives good \(g_n\) with utility \(1/n\). The utilitarian welfare of this allocation is \(n-1+1/n\), and the egalitarian welfare is \(1/n\). Therefore, the strong utilitarian price is at least \((n-1+1/n)/(1/n) = n^2-n+1\), and the strong egalitarian price is at least \((1/n)/0 = \infty\). The bound for the strong egalitarian price is obviously tight. ◻

Proof. Consider an instance with \(n \geq 2\) agents and \(m = n\) goods where \(u_i(g_j) = 1\) if \(j = i\) and \(u_i(g_j) = 0\) otherwise. The maximum egalitarian welfare is \(1\), which is obtained when each agent \(i \in N\) receives the good \(g_i\). On the other hand, consider an allocation obtained via the ECE algorithm where in the first round, \(g_1\) is allocated to agent \(1\), and in the second round, \(g_2\) is also allocated to agent \(1\). This allocation can be obtained with the heuristic in [thm:agent95good95with95max95util95first95round95only], since \(u_i(g_j)\) is indeed maximized when \(i = j = 1\). Furthermore, agent \(1\) remains unenvied at the end of the first round, and therefore can receive good \(g_2\) in the second round. Since the ECE algorithm can only add new goods to existing bundles and change the ownership of existing bundles, \(g_1\) and \(g_2\) will stay in the same bundle for the remainder of the algorithm. This leaves only \(n-2\) goods to be distributed among the remaining \({n-1}\) bundles. Hence, at least one agent must end up with an empty bundle. It follows that the egalitarian welfare of this allocation is \(0\), and the strong egalitarian price of this instance is \(1/0 = \infty\). ◻

Proof. We begin by proving the upper bound. Let an instance with \(n \geq 2\) agents and \(m \geq 1\) goods be given. Let \(v = \max_{i \in N,\, g \in M} u_i(g)\) be the maximum utility of any agent for any good, and \(\mathcal{A} = (A_1, \dots, A_n)\) be an allocation of this instance obtained by the ECE algorithm using the heuristic where in the first round, some good of utility \(v\) is allocated to an agent who values it at \(v\). Without loss of generality, assume that the agents \(1, \dots, n\) are sorted in descending order of utility, that is, \(u_1(A_1) \geq \dots \geq u_n(A_n)\).

We first find an upper bound on the maximum utilitarian welfare of this instance in terms of \(n\), \(v\), and the utilitarian welfare of the allocation \(\mathcal{A}\). Observe that for each agent \(i \in N\) who is envied by some other agent, there exists a good \(g'_i \in A_i\), depending only on \(i\), such that removing this good from agent \(i\)’s bundle resolves all envy towards her,⁹ that is, \(u_j(A_j) \geq u_j(A_i \setminus \{g'_i\})\) for all agent \(j \in N\). Let \(M'\) be the set of all such goods \(g'_i\) belonging to any agent \(i\) who is envied by another agent—if there are multiple such goods \(g'_i\) for some agent \(i\), we only include one of them in \(M'\). Note that \(|M'| \leq n-1\), since at least one agent is unenvied in \(\mathcal{A}\) due to the final envy cycle elimination step. Furthermore, for any agents \(i, j \in N\), we have \(u_i(A_i) \geq u_i(A_j \setminus M')\). Hence, for any agent \(i \in N\), we have \[\begin{align} u_i(M \setminus M') &= u_i\left(\left(\bigcup_{j \in N} A_j\right) \setminus M'\right) \\ &= u_i\left(\bigcup_{j \in N} \left(A_j \setminus M'\right)\right) \\ &\leq \sum_{j \in N} u_i(A_j \setminus M') \\ &\leq n\cdot u_i(A_i). \end{align}\]

Consider the agent with the highest utility in allocation \(\mathcal{A}\), namely, agent \(1\). Note that some agent is allocated a good of utility \(v\) in the first round, and her utility never decreases throughout the execution of the ECE algorithm. Furthermore, by the proof of 1, at least one agent receives a utility of at least \(1/n\). Since agent \(1\) has the highest utility among all agents, we have \(u_1(A_1) \geq \max\{1/n, v\}\).

We can now find an upper bound for the maximum utilitarian welfare. Let \(\mathcal{A}^* = (A^*_1, \dots, A^*_n)\) be an allocation maximizing the utilitarian welfare. Then, the maximum utilitarian welfare, denoted by \(\mathrm{MUW}\), is \[\begin{align} &\mathrm{MUW}= \sum_{i \in N} u_i(A^*_i) \\ &\quad\leq \sum_{i \in N} u_i(A^*_i \cap M') + \sum_{i \in N} u_i(A^*_i \setminus M') \\ &\quad\leq |M'|v + \sum_{i \in N} u_i(M \setminus M') \\ &\quad\leq (n-1)v + u_1(M \setminus M') + \sum_{i \in N \setminus \{1\}} u_i(M \setminus M')\\ &\quad\leq (n-1)v + 1 + \sum_{i \in N \setminus \{1\}} n\cdot u_i(A_i) } \\ &\quad= (n-1)v + 1 - n\cdot u_1(A_1) + \sum_{i \in N} n\cdot u_i(A_i) \\ &\quad\leq (n-1)v + 1 - \max\{1, nv\} + \sum_{i \in N} n\cdot u_i(A_i) } \\ &\quad= n\cdot\sum_{i \in N} u_i(A_i) + \min\{(n-1)v, 1-v\} \\ &\quad= n\cdot \mathrm{UW}+ \min\{(n-1)v, 1-v\}, \end{align}\] where \(\mathrm{UW}= \sum_{i \in N} u_i(A_i)\) is the utilitarian welfare of the allocation \(\mathcal{A}\). Since this holds for any allocation that can be output by the specified heuristic, the strong utilitarian price of this heuristic for the given instance is at most \[\label{eq:first95round95only95muw95ub} \frac{\mathrm{MUW}}{\mathrm{UW}} \leq n + \frac{\min\{(n-1)v, 1-v\}}{\mathrm{UW}}.\tag{1}\]

Next, we derive an implicit lower bound on the utilitarian welfare \(\mathrm{UW}\) of the allocation \(\mathcal{A}\), by finding a lower bound on the utility of each agent, \(u_i(A_i)\) for \(i \in N\). To this end, we use the fact that the envy graph of this allocation is acyclic, as ensured by the last envy cycle elimination step of the ECE algorithm. Hence, the envy graph admits a topological ordering \(\pi(n), \pi(n-1), \dots, \pi(1)\), where \(\pi\) is a permutation of \(N\) and for any \(i, j \in N\) with \(i < j\), agent \(\pi(i)\) does not envy agent \(\pi(j)\). Then, for any \(i, j \in N\) with \(i \leq j\), we have \(u_{\pi(i)}(A_{\pi(i)}) \geq u_{\pi(i)}(A_{\pi(j)})\). Furthermore, for the remaining pairs \(i, j \in N\) where \(i > j\), agent \(\pi(i)\) is EF1 towards agent \(\pi(j)\), so \(u_{\pi(i)}(A_{\pi(i)}) \geq u_{\pi(i)}(A_{\pi(j)} \setminus \{g\})\) for some good \(g \in M\). On the other hand, it holds that \(u_{\pi(i)}(g) \leq v\) by definition of \(v\). Therefore, we have \(u_{\pi(i)}(A_{\pi(i)}) \geq u_{\pi(i)}(A_{\pi(j)} \setminus \{g\}) \geq u_{\pi(i)}(A_{\pi(j)}) - v\). It follows that for any \(i \in N\), \[\begin{align} 1 &= u_{\pi(i)}\left(\bigcup_{j=1}^n A_{\pi(j)}\right)\\ &\leq \sum_{j=1}^n u_{\pi(i)}(A_{\pi(j)}) \\ &= \sum_{j=1}^{i-1} u_{\pi(i)}(A_{\pi(j)}) + \sum_{j=i}^n u_{\pi(i)}(A_{\pi(j)}) \\ &\leq \sum_{j=1}^{i-1} \left(u_{\pi(i)}(A_{\pi(i)}) + v\right) + \sum_{j=i}^n u_{\pi(i)}(A_{\pi(i)}) \\ &= n\cdot u_{\pi(i)}(A_{\pi(i)}) + (i-1)v. \end{align}\] Equivalently, \(u_{\pi(i)}(A_{\pi(i)}) \geq (1-(i-1)v)/n\) for each \(i \in N\). Note that for each \(i, j \in N\) with \(i \geq j\), it holds that \((1-(i-1)v)/n \leq (1-(j-1)v)/n\). Furthermore, for each \(i \in N\), there exist \(i\) indices \(j\) such that \(i \geq j\) and thus \(u_{\pi(j)}(A_{\pi(j)}) \geq (1-(i-1)v)/n\). Hence, for each \(i \in N\), there are at least \(i\) agents with utility at least \((1-(i-1)v)/n\). Then, by the assumption that \(u_1(A_1) \geq \dots \geq u_n(A_n)\), it follows that for each \(i \in N\), \[\label{eq:first95round95only95agent95utility95lb} u_i(A_i) \geq \frac{1-(i-1)v}{n}.\tag{2}\]

We can now derive the required upper bound on the strong utilitarian price for the given instance. We first consider the case where \(v \leq 1/n\). From 2 , we have \[\begin{align} \mathrm{UW}= \sum_{i=1}^n u_i(A_i) \geq \sum_{i=1}^{n} \frac{1-(i-1)v}{n} &= 1 - \frac{(n-1)v}{2}. \end{align}\] Then, from 1 , the strong utilitarian price for the given instance is \[\begin{align} \frac{\mathrm{MUW}}{\mathrm{UW}} &\leq n + \frac{\min\{(n-1)v, 1-v\}}{\mathrm{UW}} \\ &\leq n + \frac{(n-1)v}{1 - (n-1)v/2}\\ &= n + \frac{2(n-1)}{2/v-(n-1)} \\ &\leq n + \frac{2n-2}{2n-n+1}\\ &= n + \frac{2n-2}{n+1}. \end{align}\] On the other hand, note that when \(x = 1/n\), \[\begin{align} \frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}} &= \frac{1-\frac{1}{n}}{\frac{1}{n} + \sum_{i=2}^{n} \frac{1-(i-1)/n}{n}} \\ &= \frac{n-1}{1 + (n-1) - (n-1)/2} \\ &= \frac{2n-2}{n+1}. \end{align}\] Therefore, we have \[\begin{align} \frac{\mathrm{MUW}}{\mathrm{UW}} \leq n + \max_{x \in [1/n, 1]} \left(\frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}}\right), \end{align}\] which gives the required upper bound on the strong utilitarian price for the specified instance when \(v \leq 1/n\).

We turn our attention to the remaining case where \(v > 1/n\). In this case, \(1/v < n\), so \(\lceil 1/v \rceil \leq n\). Then, we have \[\begin{align} \mathrm{UW}= \sum_{i=1}^n u_i(A_i) \geq \sum_{i=1}^{\lceil 1/v \rceil} u_i(A_i) &\geq v + \sum_{i=2}^{\lceil 1/v \rceil} \frac{1-(i-1)v}{n}. \end{align}\] Here, the first inequality holds since \(\lceil 1/v \rceil \leq n\). Moreover, the last inequality follows from 2 and \({u_1(A_1) \geq v}\), which holds by the assumptions that agent \(1\) has the maximum utility and that some agent is allocated a good of utility \(v\) in the first round. Subsequently, 1 implies that the strong utilitarian price of the specified heuristic for the given instance is at most \[\begin{align} \frac{\mathrm{MUW}}{\mathrm{UW}} \leq n + \frac{\min\{(n-1)v, 1-v\}}{\mathrm{UW}} &= n + \frac{1-v}{v + \sum_{i=2}^{\lceil 1/v \rceil} \frac{1-(i-1)v}{n}}\\ &\leq n + \max_{x \in [1/n, 1]} \left(\frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}}\right). \end{align}\] For the last inequality, note that \(v > 1/n\) by the case assumption and \(v = \max_{i \in N,\, g \in M} u_i(g) \leq 1\) since the instance is normalized. This completes our proof for the upper bound on the strong utilitarian price for the specified heuristic.

Next, we prove the lower bound of the strong utilitarian price. To this end, we show that for any \(n \geq 2\) and \(x \in [1/n, 1]\), there exists an instance with \(n\) agents such that the strong utilitarian price for the given instance is exactly \[n + \frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}}.\] This implies that the upper bound proven earlier is tight.

Let \(n \geq 2\), \(x \in [1/n, 1]\), \(t = \lceil 1/x \rceil\), and \(\delta = 1 - (t - 1)x\). Note that \(t \leq n\) and \(0 \leq \delta \leq x\). We construct an instance with \(n\) agents, \(m = tn + n - 1\) goods, and the following utilities: Each of the goods \(g_1, \dots, g_{tn}\) is valued positively by at most one agent.

• For each \(i \in \{1, \dots, t\}\), every agent \(j \neq i\) values the goods \(g_{(i-1)n+1}, \dots, g_{in}\) at \(0\).

• For each \(i \in \{2, \dots, t\}\), agent \(i\) values each of the goods \(g_{(i-1)n+1}, \dots, g_{in}\) at \((1-(i-1)x)/n\).

• Agent \(1\) values each of the goods \(g_{1}, \dots, g_{t-1}\) at \(x\) and good \(g_t\) at \(\delta\).

For the remaining \(n-1\) goods, the utilities are as follows:

• Agent \(1\) values goods \(g_{tn+1}, \dots, g_m\) at \(0\).

• For each \(i \in \{2, \dots, t\}\), agent \(i\) values each of the goods \(g_{tn+1}, \dots, g_{tn+i-1}\) at \(x\) and the remaining goods at \(0\).

• For each \(i \in \{t+1, \dots, n\}\), agent \(i\) values good \(g_{tn+1}\) at \(\delta\), values each of the goods \(g_{tn+i-(t-1)}, \dots,\linebreak[1] g_{tn+i-1}\) at \(x\), and values the remaining goods at \(0\).

Observe that \(\max_{i \in N,\, g \in M} u_i(g) = x\).

We consider the following allocation obtained with the ECE algorithm using the heuristic where in the first round, a good \(g \in M\) is allocated to an agent \(i \in N\) such that \(u_i(g)\) is maximized. In the first round, good \(g_1\) is allocated to agent \(1\) who values it at \(x\). Then, in round \(r \in \{2, \dots, n\}\), good \(g_r\) is allocated to agent \(r\). This creates no envy, since agent \(1\) values each of the goods \(g_1, \dots, g_n\) no more than \(x\), and each agent \(i \in N \setminus \{1\}\) values goods \(g_1, \dots, g_n\) at \(0\).

We turn our attention to rounds \({(i-1)n} + 1\) to \(in\) for each \(i \in \{2, \dots, t\}\). In round \(r = (i-1)n+1\), good \(g_r\) is allocated to agent \(i\) who values it at \((1-(i-1)x)/n\). Then, in rounds \((i-1)n+2, \dots, in\), goods \(g_{(i-1)n+2}, \dots, g_{in}\) are allocated to agents in \(N \setminus \{i\}\) in such a way that each of these \(n-1\) agents receives exactly one of these \(n-1\) goods. Again, this creates no envy, since agent \(i\) is the only agent who values any of the goods \(g_{(i-1)n+1}, \dots, g_{in}\) positively, and she is the first agent to receive any of these goods. Hence, there is no envy between any two agents at the end of round \(t n\).

Next, in each round \(r \in \{t n + 1,\linebreak[1] \dots, t n + n - 1\}\), good \(g_r\) is allocated to agent \(r - t n\). While this introduces some envy between agents, we show that there is no envy cycle at any point. To this end, observe that for each agent \(i \in N\), it holds that \(u_i(g_j) = 0\) whenever \(j \geq t n + i\). Since there is no envy at the end of round \(t n\), and afterwards each agent \(k \in N \setminus \{n\}\) only receives the good \(g_{t n + k}\), agent \(k\) is not envied by any agent \(i \leq k\). It follows that there is no envy cycle in the last \(n-1\) rounds of the ECE algorithm as well.

We now compute the utilitarian welfare of this allocation. Agent \(1\) receives a utility of \(x\) and each agent \(i \in \{2, \dots, t\}\) receives a utility of \((1-(i-1)x)/n\). Any other agent receives a utility of \(0\). Hence, the utilitarian welfare is exactly \[\label{eq:first95round95only95lb95uw} \mathrm{UW}= x + \sum_{i=2}^{t} \frac{1-(i-1)x}{n} = x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}.\tag{3}\]

On the other hand, the maximum utilitarian welfare is obtained when each agent \(i \in \{1, \dots, t\}\) receives the good \(g_j\) for each \(j \in \{(i-1)n + 1, \dots, in\}\), and each good \(g_j\) with \(j \in \{t n + 1, \dots, t n + n - 1\}\) is allocated to agent \(j - t n + 1\). Then, agent \(1\) receives a utility of \(1\), each agent \(i \in \{2, \dots, t\}\) receives a utility of \(1 - (i-2)x\), and each agent \(i \in \{t + 1, \dots, n\}\) receives a utility of \(x\). Hence, the maximum utilitarian welfare is \[\begin{align} \mathrm{MUW}&= 1 + \sum_{i=2}^{t} (1-(i-2)x) + (n-t)x \\ &= 1 + \sum_{i=2}^{t} (1-(i-1)x) + (n-1)x \\ &= 1 + n \cdot \sum_{i=2}^{t} \frac{1-(i-1)x}{n} + (n-1)x \\ &= 1 + n \cdot \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n} + (n-1)x \\ &= 1 + n\cdot\mathrm{UW}- nx + (n-1)x } \\ &= 1 + n\cdot\mathrm{UW}- x. \end{align}\]

Therefore, the strong utilitarian price of this instance is \[\begin{align} \frac{\mathrm{MUW}}{\mathrm{UW}} &= n + \frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}}, \end{align}\] completing the proof. ◻

Proof. For each integer \(t \in \{1, \dots, n\}\) and real number \(x \in [1/n, 1]\), we define \[\varphi(t, x) = \frac{1-x}{x + \sum_{i=2}^t \frac{1-(i-1)x}{n}}.\] Then, \(f(x) = \varphi(\lceil 1/x \rceil, x)\).

Since \(f\) itself is not easily differentiable, we shall determine the slope of \(f\) using the partial derivative of \(\varphi\) with respect to \(x\): \[\require{physics} \begin{align} \pdv{\varphi(t, x)}{x} &= \pdv{x} \left(\frac{1-x}{x + \sum_{i=2}^t \frac{1-(i-1)x}{n}}\right) \\ &= \pdv{x} \left(\frac{1-x}{\frac{t-1}{n} + \left(1 - \frac{(t-1)t}{2n}\right)x}\right)\\ &= \pdv{x} \left(\frac{2n(1-x)}{2t - 2 + \left(2n + t - t^2\right)x}\right) \\ &= 2n \left(-\frac{1}{2t - 2 + \left(2n + t - t^2\right)x} - \frac{(2n + t - t^2)(1-x)}{\big(2t - 2 + (2n + t - t^2)x\big)^2} \right) \\ &= \frac{2n(t^2-3t-2n+2)}{\big(2t - 2 + (2n + t - t^2)x\big)^2} \\ &= \frac{2n(t^2-3t-2n+2)}{\big(2nx + (t-1)(2-tx)\big)^2}. \end{align}\] Note that \(2n > 0\). Furthermore, for any \(t \in \{2, \dots, n\}\) and \(x \in [1/t, 1/(t-1)]\), we have \(2nx + (t-1)(2-tx) > 2-tx \geq 2-t/(t-1) \geq 0\), which gives \((2nx + (t-1)(2-tx))^2 > 0\). Solving the quadratic equation \(t^2-3t-2n+2 = 0\) gives exactly one positive root \(t = (3+\sqrt{8n+1})/2\) and one negative root \(t = (3-\sqrt{8n+1})/2\). Let \(\alpha = (3+\sqrt{8n+1})/2\) be the positive root. We can conclude that for any \(t \in \{2, \dots, n\}\) and \(x \in [1/t, 1/(t-1)]\):

• \(\pdv*{\varphi(t, x)}{x} > 0\) if \(t > \alpha\),

• \(\pdv*{\varphi(t, x)}{x} = 0\) if \(t = \alpha\), and

• \(\pdv*{\varphi(t, x)}{x} < 0\) if \(t < \alpha\).

We explain how the slope of \(\varphi\) translates to the slope of \(f\). Note that for any \(t \in \{2, \dots, n\}\) and \(x \in [1/t, 1/(t-1))\), we have \(t = \lceil 1/x\rceil\), and therefore \(f(x) = \varphi(t, x)\). Hence, for any \(t \in \{2, \dots, n\}\) and \(x \in (1/t, 1/(t-1))\), we have \(f'(x) = \pdv*{\varphi(t, x)}{x}\). Furthermore, \(f\) is continuous from the right at \(x \in \{1/n, 1/(n-1),\linebreak[1] \dots, 1/2\}\). For each \(t \in \{1, \dots, n-1\}\), the following calculation shows that \(f\) is continuous from the left at \(1/t\): \[\begin{align} \lim_{x \to (1/t)^-} f(x) &= \lim_{x \to (1/t)^-} \varphi(t+1, x)\\ &= \varphi\left(t+1, \frac{1}{t}\right) \\ &= \frac{1-\frac{1}{t}}{\frac{1}{t} + \sum_{i=2}^{t+1} \frac{1-(i-1)/t}{n}} \\ &= \frac{1-\frac{1}{t}}{\frac{1}{t} + \sum_{i=2}^{t} \frac{1-(i-1)/t}{n}}\\ &= \varphi\left(t, \frac{1}{t}\right) \\ &= f\left(\frac{1}{t}\right). \end{align}\] Combined with the earlier observations, we have shown that \(f\) is continuous on \([1/n, 1]\).

Now, let \(\beta = (1+\sqrt{8n+1})/2\linebreak[1] = \alpha - 1\). We show that \(f\) is non-decreasing at \(x\) if \(x < 1/\lceil \beta \rceil\) and is strictly decreasing at \(x\) if \(x > 1/\lceil \beta \rceil\). Let \(x \in (1/n, 1)\) be such that \(x < 1/\lceil \beta \rceil\). Then, \(\lceil 1/x \rceil \geq 1/x > \lceil \beta \rceil\), so \(\lceil 1/x \rceil \geq \lceil \beta \rceil + 1 = \lceil \alpha \rceil \geq \alpha\). If \(x \not\in \{1/(n-1), 1/{(n-2)},\linebreak[1] \dots, 1/2\}\), then clearly \(f\) is non-decreasing at \(x\) since \(f'(x) = \pdv*{\varphi(\lceil 1/x \rceil, x)}{x} \geq 0\). Otherwise, let \(x = 1/t\) where \(t \in \{2, \dots, n-1\}\). Since \(t \geq \alpha\), \[\begin{align} \lim_{z \to (1/t)^+} f'(z) = \lim_{z \to (1/t)^+} \pdv*{\varphi(t, z)}{z} \geq 0, \end{align}\] and since \(t+1 > \alpha\), \[\begin{align} \lim_{z \to (1/t)^-} f'(z) = \lim_{z \to (1/t)^-} \pdv*{\varphi(t+1, z)}{z} \geq 0. \end{align}\] Hence, \(f\) is non-decreasing at \(x\) in this case.

On the other hand, let \(x \in (1/n, 1)\) be such that \(x > 1/\lceil \beta \rceil\). In this case, \(1/x < \lceil \beta \rceil\), and so \(\lceil 1/x \rceil \leq \lceil \beta \rceil < \beta + 1 = \alpha\). If \(x \not\in \{1/(n-1), 1/(n-2),\linebreak[1] \dots, 1/2\}\), then \(f\) is strictly decreasing at \(x\) since \(f'(x) = \pdv*{\varphi(\lceil 1/x \rceil, x)}{x} < 0\). Otherwise, suppose that \(x = 1/t\) where \(t \in \{2, \dots, n-1\}\). Since \(t < \alpha\), \[\begin{align} \lim_{z \to (1/t)^+} f'(z) = \lim_{z \to (1/t)^+} \pdv*{\varphi(t, z)}{z} < 0. \end{align}\] Furthermore, since \(t = 1/x < \lceil \beta \rceil\) and \(t\) is an integer, we have \(t + 1 \leq \lceil \beta \rceil < \alpha\). Then, \[\begin{align} \lim_{z \to (1/t)^-} f'(z) = \lim_{z \to (1/t)^-} \pdv*{\varphi(t+1, z)}{z} < 0. \end{align}\] Thus, \(f\) is strictly decreasing at \(x\) in this case.

We now observe that \(\lceil \beta \rceil = \lceil \sqrt{2n} + 1/2 \rceil\) for all integers \(n \geq 2\). To see this, first note that \(\beta > (\sqrt{8n}+1)/2 = \sqrt{2n} + 1/2\). Hence, \(\lceil \beta \rceil \geq \lceil \sqrt{2n} + 1/2 \rceil\). To prove the inequality in the opposite direction, notice that \(\sqrt{2n} + 1/2\) is never an integer. Indeed, if \(\sqrt{2n} = k - 1/2\) for some integer \(k\), then \(2n = k^2 - k + 1/4\), contradicting the fact that \(2n\) must be an integer. Let \(t = \lceil \sqrt{2n} + 1/2 \rceil\). Then, \(t > \sqrt{2n} + 1/2 = (\sqrt{8n}+1)/2\), or equivalently, \((2t - 1)^2 > 8n\). Since \(t\) is an integer, so is \((2t - 1)^2\), and therefore \((2t - 1)^2 \geq 8n+1\). Hence, \(\lceil \sqrt{2n} + 1/2 \rceil = t \geq \beta\).

To complete the proof, observe that when \(n = 2\), we have \(\lceil \sqrt{2n} + 1/2 \rceil > n\), or equivalently, \(1/n > 1/\lceil \sqrt{2n} + 1/2 \rceil\). This means that \(f(x)\) is strictly decreasing on all \(x \in [1/n, 1]\). That is, the maximum of \(f\) is obtained at \(1/n = 1/2\) when \(n = 2\). On the other hand, if \(n \geq 3\), then \[\begin{align} \sqrt{2n} + \frac{1}{2} &\leq \sqrt{(n-1)n} + \frac{1}{2} \\ &= \sqrt{\left(\sqrt{n^2-n} + \frac{1}{2}\right)^2} \\ &= \sqrt{n^2 - n + \sqrt{n^2-n} + \frac{1}{4}} \\ &= \sqrt{n^2 + \sqrt{n^2-n} - \sqrt{\left(n - \frac{1}{4}\right)^2}} \\ &= \sqrt{n^2 + \sqrt{n^2-n} - \sqrt{n^2 - \frac{n}{2} +\frac{1}{16}}} \\ &< \sqrt{n^2} \\ &= n. \end{align}\] Hence, \(1/\lceil \sqrt{2n} + 1/2 \rceil \in [1/n, 1]\). It then follows from our earlier observations that \(1/\lceil \sqrt{2n} + 1/2 \rceil \in \mathop{\mathrm{arg\,max}}_x f\). ◻

Proof of [thm:agent95good95with95max95util95first95round95only]. The strong egalitarian price has been shown in 3. For the strong utilitarian price, the closed-form expression can be obtained from 4 5. Let \[f(x) = \frac{1-x}{x + \sum_{i=2}^{\lceil 1/x \rceil} \frac{1-(i-1)x}{n}}\] be defined for any \(x \in [1/n, 1]\).

If \(n = 2\), then the strong utilitarian price is \[\begin{align} 2 + f\left(\frac{1}{2}\right) = 2 + \frac{1-\frac{1}{2}}{\frac{1}{2} + \sum_{i=2}^{2} \frac{1-(i-1)/2}{2}} = 2 + \frac{\frac{1}{2}}{\frac{1}{2} + \frac{1}{4}} &= \frac{8}{3}, \end{align}\] proving [thm:agent95good95with95max95util95first95round95only](a).

Suppose now that \(n \geq 3\). Let \(s = \lceil \sqrt{2n} - 1/2 \rceil\) be defined as in [thm:agent95good95with95max95util95first95round95only](b). From 4 5, the strong utilitarian price is \[\begin{align} n + f\left(\frac{1}{s+1}\right) &= n + \frac{1-\frac{1}{s+1}}{\frac{1}{s+1} + \sum_{i=2}^{s+1} \frac{1-(i-1)/(s+1)}{n}} \\ &= n + \frac{ns}{n + s(s+1) - s(s+1)/2} \\ &= n + \frac{2ns}{2n + s(s+1)}, \end{align}\] as claimed in [thm:agent95good95with95max95util95first95round95only](b).

It remains to give the simplified approximation of the strong utilitarian price when \(n \geq 3\), that is, to prove that \[\label{eq:first95round95only95simplified} n + \sqrt{\frac{n}{2}} - \frac{1}{4} < n + f\left(\frac{1}{s+1}\right) < n + \sqrt{\frac{n}{2}} - \frac{1}{5}.\tag{4}\]

We start by proving the upper bound. Define \[h(t) = \frac{2nt}{2n + t(t+1)}\] for any \(t \in \mathbb{R}_{>0}\). Then, \(f(1/(s+1)) = h(s)\). We shall prove that \(h(s) \leq h(\sqrt{2n})\) using the derivative of \(h\): \[\begin{align} h'(t) = \frac{2n(2n+t+t^2)-2nt(1+2t)}{(2n+t+t^2)^2} &= \frac{2n(2n-t^2)}{(2n+t+t^2)^2}. \end{align}\] Note that for any \(t \in \mathbb{R}_{>0}\), we have both \(2n > 0\) and \((2n+t+t^2)^2 > 0\), and \(2n-t^2 \geq 0\) holds if and only if \(t \leq \sqrt{2n}\). Hence, the maximum of \(h\) is achieved at \(t = \sqrt{2n}\), and therefore \(h(s) \leq h(\sqrt{2n})\). That is, \[\begin{align} f\left(\frac{1}{s+1}\right) = h(s) \leq h\left(\sqrt{2n}\right) &= \frac{2n\sqrt{2n}}{4n +\sqrt{2n}}. \end{align}\] Let \(y = \sqrt{2n}\). Then, we have \[\begin{align} \frac{2n\sqrt{2n}}{4n +\sqrt{2n}} = \frac{y^3}{2y^2 + y} &= \frac{y}{2} - \frac{1}{4} + \frac{1}{4(2y + 1)} \\ &= \sqrt{\frac{n}{2}} - \frac{1}{4} + \frac{1}{4(2\sqrt{2n} + 1)} \\ &< \sqrt{\frac{n}{2}} - \frac{1}{4} + \frac{1}{20}\\ &= \sqrt{\frac{n}{2}} - \frac{1}{5}. \end{align}\] Hence, \(f(1/(s+1)) < \sqrt{n/2} - 1/5\).

We next prove the lower bound of 4 . Let \(v = 1/(\sqrt{2n} + 1/2)\). Recall from the proof of 5 that \(\sqrt{2n} + 1/2\) is never an integer, that is, \(\sqrt{2n} + 1/2 < \lceil \sqrt{2n} + 1/2 \rceil = s+1\). This means that \(v > 1/(s+1) \geq 1/n\), where the last inequality holds since \(n\ge 3\). Furthermore, we have shown in the proof of 5 that \(f\) is strictly decreasing at any \(x \in [1/n, 1]\) with \(x > 1/(s+1) = 1/\lceil\beta\rceil\). Hence, \(f(1/(s+1)) > f(v)\). Therefore, it suffices to show that \(f(v) \geq \sqrt{n/2} - 1/4\). We have \[\begin{align} f(v) &= \frac{1-v}{v + \sum_{i=2}^{\lceil 1/v \rceil} \frac{1-(i-1)v}{n}} \\ &= \frac{1-v}{v + \frac{\lceil 1/v \rceil - 1}{n} - \frac{(\lceil 1/v \rceil - 1)\lceil 1/v \rceil v}{2n}} \\ &= \frac{2n(1-v)}{2nv + 2s - s(s+1)v}\\ &= \frac{2n(1-v)}{-v(s^2 + (1-2/v)s - 2n)} \\ &= \frac{2n(1-v)}{-v[(s + (v-2)/(2v))^2 - ((v-2)/(2v))^2 - 2n]} \\ &\geq \frac{2n(1-v)}{-v[-((v-2)/(2v))^2-2n]}\\ &= \frac{8n(1/v-1)}{(1-2/v)^2+8n}. \end{align}\] Let \(z = \sqrt{8n} = 2\sqrt{2n}\). Then, \(v = 1/(\sqrt{2n} + 1/2) = 2/(z+1)\). It follows that \[\begin{align} f(v) \geq \frac{z^2((z+1)/2 - 1)}{(1-(z+1))^2+z^2} = \frac{z^2(z-1)}{4z^2} &= \sqrt{\frac{n}{2}} - \frac{1}{4}. \end{align}\] Therefore, \(f(1/(s+1)) > \sqrt{n/2} - 1/4\), as desired. ◻

Proof. We begin by addressing the strong utilitarian price ([thm:agent95good95with95max95util](a)). The upper bound follows from the strong utilitarian price of the ECE algorithm using the heuristic that chooses an unenvied agent and an available good in the first round ([thm:agent95good95with95max95util95first95round95only](a) and (b)), since the set of allocations produced by the heuristic that chooses a pair of unenvied agent and available good maximizing the utility in every round is a subset of those obtained with the heuristic choosing such a pair in the first round.

For the lower bound, we construct an instance with \(n\) agents and \(m = x^n\) goods, where \(x\) is a positive integer divisible by \(n\). Let \(0 < \epsilon < 1/x^n\). The agents’ utilities are defined as follows:

• For each \(i \in N \setminus \{n\}\), \(u_i(g_j) = (1-\epsilon)/x^i\) if \(j \leq x^i\) and \(u_i(g_j) = \epsilon/(x^n-x^i)\) otherwise.

• \(u_n(g_j) = 1/x^n\) for each \(j\).

We consider the allocation obtained by the ECE algorithm with the heuristic choosing a pair of unenvied agent and available good maximizing the utility in every round. We assume that ties are broken by choosing an agent and a good with the lowest indices. Observe that the goods \(g_1, \dots, g_m\) are sorted in non-increasing order of utility for every agent. Therefore, the goods must be allocated in the order \(g_1, \dots, g_m\) to some unenvied agent who values it most.

In order to determine the utilitarian welfare of the resulting allocation, we show by induction that for each \(t \in \{0, \dots, m/n-1\}\), each agent must receive exactly one of goods \(g_{tn+1}, \dots, g_{tn+n}\). This is obvious for the first \(n\) rounds, since any agent with a non-empty bundle must be envied by another agent with an empty bundle. Hence, the ECE algorithm will allocate the first \(n\) goods to \(n\) distinct agents. We next establish the inductive step. Let \(t \in \{1, \dots, m/n-1\}\). Assume, as the inductive hypothesis, that for each \(t' \in \{0, \dots, t-1\}\), each agent receives exactly one of goods \(g_{t'n+1}, \dots, g_{t'n+n}\). Note that for every \(t'' \in \{0, \dots, m/n-1\}\) and each agent \(i \in N\), all of the goods \(g_{t''n+1}, \dots, g_{t''n+n}\) have the same utility to agent \(i\). Hence, the inductive hypothesis implies that in the partial allocation obtained after round \(tn\), each agent \(i \in N\) values all the agents’ bundles equally. Subsequently, any agent who has received a good in some round \(r \in \{tn+1, \dots, tn+n\}\) must be envied by another agent who has not received a good since the beginning of round \(tn+1\). Therefore, the ECE algorithm allocates the goods \(g_{tn+1}, \dots, g_{tn+n}\) to \(n\) distinct agents, completing the induction. This implies that at the end of \(m\) rounds, each agent values all the agents’ bundles equally, receiving a utility of exactly \(1/n\). It follows that the utilitarian welfare of this allocation is \(1\).

On the other hand, suppose that the first \(x\) goods are allocated to agent \(1\), and each agent \(i \in N \setminus \{1\}\) receives the goods \(g_{x^{i-1} + 1}, \dots, g_{x^i}\). Then, agent \(1\) receives a utility of \(1-\epsilon\), each agent \(i \in N \setminus \{1, n\}\) receives a utility of \((1-\epsilon)(1 - 1/x) = 1 - \epsilon - (1-\epsilon)/x\), and agent \(n\) receives a utility of \(1-1/x \geq 1 - \epsilon - (1-\epsilon)/x\). Hence, the maximum utilitarian welfare is at least \(n(1-\epsilon) - (n-1)(1-\epsilon)/x\).

Therefore, the strong utilitarian price of this instance is at least \(n(1-\epsilon) - (n-1)(1-\epsilon)/x\), which approaches \(n\) as \(\epsilon \rightarrow 0\) and \(x \rightarrow \infty\).

We next derive the lower and upper bounds for the strong egalitarian price when \(n = 2\) ([thm:agent95good95with95max95util](b)). For the lower bound, consider an instance with \(m \geq 3\) goods and the following utilities:

• \(u_1(g_j) = 1/2\) if \(j \leq 2\) and \(u_1(g_j) = 0\) otherwise.

• \(u_2(g_j) = 1/m\) for all \(j\).

Consider the allocation obtained by the ECE algorithm with the heuristic that chooses a pair of unenvied agent and unallocated good maximizing the utility in every round. We assume that ties are broken by choosing the agent and good with the lowest indices. Then, in the first round, \(g_1\) is allocated to agent \(1\). This causes agent \(2\) to envy agent \(1\), so in the second round, \(g_2\) is allocated to agent \(2\). At this point, agent \(1\) values each of the two bundles exactly \(1/2\). Note that while new goods may be added to the bundles and the bundles may be swapped later, the ECE algorithm cannot take a good from one bundle and move it to the other bundle. Since goods \(g_1\) and \(g_2\) are placed in different bundles in round \(2\), in the final allocation, agent \(1\)’s bundle can contain only one of \(g_1\) and \(g_2\). Hence, agent \(1\)’s utility, and therefore the egalitarian welfare, is at most \(1/2\).

Now, consider instead the allocation where agent \(1\) gets both goods \(g_1\) and \(g_2\), while the remaining goods are allocated to agent \(2\). Then, agent \(1\) gets a utility of \(1\) and agent \(2\) gets a utility of \(1-2/m\). The egalitarian welfare of this allocation is \(1-2/m\). Therefore, the strong egalitarian price of this instance is at least \((1-2/m)/(1/2)\), which approaches \(2\) as \(m\rightarrow \infty\).

We next prove that the strong egalitarian price when \(n = 2\) is at most \(3\). If \(m = 1\), every allocation has an egalitarian welfare of \(0\), so the strong egalitarian price is \(1\). Take any instance with \(n = 2\) agents and \(m \geq 2\) goods, and let \((A_1, A_2)\) be an allocation obtained with the ECE algorithm using the heuristic that chooses a pair of unenvied agent and unallocated good maximizing the utility in every round. Consider an agent with the minimum utility between the two agents; without loss of generality, assume that this is agent \(2\). Then, the egalitarian welfare of the allocation \((A_1, A_2)\) is the utility of agent \(2\).

If agent \(2\) does not envy agent \(1\), then \(1 \leq u_2(A_1) + u_2(A_2) \leq 2u_2(A_2)\), so \(u_2(A_2) \geq 1/2\). Since the maximum egalitarian welfare is at most \(1\), the egalitarian welfare in this case is at least \(1/2\) times the maximum. From now on, assume that agent \(2\) envies agent \(1\).

Let \(g\) be the last good added to the bundle \(A_1\). Since agent \(2\) envies agent \(1\), good \(g\) must be allocated to agent \(1\) and there are no bundle exchanges afterward. On the other hand, agent \(2\) must not envy agent \(1\) immediately before good \(g\) is allocated. Since agent \(2\)’s utility never decreases, \(u_2(A_2) \geq u_2(A_1 \setminus \{g\})\).

We consider two cases. First, suppose that \(u_1(g) \geq u_2(g)\). Observe that in any allocation, the utility of the agent who is not allocated good \(g\) is at most¹⁰ \(1-u_2(g)\). Hence, the maximum egalitarian welfare is at most \(1-u_2(g)\). This means that \(1-u_2(g) \leq u_2(M \setminus \{g\}) \leq u_2(A_1 \setminus \{g\}) + u_2(A_2) \leq 2u_2(A_2)\). Therefore, agent \(2\)’s utility is at least \(1/2\) times the maximum egalitarian welfare.

On the other hand, suppose that \(u_1(g) < u_2(g)\). Since good \(g\) is allocated to agent \(1\), according to the ECE heuristic used, agent \(2\) must be envied by agent \(1\) immediately before good \(g\) is allocated. In particular, agent \(2\) must own a non-empty bundle at this point. Note that empty bundles are not involved in bundle exchanges. Hence, the heuristic must have allocated some good \(g'\) to agent \(2\) prior to the round when good \(g\) is allocated to agent \(1\); by definition of the heuristic, \(u_2(g') \geq u_2(g)\). Furthermore, since the ECE algorithm never decreases agent \(2\)’s utility, we have \(u_2(A_2) \geq u_2(g') \geq u_2(g)\). Therefore, \(1 \leq u_2(g) + u_2(A_1 \setminus \{g\}) + u_2(A_2) \leq 3u_2(A_2)\). Equivalently, \(u_2(A_2) \geq 1/3\). Since the maximum egalitarian welfare is at most \(1\), it follows that agent \(2\)’s utility is at least \(1/3\) times the maximum egalitarian welfare. Hence, we have shown that in each case, the egalitarian welfare of the allocation—which is equal to agent \(2\)’s utility—is at least \(1/3\) times the maximum egalitarian welfare.

Lastly, we determine the strong egalitarian price when \(n \geq 3\) ([thm:agent95good95with95max95util](c)). Consider an instance with \(n \geq 3\) agents, \(m = n\) goods, and the following utilities:

Consider the allocation produced by the ECE algorithm using the heuristic that chooses a pair of agent and good maximizing the utility in every round. Assume that ties are broken by choosing the agent and good with the lowest indices. For each \(i \in \{1, \dots, n-3\}\), the heuristic must choose to allocate good \(g_i\) to agent \(i\). Then, in the last three rounds, goods \(g_{n-2}, g_{n-1},\) and \(g_n\) are allocated to agents \(n-2, n-1,\) and \(n\) respectively. Note that only agent \(n\) envies another agent, so no envy cycle exists. Since agent \(n\) receives a utility of \(0\), the egalitarian welfare of this allocation is also \(0\).

On the other hand, consider the allocation where goods \(g_1, \dots, g_{n-3}\) are allocated to agents \(1, \dots, n-3\) respectively, and goods \(g_{n-2}, g_{n-1},\) and \(g_n\) are allocated to agents \(n-2, n,\) and \(n-1\) respectively. The egalitarian welfare of this allocation is \(1/3\). Hence, the strong egalitarian price of this instance is \((1/3)/0 = \infty\). ◻

Proof. Let \(\mathcal{A} = (A_1, \dots, A_n)\) be an allocation with maximum egalitarian welfare. If there is some agent \(i \in N\) such that \(A_i = \emptyset\), then the maximum egalitarian welfare is \(0\), which is at most \((m-n+1) \cdot \min_{i \in N} u_i(g'_i)\). We can now assume that \(A_i \neq \emptyset\) for any \(i \in N\). For each \(i \in N\), let \(g''_i\) be some good in \(A_i\) such that \(u_i(g''_i)\) is maximized. By the choice of \(g'_1, \dots, g'_n\), we have \(\min_{i \in N} u_i(g'_i) \geq \min_{i \in N} u_i(g''_i)\). Now fix agent \(k\) such that \(u_k(g''_k) = \min_{i \in N} u_i(g''_i)\). Observe that \[\begin{align} u_k(A_k) \leq \sum_{g \in A_k} u_k(g) \leq |A_k|\cdot u_k(g''_k) \leq (m-n+1) \cdot u_k(g''_k), \end{align}\] where the last inequality follows from the fact that \(|A_i| \geq 1\) for any \(i \in N \setminus \{k\}\), and so \(|A_k| \leq m-n+1\). Since \(u_k(A_k)\) is at least the egalitarian welfare of allocation \(\mathcal{A}\), and \(u_k(g''_k) = \min_{i \in N} u_i(g''_i)\) is at most \(\min_{i \in N} u_i(g'_i)\), it follows that the maximum egalitarian welfare of the given instance is at most \((m-n+1) \cdot \min_{i \in N} u_i(g'_i)\). ◻

Proof of [thm:max95min95matching]. We start by finding the strong egalitarian price. If \(m < n\), the strong egalitarian price is \(1\) since every allocation has egalitarian welfare \(0\). For the case where \(m \geq n\), the upper bound follows directly from [lem:max95min95matching] since the ECE algorithm never decreases the utility of any agent, and thus also the egalitarian welfare.

We next prove the lower bound. If \(m = n\), then \(m-n+1 = 1\) and the lower bound holds trivially. Assume henceforth that \(m > n\). Let \(k = m-n+1 \geq 2\) and \(0 < \epsilon < 1/4\). Consider the following instance with \(n\) agents and \(m\) goods:

• For each \(i \in N \setminus \{n-1, n\}\), \(u_i(g_i) = 1\).

• \(u_{n-1}(g_{n-1}) = 1-1/(2k)-\epsilon\) and \(u_{n-1}(g_n) = 1/(2k)+\epsilon\).

• \(u_n(g_{n-1}) = 1/2\), and \(u_n(g_j) = 1/(2k)\) for \(j \geq n\).

• \(u_i(g_j) = 0\) for all other pairs \((i, j)\).

The expression \(\min_{i \in N} u_i(g'_i)\) is maximized if and only if \(g'_i = g_i\) for each \(i \in N \setminus \{n-1, n\}\), \(g'_{n-1} = g_n\), and \(g'_n = g_{n-1}\). In this case, \(\min_{i \in N} u_i(g'_i) = u_{n-1}(g_n) = 1/(2k)+\epsilon\). Hence, the max-min matching heuristic allocates \(g'_i\) to agent \(i\) in each round \(i\in\{1,\dots,n\}\). In particular, agent \(n\) receives good \(g_{n-1}\) of utility \(1/2\). Since her utility never decreases throughout the execution of the ECE algorithm, agent \(n\) will never envy another agent after round \(n\). This means that agent \(n\)’s bundle will never be passed to a different agent, and good \(g_{n-1}\) will stay in agent \(n\)’s possession until the end of the algorithm. On the other hand, agent \((n-1)\)’s utility at the end of the algorithm is at most \(u_{n-1}(M \setminus \{g_{n-1}\}) = 1/(2k) + \epsilon\). It follows that any allocation of this instance produced by the ECE algorithm with the max-min matching heuristic has an egalitarian welfare of at most \(1/(2k)+\epsilon\).

Now, consider the allocation where each agent \(i \in N \setminus \{n\}\) receives good \(g_i\), while agent \(n\) receives goods \(g_n, \dots, g_m\). In this allocation, each agent \(i \in N \setminus \{n-1, n\}\) receives a utility of \(1\), agent \(n-1\) receives a utility of \(1-1/(2k)-\epsilon\), and agent \(n\) receives a total utility of \(k \cdot 1/(2k) = 1/2\). Since \(k \geq 2\) and \(\epsilon < 1/4\), we have \(1-1/(2k)-\epsilon > 1/2\). Hence, the egalitarian welfare of this allocation is \(1/2\).

Therefore, the strong egalitarian price of this instance is at least \((1/2)/(1/(2k)+\epsilon)\), which approaches \(k = m-n+1\) as \(\epsilon\) approaches \(0\). By the upper bound established earlier, it follows that the strong egalitarian price of the ECE algorithm with the max-min matching heuristic is exactly \(m-n+1\).

We continue by finding the strong utilitarian price. The upper bound follows from the strong utilitarian price of the vanilla ECE algorithm ([prop:strong95price]), since the set of allocations that can be obtained with any ECE heuristic is a subset of all allocations that can be produced by the ECE algorithm.

For the lower bound, consider an instance with \(n \geq 2\) agents, \(m = kn-1\) goods where \(k \geq 2\) is an integer, and the following utilities:

• \(u_1(g_j) = 1/m\) for all \(j\).

• For each \(i \in N \setminus \{1\}\), \(u_i(g_i) = 1/m\) and \(u_i(g_{(k-1)n+i-1}) = 1-1/m\).

• \(u_i(g_j) = 0\) for all other pairs \((i, j)\).

Consider the following allocation obtained by the max-min matching heuristic: In each round \(i \in \{1, \dots, n\}\), we allocate good \(g'_i = g_i\) to agent \(i\). Then, \(\min_{i \in N} u_i(g'_i) = 1/m\), which is the maximum egalitarian welfare for any partial allocation where each agent receives exactly one good, since \(u_1(g) = 1/m\) for any good \(g\). In the subsequent rounds, the goods are allocated in increasing order of their indices from \(g_{n+1}\) to \(g_m\) such that for each \(t \in \{1, \dots, k-1\}\) and \(i \in \{1, \dots, n\}\), good \(g_{tn+i}\) is given to agent \(i\) (except when \(t = k-1\) and \(i = n\), since \(g_{kn}\) does not exist).

In the first \((k-1)n\) rounds, the intermediate allocations remain envy-free. After round \((k-1)n+i\) for each \(i \in \{1, \dots, n-1\}\), agent \(i+1\) begins to envy agent \(i\), and continues to envy her until the end of the algorithm. Hence, the envy graph remains acyclic throughout. At the end, agent \(1\) gets a total utility of \(k/m\) and each of the remaining agents gets a total utility of \(1/m\). Therefore, the utilitarian welfare of this allocation is \((k+n-1)/m\).

On the other hand, consider the allocation where each agent \(i \in N \setminus \{1\}\) only gets the good \(g_{(k-1)n+i-1}\), and agent \(1\) gets the remaining goods \(g_1, \dots, g_{(k-1)n}\). In this case, agent \(1\) gets a total utility of \((k-1)n/m = 1-(n-1)/m\), while each of the remaining agents gets a total utility of \(1-1/m\). Hence, the utilitarian welfare of this allocation is \(n-(2n-2)/m\).

Therefore, the strong utilitarian price of this instance is at least \[\begin{align} \frac{n-\frac{2n-2}{m}}{\frac{k+n-1}{m}} &= \frac{nm-2n+2}{k+n-1} \\ &= \frac{n(kn-1)-2n+2}{k+n-1}\\ &= \frac{kn^2-3n+2}{k+n-1} \\ &= n^2 - \frac{n^3-n^2+3n-2}{k+n-1}, \end{align}\] which approaches \(n^2\) as \(k\rightarrow\infty\). ◻

Proof. Consider any instance with \(n \geq 2\) agents, \(m \geq 2\) goods, and the following utilities: Let \(0 < \epsilon < 1\). For each agent \(i \in N\), \[\begin{align} u_i(S) = \begin{cases} 1 &\text{if S = M,} \\ \epsilon &\text{if \emptyset \subsetneq S \subsetneq M, and} \\ 0 &\text{if S = \emptyset.} \end{cases} \end{align}\]

Now suppose that some agent \(i \in N\) has a utility of strictly more than \(\epsilon\). Then, she must be allocated the whole bundle of goods \(M\). This means that some agent \(j \in N\) owns an empty bundle. For any good \(g \in M\), we have \(u_j(A_i \setminus \{g\}) = \epsilon > 0 = u_j(A_j)\). In other words, agent \(j\) is not EF1 toward agent \(i\). By contraposition, it follows that in any EF1 allocation, every agent has a utility of at most \(\epsilon\). Therefore, the maximum utilitarian welfare of any EF1 allocation is \(n\epsilon\). Since it is possible to obtain a utilitarian welfare of \(1\) by allocating the entire bundle of goods \(M\) to a single agent, the weak utilitarian price of EF1 for this instance is at least \(1/(n\epsilon)\), which approaches \(\infty\) as \(\epsilon \to 0\). Furthermore, since any allocation obtained by the ECE algorithm is necessarily EF1 under monotone utilities, the weak utilitarian price of ECE is also \(\infty\). ◻

Proof. Consider any instance with \(n \geq 2\) agents, \(m = n+2\) goods, and the following utilities:

• \(u_1(S) = |S \cap \{g_1, g_2, g_3, g_4\}|/4\).

• \(u_2(S) = 1\) if \(|S \cap \{g_1, g_2, g_3, g_4\}| \geq 3\), and \(u_2(S) = 0\) otherwise.

• For each agent \(i \in N \setminus \{1, 2\}\), \(u_i(S) = 1\) if \(g_{i+2} \in S\), and \(u_i(S) = 0\) otherwise.

Let \(\mathcal{A} = (A_1, \dots, A_n)\) be an allocation with positive egalitarian welfare. In particular, \(u_2(A_2) > 0\), which means that \(|A_2 \cap \{g_1, g_2, g_3, g_4\}| \geq 3\). This implies that \(|A_1 \cap \{g_1, g_2, g_3, g_4\}| \leq 4-3 = 1\), and for any \(g \in A_2\), it holds that \(|(A_2 \setminus \{g\}) \cap \{g_1, g_2, g_3, g_4\}| \geq 3-1 = 2\). Consequently, we have \(u_1(A_1) \leq 1/4\), whereas \(u_1(A_2 \setminus \{g\}) \geq 2/4\) for any \(g \in A_2\). Therefore, agent \(1\) is not EF1 towards agent \(2\). It follows that any EF1 allocation cannot have a positive egalitarian welfare.

On the other hand, consider the allocation where agent \(1\) receives good \(g_1\), agent \(2\) receives goods \(g_2\), \(g_3\), \(g_4\), while each agent \(i \in N \setminus \{1, 2\}\) receives good \(g_{i+2}\). In this allocation, agent \(1\) receives a utility of \(1/4\) and each of the remaining agents receives a utility of \(1\). Hence, the maximum egalitarian welfare of this instance is at least \(1/4\). Therefore, the weak egalitarian price of EF1 is \((1/4)/0 = \infty\). ◻