Fair cake-cutting

If a cake with a selection of toppings is simply cut into equal slices, different people will receive different amounts of its toppings, and some may not regard this as a fair division of the cake.

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

The "cake" is only a metaphor; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time.

The prototypical procedure for fair cake-cutting is divide and choose, which is mentioned in the book of Genesis to resolve Abraham and Lot's conflict. This procedure solves the fair division problem for two people. The modern study of fair cake-cutting was initiated during World War II, when Hugo Steinhaus asked his students Stefan Banach and Bronisław Knaster to find a generalization of divide-and-choose to three or more people. They developed the last diminisher procedure.[1] Today, fair cake-cutting is the subject of intense research in mathematics, computer science, economics and political science.[2]

  1. ^ Steinhaus, Hugo (1949). "The problem of fair division". Econometrica. 17: 315–9. doi:10.2307/1907319. JSTOR 1907319.
  2. ^ Ariel Procaccia, "Cake Cutting Algorithms". Chapter 13 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)