Optimal Proportional Cake Cutting with Connected Pieces
Abstract
We consider the classic cake cutting problem where one allocates a divisible cake to n participating agents. Among all valid divisions, fairness and efficiency (a.k.a. ~social welfare) are the most critical criteria to satisfy and optimize, respectively. We study computational complexity of computing an efficiency optimal division given the conditions that the allocation satisfies proportional fairness and assigns each agent a connected piece. For linear valuation functions, we give a polynomial time approximation scheme to compute an efficiency optimal allocation. On the other hand, we show that the problem is NP-hard to approximate within a factor of Ω 1/√n for general piecewise constant functions, and is NP-hard to compute for normalized functions.
Cite
Text
Bei et al. "Optimal Proportional Cake Cutting with Connected Pieces." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8243Markdown
[Bei et al. "Optimal Proportional Cake Cutting with Connected Pieces." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/bei2012aaai-optimal/) doi:10.1609/AAAI.V26I1.8243BibTeX
@inproceedings{bei2012aaai-optimal,
title = {{Optimal Proportional Cake Cutting with Connected Pieces}},
author = {Bei, Xiaohui and Chen, Ning and Hua, Xia and Tao, Biaoshuai and Yang, Endong},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {1263-1269},
doi = {10.1609/AAAI.V26I1.8243},
url = {https://mlanthology.org/aaai/2012/bei2012aaai-optimal/}
}