Search in Co-Wiki

Fair cake-cutting

game-theory 4517 tokens 20 outbound links

Fair cake-cutting

The "cake" is a stand-in object purposed to model fair cake-cutting procedures, whose applications extend to 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. Today, fair cake-cutting is the subject of intense research in mathematics, computer science, economics and political science.

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 Rd.

There are n people with subjective value functions over C. Each person i has a 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. 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).

The n people have equal rights to C. I.e., there is no dispute over the rights of the people – everyone agrees that everyone else is entitled to a fair share. The only problem is how to divide the cake such that each person receives a fair share.

In the following examples the following cake will be used 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 ### Proportionality 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:

:<math>\forall{i}:\ V_i(X_i)\geq 1/n</math>

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

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

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):

:<math>\forall i: V_i(X_i)\geq w_i </math>

Where the w'i are weights that sum up to 1.

Envy-freeness 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:

:<math>\forall i,j:\ V_i(X_i)\geq V_i(X_j)</math>

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. If the value functions are additive then this division is also PR; otherwise, proportionality is not guaranteed.

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.

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 [[last-diminisher|reentrant variant of the Last Diminisher protocol]] finds an additive approximation to an envy-free division in bounded time. Specifically, for every constant <math>\epsilon>0</math>, it returns a division in which the value of each partner is at least the largest value minus <math>\epsilon</math>, in time <math>O(n^2/\epsilon)</math>. 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 Ω(n2) 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.

Other criteria 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:

:<math>\forall i,j:\ V_i(X_i) = V_j(X_j)</math>

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

:<math>\forall{i,j}:\ V_i(X_j) = w_j</math>

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

:<math>\forall i,j:\ V_i(X_j) = 1/n</math>

Probabilistic fair division Traditional fair division methods typically allocate fixed shares of a resource to each participant in a deterministic manner. In contrast, probabilistic fair division assigns shares based on probabilities determined by participants’ attributes, such as contributions, needs, or individual scores.

One example is the boltzmann-fair-division approach, which applies the Boltzmann distribution from statistical mechanics. In this framework, each participant's share is determined according to an exponential function of their score. The allocation rule is as follows:

:<math>p_i = \frac{\exp(\beta s_i)}{\sum_j \exp(\beta s_j)}</math>

Here, <math>p_i</math> is the share assigned to participant <math>i</math>, <math>s_i</math> is the score or merit of participant <math>i</math>, and <math>\beta</math> is a parameter that controls the balance between equality and merit-based allocation. When <math>\beta = 0</math>, the method reduces to equal division. As <math>\beta</math> increases, the allocation becomes more heavily weighted toward participants with higher scores.

This method seeks to maximize entropy under the constraints given by the participants’ scores, producing allocations that can interpolate between strict equality and strong meritocracy. The probabilistic approach can be applied in various contexts, including the division of divisible or indivisible resources, and can be adjusted to reflect different societal preferences for fairness or efficiency.

Other probabilistic division mechanisms, such as random lotteries or assignment by chance, are also used, particularly in cases involving indivisible goods or when deterministic solutions are difficult to implement.

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–beck-land-division-problem|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.

Procedural requirements 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.

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. 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.

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. 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". 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.

Models of computation Reasoning about the run-time complexity of algorithms requires a model of computation. Several such models are common in the literature:

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 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 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 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:

See also * [[fair-item-allocation]] – a similar problem in which the items to divide are indivisible. Cake sharing - a problem in which a group of agents have to select a single piece of cake, of a given fixed size, which would be available to all'' agents together. * Growing the pie. * [[boltzmann-fair-division]].

References <references />

Further reading * *