What does Stable Matching without Blocking Pairs conclude, in numbers, about “Classical Sources East and West: the Marriage Officer of the Rites of Zhou and Gale and Shapley 1962”?
Answer: The marriage officer of the Rites of Zhou describes a centralised matching institution: registration, an annual meeting, care for the unmatched, and, during the meeting, "those who elope are not stopped". It got right the importance of centralisation and a single point in time, and it looked after the people of Chapters 5 and 6 who are unmatched under every stable algorithm. It got wrong the use of coercion and punishment, and it organised meetings without prescribing how pairs are formed. Program p71 writes "those who elope are not stopped" as a dynamic: when blocking pairs act one after another, all 1,000 markets reach stability, but the random order breaks 57.37 betrothals on average and 1348 in the longest case. Two specific claims of Gale and Shapley's 1962 paper hold up under p72: the copies method and the quota algorithm agree in 500 markets, and the paper's roommates example has no stable pairing. The next chapter brings the whole book down to a weekly pairing sheet and a pre-registered test plan.
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: 1000, 1348, 57.37
start: a random arranged pairing of 8 and 8, 1000 markets rule stable mean steps median max steps cycles ends at DA random 1000 57.37 37 1348 0 0.530 fixed 1000 12.71 12 44 0 0.879 each step breaks one existing pairing; letting blocking pairs act does end in stability, after a chain of broken promises that DA, run before anything is announced, never makes.
Show the full program
# Chapter 7. p71: "those who elope are not stopped" as a dynamic.
# Model: 8 and 8 agents with uniformly random rankings (fixed seed,
# 1,000 illustrative markets). Start from a pairing arranged at random
# without asking anyone, then let one blocking pair at a time leave
# their partners and pair up (their old partners become single).
# Random order: pick a blocking pair at random (Roth and Vande Vate
# 1990 prove this reaches a stable matching with probability one).
# Fixed order: always the first blocking pair in a fixed scan; such
# deterministic orders can cycle for ever (Knuth 1976). From a full
# pairing to a full pairing every step forms one pair and breaks one, so
# steps = broken pairings. We report steps, cycles detected, and how
# often the end point is the left-proposing DA outcome.
import math
import random
N, MARKETS, LIMIT = 8, 1000, 2000
rng = random.Random(20261113)
def blocking_pairs(m, cp, bp):
# m: 左侧 -> 右侧(或 None);返回所有私奔对
owner = [None] * N
for a, b in enumerate(m):
if b is not None:
owner[b] = a
out = []
for a in range(N):
cut = cp[a].index(m[a]) if m[a] is not None else N
for b in cp[a][:cut]:
o = owner[b]
if o is None or bp[b].index(a) < bp[b].index(o):
out.append((a, b))
return out
def elope(m, a, b):
m = list(m)
for x in range(N):
if m[x] == b:
m[x] = None
m[a] = b
return tuple(m)
def deferred(cp, bp):
rank = [{a: i for i, a in enumerate(v)} for v in bp]
nxt, held, free = [0] * N, [None] * N, list(range(N))
while free:
a = free.pop()
b = cp[a][nxt[a]]
nxt[a] += 1
cur = held[b]
if cur is None:
held[b] = a
elif rank[b][a] < rank[b][cur]:
held[b] = a
free.append(cur)
else:
free.append(a)
m = [None] * N
for b, a in enumerate(held):
m[a] = b
return tuple(m)
res = {"random": ([], 0, 0), "fixed": ([], 0, 0)}
for _ in range(MARKETS):
cp = [rng.sample(range(N), N) for _ in range(N)]
bp = [rng.sample(range(N), N) for _ in range(N)]
da = deferred(cp, bp)
start = list(range(N))
rng.shuffle(start)
for rule in ("random", "fixed"):
m, steps, seen, cyc = tuple(start), 0, {tuple(start)}, False
while steps < LIMIT:
bl = blocking_pairs(m, cp, bp)
if not bl:
break
a, b = rng.choice(bl) if rule == "random" else bl[0]
m = elope(m, a, b)
steps += 1
if rule == "fixed":
if m in seen:
cyc = True
break
seen.add(m)
st, cy, at_da = res[rule]
if not cyc and steps < LIMIT:
st.append(steps)
res[rule] = (st, cy + int(cyc), at_da + int(m == da))
print("start: a random arranged pairing of %d and %d, %d markets"
% (N, N, MARKETS))
print("rule stable mean steps median max steps cycles ends at DA")
for rule in ("random", "fixed"):
st, cy, at_da = res[rule]
st.sort()
print("%-7s %6d %10.2f %6d %9d %6d %10.3f"
% (rule, len(st), math.fsum(st) / len(st), st[len(st) // 2],
st[-1], cy, at_da / MARKETS))
print("each step breaks one existing pairing; letting blocking pairs act")
print("does end in stability, after a chain of broken promises that DA,")
print("run before anything is announced, never makes.")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 7: Classical Sources East and West: the Marriage Officer of the Rites of Zhou and Gale and Shapley 1962. 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 2 · Deferred Acceptance: Why an Algorithm That Only Holds, Never Commits, Must Converge
- 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 8 · Closing the Loop: a Weekly Slot Sheet, the Stable Pairing Matcher and a Pre-Registered Test