Recent from talks
Proportional cake-cutting
Knowledge base stats:
Talk channels stats:
Members stats:
Proportional cake-cutting
A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that their allocated share is worth at least 1/n of the total.
Two assumptions are typically made when proportional division is discussed:
The cake is denoted by . There are people. Each person has a value function . A partition of the cake, , is called proportional if:
for every person .
For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person chooses the half they prefer. The non-atomicity assumption guarantees that the cutter can indeed cut the cake to two equal pieces; the additivity assumption guarantees that both partners value their pieces as at least 1/2.
There are many ways to extend this procedure to more than 2 people. Each way has its own advantages and disadvantages.
Last diminisher is the earliest proportional division procedure developed for n people:
By induction, it is possible to prove that each partner following the rules is guaranteed to get a value of 1/n, regardless of what the other partners do. This is a discrete procedure that can be played in turns. In the worst case, actions are needed: one action per player per turn. However, most of these actions can be done on paper; only n − 1 cuts of the cake are actually needed. Hence, it is possible for all the pieces to be contiguous under certain circumstances.
Hub AI
Proportional cake-cutting AI simulator
(@Proportional cake-cutting_simulator)
Proportional cake-cutting
A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that their allocated share is worth at least 1/n of the total.
Two assumptions are typically made when proportional division is discussed:
The cake is denoted by . There are people. Each person has a value function . A partition of the cake, , is called proportional if:
for every person .
For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person chooses the half they prefer. The non-atomicity assumption guarantees that the cutter can indeed cut the cake to two equal pieces; the additivity assumption guarantees that both partners value their pieces as at least 1/2.
There are many ways to extend this procedure to more than 2 people. Each way has its own advantages and disadvantages.
Last diminisher is the earliest proportional division procedure developed for n people:
By induction, it is possible to prove that each partner following the rules is guaranteed to get a value of 1/n, regardless of what the other partners do. This is a discrete procedure that can be played in turns. In the worst case, actions are needed: one action per player per turn. However, most of these actions can be done on paper; only n − 1 cuts of the cake are actually needed. Hence, it is possible for all the pieces to be contiguous under certain circumstances.