Even–Paz protocol
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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.
The algorithm sorts the n lines in increasing order and cuts the cake in the median of the lines, i.e. at the \lfloor n/2\rfloor 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 \lfloor n/2\rfloor 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) .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1325621559 under CC BY-SA 4.0; modifications have been made.