Chore Cutting: Envy and Truth
Not on the map. Why?
Abstract (arXiv)
We study the fair division of divisible bad resources with strategic agents who can manipulate their private information to get a better allocation. Within certain constraints, we are particularly interested in whether truthful envy-free mechanisms exist over piecewise-constant valuations. We demonstrate that no deterministic truthful envy-free mechanism can exist in the connected-piece scenario, and the same impossibility result occurs for hungry agents. We also show that no deterministic, truthful dictatorship mechanism can satisfy the envy-free criterion, and the same result remains true for non-wasteful constraints rather than dictatorship. We further address several related problems and directions.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 12 of its 45 references that are in the map. First posted on arXiv 23 Jan 2023.
Builds on
12 of 45 references.
References · 12
- 2016A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agentscited by 7
- 2015A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agentscited by 4
- 2019Algorithms for Competitive Division of Chorescited by 4
- 2017The Query Complexity of Cake Cuttingcited by 3
- 2017Deterministic, Strategyproof, and Fair Cake Cuttingcited by 2
- 2017On the Complexity of Chore Divisioncited by 2
- 2020Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chorescited by 2
- 2021On Existence of Truthful Fair Cake Cutting Mechanismscited by 2
- 2021Truthful Cake Sharingcited by 2
- 2013Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuationscited by 1
- 2018Truthful Fair Division without Free Disposalcited by 1
- 2022Strategyproof and Proportional Chore Division for Piecewise Uniform Preferencescited by 1
Built on by
Not cited yet.