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
102000 24.1 29.3 0.241 48
201000 63.0 72.0 0.157 138
50400 209.0 225.0 0.084 421
100200 495.0 518.7 0.050 805
20060 1153.2 1175.6 0.029 1663
worst case found by hill climbing (5 restarts each):
n4: 13 proposals, bound n^2 - n + 1 = 13
n5: 21 proposals, bound n^2 - n + 1 = 21
n6: 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