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