Stromquist moving-knife procedure
Encyclopedia
In problems of envy-free division
, the Stromquist moving-knife procedure is a moving-knife procedure
for three players. It is named after Walter Stromquist who presented it in 1980.
This procedure was the first envy-free moving knife procedure devised for three players. It is not necessarily efficient
. It requires only two cuts, the minimum for three pieces. There is no natural generalization to more than three players which divides the cake without extra cuts.
begins with his knife at the left hand side of the cake; the referee then draws the knife across the cake, from left to right. Each of the three players holds a knife, parallel to the referee's, at a position which he thinks halves the portion of the cake to the right of the referee's knife.
Any player may call "cut" at any time: the player who calls receives the part of the cake to the left of the referee's knife. The cake is then cut by the middle player's knife (that is, the knife that is second in order from the referee's). Of the two other (i.e, non-calling) players, the one whose knife is closest to the referee's gets the middle piece, and the other player gets the rightmost piece.
The optimal strategy for each player before cut is called is to ensure that if anyone else says cut they receive as large as possible a division. Placing their knife so it divides the portion to the right of the referee's knife in two according to them ensures this. There is no point them saying cut until they judge the piece on the left of the referee's knife is as big to the bit they would get anyway from someone else saying cut. They should say cut when there is equality otherwise the piece on the left could be claimed by someone else and it could be larger than they would get from the division of the piece to the right of the referee's knife.
Following their optimal strategy each person will get the largest or one of the largest pieces by their own valuation and therefore the division is envy free.
Envy-free
In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....
, the Stromquist moving-knife procedure is a moving-knife procedure
Moving-knife procedure
In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. The canonical example is the division of a cake using a knife....
for three players. It is named after Walter Stromquist who presented it in 1980.
This procedure was the first envy-free moving knife procedure devised for three players. It is not necessarily efficient
Efficiency (economics)
In economics, the term economic efficiency refers to the use of resources so as to maximize the production of goods and services. An economic system is said to be more efficient than another if it can provide more goods and services for society without using more resources...
. It requires only two cuts, the minimum for three pieces. There is no natural generalization to more than three players which divides the cake without extra cuts.
The Procedure
In the procedure, the refereeReferee
A referee is the person of authority, in a variety of sports, who is responsible for presiding over the game from a neutral point of view and making on the fly decisions that enforce the rules of the sport...
begins with his knife at the left hand side of the cake; the referee then draws the knife across the cake, from left to right. Each of the three players holds a knife, parallel to the referee's, at a position which he thinks halves the portion of the cake to the right of the referee's knife.
Any player may call "cut" at any time: the player who calls receives the part of the cake to the left of the referee's knife. The cake is then cut by the middle player's knife (that is, the knife that is second in order from the referee's). Of the two other (i.e, non-calling) players, the one whose knife is closest to the referee's gets the middle piece, and the other player gets the rightmost piece.
Analysis
In order to show that the procedure is envy-free one has to show that each player believes that - according to his measure - no other player received more than him.The optimal strategy for each player before cut is called is to ensure that if anyone else says cut they receive as large as possible a division. Placing their knife so it divides the portion to the right of the referee's knife in two according to them ensures this. There is no point them saying cut until they judge the piece on the left of the referee's knife is as big to the bit they would get anyway from someone else saying cut. They should say cut when there is equality otherwise the piece on the left could be claimed by someone else and it could be larger than they would get from the division of the piece to the right of the referee's knife.
Following their optimal strategy each person will get the largest or one of the largest pieces by their own valuation and therefore the division is envy free.