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 each 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.
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".
Degenerate case of a common preference function.
The algorithm simplifies in the degenerate case that all partners have the same preference function because the partner that optimally first cuts a slice will also be its last diminisher. Equivalently, each partner 1, 2, ..., "n"−1 in turn cuts a slice from the remaining cake. Then in reverse order, each partner "n", "n"−1, ..., 1 in turn selects a slice that has not yet been claimed. The first partner who cut a slice other than of value 1/"n" would be envious of another partner who ended up with more than they did.
Analysis.
The last-diminisher protocol is discrete and can be played in turns. In the worst case, "n" × (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:
Continuous version.
A continuous-time version of this protocol can be executed using the Dubins-Spanier Moving-knife procedure. 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 formula_1 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 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 formula_2 and add a rule that allows each partner to re-enter at most formula_3 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 formula_2. The method is: always cut the current slice such that the remainder has a value of formula_2 plus your current value. This guarantees that your value grows by formula_2 each time you win, and if you don't win - the value of the winner is at most formula_2 more than your own value. Thus, the level of envy is at most formula_2 (an additive constant).
The run-time is at most formula_9, since there are at most formula_10 steps and at each step we query each of the formula_11 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.
 ;templatestyles src="Reflist/styles.css" / ;