The Even-Paz algorithm is an computationally-efficient algorithm for fair cake-cutting. It involves a certain heterogeneous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to achieve a proportional division.
Contents
History
The first published algorithm for proportional division of a cake was the Last diminisher algorithm, published in 1948. Its run-time complexity was O(n^2). in 1984, Shimon Even and Azaria Paz published their improved algorithm, whose run-time complexity is only O(n log n).
Description
The algorithm uses 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:
It is possible to prove by induction that every partner playing by the rules is guaranteed a piece with a value of at least 1/n, regardless of what the other partners do.
Thanks to the divide-and-conquer 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).
Optimality
Several years after the publication of the Even-Paz algorithm, it was proved that 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) actions, even if the procedure is allowed to assign to each partner a non-contiguous piece, and even if the procedure is allowed to only guarantee approximate fairness.
These hardness results imply that the Even-Paz algorithm 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; see Edmonds-Pruhs algorithm.
Randomized version
It is possible to use randomization in order to reduce the number of marks. The following randomized version of the recursive halving procedure achieves a proportional division using only O(n) mark queries on average. The idea is that, in each iteration, instead of asking all partners to make a half-value mark, only some partners are asked to make such marks, while the other partners only choose which half they prefer. The partners are sent either to the west or to the east according to their preferences, until the number of partners in each side is n/2. Then a cut is made, and each group of n/2 partners divides its half recursively.
In the worst case we still need n-1 marks per iteration so the worst-case number of marks required is O(n log n). However, on average only O(log n) marks are required per iteration; by solving a recurrence formula it is possible to show that the average number of marks required is O(n).
Note that the total number of queries is still O(n log n), since each partner has to select a half.