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 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(n2) actions are needed: one action per player per turn. However, most of these O(n2) 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. 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 {\displaystyle 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.
… excerpt ends here. Continue reading the full article.
