On the Complexity of Chore Division

On the Complexity of Chore Division

Alireza Farhadi, MohammadTaghi Hajiaghayi

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 226-232. https://doi.org/10.24963/ijcai.2018/31

We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among n different players. This problem is the dual variant of the cake cutting problem in which we want to allocate a desirable object. In this paper, we show that chore division and cake cutting problems are closely related to each other and provide a tight lower bound for proportional chore division.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory