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
[edit]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
[edit]The algorithm uses a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n log n).
- Each partner is asked to draw a line dividing the cake into a right and left part such that he believes the ratio is ⌊n/2⌋:⌈n/2⌉. 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, i.e. at the ⌊n/2⌋th line. E.g., if there are 5 partners that draw lines at x=1, x=3, x=5, x=8 and x=9, then the algorithm cuts the cake vertically at x=5.
- The algorithm assigns to each of the two parts the partners whose line is inside that part, i.e. the partners that drew the first ⌊n/2⌋ lines get assigned to the left part, the others to the right part. E.g., the partners that drew lines at x=1, x=3 and x=5 are assigned to the left part and the other partners are assigned to the right part. Each part 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 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
[edit]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
[edit]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
[edit]- ^ 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.
- ^ Sgall, Jiří; 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. pp. 271–278. doi:10.1145/1109557.1109588. ISBN 978-0898716054., Edmonds, Jeff (2011). "Cake cutting really is not a piece of cake". ACM Transactions on Algorithms. 7 (4): 1–12. CiteSeerX 10.1.1.146.1536. doi:10.1145/2000807.2000819. S2CID 2440968.
- ^ 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