AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Simultaneous Cake Cutting
Eric Balkanski, Simina Brânzei, David Kurokawa, Ariel D. Procaccia

Last modified: 2014-06-21

Abstract


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.

Keywords


cake cutting; fair division; communication complexity; mechanism design

Full Text: PDF