CS Paper Radar

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

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

cs.GT cs.AIcs.MA ·submitted 2026-10-14 07:11 UTC · v2
publishedtheory

Abstract

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.

Comment
We prove that computing a contiguous envy-free cake division is PPAD-complete for additive valuations, and that computing a contiguous EF$c$ allocation of goods on a path is PPAD-complete for every fixed $c \geq 1$, resolving open questions of Goldberg, Hollender and Suksompong (JAIR 2020) and Bilò et al.\ (ITCS 2019)

Closest papers

Nearest neighbours by meaning across the whole index.

Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints

cs.GT ·2026-08-10 ·Max Dupré la Tour
theory similarity 0.74
Abstract

We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced allocation that is envy-free up to one good and one chore (EF$1^c_g$). This directly implies balanced EF$1$ when each valuation is either monotone nondecreasing or monotone nonincreasing. We also show that balanced EF$1$ cannot be guaranteed without monotonicity: there exists an instance with three agents, nine items, and identical nonmonotone valuations that admits no balanced EF$1$ allocation. We then consider a common laminar matroid constraint. Whenever a complete feasible allocation exists, we prove that there is a complete feasible allocation that is balanced and envy-free up to two goods and two chores (EF$2^c_g$) for arbitrary valuations. The allocation can additionally be chosen so that the numbers of items from every laminar set assigned to the three agents differ by at most two. Most proofs in this paper were obtained using GPT-5.6. We subsequently verified the proofs for correctness and refined their exposition and arguments, also with the aid of GPT-5.6.

0.04

Resolving Envy by Adding Goods with Bounded Supply: A Type-Count Dichotomy and Two-Agent Hardness

cs.GT cs.DS ·2026-08-10 ·Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen, Stéphane Vialette, Géraldine Jean +2 more
theory similarity 0.74
Abstract

We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary additive valuations. With one additional item type, EEAG is polynomial-time solvable for any number of agents. More generally, our algorithm permits arbitrary nonnegative integer per-copy values. The envy constraints form a system of difference constraints, and Bellman--Ford returns the componentwise least feasible extension. In contrast, with exactly two additional item types, EEAG is \textsf{NP}-complete even when both types have positive finite supply and the approvers of one type form a subset of the approvers of the other. This closes the two-type case left open by Bentert et al. Separately, we prove weak \textsf{NP}-completeness even for two agents with identical additive valuations, one initially endowed good, and a growing number of unit-supply item types. Thus, bounded-supply hardness appears both with two item-types and many agents and with two agents and many item-types.

0.04

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

cs.GT cs.AI ·2026-10-04 ·Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
theory similarity 0.73
Abstract

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

0.04

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

cs.GT cs.CC ·2026-09-23 ·Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
theory similarity 0.72
Abstract

Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

0.03

Pareto Inefficiency of EFX

cs.GT ·2026-10-21 ·Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
similarity 0.72
Abstract

We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX) and Pareto optimality. While some of the earliest work on EFX showed that Pareto optimal EFX allocations may not exist if agents can have zero value for some goods, it has remained open whether the same is true when all values are positive. We present a simple instance in which every good has positive value to every agent, but no Pareto optimal EFX allocation exists. We then generalize to a family of instances showing that Pareto optimal $α$-EFX allocations may not exist for any $α> 2/3$.

0.39

Best-of-Both-Worlds Fair Division via Subsidies

cs.GT ·2026-10-10 ·Surya Panchapakesan, Rohit Vaish
theory similarity 0.72
Abstract · 16 pages in main body, 1 page appendix

We study the relationship between fair division with $\textit{subsidies}$ and $\textit{best-of-both-worlds}$ (BoBW) fairness for indivisible items. We prove a general reduction of BoBW existence to envy-freeability. Specifically, for any scale-free ex-post property $P$ (e.g., EF1, EFX, PO) and any scale-free valuation class $\mathcal{V}$ (e.g, additive, submodular, subadditive, monotone), if every instance in $\mathcal{V}$ admits a $P$-allocation that can be made envy-free using subsidies, then every such instance admits an ex-ante envy-free lottery supported on $P$-allocations. The proof uses linear programming duality. As applications, the reduction gives alternative proofs of BoBW existence results for additive goods, chores, and mixtures of goods and chores. The converse of our general reduction holds for two agents but fails for three: We provide a four-good counterexample with monotone submodular valuations where an ex-ante envy-free and ex-post EF1 lottery exists, but no allocation is simultaneously EF1 and envy-freeable. For lexicographic valuations, we prove simultaneous EFX, Pareto optimality, and envy-freeability (and hence BoBW guarantees for EFX+PO) for three agents, and show that even EFX and envy-freeability can be incompatible for four agents.

0.16

To EFX OR to MMS, That is the Question

cs.GT ·2026-08-11 ·Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish
theory similarity 0.72
Abstract

We study the agent-wise disjunction of two central fairness notions for indivisible items, where every agent must be either envy-free up to any item (EFX) or maximin-share (MMS) satisfied. One might expect that having a flexible fairness requirement for individual agents will restore existence, especially because the existence of EFX itself resisted resolution for nearly a decade. Surprisingly, it does not. We construct counterexamples with three agents and eight submodular goods, and with three agents and seven submodular chores, significantly strengthening recent EFX impossibility results. On the positive side, we prove existence for additive mixed items with at most three valuation types when one type is a singleton. Additionally, we obtain polynomial-time approximation schemes for additive goods-only and chores-only instances. We also identify a clean separation between the disjunction and its constituents: For additive chores with two valuation types, EFX and MMS are both known to fail, whereas an EFX $\vee$ MMS allocation always exists. Finally, we show that identical additive valuations even admit the conjunction EFX $\wedge$ MMS for mixed items. Overall, our results show that allowing flexibility in choosing agent-specific fairness certificates expands the frontier of fair solutions while also uncovering surprising impossibilities.

0.32

The Golden Ratio: EF1 and Ordinal-MMS for Additive Goods

cs.GT ·2026-11-11 ·Hadi Hosseini, Shraddha Pathak
theory similarity 0.72
Abstract

Every complete allocation that is envy-free up to one good (EF1) guarantees each of the $n$ agents her $1$-out-of-$(2n-1)$ maximin share. Can we construct allocations that satisfy EF1 together with stronger ordinal maximin share guarantees? For additive valuations, we prove that there always exists a complete allocation that is simultaneously EF1 and ($1$-out-of-$\lfloor\varphi n\rfloor$)-MMS, where $\varphi=(1+\sqrt{5})/2$ is the golden ratio. For bivalued valuations, where each agent may have her own two non-negative values for the goods, we obtain a complete allocation that is simultaneously envy-free up to any good (EFX) and ($1$-out-of-$\lceil(7n-1)/6\rceil$)-MMS.

0.05