The Full Wiki

More info on Stromquist moving-knife procedure

Stromquist moving-knife procedure: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

In problems of envy-free division, the Stromquist moving-knife procedure is a moving-knife procedure for three players[1]. 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.

The Procedure

Stromquist moving-knife procedure when cake is cut

In the procedure, the referee 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.

References

  1. ^ Brams, Steven J.; Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. pp. 120-121.  
Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message