Fair cake-cutting
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 "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.
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.
All value functions are assumed to be absolutely continuous with respect to the length, area or (in general) Lebesgue measure.
[3] 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 symbols: In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table: The divide and choose protocol finds an allocation that is always EF.
An EF division for n people exists even when the valuations are not additive, as long as they can be represented as consistent preference sets.
In fact, envy-free divisions of connected intervals to 3 or more people cannot be found by any finite protocol.
Several variants of this property have been studied: See symmetric fair cake-cutting for details and references.
There are several levels of efficiency: For n people with additive value functions, a PEEF division always exists.
[9] If the cake is a 1-dimensional interval and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PE.
If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE.
[11] If the cake is 1-dimensional but each person may receive a disconnected subset of it, then an EF division is not necessarily PE.
This problem has been studied for a cake which is a 1-dimensional interval, each person may receive disconnected pieces, and the value functions are additive.
Lu, Peters, Aziz, Bei and Suksompong[23] extend these definitions to settings with mixed divisible and indivisible candidates (see justified representation).
