CS Paper Radar

Nearly Settling the Complexity of Connected $\varepsilon$-Envy-Free Cake Cutting

Simon Mackenzie, Mashbat Suzuki

cs.GT cs.CC ·submitted 2026-11-16 10:59 UTC · v2

Abstract

Envy-free cake cutting has been one of the central problems in fair division. In cake cutting, agents' preferences over the cake are accessed through Robertson--Webb (RW) queries. For three or more agents, no algorithm that makes finitely many RW queries can always find a contiguous, exactly envy-free allocation. For contiguous $\varepsilon$-envy-free allocations, however, Hollender and Rubinstein~(JACM, 2025) showed that $\poly(\log(1/\varepsilon))$ RW queries suffice for four agents, leaving open whether such a bound is possible for five or more agents. In this paper, we establish a striking change in query complexity: $\poly(\log(1/\varepsilon))$ RW queries suffice for up to five agents, whereas $(1/\varepsilon)^{Ω(1)}$ queries are necessary for seven or more agents, even when valuations are additive. Thus, we resolve the five-agent case and, more broadly, determine whether polylogarithmic query complexity is possible for every number of agents except six. We also explore the computational complexity of finding contiguous $\varepsilon$-envy-free allocations. When monotone Lipschitz valuations are given by polynomial-time evaluation procedures (e.g., arithmetic circuits and efficiently computable Turing machines), we show that an $\varepsilon$-envy-free division can be computed in polynomial time for five agents. In contrast, even for additive valuations, finding an $\varepsilon$-envy-free division is UEOPL-hard for every fixed number of agents $n\ge7$ and PPAD-complete for every fixed $n\ge13$.

Comment
66 pages, 2 figures. We corrected the attribution in the seven-agent hardness proof to make explicit its use of the theorem of Hollender, Maystre and Risse that the Jordan Curve problem is UEOPL-hard. We also clarified the attribution of earlier algorithms and reductions and the assumptions behind prior query bounds. The main results are unchanged

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Envy-Free Cake Cutting with Polynomial Expected Queries

cs.GT cs.CC ·2026-10-20 ·Simon Mackenzie, Mashbat Suzuki
theory similarity 0.85
Abstract · 56 pages, 4 figures. Preliminary version

Envy-free cake cutting asks how to divide a resource so that no agent prefers another agent's share. Finding such a division with few queries about preferences has been a longstanding challenge. Aziz and Mackenzie gave the first query bound depending only on the number $n$ of agents: a tower of six $n$'s. Subsequent improvements culminated in Ye and Bai's single-exponential bound of $n^{O(1)}2^n$. A large gap remains between this deterministic upper bound and Procaccia's general lower bound of $Ω(n^2)$. Whether polynomially many queries suffice is a central open question in fair division. We show that a polynomial expected query bound is possible. Our randomised protocol uses only independent, uniformly sampled points from the cake as its source of randomness. For every profile of $n$ agents with nonnegative, additive, nonatomic valuations, the protocol has the following guarantees: (1) It terminates with probability one. (2) Every allocation it returns is complete and exactly envy-free. (3) Its expected number of Robertson-Webb queries is $\widetilde{O}(n^{30})$. The expectation is taken solely over the protocol's random choices, with no distributional assumptions on preferences.

0.31

Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting

cs.GT ·2026-09-04 ·Qilin Ye, Yannan Bai
theory similarity 0.80
Abstract

Envy-free cake cutting is a central problem in fair division with a striking divide between existence and computation. Classical topology guarantees that envy-free allocations exist, yet finding one efficiently (in the Robertson-Webb query model) has resisted decades of work. The seminal work by Aziz and Mackenzie established the existence of a bounded protocol for every $n$, but its query bound is $n^{n^{n^{n^{n^n}}}}$. Subsequently, Sokolov modified their protocol and sharpened its analysis, obtaining a bound of $n^{8n^2(1+o(1))}$ queries, the best deterministic upper bound known before this work. In contrast, the general lower bound, due to Procaccia, is merely $Ω(n^2)$. We close much of this gap with a deterministic protocol using $n^{O(1)}2^n$ queries, the first single-exponential bound for general valuations. Like Aziz and Mackenzie, we repeatedly allocate cake without envy until some agents can leave with their pieces, guaranteed not to envy anyone who stays, even if a staying agent receives all the remaining cake. To reach this state, Aziz and Mackenzie generate $n^{n^{n^n}}$ partial allocations so that enough of them can be redistributed without conflict. Instead, we show that only polynomially many partial allocations suffice. Our key idea is to ``prune'' scarce allocations upfront: if only a few allocations can help a certain pair of agents, we discard them and handle that pair another way, leaving plenty of allocations for every remaining pair so each gets a distinct one. As a result, we make only polynomially many calls to Aziz and Mackenzie's subroutines, and this gives us our $n^{O(1)}2^n$ bound.

