file.pdf (283.54 kB)

Simultaneous Cake Cutting

Download (283.54 kB)
journal contribution
posted on 01.11.2002 by Eric Balkanski, Simina Brânzei, David Kurokawa, Ariel D. Procaccia

We introduce the simultaneous model for cake cutting (the fair allocation of a divisible good), in which agents simultaneously send messages containing a sketch of their preferences over the cake. We show that this model enables the computation of divisions that satisfy proportionality — a popular fairness notion — using a protocol that circumvents a standard lower bound via parallel information elicitation. Cake divisions satisfying another prominent fairness notion, envy-freeness, are impossible to compute in the simultaneous model, but admit arbitrarily good approximations.

History

Publisher Statement

Electronic version of an article published as International Journal of Foundations of Computer Science 14(4), 2003, pp. 583-604 . http://dx.doi.org/10.1142/S012905410300190X © [copyright World Scientific Publishing Company] [http://www.worldscinet.com/ijfcs/14/1404/S012905410300190X.html]

Date

01/11/2002

Exports

Exports