What does Braess's Paradox and the Price of Anarchy conclude, in numbers, about “Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth”?

Answer: 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.

Scope of the numbers: The models of traffic pools and recommender algorithms are schematic and describe no real platform; the book is not investment, business or marketing advice. Marked boxes separate published evidence, runnable Python calculations (16 programs, all checked), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 183, 204, 500

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]]
Show the full program
# 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)}")

Single source and citation

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks (Version 1.0.0), Chapter 6: Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth. 5D Library. https://doi.org/10.5281/zenodo.23782094

DOI: 10.5281/zenodo.23782094 · Read the monograph · 5DL-B-032 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026032,
  author    = {Fan, Yafu},
  title     = {Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.23782094},
  url       = {https://doi.org/10.5281/zenodo.23782094}
}

Other chapter answers in this book