What does Stable Matching without Blocking Pairs conclude, in numbers, about “Short Lists, Ties and Guessed Preferences”?

Answer: Chapter 6 handles incomplete lists and ties and shows that guessed preferences cannot give a stable sheet: with a noise standard deviation of only 0.05, 0.790 of markets keep blocking pairs.

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.05, 0.790

sigma | blocking pairs markets with clients with a
| per market any blocking different partner
0.00 |0.00 0.000 0.000
0.05 |1.60 0.790 0.375
0.10 |2.86 0.928 0.499
0.20 |5.86 0.987 0.648
0.40 |10.38 0.997 0.760
0.80 |15.25 1.000 0.838
a guess with noise of 0.1 on a 0-1 scale already leaves most
markets with someone who would rather elope.
Show the full program
# Chapter 6. p63: stable for guessed rankings is not stable for real ones.
# Model: 10 clients and 10 buyers with true values drawn uniformly
# (fixed seed, 1,000 illustrative markets per row). An operator who
# does not ask, and instead guesses each value as the true value plus
# Gaussian noise of standard deviation sigma, runs DA on the guesses.
# We count blocking pairs judged by the TRUE rankings, and the share of
# clients whose partner differs from DA on the stated rankings. This is
# the arithmetic behind the book's rule: match only on rankings that
# the parties stated themselves.
import math
import random

N, MARKETS = 10, 1000
rng = random.Random(20261113)


def order(vals):
    return [sorted(range(N), key=lambda j, v=row: -v[j]) for row in vals]


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("sigma | blocking pairs  markets with  clients with a")
print("      | per market      any blocking  different partner")
for sigma in (0.0, 0.05, 0.1, 0.2, 0.4, 0.8):
    bl, anyb, moved = [], 0, []
    for _ in range(MARKETS):
        cv = [[rng.random() for _ in range(N)] for _ in range(N)]
        bv = [[rng.random() for _ in range(N)] for _ in range(N)]
        cp, bp = order(cv), order(bv)
        gc = order([[x + rng.gauss(0, sigma) for x in r] for r in cv])
        gb = order([[x + rng.gauss(0, sigma) for x in r] for r in bv])
        truth = deferred(cp, bp)
        guess = deferred(gc, gb)
        k = blocking(guess, cp, bp)
        bl.append(k)
        anyb += int(k > 0)
        moved.append(len([c for c in range(N) if guess[c] != truth[c]]))
    print("%5.2f | %8.2f        %8.3f      %8.3f"
          % (sigma, math.fsum(bl) / MARKETS, anyb / MARKETS,
             math.fsum(moved) / MARKETS / N))
print("a guess with noise of 0.1 on a 0-1 scale already leaves most")
print("markets with someone who would rather elope.")

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 6: Short Lists, Ties and Guessed Preferences. 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