| Residential College | false |
| Status | 已發表Published |
| Optimal Proportional Cake Cutting with Connected Pieces | |
Bei, Xiaohui1; Chen, Ning2; Hua, Xia2; Tao, Biaoshuai2; Yang, Endong2
| |
| 2012-07 | |
| Publisher | Association for the Advancement of Artificial Intelligence |
| Conference Name | Proceedings of the National Conference on Artificial Intelligence |
| Conference Place | Toronto |
| Conference Date | 22 July 2012 to 26 July 2012 |
| 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. |
| Keyword | Cake Cutting, Fairness, Welfare |
| DOI | 10.1609/aaai.v26i1.8243 |
| URL | View the original |
| Language | 英語English |
| Fulltext Access | |
| Citation statistics | |
| Document Type | Conference proceedings |
| Collection | DEPARTMENT OF FINANCE AND BUSINESS ECONOMICS |
| Affiliation | 1.Tsinghua University 2.Nanyang Technological University |
| Recommended Citation GB/T 7714 | Bei, Xiaohui,Chen, Ning,Hua, Xia,et al. Optimal Proportional Cake Cutting with Connected Pieces[C]:Association for the Advancement of Artificial Intelligence, 2012. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment