Mind the Gap: Cake Cutting With Separation

Authors

  • Edith Elkind University of Oxford
  • Erel Segal-Halevi Ariel University
  • Warut Suksompong National University of Singapore

Keywords:

Fair Division

Abstract

We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then establish several computational properties of maximin share fairness---for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved.

Downloads

Published

2021-05-18

How to Cite

Elkind, E., Segal-Halevi, E., & Suksompong, W. (2021). Mind the Gap: Cake Cutting With Separation. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5330-5338. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16672

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms