Gale-Shapley Stable Matching: Pairings without Blocking Pairs for Buyers and Clients, Creators and Brands, Photographers and Slots: chapter answers
When a boutique assigns personal buyers to booked clients, a studio schedules photographers' slots for brands, or a platform pairs creators with brands, the usual procedures are first come, first served or the highest score picks first. This book refutes the belief behind them: that a fair procedure carried out conscientiously yields a sheet that holds. Both procedures ask only one side what it wants and leave blocking pairs, two people who each prefer the other to their assigned partner; the deferred-acceptance algorithm of Gale and Shapley (1962) always yields a sheet without blocking pairs…
DOI pending · monograph page goes live after publication · 5DL-B-299 · 中文版
- Chapter 1 · First Come and Highest Score First: Where Blocking Pairs Come From
Chapter 1 finds in an illustrative sweep that the more tastes agree, the worse first come does, with blocking pairs rising from 4.14 to 14.12 on average, while score first is stable only when all buyers see clients iden… - Chapter 2 · Deferred Acceptance: Why an Algorithm That Only Holds, Never Commits, Must Converge
Deferred acceptance turns "say yes first" into "hold first". Proposers move down their own lists, and receivers keep only the best offer so far, until nobody is returned any more. Two monotone movements, proposers only… - Chapter 3 · Proposer Optimality: the Lattice of Stable Matchings and the Value of Speaking First
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. - Chapter 4 · Telling the Truth and the Short List: the Proposer's Honesty and the Receiver's Gamble
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. - Chapter 5 · Many-to-One: Photographers' Slots, Hospitals and Residents
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. - Chapter 6 · Short Lists, Ties and Guessed Preferences
Chapter 6 handles incomplete lists and ties and shows that guessed preferences cannot give a stable sheet: with a noise standard deviation of only 0.05, 0.790 of markets keep blocking pairs. - Chapter 7 · Classical Sources East and West: the Marriage Officer of the Rites of Zhou and Gale and Shapley 1962
The marriage officer of the Rites of Zhou describes a centralised matching institution: registration, an annual meeting, care for the unmatched, and, during the meeting, "those who elope are not stopped". It got right t… - Chapter 8 · Closing the Loop: a Weekly Slot Sheet, the Stable Pairing Matcher and a Pre-Registered Test
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…
Illustrative model calculation, not a live quote