A Dictatorship Theorem for Cake Cutting

Brânzei, Simina; Miltersen, Peter Bro

A Dictatorship Theorem for Cake Cutting

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 482-487.

Abstract

We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol for two agents in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. For n > 2 agents, a similar impossibility holds, namely there always exists an agent that gets the empty piece (i.e. no cake). In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

Simina Brânzei, and Peter Bro Miltersen. 2015. A Dictatorship Theorem for Cake Cutting. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 482–487. https://ijcai.org/proceedings/2015/74

@inproceedings{ijcai2015p74,
  title     = {A Dictatorship Theorem for Cake Cutting},
  author    = {Brânzei, Simina and Miltersen, Peter Bro},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {482--487},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/74},
}

TY  - CPAPER
TI  - A Dictatorship Theorem for Cake Cutting
AU  - Brânzei, Simina
AU  - Miltersen, Peter Bro
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 482
EP  - 487
UR  - https://ijcai.org/proceedings/2015/74
ER  -