Algorithmic Solutions for Envy-Free Cake Cutting

• 成果类型: Article
• 署名作者: Deng, Xiaotie; Qi, Qi; Saberi, Amin
• 署名单位: University of Liverpool; City University of Hong Kong; Hong Kong University of Science & Technology; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1116
• 发表日期: 2012
• 页码: 1461-1476
• 关键词: sperners lemma; complexity; division; THEOREMS; fairness

摘要

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 c. We derive a matching lower and upper bound of theta(1/is an element of)(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. Subject classifications: fair division; cake cutting; envy-free; FPTAS; fixed point; PPAD. Area of review: Optimization. History: Received April 2010; revisions received March 2011, September 2011; accepted January 2012.