What does Stable Matching without Blocking Pairs conclude, in numbers, about “Many-to-One: Photographers' Slots, Hospitals and Residents”?
Answer: Chapter 5 extends matching to many-to-one settings such as photographers' slots, tests the rural hospitals theorem and prices stability: in 0.115 of weeks, filling up regardless of rankings books about 1.04 more shoots.
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.115, 1.04
| weeks 400; stable assignments per week: mean 1.040, max 2 | |
| weeks with more than one stable assignment | 16 |
| violations of the same-fill and same-unplaced claims | 0 |
| weeks where a stable rule places fewer shoots than the largest | |
| feasible assignment | 46 (0.115), shortfall 1.04 shoots on average |
Show the full program
# Chapter 5. p52: who gets a slot does not depend on which stable rule.
# Model: 3 photographers with 2, 1 and 1 slots; 6 shoots. Each shoot
# lists 1 to 3 acceptable photographers in random order; a photographer
# accepts a shoot with probability 0.8 and ranks the accepted ones at
# random (fixed seed, 400 illustrative weeks). Every assignment of
# shoots to a photographer or to nobody (4^6 = 4,096 per week) is
# checked for capacity, mutual acceptability and blocking pairs.
# Claims checked (the "rural hospitals" theorem, Roth 1986; see Roth
# and Sotomayor 1990): every stable assignment fills
# each photographer with the same number of shoots and leaves the same
# shoots unplaced; an under-filled photographer gets the same shoots in
# all of them. Also: how often does stability cost placements, compared
# with the largest feasible assignment that ignores rankings?
import itertools
import math
import random
CAP = [2, 1, 1]
P, S, WEEKS = 3, 6, 400
rng = random.Random(20261113)
def week():
sp = [rng.sample(range(P), rng.randint(1, 3)) for _ in range(S)]
pp = []
for p in range(P):
acc = [s for s in range(S) if p in sp[s] and rng.random() < 0.8]
rng.shuffle(acc)
pp.append(acc)
return sp, pp
def feasible(a, sp, pp):
for p in range(P):
if a.count(p) > CAP[p]:
return False
return all(p is None or (p in sp[s] and s in pp[p])
for s, p in enumerate(a))
def stable(a, sp, pp):
for s in range(S):
lst = sp[s]
cut = lst.index(a[s]) if a[s] is not None else len(lst)
for p in lst[:cut]:
if s not in pp[p]:
continue
held = [t for t in range(S) if a[t] == p]
if len(held) < CAP[p]:
return False
if pp[p].index(s) < max(pp[p].index(t) for t in held):
return False
return True
n_stable, viol, cost, gap = [], 0, 0, []
for _ in range(WEEKS):
sp, pp = week()
feas = [a for a in itertools.product([None, 0, 1, 2], repeat=S)
if feasible(a, sp, pp)]
st = [a for a in feas if stable(a, sp, pp)]
n_stable.append(len(st))
fills = {tuple(a.count(p) for p in range(P)) for a in st}
unplaced = {tuple(s for s in range(S) if a[s] is None) for a in st}
if len(fills) != 1 or len(unplaced) != 1:
viol += 1
for p in range(P):
under = [a for a in st if a.count(p) < CAP[p]]
if under and len({tuple(s for s in range(S) if a[s] == p)
for a in st}) != 1:
viol += 1
placed_st = S - len(next(iter(unplaced)))
best = max(S - a.count(None) for a in feas)
if best > placed_st:
cost += 1
gap.append(best - placed_st)
print("weeks %d; stable assignments per week: mean %.3f, max %d"
% (WEEKS, math.fsum(n_stable) / WEEKS, max(n_stable)))
print("weeks with more than one stable assignment: %d"
% len([x for x in n_stable if x > 1]))
print("violations of the same-fill and same-unplaced claims: %d" % viol)
print("weeks where a stable rule places fewer shoots than the largest")
print("feasible assignment: %d (%.3f), shortfall %.2f shoots on average"
% (cost, cost / WEEKS, math.fsum(gap) / len(gap)))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 5: Many-to-One: Photographers' Slots, Hospitals and Residents. 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 4 · Telling the Truth and the Short List: the Proposer's Honesty and the Receiver's Gamble
- 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