What does Stable Matching without Blocking Pairs conclude, in numbers, about “Telling the Truth and the Short List: the Proposer's Honesty and the Receiver's Gamble”?
Answer: Chapter 4 shows that proposers lose nothing by honesty, that 0.233 of receivers can gain by misreporting, and that shortening a list is a gamble that may end with nothing.
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.233
| markets 500 of 4x4, every agent tries all 65 reported lists | |
| creators (proposers) who can gain by lying | 0 of 2000 |
| brands (receivers) who can gain by lying | 465 of 2000 (0.233) |
| markets where at least one brand can gain | 188 of 500 (0.376) |
| mean gain of a gaining brand | 1.64 places |
| brands whose best lie beats their brand-optimal stable partner | 0 |
Show the full program
# Chapter 4. p41: who can gain by misstating a ranking? Exhaustive check.
# Model: 4 creators propose to 4 brands, uniformly random true rankings,
# fixed seed, 500 illustrative markets. For every agent we try every
# possible reported list (each ordered subset of the other side: 65
# lists, truncations included) with everyone else truthful, and ask
# whether the outcome under the TRUE ranking beats truth-telling.
# Theory: proposers can never gain (Dubins and Freedman 1981; Roth
# 1982); receivers sometimes can (Roth 1982).
import itertools
import math
import random
N, MARKETS = 4, 500
rng = random.Random(20261113)
LISTS = [list(p) for k in range(N + 1)
for p in itertools.permutations(range(N), k)]
def deferred(pp, rp):
rank = [{p: i for i, p in enumerate(v)} for v in rp]
nxt, held, free = [0] * N, [None] * N, list(range(N))
while free:
p = free.pop()
while nxt[p] < len(pp[p]) and p not in rank[pp[p][nxt[p]]]:
nxt[p] += 1
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 held
def value(true, partner):
return N - true.index(partner) if partner is not None else 0
prop_gain = rec_gain = rec_any = beyond = 0
rec_size = []
for _ in range(MARKETS):
kp = [rng.sample(range(N), N) for _ in range(N)]
bp = [rng.sample(range(N), N) for _ in range(N)]
held = deferred(kp, bp)
part_k = {k: b for b, k in enumerate(held) if k is not None}
for k in range(N):
base = value(kp[k], part_k.get(k))
for lst in LISTS:
h = deferred(kp[:k] + [lst] + kp[k + 1:], bp)
got = {kk: b for b, kk in enumerate(h) if kk is not None}
if value(kp[k], got.get(k)) > base:
prop_gain += 1
break
bh = deferred(bp, kp) # 品牌提议:品牌最优稳定配对
bopt = [None] * N
for k, b in enumerate(bh):
if b is not None:
bopt[b] = k
any_here = False
for b in range(N):
base = value(bp[b], held[b])
best = base
for lst in LISTS:
h = deferred(kp, bp[:b] + [lst] + bp[b + 1:])
best = max(best, value(bp[b], h[b]))
if best > base:
rec_gain += 1
any_here = True
rec_size.append(best - base)
if best > value(bp[b], bopt[b]):
beyond += 1
if any_here:
rec_any += 1
print("markets %d of %dx%d, every agent tries all %d reported lists"
% (MARKETS, N, N, len(LISTS)))
print("creators (proposers) who can gain by lying: %d of %d"
% (prop_gain, MARKETS * N))
print("brands (receivers) who can gain by lying: %d of %d (%.3f)"
% (rec_gain, MARKETS * N, rec_gain / (MARKETS * N)))
print("markets where at least one brand can gain: %d of %d (%.3f)"
% (rec_any, MARKETS, rec_any / MARKETS))
print("mean gain of a gaining brand: %.2f places"
% (math.fsum(rec_size) / len(rec_size)))
print("brands whose best lie beats their brand-optimal stable partner: %d"
% beyond)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 4: Telling the Truth and the Short List: the Proposer's Honesty and the Receiver's Gamble. 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 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