What does Stable Matching without Blocking Pairs conclude, in numbers, about “Proposer Optimality: the Lattice of Stable Matchings and the Value of Speaking First”?
Answer: Chapter 3 lists all stable matchings and shows that proposer-optimal means receiver-worst, while one extra person on one side shrinks the value of speaking first from 6.02 places to 0.62.
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.62, 6.02
clients buyers | clients propose | buyers propose | gap in
| client buyer | client buyer | client rank
40 39 | 9.59 3.86 | 11.21 3.19 | 1.62
40 40 | 3.99 9.80 | 10.01 3.88 | 6.02
40 41 | 3.18 11.46 | 3.80 9.87 | 0.62
balanced: proposing is worth several ranks; unbalanced: the short
side does well and the long side does poorly whoever proposes.Show the full program
# Chapter 3. p33: one extra buyer erases the advantage of proposing.
# Model: 40 clients and 39, 40 or 41 buyers, uniformly random complete
# rankings, fixed seed, 400 illustrative markets per row. Each market is
# solved with clients proposing and with buyers proposing; the program
# reports the mean rank of the partner for matched clients and matched
# buyers. Question (Ashlagi, Kanoria and Leshno 2017): does the side
# that proposes still matter once the two sides differ by one agent?
import math
import random
rng = random.Random(20261114)
C, REPS = 40, 400
def deferred(pp, rp):
rank = [{p: i for i, p in enumerate(v)} for v in rp]
nxt, held = [0] * len(pp), [None] * len(rp)
free = list(range(len(pp)))
while free:
p = free.pop()
if nxt[p] >= len(pp[p]):
continue
r = pp[p][nxt[p]]
nxt[p] += 1
cur = held[r]
if cur is None:
held[r] = p
elif rank[r][p] < rank[r][cur]:
held[r] = p
free.append(cur)
else:
free.append(p)
return {p: r for r, p in enumerate(held) if p is not None}
print("clients buyers | clients propose | buyers propose | gap in")
print(" | client buyer | client buyer | client rank")
for nb in (39, 40, 41):
acc = [[], [], [], []]
for _ in range(REPS):
cp = [rng.sample(range(nb), nb) for _ in range(C)]
bp = [rng.sample(range(C), C) for _ in range(nb)]
mc = deferred(cp, bp)
mb = {c: b for b, c in deferred(bp, cp).items()}
for k, m in enumerate((mc, mb)):
rc = [cp[c].index(b) + 1 for c, b in m.items()]
rb = [bp[b].index(c) + 1 for c, b in m.items()]
acc[2 * k].append(math.fsum(rc) / len(rc))
acc[2 * k + 1].append(math.fsum(rb) / len(rb))
a = [math.fsum(v) / REPS for v in acc]
print("%7d %6d | %6.2f %6.2f | %6.2f %6.2f | %6.2f"
% (C, nb, a[0], a[1], a[2], a[3], a[2] - a[0]))
print("balanced: proposing is worth several ranks; unbalanced: the short")
print("side does well and the long side does poorly whoever proposes.")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 3: Proposer Optimality: the Lattice of Stable Matchings and the Value of Speaking First. 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 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 7 · Classical Sources East and West: the Marriage Officer of the Rites of Zhou and Gale and Shapley 1962
- Chapter 8 · Closing the Loop: a Weekly Slot Sheet, the Stable Pairing Matcher and a Pre-Registered Test