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 of the total.
Two assumptions are typically made when proportional division is discussed: The valuations of the partners are non-atomic, i.e., there are no indivisible elements with positive value. The valuations of the partners are additive, i.e., when a piece is divided, the value of the piece is equal to the sum of its parts.
Formal definitions 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 .
Procedures
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 two people. Each way has its own advantages and disadvantages.
Simple procedures
The last diminisher procedure is the earliest proportional division procedure developed for n people: One of the partners is asked to draw a piece which he values as at least . The other partners in turn have the option to claim that the current piece is actually worth more than ; in that case, they are asked to diminish it such that the remaining value is according to their own valuation. The last partner to diminish the current piece, receives it. The remaining cake is then divided in the same way among the remaining people. By induction, it is possible to prove that each partner following the rules is guaranteed to get a value of , 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 cuts of the cake are actually needed. Hence, it is possible for all the pieces to be contiguous under certain circumstances.
The moving-knife procedure is a continuous-time version of last diminisher procedure. A knife is passed over the cake, perpendicular to the direction of travel, from left end toward the right end. Any person says 'stop' when they think that of the cake is to the left of the knife. (The call stops the knife at what the caller thinks is fair and any delay in calling would allow the other to take what would by then have grown to be too much.) Then the cake is cut and they get that piece. This is repeated with the remaining cake and partners. The last partner gets the remainder of the cake.
The Fink protocol is an algorithm that continues the division into successively smaller "equal" portions. The first partner divides the resource into what they believe are equal halves. The second then chooses a half, leaving the remainder for the first partner. Each of these two partners then divide their respective portions into thirds. The third partner picks two of the resulting portions: one from the first partner and one from the second partner. If there are four partners, each of the first three partners divides their portions into fourths, and the process continues. The advantage of this protocol is that it can be executed online – as new partners enter the party, the existing division is adjusted to accommodate them, without needing to restart the entire division process. The disadvantage is that the each partner receives a large number of disconnected pieces rather than a single connected piece.
The lone divider procedure is based on an equal partition made by a single agent. Its advantage is that it can be generalized to yield a symmetric fair cake-cutting.
Recursive halving
Using a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n log n). For simplicity the procedure is described here for an even number of partners, but it can be easily adapted to any number of partners:
Each partner is asked to draw a line dividing the cake to two pieces that he believes to be of equal value. The cuts are required to be non-intersecting; a simple way to guarantee this is to allow only horizontal lines or only vertical lines. The algorithm sorts the n lines in increasing order and cuts the cake in the median of the lines. E.g., if there are 4 partners that draw lines at x = 1, x = 3, x = 5 and x = 9, then the algorithm cuts the cake vertically at x = 4. The algorithm assigns to each of the two halves partners – the partners whose line is inside that half. E.g., the partners that drew lines at x = 1 and x = 3 are assigned to the left half and the other two partners are assigned to the right half. Each half is divided recursively among the partners assigned to it.
It is possible to prove by induction that every partner playing by the rules is guaranteed a piece with a value of at least , regardless of what the other partners do.
Thanks to the divide-and-choose strategy, the number of iterations is only O(log n), in contrast to O(n) in the last diminisher procedure. In each iteration, each partner is required to make a single mark. Hence, the total number of marks required is O(n log n).
This algorithm has a randomized version which can be used to reduce the number of marks; see Even-Paz algorithm.
Selection procedures
A different approach to cake-cutting is to let each of the n partners draw n pieces, and give each partner one of his pieces such that the selected pieces do not overlap.
As a simple example of a selection procedure, assume the cake is a 1-dimensional interval and that each partner wants to receive a single contiguous interval. Use the following protocol: Each partner privately partitions the cake into n intervals that he considers to be of equal value; these are called candidate pieces. The protocol orders the candidate pieces by increasing order of their right endpoint (moving from left to right), and selects the interval with the leftmost right endpoint. This interval is called a final piece. The protocol gives the final piece to its owner and remove all candidates intersected by it. Step 2 is then repeated with the remaining intervals of the remaining partners. The selection rule in step 2 guarantees that, at each iteration, at most one interval of every partner is removed. Hence, after each iteration the number of intervals per partners is still equal to the number of partners, and the process can proceed until every partner receives an interval.This selection procedure is similar to Earliest deadline first scheduling)
This protocol requires each partner to answer n queries, so the query complexity is O(n2), similarly to the last diminisher procedure.
Randomized versions
Randomization can be used to reduce the number of queries. The idea is that each partner reports, not the entire collection of n candidates, but only a constant number d of candidates, picked at random. The query complexity is O(n), which is the best possible. In many cases, it will still be possible to give each partner a single candidate such that the candidates do not overlap. However, there are scenarios in which such an allocation will be impossible.
We can still cut a cake using O(n) queries if we make several compromises: Instead of guaranteeing full proportionality, we guarantee partial proportionality, i.e. each partner receives a certain constant fraction of the total value, where . Instead of giving each partner a single contiguous piece, we give each partner a union of one or more disjoint pieces.
The general scheme is as follows: Each partner privately partitions the cake into pieces of equal subjective value. These pieces are called candidate pieces. Each partner picks 2d candidate pieces uniformly at random, with replacement. The candidates are grouped into d pairs, which the partner reports to the algorithm. These pairs are called quarterfinal brackets. From each quarterfinal bracket, the algorithm selects a single piece – the piece that intersects the fewer number of other candidate pieces. These pieces are called semifinal pieces. For each partner, the algorithm selects a single piece; they are called final pieces. The final pieces are selected such that each point of the cake is covered by at most 2 final pieces (see below). If this succeeds, proceed to step #5. If this fails, start over at step #1. Each part of the cake which belongs to only a single final piece, is given to the owner of that piece. Each part of the cake which belongs to 2 final pieces, is divided proportionally by any deterministic proportional division algorithm.
The algorithm guarantees that, with probability O(1a2), each partner receives at least half of one of his candidate pieces, which implies (if the values are additive) a value of at least . There are O(n) candidate pieces and O(n) additional divisions in step #5, each of which takes O(1) time. Hence the total run-time of the algorithm is O(n).
The main challenge in this scheme is selecting the final pieces in step #4. For details, see Edmonds–Pruhs protocol.
Hardness results The hardness results are stated in terms of the Robertson–Webb query model, i.e., they relate to procedures asking the agents two types of queries: "Evaluate" and "Mark".
Every deterministic proportional division procedure for partners must use at least n queries, even if all valuations are identical.
Moreover, every deterministic or randomized proportional division procedure assigning each person a contiguous piece must use Ω(n log n) actions.
Moreover, every deterministic proportional division procedure must use Ω(n log n) queries, even if the procedure is allowed to assign to each partner a piece that is a union of intervals, and even if the procedure is allowed to only guarantee approximate fairness. The proof is based on lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width.,
These hardness results imply that recursive halving is the fastest possible algorithm for achieving full proportionality with contiguous pieces, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even with disconnected pieces. The only case in which it can be improved is with randomized algorithms guaranteeing partial proportionality with disconnected pieces.
If the players are able to cut with only finite precision, then the Ω(n log n) lower bound also includes randomized protocols.
The following table summarizes the known results:
Proportionality(full/partial) Pieces(contiguous/disjoint) Protocol type(deterministic/randomized) Queries(exact/approximate) #queries full contiguous det. exact O(n log n)Ω(n log n) full contiguous det. approximate Ω(n log n) full contiguous rand. exact O(n log n)Ω(n log n) full contiguous rand. approximate Ω(n log n) full disconnected det. exact O(n log n)Ω(n log n) full disconnected det. approximate Ω(n log n) full disconnected rand. exact O(n log n) full disconnected rand. approximate Ω(n log n) partial contiguous det. exact O(n log n)Ω(n log n) partial contiguous det. approximate Ω(n log n) partial contiguous rand. exact O(n log n) partial contiguous rand. approximate Ω(n log n) partial disconnected det. exact O(n log n)Ω(n log n) partial disconnected det. approximate Ω(n log n) partial disconnected rand. exact O(n) partial disconnected rand. weakly approx. (error independentof value) O(n) partial disconnected rand. approximate Ω(n log n)
Variants
Different entitlements