# Chore Cutting: Envy and Truth

arXiv: https://arxiv.org/abs/2301.09306 · HTML: https://mlsanity.com/paper/2301.09306/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 23 Jan 2023.

## Builds on (most cited first, 12 of 12)

- [A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents](https://mlsanity.com/paper/1604.03655/) (2016)
- [A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents](https://mlsanity.com/paper/1508.05143/) (2015)
- [Algorithms for Competitive Division of Chores](https://mlsanity.com/paper/1907.01766/) (2019)
- [The Query Complexity of Cake Cutting](https://mlsanity.com/paper/1705.02946/) (2017)
- [Deterministic, Strategyproof, and Fair Cake Cutting](https://mlsanity.com/paper/1705.06306/) (2017)
- [On the Complexity of Chore Division](https://mlsanity.com/paper/1710.00271/) (2017)
- [Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores](https://mlsanity.com/paper/2008.00285/) (2020)
- [On Existence of Truthful Fair Cake Cutting Mechanisms](https://mlsanity.com/paper/2104.07387/) (2021)
- [Truthful Cake Sharing](https://mlsanity.com/paper/2112.05632/) (2021)
- [Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations](https://mlsanity.com/paper/1307.2908/) (2013)
- [Truthful Fair Division without Free Disposal](https://mlsanity.com/paper/1804.06923/) (2018)
- [Strategyproof and Proportional Chore Division for Piecewise Uniform Preferences](https://mlsanity.com/paper/2204.00456/) (2022)

## 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.