Even–Paz protocol
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.
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).[1]
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:
- 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 n/2 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 western half and the other two partners are assigned to the eastern half. Each half is divided recursively among the n/2 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 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.[2]
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.[3]
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.[1] 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.[4]
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.
References
- ^ a b Even, S.; Paz, A. (1984). "A note on cake cutting". Discrete Applied Mathematics. 7 (3): 285. doi:10.1016/0166-218x(84)90005-2.
- ^ Woeginger, Gerhard J. (2007). "On the complexity of cake cutting". Discrete Optimization. 4 (2): 213–220. doi:10.1016/j.disopt.2006.07.003.
- ^ Edmonds, Jeff (2006). "Cake cutting really is not a piece of cake". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. doi:10.1145/1109557.1109588., Edmonds, Jeff (2011). "Cake cutting really is not a piece of cake". ACM Transactions on Algorithms. 7 (4): 1–12. doi:10.1145/2000807.2000819.
- ^ This randomized recursive halving algorithm is similar to a well-known randomized algorithm for Ranking - finding the r-ranked element in an array of numbers