Improved Parallel Algorithms for EF1 Allocations
Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang, Gregory Kehne · 2026
Read Improved Parallel Algorithms for EF1 Allocations by Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang, Gregory Kehne (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16791.txt.
Introduction
Gowda and colleagues strengthen parallel algorithms for envy-free-up-to-one-good allocation. For two agents, depth falls from logarithmic-squared to logarithmic in goods, and work from m log m to linear. They extend this to any constant number of agents with NC algorithms, plus randomized near m-over-n depth algorithms. Their methods bypass the CC-hardness of simulating Round Robin, and prove that simulation CC-complete. They give envy-free-up-to-k allocations for k near root m in randomized NC.
Catalog record
| CREATOR | Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang, Gregory Kehne |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77931 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16791
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Parallel Algorithms for EF1 Allocations Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang, Gregory Kehne Abstract Allocating m m indivisible goods among n n agents is a fundamental task in fair division. Recent work of Garg and Psomas [AAMAS 2025] initiated the study of parallel algorithms for envy-free up to one good ( 𝖤𝖥𝟣 \mathsf{EF1} ) allocations, giving 𝖭𝖢 \mathsf{NC} algorithms for 2 2 and 3 3 agents. They also showed 𝖢𝖢 \mathsf{CC} -hardness results for simulating the classic Round Robin algorithm for 𝖤𝖥𝟣 \mathsf{EF1} allocations, even when each agent values at most 3 3 goods and each good is valued by at most 3 3 agents. We strengthen these results. For the case of 2 2 agents, we quadratically improve the depth from O ( log 2 m ) O(\log^{2}m) to O ( log m ) O(\log m) and the work from O ( m log m ) O(m\log m) to O ( m ) O(m) . Furthermore, we significantly generalize beyond 3 3 agents by giving 𝖭𝖢 \mathsf{NC} algorithms for any constant number of agents. We also give randomized algorithms with depth O ~ ( m / n ) \tilde{O}(m/n) and polynomial work. As corollaries of these results, we obtain 𝖭𝖢 \mathsf{NC} algorithms whenever each agent values at most 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 ( m ) {\mathsf{polylog}}(m) goods and each good is valued by at most O ( 1 ) O(1) agents, and 𝖱𝖭𝖢 \mathsf{RNC} algorithms when each agent values at most 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 ( m ) {\mathsf{polylog}}(m) goods. As such, our algorithms bypass the 𝖢𝖢 \mathsf{CC} -hardness of Garg and Psomas by not simulating Round Robin. We also complement the aforementioned 𝖢𝖢 \mathsf{CC} -hardness by showing the 𝖢𝖢 \mathsf{CC} -completeness of simulating Round Robin. Lastly, beyond 𝖤𝖥𝟣 \mathsf{EF1} allocations, we show that computing envy-free up to k k goods allocations is possible for k ≈ m k\approx\sqrt{m} in 𝖱𝖭𝖢 \mathsf{RNC} , or k = m ε k=m^{\varepsilon} in sublinear depth for any constant ε > 0 \varepsilon>0 . 1 Introduction The fair allocation of indivisible goods is a central problem in computational social choice 9 . Here, we are given m goods and n agents and must decide how to assign goods to agents in such a way as to satisfy some notion of fairness. One natural such notion is envy-freeness ( \mathsf{EF} ): no agent a should prefer another agent b ’s bundle of goods over their own 23 . Unfortunately envy-freeness is unobtainable, as illustrated by the case of two agents and one good. A classic relaxation of envy-freeness which circumvents this issue is envy-freeness-up-to-one-good ( \mathsf{EF1} ): no agent a should prefer another agent b ’s goods over their own as long as they are allowed to ignore their favorite of b ’s goods 12 ; 32 . A simple way of seeing that \mathsf{EF1} allocations always exist is a proof by algorithm: in particular, the classic Round Robin protocol. Here, we fix an ordering on the agents and then, in this order, each agent repeatedly chooses their favorite among the remaining goods. Assuming agents’ values for goods are additive—that is, agent a gives good g value v_{a}(g) and gives goods S value v_{a}(S):=\sum_{g\in S}v_{a}(g) —then it is a simple exercise to see that the resulting allocation is \mathsf{EF1} . Motivated by the extensive work on algorithms for \mathsf{EF1} allocations and the scale of many \mathsf{EF1} instances of practical interest, 24 initiated the study of parallel algorithms for \mathsf{EF1} allocations. Efficient parallel algorithms for \mathsf{EF1} allocations based on Round Robin seem quite hopeless. In particular, an efficient parallel algorithm is generally understood to be an \mathsf{NC} algorithm---namely, one that has polylogarithmic depth and polynomial work. 1 1 1 We make use of standard work-depth models of parallel computation; see Section 1.3 for details. Round Robin, however, induces chains of linear-length sequential dependencies since each good chosen by each agent delicately depends upon all prior choices of all other agents. Formalizing these issues, 24 showed that simulating Fixed-Order Round Robin—where the ordering of the agents is part of the input—is Comparator-Circuit-hard ( \mathsf{CC} -hard). \mathsf{CC} -hardness is a standard notion of parallel hardness widely thought to rule out \mathsf{NC} algorithms 34 ; 16 . Even worse, this \mathsf{CC} -hardness holds in the case of additive valuations, even when each agent has non-zero value for at most 3 goods and each good has at most 3 agents that give it non-zero value. While several other efficient algorithms for \mathsf{EF1} allocations are known, including envy-cycle elimination 32 and recursive probabilistic serial 4 , like Round Robin these algorithms allocate goods one-at-a-time and so appear fundamentally sequential. Still other approaches appear computationally intractable, optimizing \mathsf{NP} -hard 40 and even \mathsf{APX} -hard objectives 13 ; 31 or finding equilibria in games for which the task is \mathsf{PPAD} -complete 12 ; 39 . That successful approaches for \mathsf{EF1} allocations are sequential may not be an accident; \mathsf{EF1} is a global property of instances in that changing the allocation of a single good can dramatically affect envy relationships between the donor, the recipient and other agents. Likewise, it is not clear how to efficiently combine two disjoint \mathsf{EF1} allocations of goods with a common set of agents into a single allocation—a major barrier to divide-and-conquer-type parallel algorithms. The apparent difficulty of computing \mathsf{EF1} allocations in parallel for general instances motivates our central question: Does there exist a reasonable class of \mathsf{EF1} allocation instances which admit efficient parallel algorithms? Instances with a small number of agents is among the most promising such classes. In particular, there is extensive work on algorithms for fair division with boundedly-many agents, including on the query complexity of \mathsf{EF1} allocations for 2 or 3 agents 38 , the comparison-based query complexity for \mathsf{EF1} allocations 11 for 2 or 3 agents, \mathsf{EF1} allocations that are Pareto optimal for constantly-many agents 33 and envy-free up to any good ( \mathsf{EFX} ) allocations for 2 40 or 3 agents 14 ; we give more details on these works in Section 1.2 . In the spirit of these works, 24 recently gave \mathsf{NC} algorithms with O(\log^{2}m) depth and O(m\log m) work for 2 or 3 agents with additive valuations. However, no \mathsf{NC} algorithms are known for \mathsf{EF1} allocations for even only 4 agents. 1.1 Our Contributions In this work, we significantly improve on the existing parallel algorithms for \mathsf{EF1} allocations. First, for the case of two agents, we quadratically improve the O(\log^{2}m) depth of 24 to O(\log m) while also improving the work from O(m\log m) to O(m) . Theorem 1.1 . There is an O(\log m) depth and O(m) work algorithm that outputs an \mathsf{EF1} allocation for two agents with additive valuations. Our algorithm for the two-agent case can be understood as implementing a certain recursive game. An instance of the game comes with an ordering over the agents and, in turn, decomposes into two subgames. In each game, the agent that goes first chooses one subgame in which to go first and one subgame in which to go second. The base case consists of the agent that goes first and chooses their favorite of two goods, leaving the other