Simultaneous Cake Cutting

Authors

  • Eric Balkanski Carnegie Mellon University
  • Simina Brânzei Aarhus University
  • David Kurokawa Carnegie Mellon University
  • Ariel Procaccia Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v28i1.8802

Keywords:

cake cutting, fair division, communication complexity, mechanism design

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.

AAAI 2014 Proceedings Cover

Downloads

Published

2014-06-21

How to Cite

Balkanski, E., Brânzei, S., Kurokawa, D., & Procaccia, A. (2014). Simultaneous Cake Cutting. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8802

Issue

Vol. 28 No. 1 (2014): Twenty-Eighth AAAI Conference on Artificial Intelligence

Section

AAAI Technical Track: Game Theory and Economic Paradigms