Selfridge-Conway Procedure

3 Players Discrete 7-17 RW Queries

Overview

Though neither Selfridge or Conway every actually published this fundamental envy-free procedure for three players, they both discovered it independently, laying the way for the publication of more complex envy-free procedures.

Read more →

Algorithm Flowchart

Fairness Properties

The Selfridge-Conway procedure satisfies one fundamental fairness property:

Envy-freeness

No player prefers any other player's final allocation to their own.

Formal Statement: $\forall i,j \in \{1,2,3\}, v_i(\text{allocation}_i) \geq v_i(\text{allocation}_j)$

Proof Structure: We prove envy-freeness by analyzing each phase separately and showing that no envy is created in either phase.

Phase 1 Analysis (Main Pieces):

  • Player 1 (Divider): Cannot envy others because they created three pieces they value equally. Regardless of which piece they receive, it equals 1/3 of their total valuation.
  • Player 2 (Trimmer): Cannot envy others because after trimming, they ensured at least two pieces were tied for largest in their view. Player 2 either chooses first (if Player 3 took the trimmed piece) or gets one of their top two pieces.
  • Player 3 (First Chooser): Cannot envy others because they chose first from all available pieces, selecting their most preferred option.

Key Constraint: If Player 3 doesn't choose the trimmed piece, Player 2 must take it. This ensures Player 2 still gets a piece they consider tied for best.

Phase 2 Analysis (Trimmings): Let $T$ be the player who received the trimmed piece and $NT$ be the other non-divider.

  • Player $T$: Chooses first from the trimming pieces, so they get their preferred share of the trimmings.
  • Player 1 (Divider): Has "irrevocable advantage" over player $T$. Since the trimmed piece plus trimmings equals an original piece that Player 1 valued at 1/3, Player 1 will never envy player $T$ regardless of how the trimmings are divided.
  • Player $NT$: Cut the trimmings into three equal pieces from their perspective, so they cannot envy the piece they receive.

Domination Principle: The crucial insight is that Player 1 "dominates" player $T$ with respect to the trimmings. Player 1 would not envy player $T$ even if player $T$ received all the trimmings, because trimmed piece + trimmings = original piece ≤ 1/3 in Player 1's valuation.

Conclusion: Since no player envies any other in either phase, and the phases exhaust all the cake, the final allocation is envy-free.