A Dictatorship Theorem for Cake Cutting

Simina Branzei; Peter Bro Miltersen

A Dictatorship Theorem for Cake Cutting

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

Original language	English
Title of host publication	Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
Editors	Qiang Yang, Michael Wooldridge
Number of pages	8
Publisher	AAAI Press
Publication date	2015
Pages	481-488
ISBN (Print)	978-1-57735-738-4
Publication status	Published - 2015
Event	International Joint Conference on Artificial Intelligence - Buinos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015 Conference number: 24

Conference

Conference	International Joint Conference on Artificial Intelligence
Number	24
Country/Territory	Argentina
City	Buinos Aires
Period	25/07/2015 → 31/07/2015

Access to Document

http://ijcai.org/papers15/Papers/IJCAI15-074.pdf

Cite this

@inproceedings{e64d1cd575a4494cb75b4bfd759ed31c,

title = "A Dictatorship Theorem for Cake Cutting",

abstract = "We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.",

author = "Simina Branzei and Miltersen, {Peter Bro}",

year = "2015",

language = "English",

isbn = "978-1-57735-738-4",

pages = "481--488",

editor = "{ Yang}, {Qiang } and { Wooldridge}, {Michael }",

booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)",

publisher = "AAAI Press",

note = "International Joint Conference on Artificial Intelligence, IJCAI ; Conference date: 25-07-2015 Through 31-07-2015",

}

Branzei, S & Miltersen, PB 2015, A Dictatorship Theorem for Cake Cutting. in Q Yang & M Wooldridge (eds), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI Press, pp. 481-488, International Joint Conference on Artificial Intelligence, Buinos Aires, Argentina, 25/07/2015. <http://ijcai.org/papers15/Papers/IJCAI15-074.pdf>

A Dictatorship Theorem for Cake Cutting. / Branzei, Simina ; Miltersen, Peter Bro.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015). ed. / Qiang Yang; Michael Wooldridge. AAAI Press, 2015. p. 481-488.

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - A Dictatorship Theorem for Cake Cutting

AU - Branzei, Simina

AU - Miltersen, Peter Bro

N1 - Conference code: 24

PY - 2015

Y1 - 2015

N2 - We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

AB - We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

UR - http://ijcai.org/papers15/contents.php

M3 - Article in proceedings

SN - 978-1-57735-738-4

SP - 481

EP - 488

BT - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

A2 - Yang, Qiang

A2 - Wooldridge, Michael

PB - AAAI Press

T2 - International Joint Conference on Artificial Intelligence

Y2 - 25 July 2015 through 31 July 2015

ER -

A Dictatorship Theorem for Cake Cutting

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this