Fair cake-cutting
Fair cake-cutting is a kind of fair division problem.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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, e.g., 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 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.…
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, e.g., 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 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. 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 X_i , and C = X_1 \cup \cdots \cup X_n . 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. \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: \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: \forall i,j:\ V_i(X_j) = 1/n p_i = \frac{\exp(\beta s_i)}{\sum_j \exp(\beta s_j)} Here, p_i is the share assigned to participant i , s_i is the score or merit of participant i , and \beta is a parameter that controls the balance between equality and merit-based allocation. When \beta = 0 , the method reduces to equal division.
As \beta 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.
A stronger notion is utilitarian-maximality – maximizing the sum of utilities. (UM). When the value functions are additive, 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 allocations follows from classic measure-theoretic theorems. See Utilitarian cake-cutting.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373717180 under CC BY-SA 4.0; modifications have been made.