5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文

Chapter 6 Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth

Markets without prices

The “markets” of the earlier chapters share one feature: each person chooses a road, a niche or an item, and the chosen side does not refuse. Many important markets are not like this. Hospitals choose doctors and doctors choose hospitals; schools admit students and students choose schools; brands look for creators to work with and creators choose brands. In such two-sided matching markets a deal cannot be completed by price alone on one side; both sides must be willing.

These markets commonly fail in three ways. The first is instability: of two matched pairs, one member of each would rather work with the other, so both break their agreements and re-pair; such a pair is called a blocking pair. The second is early contracting (unravelling): to lock in good partners before anyone else, participants make offers earlier and earlier, deciding when they know very little. The third is congestion: too many offers and too little time to decide, so the market cannot clear.

Evidence

Early contracting and the centralised match for doctors. In 1984 Roth studied the history of the American market for medical interns: in the 1940s hospitals competed to hire earlier and earlier, with offers sometimes made two years before the internship began; a centralised matching procedure was set up in the early 1950s, and Roth showed that its algorithm is equivalent to the Gale–Shapley algorithm with hospitals proposing, so that it produces stable matchings, which can explain why it survived (Roth 1984). In 1994 Roth and Xing compared the advancing timing of transactions in many markets and discussed the conditions that cause unravelling and the institutions used to counter it (Roth and Xing 1994). In 1999 Roth and Peranson redesigned the algorithm of the US National Resident Matching Program, switching to applicants as proposers and handling practical constraints such as couples applying together (Roth and Peranson 1999). In 2003 Niederle and Roth studied the gastroenterology specialty: after it left the centralised match, hiring moved earlier and doctors’ mobility between hospitals fell (Niederle and Roth 2003).

Evidence

The 2012 Nobel Memorial Prize in Economic Sciences. The 2012 prize was awarded to Roth and Shapley “for the theory of stable allocations and the practice of market design”; the prize committee noted that the redesigns of doctor matching and school admissions in which Roth took part were all based on the Gale–Shapley algorithm (Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences 2012). Gale had died in 2008.

The deferred-acceptance algorithm

Calculation

There are nn proposers (for example, doctors) and nn receivers (for example, hospitals); each ranks every member of the other side in a strict order of preference.

Deferred acceptance (Gale and Shapley 1962): each proposer not currently held applies to the most preferred receiver on his list who has not yet rejected him; each receiver, among all who apply to him, “provisionally” keeps only the one he likes best and rejects the rest; those rejected apply to the next receiver on their lists. When no one is rejected any more, the provisional acceptances become the final matching (Gale and Shapley 1962).

Acceptance is “deferred”: the person a receiver holds may be replaced at any time by a better applicant, so the receiver need not make a final decision while he knows little.

Evidence

Properties of the algorithm. Gale and Shapley proved that the algorithm always ends in finitely many steps, that the result is always stable (no blocking pair), and that for the proposers it is the best of all stable matchings: each proposer’s partner is no worse than any partner he could have in any other stable matching (Gale and Shapley 1962). The same matching is the worst of all stable matchings for the receivers, and the order in which proposers apply does not affect the result (Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences 2012).

Calculation

# Deferred acceptance (Gale & Shapley 1962) and the set of all stable matchings.
# Proposers and receivers each rank everyone on the other side. Checks on 500 random 6 x
# 6 markets: the result is stable; every proposer gets her best partner among ALL stable
# matchings; every receiver gets his worst; and the order in which proposers move does
# not matter.
import itertools, random
rng = random.Random(12)

def deferred_acceptance(P, R, order=None):
    """P[i] = proposer i's ranking of receivers, R[j] = receiver j's ranking of proposers.
    Returns match[i] = receiver matched to proposer i."""
    n = len(P)
    rank = [{p: k for k, p in enumerate(R[j])} for j in range(n)]
    nxt, held, free = [0] * n, {}, list(order if order else range(n))
    while free:
        i = free.pop(0); j = P[i][nxt[i]]; nxt[i] += 1
        if j not in held: held[j] = i
        elif rank[j][i] < rank[j][held[j]]: free.append(held[j]); held[j] = i
        else: free.append(i)
    match = [None] * n
    for j, i in held.items(): match[i] = j
    return match

