# On the Complexity of Chore Division

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2017.

## Built on by (most cited first, 2 of 2)

- [Chore Cutting: Envy and Truth](https://mlsanity.com/paper/2301.09306/) (2023)
- [Externalities in Chore Division](https://mlsanity.com/paper/2303.12446/) (2023)

## Abstract (arXiv)

We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among n different players. The goal is to find an allocation such that the cost of the chore assigned to each player be at most 1/n of the total cost. This problem is the dual variant of the cake cutting problem in which we want to allocate a desirable object. Edmonds and Pruhs showed that any protocol for the proportional cake cutting must use at least Omega(n log n) queries in the worst case, however, finding a lower bound for the proportional chore division remained an interesting open problem. We show that chore division and cake cutting problems are closely related to each other and provide an Omega(n log n) lower bound for chore division.