Last diminisher

The last diminisher procedure is a procedure for fair cake-cutting. It involves a certain heterogenous 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, i.e., divide the cake among them such that person receives a piece with a value of at least 1/n of the total value according to his own subjective valuation. For example, if Alice values the entire cake as $100 and there are 5 partners then Alice can receive a piece that she values as at least $20, regardless of what the other partners think or do.

History

During world war II, the Polish-Jewish mathematician Hugo Steinhaus, who was hiding from the Nazis, occupied himself with the question of how to divide resources fairly. Inspired by the Divide and choose procedure for dividing a cake between two brothers, he asked his students, Stefan Banach and Bronisław Knaster, to find a procedure that can work for any number of people, and published their solution.^[1]

This publication has initiated a new research topic which is now studied by many researchers in different disciplines; see fair division.

Description

This is the description of the division protocol in the words of the author:

"The partners being ranged A, B, C,.. N, A cuts from the cake an arbitrary part. B has now the right, but is not obliged, to diminish the slice cut off. Whatever he does, C has the right (without obligation) to diminish still the already diminished (or not diminished) slice, and so on up to N. The rule obliges the "last diminisher" to take as his part the slice he was the last to touch. This partner being thus disposed of, the remaining n-1 persons start the same game with the remainder of the cake. After the number of participants has been reduced to two, they apply the classical rule for halving the remainder."

Each partner has a method that guarantees that he receives a slice with a value of at least 1/n. The method is: always cut the current slice such that the remainder has a value of 1/n for you. There are two options: either you receive the slice that you have cut, or another person receives a smaller slice, whose value for you is less than 1/n. In the latter case, there are n-1 partners remaining and the value of the remaining cake is more than (n-1)/n. Hence by induction it is possible to prove that the received value is at least 1/n.

Analysis

The last-diminisher protocol is discrete and can be played in turns. In the worst case, $n\times(n-1)/2 = O(n^2)$ actions are needed: one action per player per turn.

However, most of these O(n^2) actions are not actual cuts, i.e. Alice can mark her desired slice on a paper and have the other players diminish them on the same paper etc.; only the "last diminisher" has to actually cut the cake. So, only n-1 cuts are needed.

The procedure is very liberal regarding the cuts. the cuts made by the partners can have any shape; they can even be disconnected. On the other hand, it is possible to restrict the cuts in order to guarantee that the pieces have a nice shape. In particular:

If the original cake is connected, then it is possible to guarantee that each piece is connected (contiguous).
If the original cake is a convex set, then it is possible to guarantee that each piece is convex.
If the original cake is a rectangle, then it is possible to guarantee that each piece is a rectangle.
If the original cake is a triangle, then it is possible to guarantee that each piece is a triangle.

Continuous version

A continuous-time version of this protocol can be executed using the Dubins-Spanier Moving-knife procedure.^[2] It was the first example of a continuous procedure in fair division. The knife is passed over the cake from the left end to the right. Any player may say stop when they think $1 / n$ of the cake is to the left of the knife, the cake is cut and the player who spoke gets that piece. Repeat with the remaining cake and players, the last player gets the remainder of the cake. Similar to the last diminisher procedure, it can be used to cut the cake into contiguous parts for each player.

Approximate-envy-free version

When there are 3 or more partners, the division obtained by the last-diminisher protocol is not always envy-free. For example, suppose the first partner Alice receives a piece (which she values as 1/3 of the total). Then, the other two partners Bob and Charlie divide the remainder in such a way that is fair in their opinion, but in Alice's opinion Bob's share is worth 2/3 while Charlie's share is worth 0. Then Alice envies Bob.

A simple solution^[3] is to allow re-entrance. I.e, a partner that won a piece by being the last diminisher, does not have to leave the game, but may rather stay and participate in further steps. If he wins again, he must release his current piece and it is returned to the cake. In order to make sure that the protocol terminates, we select a certain constant $\epsilon$ and add a rule that allows each partner to re-enter at most $1/\epsilon$ times.

In the reentrant version, each partner has a method that guarantees that he receives a slice with a value of at least the largest value minus $\epsilon$ . The method is: always cut the current slice such that the remainder has a value of $\epsilon$ plus your current value. This guarantees that your value grows by $\epsilon$ each time you win, and if you don't win - the value of the winner is at most $\epsilon$ more than your own value. Thus, the level of envy is at most $\epsilon$ (an additive constant).

The run-time is at most $n^2/\epsilon$ , since there are at most $n/\epsilon$ steps and at each step we query each of the $n$ partners.

A disadvantage of the approximate-envy-free variant is that the pieces are not necessarily connected, since pieces are constantly returned to the cake and re-divided. See envy-free cake-cutting#Connected pieces for other solutions to this problem.

Improvements

The last diminisher procedure has been improved later in many ways. For details, see proportional division.

References

↑ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica.
↑ Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly 68: 1. doi:10.2307/2311357. JSTOR 2311357.
↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division: From cake-cutting to dispute resolution. pp. 130–131. ISBN 0521556449.

This article is issued from Wikipedia - version of the Saturday, January 30, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.