def blocking_pairs(match, P, R):
    n = len(P); partner = {j: i for i, j in enumerate(match)}
    return [(i, j) for i in range(n) for j in range(n) if match[i] != j
            and P[i].index(j) < P[i].index(match[i])
            and R[j].index(i) < R[j].index(partner[j])]

def all_stable(P, R):
    return [list(m) for m in itertools.permutations(range(len(P)))
            if not blocking_pairs(m, P, R)]

def market(n):
    P = [rng.sample(range(n), n) for _ in range(n)]
    R = [rng.sample(range(n), n) for _ in range(n)]
    return P, R

ok = {"stable": 0, "proposer-best": 0, "receiver-worst": 0, "order-free": 0}
counts = {}
for _ in range(500):
    P, R = market(6)
    m = deferred_acceptance(P, R)
    S = all_stable(P, R)
    counts[len(S)] = counts.get(len(S), 0) + 1
    ok["stable"] += not blocking_pairs(m, P, R)
    ok["proposer-best"] += all(P[i].index(m[i]) == min(P[i].index(s[i]) for s in S)
                               for i in range(6))
    inv = lambda mm: {j: i for i, j in enumerate(mm)}
    ok["receiver-worst"] += all(R[j].index(inv(m)[j])
                                == max(R[j].index(inv(s)[j]) for s in S)
                                for j in range(6))
    ok["order-free"] += all(deferred_acceptance(P, R, rng.sample(range(6), 6)) == m
                            for _ in range(5))
print("500 random 6 x 6 markets:\n   " + ", ".join(f"{k} {v}/500" for k, v in ok.items()))
print("number of stable matchings per market: "
      + ", ".join(f"{k}: {counts[k]}" for k in sorted(counts)))
# A small market with three stable matchings: which side proposes decides who is
# favoured.
P = [[0, 1, 2], [1, 2, 0], [2, 0, 1]]           # proposer i likes receiver i best
R = [[1, 2, 0], [2, 0, 1], [0, 1, 2]]           # receiver j likes proposer j + 1 best
mp = deferred_acceptance(P, R); mr = deferred_acceptance(R, P)
mr = [mr.index(i) for i in range(3)]              # rewrite as proposer i -> receiver
for lab, m in (("proposers propose", mp), ("receivers propose", mr)):
    print(f"3 x 3, {lab}: {m}; ranks: proposers "
          f"{[P[i].index(m[i]) + 1 for i in range(3)]}, receivers "
          f"{[R[m[i]].index(i) + 1 for i in range(3)]}")
print(f"   all stable matchings (proposer i -> receiver): {all_stable(P, R)}")
# 500 random 6 x 6 markets:
#    stable 500/500, proposer-best 500/500, receiver-worst 500/500, order-free 500/500
# number of stable matchings per market: 1: 183, 2: 204, 3: 78, 4: 25, 5: 7, 6: 2, 8: 1
# 3 x 3, proposers propose: [0, 1, 2]; ranks: proposers [1, 1, 1], receivers [3, 3, 3]
# 3 x 3, receivers propose: [2, 0, 1]; ranks: proposers [3, 3, 3], receivers [1, 1, 1]
#    all stable matchings (proposer i -> receiver): [[0, 1, 2], [1, 2, 0], [2, 0, 1]]

The program checks these properties one by one on 500 random 6 × 6 markets: every result is stable; every proposer gets his best partner among all stable matchings (found by enumerating all 720 pairings); every receiver gets his worst; and shuffling the order of applications five times never changes the result. There is often more than one stable matching: only 183 of the 500 markets have a unique one, 204 have two, and one market has eight.

The final 3 × 3 example shows how much “who proposes” matters. Proposer ii likes receiver ii best, and receiver jj likes proposer j+1j + 1 best. When the proposers propose, every proposer gets his first choice and every receiver his last; when the receivers propose, the reverse. Between the two lies a third stable matching in which everyone gets his second choice. All three are stable; which one the algorithm picks depends on which side the rules let speak first.

Who can gain by lying?

Evidence

