License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.21
URN: urn:nbn:de:0030-drops-58639
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5863/
Ito, Hiro ;
Ueda, Takahiro
How to Solve the Cake-Cutting Problem in Sublinear Time
Abstract
The cake-cutting problem refers to the issue of dividing a cake into pieces and distributing them to players who have different value measures related to the cake, and who feel that their portions should be "fair." The fairness criterion specifies that in situations where n is the number of players, each player should receive his/her portion with at least 1/n of the cake value in his/her measure. In this paper, we show algorithms for solving the cake-cutting problem in sublinear-time. More specifically, we preassign fair portions to o(n) players in o(n)-time, and minimize the damage to the rest of the players. All currently known algorithms require Omega(n)-time, even when assigning a portion to just one player, and it is nontrivial to revise these algorithms to run in o(n)-time since many of the remaining players, who have not been asked any queries, may not be satisfied with the remaining cake. To challenge this problem, we begin by providing a framework for solving the cake-cutting problem in sublinear-time. Generally speaking, solving a problem in sublinear-time requires the use of approximations. However, in our framework, we introduce the concept of "epsilon n-victims," which means that (epsilon x n) players (victims) may not get fair portions, where 0< epsilon =< 1 is an arbitrary constant. In our framework, an algorithm consists of the following two parts: In the first (Preassigning) part, it distributes fair portions to r < n players in o(n)-time. In the second (Completion) part, it distributes fair portions to the remaining n-r players except for the (epsilon x n) victims in poly(n)-time. There are two variations on the r players in the first part. Specifically, whether they can or cannot be designated. We will then present algorithms in this framework. In particular, an O(r/epsilon)-time algorithm for r =< (epsilon x n)/127 undesignated players with (epsilon x n)-victims, and an tilde{O}(r^2/epsilon)-time algorithm for r =< (epsilon x e^(((sqrt(ln(n)))/7) designated players and epsilon =< 1/e with (epsilon x n)-victims are presented.
BibTeX - Entry
@InProceedings{ito_et_al:LIPIcs:2016:5863,
author = {Hiro Ito and Takahiro Ueda},
title = {{How to Solve the Cake-Cutting Problem in Sublinear Time}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-005-7},
ISSN = {1868-8969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5863},
URN = {urn:nbn:de:0030-drops-58639},
doi = {10.4230/LIPIcs.FUN.2016.21},
annote = {Keywords: sublinear-time algorithms, cake-cutting problem, simple fair, preassign, approximation}
}
|
Keywords: |
|
sublinear-time algorithms, cake-cutting problem, simple fair, preassign, approximation |
|
Collection: |
|
8th International Conference on Fun with Algorithms (FUN 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
02.06.2016 |
