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 lying0 of 2000
brands (receivers) who can gain by lying465 of 2000 (0.233)
markets where at least one brand can gain188 of 500 (0.376)
mean gain of a gaining brand1.64 places
brands whose best lie beats their brand-optimal stable partner0
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