Stromquist Moving Knife Procedure

The first envy-free moving knife procedure for three players

3 Players Continuous $\infty$ RW Queries

Overview

The Stromquist moving knife procedure, introduced by Walter Stromquist in 1980, was the first envy-free moving knife procedure devised for three players. This procedure was the first envy-free moving knife procedure devised for three players. It represents a landmark achievement in fair division theory, solving a problem that had remained unsolved for several decades.

The procedure uses four knives simultaneously—one sword controlled by a referee and three knives controlled by the players—but requires only two cuts, ensuring each player receives a single connected piece. It requires four knives but only two cuts, so each player receives a single connected piece.

Algorithm Flowchart

Fairness Properties

Envy-Free

Guaranteed: Following this strategy each person gets the largest or one of the largest pieces by their own valuation and therefore the division is envy-free.

Proof Sketch ▶

For the "Quieters" (non-shouting players): Each of them receives a piece that contains their own knife, so they do not envy each other. Additionally, because they remained quiet, the piece they receive is larger in their eyes than Left, so they also don't envy the shouter.

For the "Shouter": The shouter receives Left, which is equal to the piece they could receive by remaining silent and larger than the third piece, hence the shouter does not envy any of the quieters.

Strategy-Proof

Guaranteed: Truthful play (following the prescribed strategy) is optimal for each player, regardless of what others do.

Historical Significance

The Stromquist procedure holds a unique place in fair division history:

• Breakthrough Result: This problem was unsolved for several tens of years, until Stromquist (1980) suggested the following division protocol
• First Envy-Free Solution: Solved the long-standing problem of envy-free division for three players with connected pieces
• Methodological Innovation: Introduced the multi-knife coordination approach that influenced subsequent algorithms
• Theoretical Foundation: Provided key insights that led to later impossibility results and complexity understanding

Theoretical Impact

Stromquist's work went beyond this single procedure. His later research (Stromquist, 2008) proved that finite protocols cannot achieve envy-free division with connected pieces for three or more players—establishing fundamental limits in computational fair division.