Algorithmic Solutions for Envy-Free Cake Cutting

Xiaotie Deng (), Qi Qi () and Amin Saberi ()
Additional contact information
Xiaotie Deng: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom; and Department of Computer Science, City University of Hong Kong, Hong Kong
Qi Qi: Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology, Hong Kong
Amin Saberi: Department of Management Science and Engineering, Stanford University, Stanford, California 94305

Operations Research, 2012, vol. 60, issue 6, 1461-1476

Abstract: We study the problem of finding an envy-free allocation of a cake to d + 1 players using d cuts. Two models are considered, namely, the oracle-function model and the polynomial-time function model. In the oracle-function model, we are interested in the number of times an algorithm has to query the players about their preferences to find an allocation with the envy less than (epsilon). We derive a matching lower and upper bound of (theta)(1/(epsilon)) d - 1 for players with Lipschitz utilities and any d > 1. In the polynomial-time function model, where the utility functions are given explicitly by polynomial-time algorithms, we show that the envy-free cake-cutting problem has the same complexity as finding a Brouwer's fixed point, or, more formally, it is PPAD-complete. On the flip side, for monotone utility functions, we propose a fully polynomial-time algorithm (FPTAS) to find an approximate envy-free allocation of a cake among three people using two cuts.

Keywords: fair division; cake cutting; envy-free; FPTAS; fixed point; PPAD (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1116 (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:inm:oropre:v:60:y:2012:i:6:p:1461-1476

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().