Truth-telling is dominant for proposers. In 1981 Dubins and Freedman proved that in the men-proposing Gale–Shapley algorithm, no man and no group of men can misstate preferences so as to make each of them strictly better off (Dubins and Freedman 1981). In 1982 Roth proved results in both directions: no mechanism that always produces a stable matching makes truthful reporting a dominant strategy for everyone; but in a mechanism that produces one side’s optimal stable matching, truthful reporting is a dominant strategy for everyone on that side (Roth 1982). In 1985 Gale and Sotomayor proved that whenever there is more than one stable matching, at least one receiver can obtain a better partner by misstating preferences (for example by declaring some proposers unacceptable) (Gale and Sotomayor 1985).

Calculation

# Who can gain by lying in proposer-side deferred acceptance? On random 4 x 4 markets each
# agent tries all 24 rankings while the others tell the truth. Proposers never gain
# (Dubins & Freedman 1981; Roth 1982); receivers sometimes do (Roth 1982; Gale &
# Sotomayor 1985). Also: can a PAIR of proposers both gain together?
import itertools, random
rng = random.Random(13)
N, MARKETS = 4, 300

def da(P, R):
    n = len(P); rank = [{p: k for k, p in enumerate(R[j])} for j in range(n)]
    nxt, held, free = [0] * n, {}, list(range(n))
    while free:
        i = free.pop(0); j = P[i][nxt[i]]; nxt[i] += 1
        if j not in held: held[j] = i
        elif rank[j][i] < rank[j][held[j]]: free.append(held[j]); held[j] = i
        else: free.append(i)
    m = [None] * n
    for j, i in held.items(): m[i] = j
    return m

LISTS = [list(p) for p in itertools.permutations(range(N))]
prop_gain = rec_gain = pair_gain = rec_markets = 0
example = None
for _ in range(MARKETS):
    P = [rng.sample(range(N), N) for _ in range(N)]
    R = [rng.sample(range(N), N) for _ in range(N)]
    m = da(P, R); partner = {j: i for i, j in enumerate(m)}
    for i in range(N):
        for L in LISTS:
            Q = [row[:] for row in P]; Q[i] = L
            prop_gain += P[i].index(da(Q, R)[i]) < P[i].index(m[i])
    found = False
    for j in range(N):
        for L in LISTS:
            S = [row[:] for row in R]; S[j] = L
            m2 = da(P, S); p2 = {jj: ii for ii, jj in enumerate(m2)}
            if R[j].index(p2[j]) < R[j].index(partner[j]):
                rec_gain += 1; found = True
                if example is None: example = (R[j], partner[j], L, p2[j])
    rec_markets += found
    for a, b in itertools.combinations(range(N), 2):
        for La, Lb in itertools.product(LISTS, repeat=2):
            Q = [row[:] for row in P]; Q[a] = La; Q[b] = Lb; m2 = da(Q, R)
            pair_gain += (P[a].index(m2[a]) < P[a].index(m[a]) and
                          P[b].index(m2[b]) < P[b].index(m[b]))
print(f"{MARKETS} random 4 x 4 markets, every unilateral misreport tried:")
print(f"   profitable lies by a proposer: {prop_gain}; by a receiver: {rec_gain}"
      f" (in {rec_markets} markets, {rec_markets / MARKETS:.0%})")
print(f"   joint lies by two proposers that make BOTH strictly better off: {pair_gain}")
true, part, lie, new = example
print(f"example: a receiver whose true ranking is {true} holds proposer {part}"
      " under truth;")
print(f"   reporting {lie} instead, he ends with proposer {new}, whom he truly prefers")
# 300 random 4 x 4 markets, every unilateral misreport tried:
#    profitable lies by a proposer: 0; by a receiver: 58 (in 12 markets, 4%)
#    joint lies by two proposers that make BOTH strictly better off: 0
# example: a receiver whose true ranking is [2, 3, 0, 1] holds proposer 0 under truth;
#    reporting [2, 3, 1, 0] instead, he ends with proposer 3, whom he truly prefers

