How to solve the cake-cutting problem in sublinear time

DOI10.4230/LIPICS.FUN.2016.21zbMATH Open1369.91106arXiv1504.00774OpenAlexW2963849341MaRDI QIDQ5282819FDOQ5282819

Authors: Hiro Ito, Takahiro Ueda 

Publication date: 17 July 2017

Abstract: In this paper, we show algorithms for solving the cake-cutting problem in sublinear-time. More specifically, we preassign (simple) 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 "eps n-victims," which means that eps n players (victims) may not get fair portions, where 0< eps =< 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 eps 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/eps)-time algorithm for r =< eps n/127 undesignated players with eps n-victims, and an O~(r^2/eps)-time algorithm for r =< eps e^{{sqrt{ln{n}}}/{7}} designated players and eps =< 1/e with eps n-victims are presented.

Full work available at URL: https://arxiv.org/abs/1504.00774

Recommendations

• scientific article; zbMATH DE number 1947449
• scientific article; zbMATH DE number 1962847
• An approximation scheme for cake division with a linear number of cuts
• Algorithms for cake cutting with equal and unequal shares
• scientific article; zbMATH DE number 3849005

zbMATH Keywords

approximationcake-cutting problemsublinear-time algorithmspreassignsimple fair

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) (n)-person games, (n>2) (91A06)

This page was built for publication: How to solve the cake-cutting problem in sublinear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282819)