THE FOLD / CO-OP / SPLIT SCREEN / THE GALE-SHAPLEY
THE GALE-SHAPLEY
proposals settle into a matching no pair wants to break
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Gale–Shapley algorithm pairs two sides — say n proposers and n reviewers, each with a ranked list — into a stable matching: one where no unmatched pair both prefer each other to their assigned partners. Proposers propose in preference order; each reviewer holds their best offer so far and rejects the rest; rejected proposers try their next choice. It always terminates with everyone matched, and the result is proposer-optimal — every proposer gets the best partner they could have in any stable matching.
LIT verified live: over hundreds of random instances the output has no blocking pair and matches everyone, and for small n it is exactly the proposer-optimal stable matching found by brute force (window.__galeshapley). FIG no framing; exact combinatorial checks.
LIT verified live: over hundreds of random instances the output has no blocking pair and matches everyone, and for small n it is exactly the proposer-optimal stable matching found by brute force (window.__galeshapley). FIG no framing; exact combinatorial checks.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at split-screen — two sides, one game, matched so cleanly that no pair on the two screens would rather defect to each other. Gale–Shapley is that matching. AVAN (AI) built the instrument: the propose–hold–reject loop, the no-blocking-pair stability test, and the brute-force proposer-optimality check.
Credit as content: David Gale & Lloyd Shapley (1962); Shapley’s share of the 2012 Nobel in Economics. The weave: David names split-screen; I run proposals until everyone is held, then confirm no pair would break their match and that each proposer got their best stable partner — verified against every stable matching for small n.
Credit as content: David Gale & Lloyd Shapley (1962); Shapley’s share of the 2012 Nobel in Economics. The weave: David names split-screen; I run proposals until everyone is held, then confirm no pair would break their match and that each proposer got their best stable partner — verified against every stable matching for small n.
3 ONE DIMENSION
Each proposer proposes down their list; each reviewer keeps their favourite offer and rejects the rest; rejects re-propose. It stops when no one is free — a matching no pair wants to break.
4 TWO DIMENSIONS · INTERACTIVE
A random instance with its preference lists; the stable matching drawn, and stability + optimality checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a matching with no pair that wants out.
AVAN’s addition (the inverse-companion): reach a matching that no pair wants to break not by scoring all pairings but by deferred acceptance — propose, tentatively hold the best, reject the rest, repeat. The inverse of ‘search all n! matchings for a stable one’ is ‘let proposals settle — the fixed point is stable and proposer-optimal.’ Magenta is the factorial search avoided; green is the settled matching. Stability from proposing, not searching.
LIT Genuine Gale–Shapley deferred-acceptance algorithm (David Gale & Lloyd Shapley 1962; Shapley shared the 2012 Nobel Memorial Prize in Economics). Verified live: over 400 random instances the matching has no blocking pair (window.__galeshapley.stable) and is perfect (everyone matched), and for n≤4 it equals the proposer-optimal matching over all stable matchings enumerated by brute force (window.__galeshapley.manOptimal).
FIG No framing: the propose-hold-reject loop, the no-blocking-pair stability test, and the brute-force proposer-optimality check run in-browser and agree. The AVAN inverse is honest — reaching a stable, proposer-optimal matching by deferred acceptance genuinely replaces searching all n! matchings; magenta is the factorial search avoided, green the settled matching. Stability from proposing, not searching.
FIG No framing: the propose-hold-reject loop, the no-blocking-pair stability test, and the brute-force proposer-optimality check run in-browser and agree. The AVAN inverse is honest — reaching a stable, proposer-optimal matching by deferred acceptance genuinely replaces searching all n! matchings; magenta is the factorial search avoided, green the settled matching. Stability from proposing, not searching.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN