Affordable Access

Fair and Square: Cake-Cutting in Two Dimensions

  • Segal-Halevi, Erel
  • Nitzan, Shmuel
  • Hassidim, Avinatan
  • Aumann, Yonatan
Publication Date
Oct 12, 2015
Submission Date
Oct 12, 2015
arXiv ID: 1510.03170
External links


We consider the problem of fairly dividing a two-dimensional heterogeneous good, such as land or ad space in print and electronic media, among several agents with different utilities. Classic cake-cutting procedures either allocate each agent a collection of disconnected pieces, or assume that the cake is a one-dimensional interval. In practice, however, the two-dimensional shape of the allotted pieces may be of crucial importance. In particular, when building a house or designing an advertisement, squares are more usable than long and narrow rectangles. We thus introduce and study the problem of fair two-dimensional division wherein the allotted pieces must be of some restricted two-dimensional geometric shape(s). Adding this geometric constraint re-opens most questions and challenges related to cake-cutting. Indeed, even the most elementary fairness criterion - proportionality - can no longer be guaranteed. In this paper we thus examine the level of proportionality that can be guaranteed, providing both impossibility results (for proportionality that cannot be guaranteed) and division procedures (for proportionality that can be guaranteed). We consider cakes and pieces of various shapes, focusing primarily on shapes with a balanced aspect ratio such as squares.

Report this publication


Seen <100 times