Irving's Algorithm (Stable Roommates 1985) — Gale-Shapley & Stable Matching

Choose Example

Controls

Preference Lists

Algorithm Pseudocode

Phase 1 (Proposal-Rejection):
  Repeat:
    Each free person proposes to the
    first on their reduced list.
    Each person holds best proposal,
    rejects rest.
    Remove rejected pairs from lists.
  Until everyone holds exactly one proposal.

  If any list becomes empty: NO STABLE
  MATCHING EXISTS.

Phase 2 (Rotation Elimination):
  While some list has length > 1:
    Find a rotation (p0,q0),(p1,q1),...
    where qi = second on pi's list,
    pi+1 = last on qi's list.
    Remove each (pi, qi) from lists.

  If any list becomes empty: NO STABLE
  MATCHING EXISTS.
  Otherwise: each list has exactly one
  entry = the stable matching.

Step Log

Irving, R.W. (1985). "An Efficient Algorithm for the Stable Roommates Problem." Journal of Algorithms, 6(4), 577–595.