0.41

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

cs.GT ·2026-11-08 ·Alireza Farhadi, Mohammadtaghi Hajiaghayi
similarity 0.80
Abstract

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using $2^{n\log_2 n+O(n)}$ queries and cuts. For both cake and chores, a Las Vegas protocol uses $O(n^{12}\log(2n))$ expected queries and $O(n^{11}\log(2n))$ expected cuts. Conversely, every exact protocol with fixed positive success probability requires $Ω(n^2)$ expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

0.19

Exact Cut Complexity of Equal-Length Proportional Cake Cutting

cs.MA cs.AIcs.DScs.GT ·2026-10-14 ·Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
publishedtheory similarity 0.79
Abstract · A preliminary version of this paper appeared in the proceedings of the 51st International Symposium on Mathematical Foundations of Computer …

We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely $2n-2$ for every $n$. This improves on the previously known quadratic upper bound. The proof combines the constrained necklace-splitting theorem with a recursive assignment argument based on Hall's theorem. The same bound extends to the stronger requirement of envy-freeness when $n$ is a prime power, and an $O(n^{1.525})$ upper bound holds for arbitrary $n$. We then ask whether such allocations can be computed. We first show that no deterministic protocol in the Robertson--Webb model terminates after finitely many queries on every instance and always returns an exact equal-length proportional allocation, even for two agents with identical valuations. For every $\varepsilon>0$, however, $O(n^2/\varepsilon)$ queries suffice to produce an allocation in which every agent receives a bundle of length exactly $1/n$ and value at least $1/n-\varepsilon$, again using at most $2n-2$ cuts. Finally, we augment the Robertson--Webb model with two-knife queries. We show that recursive balanced halving attains the optimal bound of $2n-2$ cuts when $n$ is a power of two. For arbitrary $n$, we give a procedure using $O(n\log n)$ cuts.

0.20

Cutting a Cake For Human Consumption: An Elementary $n$-agent Cake Cutting Protocol

cs.GT ·2026-10-21 ·Alexandros Psomas
similarity 0.77
Abstract

We give a bounded envy-free cake-cutting protocol for any number $n$ of agents in the Robertson--Webb model, with a short, self-contained, and elementary correctness proof. The protocol uses $2^{O(n \log n)}$ queries. Most ingredients are already known and well understood in the fair division literature; our main contribution is a simpler organization of these ideas into a protocol whose complete description and proof fit in a few pages.

0.38

Logarithmic Comparison-Query Complexity for EF1 Allocations

cs.GT ·2026-11-03 ·Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
theory similarity 0.75
Abstract

We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established $O(\log m)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $Ω(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.

0.12

PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations

cs.GT cs.AIcs.MA ·2026-10-14 ·Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
publishedtheory similarity 0.71
Abstract · We prove that computing a contiguous envy-free cake division is PPAD-complete for additive valuations, and that computing a contiguous EF$c$…

We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness holds even when $\varepsilon$ is given in unary, and even when every density takes only the values $λ$ and $2λ$ for some $λ>0$ common to all agents and has at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, even under the same density restrictions. Our key ingredient is to assign prices to the pieces so that, in every approximately envy-free allocation, all prices are nearly equal, regardless of how the pieces are assigned to the agents. We further show that, for every fixed integer $c\ge1$, computing a contiguous allocation of indivisible goods on a path that is envy-free up to $c$ goods (EF$c$) is PPAD-complete for additive valuations, and this remains true even for $c=\lfloor m^α\rfloor$ with any fixed rational $0<α<1$, where $m$ is the number of goods. This hardness holds even for binary valuations in which each good is valued by exactly one agent and all agents value the same number of goods. All these results extend to chores. Our results answer three open questions at once: whether contiguous envy-free cake cutting is PPAD-hard for additive valuations, the complexity of computing contiguous EF1 and EF2 allocations of goods on a path, and the corresponding question for EF1 allocations of chores.

0.35

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.71
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. Both asymptotic constructions use $n+O(\log n)$ items. Together with concurrent existence results of Feige (2026), this determines the threshold $n+Θ(\log n)$ for guaranteed MMS existence under additive preferences, for both goods and chores. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

0.40