arXiv preprint ·
The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Finite-Sample and Communication-Efficient Networked Information Aggregation
Steering Emergent Behavior in Multi-Agent LLM Systems via Information Networks
Welfare in Envy-free Contracts: When Agents Have Sparse Interests
Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games
Learning Global Equilibria in Non-Concave Prospect Theoretic Games
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.