← Gallery

About

Top Trading Cycles (TTC) solves the house allocation problem: each person owns a house and has preferences over all houses. TTC finds a Pareto-efficient, individually rational, strategy-proof allocation through elegant cycle detection.

Algorithm Pseudocode 
While unmatched people remain:
  1. Each person points to the owner
     of their most-preferred
     remaining house
  2. Find all directed cycles
     (at least one must exist)
  3. Execute each cycle: every
     person in the cycle gets the
     house they pointed to
  4. Remove matched people & houses
  Repeat.

Preferences

PersonOwnsPreference Order
1H1H3 > H2 > H4 > H5 > H6 > H1
2H2H1 > H3 > H4 > H5 > H6 > H2
3H3H2 > H1 > H4 > H5 > H6 > H3
4H4H6 > H5 > H1 > H2 > H3 > H4
5H5H4 > H6 > H1 > H2 > H3 > H5
6H6H5 > H4 > H1 > H2 > H3 > H6

Controls

Properties (Roth & Postlewaite 1977)

✓ Pareto Efficient — no one can improve without hurting another
✓ Individually Rational — no one worse off than keeping own house
✓ Strategy-Proof — no one benefits from misreporting preferences
Roth & Postlewaite (1977) proved TTC is the unique mechanism satisfying Pareto efficiency, individual rationality, and strategy-proofness simultaneously. When applied to school choice with "owned endowments" (current school assignment), TTC respects ownership while improving efficiency.

Event Log

Top Trading Cycles

Shapley & Scarf (1974) — House Allocation via Cycle Detection