Two-Sided Markets and Matching Theory

Markets Where "Money Isn't Everything"

On most markets, price balances supply and demand. But there are markets where monetary transfers are impossible or undesirable for ethical or legal reasons: allocating students to schools, residents to hospitals, donor organs to patients. Here, mechanisms are needed that provide a "fair" and "stable" allocation without a price signal.

Matching theory is a mathematical tool for such markets. Alvin Roth and Lloyd Shapley received the 2012 Nobel Prize for its development and practical application.

Formal Statement of the Stable Marriage Problem

Given $n$ men $M = {m_1, ..., m_n}$ and $n$ women $W = {w_1, ..., w_n}$. Each man $m_i$ has a strict linear ordering of preferences over $W$; each woman $w_j$ over $M$.

Matching $\mu$: $M \to W \cup {\varnothing}$ — a mutually one-to-one mapping (each gets at most one partner).

Stable matching: $\mu$ is stable if there is no "blocking pair" $(m, w)$ such that $m$ prefers $w$ over his partner $\mu(m)$ AND $w$ prefers $m$ over her partner $\mu(w)$.

A blocking pair is two agents who would both rather be together than with their current partners and would "leave" together—a form of instability meaning the matching won't hold.

Gale–Shapley Algorithm

Version with proposals from men (DA — Deferred Acceptance):

1. Each man proposes to the most preferred woman who hasn't yet rejected him
2. Each woman "defers" (but does not accept!) the best proposal received, rejecting the rest
3. Rejected men proceed to the next woman on their list
4. Iterate until stabilization

Gale–Shapley Theorem (1962): The DA algorithm always terminates in a finite number of steps and returns a stable matching. When proposals are made by men: the result is M-optimal (the best for all men among all stable matchings) and W-pessimal.

Numerical Example (Complete Solution)

3 men ($m_1$, $m_2$, $m_3$), 3 women ($w_1$, $w_2$, $w_3$):

Men's preferences: $m_1$: $w_1 > w_2 > w_3$; $m_2$: $w_1 > w_2 > w_3$; $m_3$: $w_1 > w_2 > w_3$.

Women's preferences: $w_1$: $m_1 > m_2 > m_3$; $w_2$: $m_2 > m_1 > m_3$; $w_3$: $m_3 > m_2 > m_1$.

Round 1: $m_1 \to w_1$ (accepted: best candidate); $m_2 \to w_1$ ($w_1$ compares: $m_1 > m_2$ $\rightarrow$ holds $m_1$, rejects $m_2$); $m_3 \to w_1$ (rejects $m_3$, as $w_1$: $m_1 > m_3$).

Round 2: $m_2 \to w_2$ (accepted); $m_3 \to w_2$ ($w_2$: $m_2 > m_3$ $\rightarrow$ holds $m_2$, rejects $m_3$).

Round 3: $m_3 \to w_3$ (accepted).

Final: $\mu = {m_1-w_1, m_2-w_2, m_3-w_3}$. Let's check stability: $(m_2, w_1)$? $m_2$ prefers $w_1$ ($w_1 > w_2$), but $w_1$ prefers $m_1$ ($m_1 > m_2$) $\rightarrow$ not blocking. $(m_3, w_1)$? $w_1$: $m_1>m_3$ $\rightarrow$ not blocking. The matching is stable ✓.

Strategic Properties

Incentive compatibility: In DA with proposals from men, truth-telling is a dominant strategy for men (no incentive to lie). Women can benefit from strategic manipulation.

Roth's Theorem (1982): There is no stable matching mechanism that is incentive-compatible for both sides. This is a fundamental limitation.

Real Applications

NRMP (USA, medical residents): Since 1952 — a DA-like algorithm. In the 1990s, Roth corrected an issue with couples (joint allocation for pairs). Annually matches ~40,000 residents.

NYC Schools (2003): The unstable "Boston" mechanism was replaced with DA. Stability removed "strategic" applications by parents. ~80,000 students each year.

Kidney Exchange (Roth, 2004): An incompatible donor–recipient pair exchanges with another incompatible pair $\rightarrow$ stable matching, saving lives. Roth devised an algorithm for chains of multiple pairs.

Internet Platforms: Airbnb (host–guest), LinkedIn (employer–candidate), Tinder (mutual match) — online versions of the matching problem.

Nobel Prize 2012: Lloyd Shapley and Alvin Roth received the Nobel Prize in Economics "for the theory of stable allocations and the practice of market design." Roth created algorithms for the medical residency market (NRMP, ~40,000 doctors per year), NYC school placement (~80,000 children annually), and kidney exchange—direct application of abstract mathematical theory to problems affecting hundreds of thousands of people.

Two-Sided Markets: Platform Economy and Strategic Design

Matching theory underpins the platform economy and market design. Uber and Lyft are two-sided markets connecting drivers and passengers: the matching algorithm optimizes the stability of matches in real time, accounting for ratings, distance, and preferences. Labor markets in medicine (US residency—NRMP), law, and academia are organized as stable matchings. The Gale–Shapley algorithm, applied in NRMP since 1952, drastically reduced the number of "unauthorized" direct contracts bypassing the official market—a sign of market instability. Amazon, Airbnb, and other marketplaces tackle the "market thickness" problem—attracting enough participants on both sides so that matchings provide high quality and low market unemployment. In search engine ad auctions, slots are assigned via the generalized second-price auction (GSP), which approximates a stable matching of advertisers to ad slots. Alvin Roth's Nobel Prize (2012) recognized market design using matching theory as a practical contribution to social welfare.

Beyond classic use, the Gale–Shapley algorithm is used in many-to-many markets with constraints: in residency assignment with couples preferences (the couples problem), where two partners want jobs in the same city. This extension makes the problem NP-hard and requires specialized heuristics, used in NRMP since 1997. Decentralized markets (MBA graduate market) without a DA algorithm display typical instability: early offers ("exploding" offers), unraveling, low quality of matches.

Assignment: Solve the stable marriage problem for 3 men and 3 women with the following preferences: $m_1$: $w_2>w_1>w_3$; $m_2$: $w_1>w_3>w_2$; $m_3$: $w_3>w_1>w_2$; $w_1$: $m_2>m_3>m_1$; $w_2$: $m_1>m_2>m_3$; $w_3$: $m_2>m_1>m_3$. Find the M-optimal and W-optimal stable matchings. Do they coincide?