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
- Chapter 1 · Braess's Paradox: One More Road, Everyone Slower
- Chapter 2 · The Price of Anarchy: How Much Can Selfishness Cost?
- Chapter 3 · Pigouvian Tolls and Potential Games: Pricing the Unseen Delay
- Chapter 4 · Congestion in Attention: Hot Niches, Hotelling and a Digital Braess Paradox
- Chapter 5 · Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation
- Chapter 8 · Practice and a Pre-Registered Trial