On the Complexity of Chore Division

Alireza Farhadi, MohammadTaghi Hajiaghayi

IJCAI 2018 pp. 226-232

doi:10.24963/IJCAI.2018/31 /ijcai/2018/farhadi2018ijcai-complexity/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Farhadi and Hajiaghayi. "On the Complexity of Chore Division." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/31

Markdown

[Farhadi and Hajiaghayi. "On the Complexity of Chore Division." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/farhadi2018ijcai-complexity/) doi:10.24963/IJCAI.2018/31

BibTeX

@inproceedings{farhadi2018ijcai-complexity,
  title     = {{On the Complexity of Chore Division}},
  author    = {Farhadi, Alireza and Hajiaghayi, MohammadTaghi},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {226-232},
  doi       = {10.24963/IJCAI.2018/31},
  url       = {https://mlanthology.org/ijcai/2018/farhadi2018ijcai-complexity/}
}