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 subjectively fair, in that each person should receive a piece that he or she believes 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 cake-cutting problem was introduced by Hugo Steinhaus after World War II^[1] and is still the subject of intense research in mathematics, computer science, economics and political science.^[2]

Assumptions

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 R^d.

There are n people with equal rights to C.^[3]

C has to be divided to n disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person i is called ${\displaystyle X_{i}}$, and ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{n}}$.

Each person should get a piece with a "fair" value. Fairness is defined based on subjective value functions. Each person i has a subjective value function V_i 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.^[4] 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.

Additionally, in some 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).

Example cake

In the following lines we will use the following cake as an illustration.

• The cake has two parts: chocolate and vanilla.
• There are two people: Alice and George.
• Alice values the chocolate as 9 and the vanilla as 1.
• George values the chocolate as 6 and the vanilla as 4.

Justice requirements

The original and most common criterion for justice is proportionality (PR). In a proportional cake-cutting, each person receives a piece that he values as at least 1/n of the value of the entire cake. In the example cake, a proportional division can be achieved by giving all the vanilla and 4/9 of the chocolate to George (for a value of 6.66), and the other 5/9 of the chocolate to Alice (for a value of 5). In symbols:

${\displaystyle \forall {i}:\ V_{i}(X_{i})\geq 1/n}$

The proportionality criterion can be generalized to situations in which the rights of the people are not equal. For example, in proportional cake-cutting with different entitlements, the cake belongs to shareholders such that one of them holds 20% and the other holds 80% of the cake. This leads to the criterion of weighted proportionality (WPR):

${\displaystyle \forall i:V_{i}(X_{i})\geq w_{i}}$

Where the w_i are weights that sum up to 1.

Another common criterion is envy-freeness (EF). In an envy-free cake-cutting, each person receives a piece that he values at least as much as every other piece. In symbols:

${\displaystyle \forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})}$

In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table:

A third, less common criterion is equitability (EQ). In an equitable division, each person enjoys exactly the same value. In the example cake, an equitable division can be achieved by giving each person half the chocolate and half the vanilla, such that each person enjoys a value of 5. In symbols:

${\displaystyle \forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})}$

A fourth criterion is exactness. If the entitlement of each partner i is w_i, then an exact division is a division in which:

${\displaystyle \forall {i,j}:\ V_{i}(X_{j})=w_{j}}$

If the weights are all equal (to 1/n) then the division is called perfect and:

${\displaystyle \forall i,j:\ V_{i}(X_{j})=1/n}$

Geometric requirements

In some cases, the pieces allocated to the partners must satisfy some geometric constraints, in addition to being fair.

• The most common constraint is connectivity. In case the "cake" is a 1-dimensional interval, this translates to the requirement that each piece is also an interval. In case the cake is a 1-dimensional circle ("pie"), this translates to the requirement that each piece be an arc; see fair pie-cutting.
• Another constraint is adjacency. This constraint applies to the case when the "cake" is a disputed territory that has to be divided among neighboring countries. In this case, it may required that the piece allocated to each country is adjacent to its current territory; this constraint is handled by Hill's land division problem.
• In land division there are often two-dimensional geometric constraints, e.g., each piece should be a square or (more generally) a fat object.^[5]

Efficiency and truthfulness

In addition to justice, it is also common to consider the economic efficiency of the division; see Efficient cake-cutting.

In addition to the desired properties of the final partitions, there are also desired properties of the division process. One of these properties is truthfulness (aka incentive compatibility), which comes in two levels.

• Weak truthfulness means that if the partner reveals his true value measure to the algorithm, he is guaranteed to receive his fair share (e.g. 1/n of the value of the entire cake, in case of proportional division), regardless of what other partners do. Even if all other partners make a coalition with the only intent to harm him, he will still receive his guaranteed proportion. Most cake-cutting algorithms are truthful in this sense.^[1]
• Strong truthfulness means that no partner can gain from lying. I.e., telling the truth is a dominant strategy. Most cake-cutting protocols are not strongly truthful, but some truthful protocols have been developed; see truthful cake-cutting.

Results

Dividing multiple cakes

There is a generalization of the cake-cutting problem in which there are several cakes, and each agent needs to get a piece in each cake.

• Cloutier, Nyman and Su^[17] study two-player envy-free multi-cake division. For two cakes, they prove that an EF allocation may not exist when there are 2 agents and each cake is cut into 2 pieces. However, an EF allocation exists when there are 2 agents and one cake is cut into 3 pieces (the least-wanted piece is discarded), or when there are 3 agents and each cake is cut into 2 pieces (one agent is ignored; the allocation is EF for the remaining two).
• Lebert, Meunier and Carbonneaux^[18] prove, for two cakes, that an EF allocation always exists when there are 3 agents and each cake is cut into 5 pieces (the two least-wanted pieces in each cake are discarded).
• Nyman, Su and Zerbib^[19] prove, for k cakes, that an EF allocation always exists when there are k(n-1)+1 agents and each cake is cut into n pieces (the allocation is EF for some set of n agents).

Two related problems are:

• Multi-layered cake-cutting,^[20] where the cakes are arranged in "layers" and pieces of the same agent must not overlap (for example, each cake represents the time in which a certain facility is available during the day; an agent cannot use two facilities simultaneously).
• Fair multi-cake cutting,^[21] where the agents do not want to get a piece on every cake, on the contrary, they want to get pieces on as few cakes as possible.

See also

• Fair item allocation – a similar problem where the items to divide are indivisible.

References

Further reading

• A list of books about fair division
• A list of research papers about fair division