Fair cake-cutting

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. It 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. Today, fair cake-cutting is the subject of intense research in mathematics, computer science, economics and political science. There is a cake C, which is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane Rd. There are n people with subjective value functions over C. Each person i has a value function Vi which maps subsets of C to numbers. All value functions are assumed to be absolutely continuous with respect to the length, area or (in general) Lebesgue measure. This means that there are no "atoms" – there are no singular points to which one or more agents assign a positive value, so all parts of the cake are divisible. In many cases, the value functions are assumed to be sigma additive (the value of a whole is equal to the sum of the values of its parts).