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