The Commons Seam · a market with the money taken out
A Coincidence of Wants
You cannot buy a kidney. It is a federal felony — so the only thing you can trade a kidney for is another kidney. And the moment money leaves a market, the oldest problem in economics walks back in the door: the double coincidence of wants.
A generation ago, the barter story was told as a fable with a happy ending: barter is a nuisance because it needs a double coincidence — I have what you want and you have what I want, at the same time — so we invented money to dissolve the need. Here is the sequel the fable never tells. Take a market where money is forbidden by law, and the double coincidence does not stay dissolved. It comes back. And a stranger's life turns on whether it can be manufactured — not by a price, but by an algorithm.
Roughly a third of people who need a kidney and bring a willing living donor are incompatible with that donor — wrong blood type, or the recipient's immune system already carries antibodies that would reject the graft. Two such pairs are a double coincidence waiting to happen: your donor might be exactly right for my patient, and mine for yours. Swap, and two people who were each holding the wrong kidney both get the right one. That is the whole idea, and it is worth a Nobel Prize, because the moment you have more than two pairs the swaps stop being obvious and start being cycles — and someone has to prove the cycles are fair, unbeatable, and impossible to game. This page builds that proof as a machine you can run.
The 2012 Nobel in Economics went to Alvin Roth and Lloyd Shapley for market design. Its most famous half is deferred acceptance — the two-sided matching that sorts doctors to hospitals and children to schools, where the stable outcomes form a lattice and no mechanism can keep both sides honest at once. This page is the other half: Top Trading Cycles, a one-sided market where everyone already owns something and trades in cycles. Its structure is the mirror image — the good outcome is a single point, not a lattice, and honesty is completely safe. Read the two as a pair; we will not re-derive deferred acceptance here.
I. The swap market, and the one allocation nobody can beat
Forget kidneys for a moment and take the cleanest possible version, the one the theorists actually proved things about. It is called a housing market (Shapley & Scarf, 1974)1: a handful of people, each already owning one indivisible thing — call them houses — and each with a strict ranking of all the houses, their own included. Nobody has money. The only move is to trade. Which trades should happen?
David Gale's answer, reported in that 1974 paper, is an algorithm so simple you can run it by hand — Top Trading Cycles. Everyone points at the owner of their single most-wanted house. Follow the arrows: in a world where every finger points at exactly one person, you are guaranteed to walk into a loop — a cycle. Everyone in that cycle trades, all at once, each getting the house they pointed at, and leaves happy. Erase them, and everyone still waiting re-points at their favourite among the houses that remain. Repeat until nobody is left. That is the entire method.
Press Run and watch it clear. The arrows are wishes; the glowing loops are trades that fire.
Notice what just happened. No money changed hands, nobody was assigned anything centrally, and yet the market cleared — every trade that fired was a genuine coincidence of wants, a loop of people each wanting what the next one owned. The question the theorists cared about is whether the particular allocation TTC lands on is the right one. It is, in a sense that is hard to improve on.
An allocation is in the core if no group of people could break away, trade only among the houses they brought, and make every member of the group at least as happy and someone strictly happier. A core allocation has no such disgruntled coalition hiding in it — nobody can credibly say "we'd have done better on our own." Shapley and Scarf proved the core here is never empty; with strict preferences it is a single point (Roth & Postlewaite, 19772), and that point is exactly what Top Trading Cycles outputs.
That is a strong claim — unique, unbeatable — so don't take it on faith. The panel below does two things, live, in your browser, on the very market shown above. First it hunts for a disgruntled coalition: it searches every subset of traders and every way they could re-trade among themselves, looking for one that would defect. Then it enumerates every allocation and keeps only the ones in the core, to confirm the core really is a single point.
The check · is TTC's outcome really the unique core?
Recomputed live on the market above. With n traders there are 2ⁿ−1 possible coalitions and n! possible allocations — small enough to check by exhaustion.
Now try to cheat
There is a second, sharper worry. TTC asks everyone to report their preferences. What stops a trader from lying — ranking the houses strategically to steer the cycles their way? The answer (Roth, 19823) is: nothing needs to. Truth is a dominant strategy. No matter what everyone else reports, no misreport of yours can ever get you a house you like better than the one honesty gets you. Pick a trader and let the panel prove it the brute way — by trying all 120 preference lists that trader could possibly submit, and reporting the best house any lie could win.
The check · try to game it
So Top Trading Cycles is efficient, it lands on the unique core, and it cannot be gamed. In fact these three properties nail it down completely: Ma (1994)4 proved TTC is the only rule that is individually rational, Pareto-efficient, and strategy-proof all at once. It is the kind of clean, total theorem that makes an economist reach for the real world. Which is where it breaks — beautifully, and instructively.
II. Where the clean theorem meets a real patient
Alvin Roth, Tayfun Sönmez and Utku Ünver did exactly that in 20045: they pointed the machinery at incompatible patient–donor pairs. Each pair "owns" one thing — its donor's kidney — and "wants" a compatible one. Run cycles, save lives. But two features of real kidneys bend the theorem, and being honest about the bend is the whole point.
1 · Preferences collapse to 0 or 1. A patient is not pickier about one compatible kidney than another — a compatible kidney is a compatible kidney. Preferences are not strict; they are binary. And Ma's uniqueness needed strictness. So real kidney exchange is not literally Top Trading Cycles. It becomes a different problem: find the maximum number of transplants on a compatibility graph — a maximum-weight packing, solved in practice by integer programming (Roth–Sönmez–Ünver, 20076). TTC is the theoretical seed; this is the crop. We will never say "kidney exchange runs TTC."
2 · Every cycle must be simultaneous. In the abstract market, a cycle fires instantly. In an operating theatre it cannot. If a 3-way cycle ran in sequence, a donor could walk out the moment their own patient received a kidney — leaving the next pair robbed. So every pair in a cycle is operated on at the same time: a k-pair cycle needs 2k operating rooms and surgical teams running at once. That is why real cycles are capped at 2 or 3 pairs. The clean theorem is not wrong; it is logistically strangled.
Below is the second instrument. The nodes are incompatible pairs, coloured by the patient's blood type; a ring marks the highly sensitized patients — the ones whose immune system rejects almost every donor, so almost no arrow points into them. Faint arrows are the compatibility graph: an arrow from pair i to pair j means i's donor could give to j's patient. The bold loops are the transplants a cap allows. Slide the cap from 2 to 3 to "no cap" and watch the count — and watch who stays dark.
Transplants
—
of 10 patients
Highly sensitized matched
—
the hardest patients
Longest structure
—
pairs in one trade
Drag the cap down to 2-way and the pool loses transplants that a single 3-way loop would have saved — because sometimes three pairs can form a cycle A→B→C→A when no two of them can trade directly. That is the finding Roth, Sönmez and Ünver published in 2007, and their paper's title is the phrase this whole page turns on: "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences." Their result: allowing 3-way exchanges on top of 2-way captures most of the gain that unlimited cycles would give — which is lucky, because unlimited cycles are exactly what the operating rooms forbid. You can watch the aggregate below.
The check · does 3-way really capture most of the gains?
This reproduces the RSU-2007 result on the stylized model — press to run fresh random pools live and total the transplants at cap 2, cap 3, and no cap.
The offline verifier runs 400 pools and prints 2-way 80.1%, 3-way 95.6% of the unbounded optimum, and confirms T(2) ≤ T(3) ≤ T(∞) on every pool it tries.
III. The gift that needs no simultaneity
Now look at who the caps leave behind. Turn the cap to 3-way and find the ringed nodes — the highly sensitized patients. They reject almost every donor, so almost no arrow points into them. To rescue one inside a cycle, you need not only a compatible donor pointing in, but the cycle to close back within three pairs — a coincidence on top of a coincidence. Short cycles structurally cannot reach them, and they pile up in the pool, waiting years. This is the hard heart of the problem: the people who need the market most are the ones it serves least.
Then a stranger walks in and offers a kidney to no one in particular.
A non-directed altruistic donor — someone who volunteers a kidney to whichever stranger the algorithm chooses — changes the physics of the trade. Because they give without needing anything back, they can start a chain instead of closing a cycle. The gift goes to a patient; that patient's willing donor now passes it forward to the next; and so on down a line. And here is the quiet miracle: a chain does not need to be simultaneous. Every patient receives a kidney before their own donor gives one, so if a link ever breaks, nobody who already donated has been robbed — the worst case is that the chain simply stops, and the last donor becomes a "bridge" who starts the next chain weeks later. No simultaneity means no length limit. A chain can run as long as the pool allows.
Flip add one altruistic donor on the instrument above, with the cap still at 3, and watch the gold node appear and thread a chain through the pool — reaching, at its far end, a highly sensitized patient that no capped cycle could touch. In the default pool that patient is #8: an AB recipient whose PRA is 96%, meaning 96 of every 100 possible donors would be rejected. Cycles never reach #8. One chain does.
Ashlagi, Gamarnik, Roth and Rees (20127) proved that in large, sparse pools — pools dominated by highly sensitized patients, which is what real registries look like — long chains disproportionately help exactly those hardest patients, in a way bounded-length cycles provably cannot. The mechanism is the one you just watched: a cycle must return to its start, a chain need not.
The honest scope. That disproportionate result is a large-pool statistic. The toy above is ten pairs — far too small and dense to reproduce it; at this scale the highly sensitized are nearly unreachable by anything, so a chain helps everyone rather than the hardest cases specifically (the verifier measures this honestly and says so). What the toy can show, exactly and per-pool, is the mechanism: a chain reaching a specific highly sensitized patient that every capped-cycle solution strands. The population-level claim is Ashlagi et al.'s, cited as theirs — not something a ten-node instrument is allowed to pretend it proved.
The check · what the instrument's numbers are, exactly
All recomputed live above. The full battery — core uniqueness, strategy-proofness, cycle-cap monotonicity, the RSU aggregate, and the stranded-patient rescue — is in research/coincidence-of-wants/verify-coincidence-of-wants.mjs, 36/36 PASS.
IV. Two chains that actually happened
None of this is a thought experiment. The chain you just watched is the mechanism behind two landmark events in transplant medicine — and it is worth keeping their numbers straight, because they are often blurred together.
| The event | What happened | Source |
|---|---|---|
| The first NEAD chain non-simultaneous, extended, altruistic-donor |
Begun in 2007 by one altruistic donor. 10 transplants over roughly 8 months across 6 centres in 5 states — 5 done simultaneously, 5 more strung out later through "bridge donors," up to 5 months apart. The proof of concept that an altruistic start relaxes the simultaneity constraint. | Rees et al., NEJM 2009; 360:1096–1101 |
| "Chain 124" the record chain |
Run by the National Kidney Registry. 30 transplants — 60 people — across 17 hospitals in 11 states over about 4 months, started by a non-directed donor named Rick Ruzzamenti. At the time, the longest kidney chain ever completed. | Kevin Sack, "60 Lives, 30 Kidneys," NYT, Feb 18 2012 |
The first NEAD chain proved the idea works; Chain 124 showed how far it scales when a single gift is allowed to run without ever having to close. Sixty people, one stranger's decision, no money anywhere in it.
V. Why any of this exists
Step back and ask why kidney exchange had to be invented at all. The answer is a single sentence of law. The National Organ Transplant Act of 1984 (42 U.S.C. §274e) makes it a federal felony to "knowingly acquire, receive, or otherwise transfer any human organ for valuable consideration." You cannot sell a kidney; you cannot buy one. The price is set, permanently, at zero.
Alvin Roth's word for this is repugnance — a transaction a society refuses to price, not because it is inefficient but because pricing it feels wrong (Roth, 20078). Forbidding the price does not make the allocation problem go away. There are still too few kidneys and too many patients; someone still has to decide who gets which. Banning money just removes the tool a market would ordinarily reach for — and forces society back into the very thing money was supposed to have retired.
Which closes the loop with where we began. Barter needs a double coincidence of wants. Money removes the need. And here, where money is forbidden, the double coincidence returns — only now it is manufactured, on purpose, by an algorithm that finds the cycles and lights the chains that a price would have found for free. Matching is what a market looks like when you take the money out. Not a refutation of the barter story. Its sequel.
"You cannot buy a kidney" is a statement about the United States and most of the world — not all of it. Iran has run a regulated, compensated living-donor programme since the 1990s, the one country that prices the transaction openly. It is the exception that shows the rule is a choice: repugnance is a constraint societies impose, and a few decline to. The market on this page is the one that grows in the soil where the price is banned.
What is exactly true here, what is stylized, and what is only cited
Exactly true, and checked live. Top Trading Cycles on a strict-preference market outputs the unique weak-domination (strict) core allocation, and it is strategy-proof — both verified by exhaustion in your browser and offline (all coalitions searched, all misreports tried). Cycle-cap monotonicity T(2) ≤ T(3) ≤ T(∞) is a theorem (more allowed cycle lengths can only help) and is confirmed on every pool. On the default pool, a highly sensitized patient (#8, AB, 96% PRA) is transplanted only when the chain is added — an exact, per-pool fact.
Which core. "Unique core" here means the weak-domination (strict) core of Roth–Postlewaite 1977, not Shapley–Scarf's larger strong-domination core. With strict preferences the two coincide at TTC's output; the distinction matters only under indifference, which is precisely the 0-1 kidney case where the clean uniqueness stops applying.
Stylized, and labelled as such. The kidney pools are generated from a deliberately simple model: approximate US ABO blood-type frequencies, standard ABO donation rules (O gives to all, AB receives from all), and a crossmatch that fails with probability equal to the patient's PRA. Sensitization is drawn bimodal — most patients low, a hard minority near-total. These reproduce the qualitative findings (3-way captures most gains; chains reach patients cycles cannot); they are not the registries' real figures, and the exact percentages depend on the model.
Only cited, not reproduced. That long chains disproportionately help the highly sensitized in large sparse pools is Ashlagi–Gamarnik–Roth–Rees 2012, proven at a scale a ten-node exact solver cannot reach. And strategy-proofness, so clean for the abstract housing market, weakens in real multi-hospital exchange: hospitals with 0-1 preferences and cycle caps can sometimes profit by hiding their own easy-to-match pairs (Ashlagi–Roth). Ma-1994's beautiful uniqueness lives in the strict-preference world; do not transplant it whole onto the clinic.
The optimiser. Maximum transplant counts under a cycle-length cap are found by exact search (enumerate the legal cycles, then a subset-DP maximum-weight packing; chains by depth-first search from the altruistic donor over the residual cover). This is exponential and only honest at small n — which is why the instruments cap the pool at ten pairs. Real exchanges solve the same problem by integer programming at national scale.
The check, in one place
Everything numeric on this page is recomputed by one file:
The README in that folder lists every primary source and what it supports.