Skip to main content
World School·Wonder·Honor-system

Stable Three-Dimensional Matching

Two-sided matching is solved. Three-sided matching is NP-hard. No stable solution guaranteed.

Play It

Characterization

In 1962, David Gale and Lloyd Shapley published "College Admissions and the Stability of Marriage," in which they proved that a stable matching — one in which no pair of agents would prefer to abandon their assigned partners for each other — always exists in a two-sided market and can be found by the deferred acceptance algorithm. The result transformed market design: Alvin Roth applied it to the National Resident Matching Program, school choice in New York and Boston, and kidney exchange, and shared the 2012 Nobel Memorial Prize with Shapley. But extend the problem to three sides — doctors, hospitals, and cities; students, courses, and time slots; workers, firms, and locations — and everything breaks. In three-dimensional stable matching, no stable solution is guaranteed to exist. The problem was shown to be NP-hard by Subramanian (1994) and others, meaning that even determining whether a stable three-sided matching exists is computationally intractable. Real-world multi-sided markets cope through a patchwork of heuristics, two-stage processes, and institutional workarounds, but no general theory of stable multi-dimensional matching exists. The Academy hosts this Wonder in the World School because it marks the exact boundary where the elegant theory of matching — one of game theory's greatest successes — meets a wall that no one has found a way around.

Lineage

David Gale and Lloyd Shapley, "College Admissions and the Stability of Marriage," American Mathematical Monthly 69(1), 1962. Alvin Roth, "The Evolution of the Labor Market for Medical Interns and Residents," Journal of Political Economy 92(6), 1984. Nobel Prize 2012 to Shapley and Roth. Ashish Subramanian, "A New Approach to Stable Matching Problems," SIAM Journal on Computing 23(4), 1994. Chien-Chung Huang, "Two's Company, Three's a Crowd," FOCS, 2007. Péter Biró and Eric McDermid, "Three-Sided Stable Matchings with Cyclic Preferences," Algorithmica 58(1), 2010.

Quests

Three quests — one for each archetype. Choose the one that fits your way of taking up the discipline.

  • Construct a three-sided matching instance — at least three agents on each of three sides — with ordinal preferences. Attempt to find a stable matching (one in which no triple of agents, one from each side, would all prefer to be matched together over their current assignments). If no stable matching exists, exhibit the blocking triple that proves instability. If one exists, verify its stability. Reflect on what makes the three-sided case structurally different from the two-sided case.

    No attestations yetOpen →
  • Run the Gale-Shapley deferred acceptance algorithm by hand or in simulation for a two-sided matching instance with at least five agents on each side. Then attempt to extend the procedure to a three-sided instance with at least three agents per side. Record where the algorithm succeeds, where it fails, and the moment at which the two-sided logic breaks down. The exercise is designed to be felt, not just computed.

    No attestations yetOpen →
  • Explain the achievement of Gale and Shapley's 1962 theorem, the practical success of stable matching in the NRMP and school choice (Roth's work), and then explain why the extension to three-sided matching fails — why stable matchings need not exist and why the decision problem is NP-complete. Cite Gale and Shapley, Roth, and at least one paper on three-dimensional instability.

    No attestations yetOpen →