THE FOLD / SPAWN / CHECKPOINT ZERO / THE TOP TRADING
THE TOP TRADING
the trade that cannot be gamed
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Everyone owns a house and everyone has an opinion about everyone else’s. Point at the owner of your favourite house; the arrows must contain a cycle; execute every cycle, remove those people, repeat. Top Trading Cycles is one page of instructions, and what it produces is the unique allocation no group could improve on by trading among themselves — and no one can ever gain by lying about their preferences. Shapley and Scarf described it in 1974, crediting the algorithm to David Gale.
LIT verified live on 60 random five-agent markets: the result is a permutation every time; it lies in the core in all 60; and exhaustive search over all 120 possible allocations finds the core contains exactly one, which is always the one TTC produced. Across 3,840 misreports — every agent trying every possible false preference order in 40 four-agent markets — the number of times lying improved an agent’s house is 0.
LIT verified live on 60 random five-agent markets: the result is a permutation every time; it lies in the core in all 60; and exhaustive search over all 120 possible allocations finds the core contains exactly one, which is always the one TTC produced. Across 3,840 misreports — every agent trying every possible false preference order in 40 four-agent markets — the number of times lying improved an agent’s house is 0.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at CHECKPOINT ZERO: everyone starts already owning something, and that starting point is what makes the whole thing work.
AVAN (AI) tested the core property by brute force over every coalition and every internal reallocation — all 31 non-empty subsets of five agents and every permutation within each — rather than checking a characterisation. Core membership is a claim about what cannot happen, and the honest way to check one is to try everything. The same applies to strategy-proofness: each agent was given every one of the 24 possible orderings to submit, not a sample. Worth naming the hypothesis that does the work: agents own their houses to begin with. Remove the endowment and the result collapses — for the same problem with no initial ownership there is no mechanism that is both efficient and strategy-proof and treats agents symmetrically.
AVAN (AI) tested the core property by brute force over every coalition and every internal reallocation — all 31 non-empty subsets of five agents and every permutation within each — rather than checking a characterisation. Core membership is a claim about what cannot happen, and the honest way to check one is to try everything. The same applies to strategy-proofness: each agent was given every one of the 24 possible orderings to submit, not a sample. Worth naming the hypothesis that does the work: agents own their houses to begin with. Remove the endowment and the result collapses — for the same problem with no initial ownership there is no mechanism that is both efficient and strategy-proof and treats agents symmetrically.
3 ONE DIMENSION
Point at your favourite. The arrows always close.
4 TWO DIMENSIONS · INTERACTIVE
Run the rounds and watch cycles peel off one at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the pointing graph, with the cycles that resolve it lit.
AVAN’s addition (the inverse-companion): the forward reading is “TTC finds the unique core allocation.” The inverse is that the algorithm never searches for it — it makes the search unnecessary by only ever executing trades nobody could object to. A cycle in which everyone receives their top remaining choice is unimprovable by construction, so the allocation is assembled entirely out of pieces that are already final. Read backwards, this is why it is strategy-proof: there is no stage at which anything is traded off against anything, so there is nothing for a lie to purchase. The mechanisms that can be gamed are the ones that balance competing claims, and TTC never balances anything.
LIT on 60 random five-agent markets the result is a permutation every time, lies in the core in all 60, and exhaustive search over all 120 possible allocations finds the core contains exactly one, always the one TTC produced; across 3,840 misreports - every agent trying every possible false preference order in 40 four-agent markets - the number of times lying improved an agent's house is 0
FIG The core property was tested by BRUTE FORCE over every coalition and every internal reallocation - all 31 non-empty subsets of five agents and every permutation within each - rather than by checking a characterisation. Core membership is a claim about what CANNOT happen, and the honest way to check one is to try everything. Same for strategy-proofness: each agent was given all 24 possible orderings, not a sample. The hypothesis doing the work deserves naming: agents OWN their houses to begin with. Remove the endowment and the result collapses. Shapley and Scarf 1974, crediting the algorithm to David Gale.
FIG The core property was tested by BRUTE FORCE over every coalition and every internal reallocation - all 31 non-empty subsets of five agents and every permutation within each - rather than by checking a characterisation. Core membership is a claim about what CANNOT happen, and the honest way to check one is to try everything. Same for strategy-proofness: each agent was given all 24 possible orderings, not a sample. The hypothesis doing the work deserves naming: agents OWN their houses to begin with. Remove the endowment and the result collapses. Shapley and Scarf 1974, crediting the algorithm to David Gale.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of CHECKPOINT ZERO · David Lee Wise (ROOT0), with AVAN