Fair Cake-cutting

2 people – proportional and envy-free division

For ${\displaystyle n=2}$ people, an EF division always exists and can be found by the divide and choose protocol. If the value functions are additive then this division is also PR; otherwise, proportionality is not guaranteed.

Proportional division

For n people with additive valuations, a proportional division always exists. The most common protocols are:

• Last diminisher, a protocol that can guarantee that the n pieces are connected (i.e. no person gets a set of two or more disconnected pieces). In particular, if the cake is a 1-dimensional interval then each person receives an interval. This protocol is discrete and can be played in turns. It requires O(n²) actions.
• The Dubins–Spanier Moving-knife procedure is a continuous-time version of Last diminisher.^[6]
• Fink protocol (also known as successive pairs or lone chooser) is a discrete protocol that can be used for online division: given a proportional division for n − 1 partners, when a new partner enters the party, the protocol modifies the existing division so that both the new partner and the existing partners remain with 1/n. The disadvantage is that each partner receives a large number of disconnected pieces.
• The Even–Paz protocol, based on recursively halving the cake and the group of agents, requires only O(n log n) actions. This is fastest possible deterministic protocol for proportional division, and the fastest possible protocol for proportional division which can guarantee that the pieces are connected.
• Edmonds–Pruhs protocol is a randomized protocol that requires only O(n) actions, but guarantees only a partially proportional division (each partner receives at least 1/an, where a is some constant), and it might give each partner a collection of "crumbs" instead of a single connected piece.
• Beck land division protocol can produce a proportional division of a disputed territory among several neighbouring countries, such that each country receives a share that is both connected and adjacent to its currently held territory.
• Woodall's super-proportional division protocol produces a division which gives each partner strictly more than 1/n, given that at least two partners have different opinions about the value of at least a single piece.

See proportional cake-cutting for more details and complete references.

The above algorithms focus mainly on agents with equal entitlements to the resource; however, it is possible to generalize them and get a proportional cake-cutting among agents with different entitlements.

Envy-free division

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. EF division has been studied separately for the case in which the pieces must be connected, and for the easier case in which the pieces may be disconnected.

For connected pieces the major results are:

• Stromquist moving-knives procedure produces an envy-free division for 3 people, by giving each one of them a knife and instructing them to move their knives continuously over the cake in a pre-specified manner.
• Simmons' protocol can produce an approximation of an envy-free division for n people with an arbitrary precision. If the value functions are additive, the division will also be proportional. Otherwise, the division will still be envy-free but not necessarily proportional. The algorithm gives a fast and practical way of solving some fair division problems.^[7][8]

Both these algorithms are infinite: the first is continuous and the second might take an infinite time to converge. In fact, envy-free divisions of connected intervals to 3 or more people cannot be found by any finite protocol.

For possibly-disconnected pieces the major results are:

• Selfridge–Conway discrete procedure produces an envy-free division for 3 people using at most 5 cuts.
• Brams–Taylor–Zwicker moving knives procedure produces an envy-free division for 4 people using at most 11 cuts.
• A reentrant variant of the Last Diminisher protocol finds an additive approximation to an envy-free division in bounded time. Specifically, for every constant ${\displaystyle \epsilon >0}$, it returns a division in which the value of each partner is at least the largest value minus ${\displaystyle \epsilon }$, in time ${\displaystyle O(n^{2}/\epsilon )}$.
• Three different procedures, one by Brams and Taylor (1995) and one by Robertson and Webb (1998) and one by Pikhurko (2000), produce an envy-free division for n people. Both algorithms require a finite but unbounded number of cuts.
• A procedure by Aziz and Mackenzie (2016) finds an envy-free division for n people in a bounded number of queries.

The negative result in the general case is much weaker than in the connected case. All we know is that every algorithm for envy-free division must use at least Ω(n²) queries. There is a large gap between this result and the runtime complexity of the best known procedure.

See envy-free cake-cutting for more details and complete references.

Efficient division

When the value functions are additive, utilitarian-maximal (UM) divisions exist. Intuitively, to create a UM division, we should give each piece of cake to the person that values it the most. In the example cake, a UM division would give the entire chocolate to Alice and the entire vanilla to George, achieving a utilitarian value of 9 + 4 = 13.

This process is easy to carry out when the value functions are piecewise-constant, i.e. the cake can be divided to pieces such that the value density of each piece is constant for all people. When the value functions are not piecewise-constant, the existence of UM divisions is based on a generalization of this procedure using the Radon–Nikodym derivatives of the value functions; see Theorem 2 of.^[6]

When the cake is 1-dimensional and the pieces must be connected, the simple algorithm of assigning each piece to the agent that values it the most no longer works. In this case, the problem of finding a UM division is NP-hard, and furthermore no FPTAS is possible unless P = NP. There is an 8-factor approximation algorithm, and a fixed-parameter tractable algorithm which is exponential in the number of players.^[9]

For every set of positive weights, a WUM division can be found in a similar way. Hence, PE divisions always exist.

Procedural fairness

Recently there is interest not only in the fairness of the final allocation but also in the fairness of the allocation procedures: there should not be a difference between different roles in the procedure. Several definitions of procedural fairness have been studied:

• Anonymity requires that, if the agents are permuted and the procedure is re-executed, then each agent receives exactly the same piece as in the original execution. This is a strong condition; currently, an anonymous procedure is known only for 2 agents.
• Symmetry requires that, if the agents are permuted and the procedure is re-executed, then each agent receives the same value as in the original execeution. This is weaker than anonymity; currently, a symmetric and proportional procedure is known for any number of agents, and it takes O(n³) queries. A symmetric and envy-free procedure is known for any number of agents, but it takes much longer - it requires n! executions of an existing envy-free procedure.
• Aristotelianity requires that, if two agents have an identical value-measure, then they receive the same value. This is weaker than symmetry; it is satisfied by any envy-free procedure. Moreover, an aristotelian and proportional procedure is known for any number of agents, and it takes O(n³) queries.

See symmetric fair cake-cutting for details and references.

Efficient fair division

For n people with additive value functions, a PEEF division always exists.^[10]

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.^[11] Hence, Simmons' protocol produces a PEEF division in this case.

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. Additionally, there are pairs of (non-additive) value functions for which no PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists.^[12]

If the cake is 1-dimensional but each person may receive a disconnected subset of it, then an EF division is not necessarily PE. In this case, more complicated algorithms are required for finding a PEEF division.

If the value functions are additive and piecewise-constant, then there is an algorithm that finds a PEEF division.^[13] If the value density functions are additive and Lipschitz continuous, then they can be approximated as piecewise-constant functions "as close as we like", therefore that algorithm approximates a PEEF division "as close as we like".^[13]

An EF division is not necessarily UM.^[14][15] One approach to handle this difficulty is to find, among all possible EF divisions, the EF division with the highest utilitarian value. 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.^[16]