Waste Makes Haste

Erel Segal-Halevi; Avinatan Hassidim; Yonatan Aumann

doi:10.1145/2988232

journal article Nov 19, 2016

Waste Makes Haste

Erel Segal-Halevi

Avinatan Hassidim Yonatan Aumann

ACM Transactions on Algorithms Vol. 13 No. 1 pp. 1-32 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/2988232

Abstract

We consider the classic problem of envy-free division of a heterogeneous good (“cake”) among several agents. It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite algorithm for three or more agents. The impossibility result, however, assumes that the entire cake must be allocated. In this article, we replace the entire-allocation requirement with a weaker
partial-proportionality
requirement: the piece given to each agent must be worth for it at least a certain positive fraction of the entire cake value. We prove that this version of the problem is solvable in bounded time even when the pieces must be connected. We present simple, bounded-time envy-free cake-cutting algorithms for (1) giving each of
n
agents a connected piece with a positive value; (2) giving each of three agents a connected piece worth at least 1/3; (3) giving each of four agents a connected piece worth at least 1/7; (4) giving each of four agents a disconnected piece worth at least 1/4; and (5) giving each of
n
agents a disconnected piece worth at least (1 − ϵ)/
n
for any positive ϵ.

Topics

No keywords indexed for this article. Browse by subject →

References

30

[1]

10.1007/s00355-015-0943-y

[2]

Aziz Haris (2015)

[3]

10.1145/2897518.2897522

[4]

Aziz Haris (2016)

[5]

10.1016/j.mathsocsci.2004.03.006

[6]

Brams Steven J. (2013)

[7]

10.1080/00029890.1995.11990526

[8]

Brams Steven J. (1996)

[9]

10.1016/j.ipl.2014.07.005

[10]

Brânzei Simina

[11]

10.1287/opre.1120.1116

[12]

The Sage Developers. 2015. SageMath the Sage Mathematics Software System (Version 6.7). http://www.sagemath.org. The Sage Developers. 2015. SageMath the Sage Mathematics Software System (Version 6.7). http://www.sagemath.org.

[13]

10.1109/focs.2006.17

[14]

10.1145/2000807.2000819

[15]

10.1007/978-3-540-68880-8_16

[16]

10.1016/0166-218x(84)90005-2

[17]

Kurokawa David

[18]

10.1080/00029890.2000.12005263

[19]

10.5555/1661445.1661484

[20]

Procaccia Ariel D.

[21]

Reitzig Raphael (2015)

[22]

Robertson Jack M. (1998)

[23]

10.1007/978-3-642-02158-9_25

[24]

Segal-Halevi Erel (2015)

[25]

Segal-Halevi Erel (2015)

[26]

Steinhaus Hugo "The problem of fair division" Econometrica (1948)

[27]

10.1080/00029890.1980.11995109

[28]

Stromquist Walter (2008)

[29]

10.2307/2589747

[30]

10.1016/j.disopt.2006.07.003

Metrics

7

Citations

30

References

Details

Published: Nov 19, 2016
Vol/Issue: 13(1)
Pages: 1-32
License: View

Authors

E

Erel Segal-Halevi

Bar-Ilan University, Ramat-Gan 5290002, Israel

A

Avinatan Hassidim

Bar-Ilan University, Ramat-Gan 5290002, Israel

Y

Yonatan Aumann

Bar-Ilan University, Ramat-Gan 5290002, Israel

Funding

BSF Award: 2012344

ISF Award: 1083/13 and 1241/12

Doctoral Fellowships of Excellence Program

Mordecai and Monique Katz Graduate Fellowship Program

Cite This Article

Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann (2016). Waste Makes Haste. ACM Transactions on Algorithms, 13(1), 1-32. https://doi.org/10.1145/2988232

Waste Makes Haste

You May Also Like