What does Stable Matching without Blocking Pairs conclude, in numbers, about “First Come and Highest Score First: Where Blocking Pairs Come From”?

Answer: Chapter 1 finds in an illustrative sweep that the more tastes agree, the worse first come does, with blocking pairs rising from 4.14 to 14.12 on average, while score first is stable only when all buyers see clients identically; on its count of eight British regions alone, Roth's comparison gives a one-sided Fisher p-value of 0.2143, so it stands only together with the theorem and the laboratory replication.

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: 14.12, 4.14

w = weight of shared taste; mean blocking pairs per market
and share of markets with at least one, 2000 markets of 8x8
w first-come score-first deferred acc.
0.004.14 0.968 4.11 0.966 0.00 0.000
0.508.06 1.000 3.62 0.946 0.00 0.000
0.8012.38 1.000 1.62 0.779 0.00 0.000
0.9513.63 1.000 0.45 0.350 0.00 0.000
1.0014.12 1.000 0.00 0.000 0.00 0.000
score-first is stable only when every buyer ranks clients by
the same score (w1); first-come is unstable at every w.
Show the full program
# Chapter 1. p12: blocking pairs of first-come and score-first, swept.
# Model: 8 clients and 8 buyers. A client's value of a buyer is
# w * (buyer's common appeal) + (1 - w) * (idiosyncratic taste); a
# buyer's value of a client is w * (client's common score) + (1 - w) *
# (idiosyncratic fit). All draws uniform on [0, 1], fixed seed; w = 0
# means tastes are private, w = 1 means everybody agrees. First-come:
# clients arrive in random order and take the best free buyer.
# Score-first: clients are served in order of their common score.
# Deferred acceptance: clients propose. 2,000 illustrative markets per w.
import math
import random

N, MARKETS = 8, 2000
rng = random.Random(20261113)


def market(w):
    qa = [rng.random() for _ in range(N)]        # 买手的公共吸引力
    qs = [rng.random() for _ in range(N)]        # 客户的公共评分
    cv = [[w * qa[b] + (1 - w) * rng.random() for b in range(N)]
          for _ in range(N)]
    bv = [[w * qs[c] + (1 - w) * rng.random() for c in range(N)]
          for _ in range(N)]
    cp = [sorted(range(N), key=lambda b, r=row: -r[b]) for row in cv]
    bp = [sorted(range(N), key=lambda c, r=row: -r[c]) for row in bv]
    return cp, bp, qs


def serial(order, cp):
    taken, m = set(), [None] * N
    for c in order:
        for b in cp[c]:
            if b not in taken:
                m[c] = b
                taken.add(b)
                break
    return m


def deferred(cp, bp):
    rank = [{c: i for i, c in enumerate(v)} for v in bp]
    nxt, held, free = [0] * N, [None] * N, list(range(N))
    while free:
        c = free.pop()
        b = cp[c][nxt[c]]
        nxt[c] += 1
        cur = held[b]
        if cur is None:
            held[b] = c
        elif rank[b][c] < rank[b][cur]:
            held[b] = c
            free.append(cur)
        else:
            free.append(c)
    m = [None] * N
    for b, c in enumerate(held):
        m[c] = b
    return m


def blocking(m, cp, bp):
    owner = [None] * N
    for c, b in enumerate(m):
        owner[b] = c
    k = 0
    for c in range(N):
        for b in cp[c][:cp[c].index(m[c])]:
            if bp[b].index(c) < bp[b].index(owner[b]):
                k += 1
    return k


print("w = weight of shared taste; mean blocking pairs per market")
print("and share of markets with at least one, %d markets of %dx%d"
      % (MARKETS, N, N))
print("   w   first-come       score-first      deferred acc.")
for w in (0.0, 0.5, 0.8, 0.95, 1.0):
    res = {"fc": [], "sf": [], "da": []}
    for _ in range(MARKETS):
        cp, bp, qs = market(w)
        arrive = list(range(N))
        rng.shuffle(arrive)
        res["fc"].append(blocking(serial(arrive, cp), cp, bp))
        order = sorted(range(N), key=lambda c: -qs[c])
        res["sf"].append(blocking(serial(order, cp), cp, bp))
        res["da"].append(blocking(deferred(cp, bp), cp, bp))
    cells = []
    for key in ("fc", "sf", "da"):
        v = res[key]
        mean = math.fsum(v) / len(v)
        share = len([x for x in v if x > 0]) / len(v)
        cells.append("%5.2f  %5.3f" % (mean, share))
    print("%5.2f   %s     %s     %s" % (w, cells[0], cells[1], cells[2]))
print("score-first is stable only when every buyer ranks clients by")
print("the same score (w = 1); first-come is unstable at every w.")

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 1: First Come and Highest Score First: Where Blocking Pairs Come From. 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