The complexity of cake cutting with unequal shares

Agnes Cseh () and Tamás Fleiner ()
Additional contact information
Agnes Cseh: Hungarian Academy of Sciences, Centre for Economic and Regional Studies, Institute of Economics
Tamás Fleiner: Department of Computer Science and Information Theory, Budapest University of Technology and Economics

No 1819, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

Keywords: fair division; cake cutting; unequal shares; complexity (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 20 pages
Date: 2018-08
New Economics Papers: this item is included in nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.mtakti.hu/wp-content/uploads/2018/09/MTDP1819.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:1819

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).