The Robertson–Webb rotating-knife procedure is a procedure for envy-free cake-cutting of a two-dimensional cake among three partners.[1]: 77–78  It makes only two cuts, so each partner receives a single connected piece.

Its main advantage over the earlier Stromquist moving-knives procedure and the later Barbanel–Brams moving-knives procedure is that it requires only a single moving-knife. This advantage uses the two-dimensional nature of the cake.

Procedure

Initially, each partner makes a vertical cut such that the cake to its left is worth for him exactly 1/3. The leftmost cut is selected. Suppose this cut belongs to Alice. So Alice receives the leftmost piece and her value is exactly 1/3. The remainder has to be divided between the remaining partners (Bob and Carl).

Note that Alice's part is worth at most 1/3 and the remainder is worth at least 2/3 for Bob and Carl. So, if Bob and Carl each receive at least half of the remainder, they do not envy. The challenge is to make sure Alice won't envy any of them.

The solution is based on the following observation: For each angle , Alice can put a knife in angle and cut the remainder to two halves equal in her eyes. This means that Alice can rotate a knife over the remainder such that the parts from the two sides of the knife are always equal in her eyes.

When the knife is at angle 0, Bob (weakly) prefers either the piece above the knife or the piece below the knife; when the knife is at angle 180, the pieces are reversed. Hence, by the intermediate value theorem, there must be an angle in which Bob thinks the pieces from both sides of the knife are equal. At this angle, Bob shouts "stop!". The cake is cut, Carl chooses a piece and Bob receives the other piece.

Analysis

Alice does not envy because for her, all three pieces are worth exactly 1/3.

Bob and Carl do not envy Alice because her piece is worth at most 1/3 and their piece at least (1/2)*(2/3) = 1/3.

Bob does not envy Carl because their pieces are equal in his eyes; Carl does not envy Bob because he picked the best piece in his eyes.

Dividing a 'bad' cake

The rotating-knife procedure can be adapted for chore division - dividing a cake with a negative value:[1]: exercise 5.10  in the initial step, The rightmost cut should be selected, instead of the leftmost cut.

See also

References

  1. 1 2 Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.