What does Stable Matching without Blocking Pairs conclude, in numbers, about “Deferred Acceptance: Why an Algorithm That Only Holds, Never Commits, Must Converge”?
Answer: Deferred acceptance turns "say yes first" into "hold first". Proposers move down their own lists, and receivers keep only the best offer so far, until nobody is returned any more. Two monotone movements, proposers only down and receivers only up, are enough to prove that the algorithm must stop and must stop without a blocking pair. The illustrative run of p21 reaches a stable sheet after 10 proposals, in which K4 ends with his last choice yet finds no brand willing to elope with him. Program p22 shows that in random markets the average number of proposals stays below Wilson's bound and, at 200 pairs, is only 0.029 of n squared; the worst case of n squared minus n plus 1 is really attained, but only with very special preferences. The order of handling does not affect the result, but the direction of proposing does, and that is the subject of the next chapter.
Scope of the numbers: Chapter 8 gives the weekly procedure, the Stable Pairing Matcher and a pre-registered test: if cancellations fall from 0.15 to 0.08, each group needs 325 pairings, with a simulated power of 0.803. Marked boxes separate published evidence, runnable Python calculations (19 programs), 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: 0.029, 10, 200, 21
| n markets mean proposals n*H_n mean/n^2 max seen | |
| 10 | 2000 24.1 29.3 0.241 48 |
| 20 | 1000 63.0 72.0 0.157 138 |
| 50 | 400 209.0 225.0 0.084 421 |
| 100 | 200 495.0 518.7 0.050 805 |
| 200 | 60 1153.2 1175.6 0.029 1663 |
| worst case found by hill climbing (5 restarts each): | |
| n | 4: 13 proposals, bound n^2 - n + 1 = 13 |
| n | 5: 21 proposals, bound n^2 - n + 1 = 21 |
| n | 6: 31 proposals, bound n^2 - n + 1 = 31 |
Show the full program
# Chapter 2. p22: how many proposals does deferred acceptance need?
# Model: n creators propose to n brands, all rankings uniformly random
# (fixed seed, illustrative). Typical case: mean proposals against
# Wilson's (1972) bound n * H_n, where H_n is the n-th harmonic number
# (the sum of 1/k for k = 1 to n). Worst case: the count can never
# exceed n^2 - n + 1; a fixed-seed hill climb over preference lists
# looks for markets that reach it, to show the bound is attained.
import math
import random
rng = random.Random(20261113)
def proposals(cp, bp):
n = len(cp)
rank = [{k: i for i, k in enumerate(v)} for v in bp]
nxt, held, free, cnt = [0] * n, [None] * n, list(range(n)), 0
while free:
k = free.pop()
b = cp[k][nxt[k]]
nxt[k] += 1
cnt += 1
cur = held[b]
if cur is None:
held[b] = k
elif rank[b][k] < rank[b][cur]:
held[b] = k
free.append(cur)
else:
free.append(k)
return cnt
def rand_market(n):
return ([rng.sample(range(n), n) for _ in range(n)],
[rng.sample(range(n), n) for _ in range(n)])
print(" n markets mean proposals n*H_n mean/n^2 max seen")
for n, reps in ((10, 2000), (20, 1000), (50, 400), (100, 200),
(200, 60)):
v = [proposals(*rand_market(n)) for _ in range(reps)]
hn = n * math.fsum(1.0 / k for k in range(1, n + 1))
print("%4d %7d %14.1f %6.1f %8.3f %8d"
% (n, reps, math.fsum(v) / reps, hn,
math.fsum(v) / reps / n / n, max(v)))
def climb(n, iters):
cp, bp = rand_market(n)
cur = proposals(cp, bp)
for _ in range(iters):
side = cp if rng.random() < 0.5 else bp
r = rng.randrange(n)
a, b = rng.sample(range(n), 2)
side[r][a], side[r][b] = side[r][b], side[r][a]
val = proposals(cp, bp)
if val >= cur:
cur = val
else:
side[r][a], side[r][b] = side[r][b], side[r][a]
return cur
print("worst case found by hill climbing (5 restarts each):")
for n in (4, 5, 6):
best = max(climb(n, 20000) for _ in range(5))
print(" n = %d: %2d proposals, bound n^2 - n + 1 = %2d"
% (n, best, n * n - n + 1))Single source and citation
Fan, Y. (2026). Gale-Shapley Stable Matching: Pairings without Blocking Pairs for Buyers and Clients, Creators and Brands, Photographers and Slots (Version 1.0.0), Chapter 2: Deferred Acceptance: Why an Algorithm That Only Holds, Never Commits, Must Converge. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-299 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026299,
author = {Fan, Yafu},
title = {Gale-Shapley Stable Matching: Pairings without Blocking Pairs for Buyers and Clients, Creators and Brands, Photographers and Slots},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · First Come and Highest Score First: Where Blocking Pairs Come From
- Chapter 3 · Proposer Optimality: the Lattice of Stable Matchings and the Value of Speaking First
- Chapter 4 · Telling the Truth and the Short List: the Proposer's Honesty and the Receiver's Gamble
- Chapter 5 · Many-to-One: Photographers' Slots, Hospitals and Residents
- Chapter 6 · Short Lists, Ties and Guessed Preferences
- Chapter 7 · Classical Sources East and West: the Marriage Officer of the Rites of Zhou and Gale and Shapley 1962
- Chapter 8 · Closing the Loop: a Weekly Slot Sheet, the Stable Pairing Matcher and a Pre-Registered Test