In 300 random 4 × 4 markets the program lets each person try all 24 rankings while everyone else tells the truth. Not once does a proposer obtain a better partner by misreporting; nor does a joint misreport by two proposers ever make both strictly better off, in line with Dubins and Freedman. Receivers are different: in 12 markets (4 %) some receiver can obtain a proposer he truly prefers by misreporting, with 58 such misreports in all. In the example, the receiver’s true ranking is [2, 3, 0, 1], and telling the truth he gets his third choice, 0; merely swapping 0 and 1 makes him reject, at some step, an applicant he would otherwise have held, setting off a chain of new applications that ends with his second choice, 3. Only reorderings are allowed here, not declaring some people unacceptable, which leaves more room for manipulation.

So the framework’s statement that “for the proposing side truth-telling is a dominant strategy” checks out, and so does “this does not hold for the receiving side”, confirmed by the program. The implication for rule designers is direct: if one side should be able to report truthfully without worry, let that side propose. This was one of the reasons Roth and Peranson switched the residency match to applicants proposing (Roth and Peranson 1999).

Note

Relation to Volume 27. The Myerson–Satterthwaite theorem of Chapter 3 of Volume 27 shows that when both sides have private information, efficiency, voluntary participation, incentive compatibility and budget balance cannot all be had; Roth’s 1982 result is a comparable limit in matching markets: stability and “both sides tell the truth” cannot be had together.

Note

When used for matching brands and creators. Replace “hospitals and doctors” with “brands and creators”, and deferred acceptance can serve as a thinking tool: check whether current partnerships contain blocking pairs (step 4 of the Chapter 8 checklist). But real matchmaking markets differ from the textbook model in important ways: a brand can work with several creators at once, prices and contract terms are negotiable, preferences change over time, and not everyone is willing to join a single centralised match at the same moment. Under these conditions, whether stable matchings exist and whether the algorithm keeps its properties must be analysed case by case; this book offers no design advice for any real platform.

Hypothesis · not established

The blocking-pair breakup hypothesis (not yet established). The author conjectures that partnerships involved in a blocking pair end sooner than others. The testable prediction is that in matchmaking data in which both sides’ rankings were collected independently in advance, such partnerships last significantly less long; if durations do not differ, the hypothesis is refuted.

Summary

Two-sided matching markets can fail through blocking pairs, early contracting and congestion. Gale and Shapley’s deferred acceptance always finds a stable matching that is the best of all stable matchings for the proposers and the worst for the receivers, whatever the order of applications; there is often more than one stable matching, and which one is chosen depends on who proposes. Truthful reporting is a dominant strategy for proposers but not for receivers: the program found profitable misreports by receivers in 4 % of random markets. No stable mechanism lets both sides tell the truth safely. A centralised match helped the doctors’ market stop contracting early, and a specialty that left it saw early hiring return. The next chapter turns to ancient Chinese writings on water control and diversion.

References

Dubins, Lester E., and David A. Freedman. 1981. “Machiavelli and the Gale–Shapley Algorithm.” The American Mathematical Monthly 88 (7): 485–94.
Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences. 2012. Stable Matching: Theory, Evidence, and Practical Design. Scientific Background on the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012. The Royal Swedish Academy of Sciences, Stockholm.
Gale, David, and Lloyd S. Shapley. 1962. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly 69 (1): 9–15. https://doi.org/10.2307/2312726.
Gale, David, and Marilda Sotomayor. 1985. “Ms. Machiavelli and the Stable Matching Problem.” The American Mathematical Monthly 92 (4): 261–68.
Niederle, Muriel, and Alvin E. Roth. 2003. “Unraveling Reduces Mobility in a Labor Market: Gastroenterology with and Without a Centralized Match.” Journal of Political Economy 111 (6): 1342–52.
Roth, Alvin E. 1982. “The Economics of Matching: Stability and Incentives.” Mathematics of Operations Research 7 (4): 617–28. https://doi.org/10.1287/moor.7.4.617.
Roth, Alvin E. 1984. “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory.” Journal of Political Economy 92 (6): 991–1016. https://doi.org/10.1086/261272.
Roth, Alvin E., and Elliott Peranson. 1999. “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design.” American Economic Review 89 (4): 748–80. https://doi.org/10.1257/aer.89.4.748.
Roth, Alvin E., and Xiaolin Xing. 1994. “Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions.” American Economic Review 84 (4): 992–1044.

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).