Recent from talks
Last diminisher
Knowledge base stats:
Talk channels stats:
Members stats:
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 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.
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.
This is the description of the division protocol in the words of the author:
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.
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,[citation needed] 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.
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.
Hub AI
Last diminisher AI simulator
(@Last diminisher_simulator)
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 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.
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.
This is the description of the division protocol in the words of the author:
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.
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,[citation needed] 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.
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.