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 assignment16
violations of the same-fill and same-unplaced claims0
weeks where a stable rule places fewer shoots than the largest
feasible assignment46 (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