Houses traded in cycles

The matching markets met so far had two sides, and nobody started out owning anything. A matching is stable when no two people would both rather have each other, stable matchings always exist, and the side that proposes gets the best of them. But no stable rule is safe from a lie: someone on the receiving side can always do better by misreporting, so a stable market and an honest one cannot be guaranteed together.

Change the market. There is only one kind of participant, and each starts out owning one indivisible good — a house, say, or a dormitory room, or a place in a school — and ranking every good, their own included. Nobody has to trade, but most would like to. Lloyd Shapley and Herbert Scarf posed the question in 1974 of which reallocations such a market should reach, and published a procedure for finding one that they credited to David Gale. Gale’s top trading cycles reaches the only allocation that no group of owners can improve on by trading among themselves, and it gives nobody any reason to lie. In this market, unlike the marriage market, the two guarantees come together.

Everyone points at the house they want most #

The procedure fits in two sentences. Every agent points at the owner of the house they like best; following the pointers leads into one or more cycles, and everyone on a cycle receives the house they point at and leaves the market with it. Repeat with the agents and houses that remain, until none do.

The first sentence always works. Every agent has exactly one arrow out, so a walk along the arrows from any starting point must eventually revisit an agent, and the part of the walk between the two visits is a cycle. The second sentence is always possible: on a cycle, the house each agent points at belongs to the next agent on the same cycle, so giving every agent on it the house they point at uses exactly the cycle’s own houses. A cycle of length one is an agent whose favourite house is their own, and they keep it.

The cycles of one round are disjoint, and they can be carried out simultaneously. Agents not on any cycle keep pointing at owners who are still in the market — some of them at agents on cycles, who will be gone in the next round, which is what makes the next round different. In the figure, G and B swap houses and H keeps their own; the other six wait.

Round by round #

After a round’s cycles leave, every remaining agent points at the owner of their favourite house among those still available, and the pattern of arrows changes.

Three rounds clear this market, and the table at the bottom shows the outcome: three agents get their first choice, and nobody does worse than the house they started with. That last property — individual rationality — is automatic. An agent’s own house stays in the market until the agent leaves, so it is always available to be pointed at, and an agent only ever points at a house at least as good as it.

Each agent also gets the best house still available at the moment they leave, which is the procedure’s other easy property. The agents who leave in the first round get their favourites outright; those in later rounds lose only houses that left earlier, taken by agents who had them as favourites. That is the seed of everything else, because an agent who leaves early cannot be made better off by any rearrangement, and an agent who leaves later lost their better options to agents who cannot be persuaded to give them up.

The only allocation no group can improve #

A group of owners blocks an allocation if it can reallocate its members’ own houses among themselves so that every member is at least as well off and one is strictly better off. An allocation that no group blocks is in the strict core, and Alvin Roth and Andrew Postlewaite proved in 1977 that when every agent’s ranking is strict, the strict core contains exactly one allocation: the one top trading cycles produces.

The census confirms it by brute force. For each random market every possible allocation is listed, and for each allocation every group of agents and every way of rearranging that group’s houses is tried. Allocations that leave nobody worse off than their own house are common — about nine on average among the 120 allocations of five agents. Those that are also Pareto efficient, with nobody improvable without loss to someone else, number between one and three. And in every market, exactly one survives every group’s objection.

The proof that the cycles’ allocation is unblockable follows the rounds. A group that tries to improve on it must include, among its members, the one who left earliest; but that agent already has their favourite house among everything still available when they left, and the group’s houses were all still available then, so that agent cannot be made better off — and cannot be made indifferent with a different house either, because rankings are strict. Peeling away the members who cannot gain leaves an empty group. The uniqueness is the subtler half, and it shows that the cycles are not one good answer among several but the only answer meeting the condition.

The ordinary core, which only forbids groups that can make all their members strictly better off, sometimes contains more than one allocation; the census finds an average of 2.67 for five agents. Requiring that groups not be able to help some members at no cost to others is what pins the answer down. The core of a cooperative game is the same idea for divisible payoffs, where it is usually a whole region and sometimes empty; houses that cannot be split make the market’s core a single point.

No lie pays #

The second guarantee is that nobody can gain by reporting a false ranking. Roth proved in 1982 that top trading cycles is strategy-proof: whatever the others report, telling the truth gives each agent a house at least as good as any lie could.

The census tries all 24 misreports for every agent in every market. Under the cycles, not one lie in any market gains anything. The comparison rule looks kinder: among allocations that leave nobody worse off, it picks the one with the smallest total rank, which is the most satisfaction in total. It can be gamed in 39 per cent of markets, sometimes by two places, because a rule that adds up everyone’s reported ranks lets one agent’s report push the sum towards the house she wants.

The reason the cycles resist is the same timing that made them unblockable. An agent’s report matters only through what she points at, and she points at her favourite available house. Pointing elsewhere either joins a cycle sooner with a worse house or delays her, and delay cannot make a better house available, because houses only ever leave. This is the property that stable matching lacks: in the marriage market, a receiver can benefit from rejecting a proposal she would accept, because rejection sends the rejected proposer elsewhere and changes what the others do; in the housing market, there is no rejection that changes what is available to her.

A stronger statement is true. Jinpeng Ma proved in 1994 that top trading cycles is the only rule that is individually rational, Pareto efficient and strategy-proof in this market. If those three properties are wanted, there is nothing to choose.

Why the marriage market cannot have both #

The contrast with stable matching is worth making exact. In the marriage market the side that proposes gets the best stable matching for it, and Lester Dubins and David Freedman proved in 1981 that the proposing side cannot gain by lying either. The trouble is entirely on the receiving side: a receiver can turn down a proposal she would in truth accept, the rejected proposer moves on and displaces someone else, and the chain of displacements can bring her a proposal she likes better. Roth proved in 1982 that no stable rule escapes this for both sides at once.

The housing market has no receiving side. Each agent both owns and demands, and the pointing in top trading cycles is the only message anyone sends; there is nothing to reject. What an agent’s report can affect is when she leaves and with which house, and since the set of available houses only shrinks, leaving later never opens a better option. The structural difference is that in the housing market an agent’s endowment guarantees her a floor, the house she brought, and every trade is voluntary from that floor; in the marriage market nobody brings anything, and stability is a condition between pairs rather than a guarantee to individuals.

The two procedures also answer different questions, which matters when they are applied to the same problem. When cities assign children to schools, each school has priorities over children — siblings, distance — and each child has preferences over schools. Atila Abdulkadiroğlu and Tayfun Sönmez showed in 2003 that both procedures can be adapted: deferred acceptance with children proposing gives a stable assignment, in which no child loses a school to a lower-priority child, and is strategy-proof for children but can be inefficient; top trading cycles, with children pointing at schools and schools at their highest-priority children, is efficient and strategy-proof but can let a child take a seat over one with higher priority. Boston chose the first in 2005 and briefly considered the second; New Orleans used the second for a time. The theorem in each case says what is guaranteed and what is given up, and the choice between them is about which guarantee a city values more.

Large random markets #

How does the procedure behave when the market is large and the rankings are random? The first round has a pleasant answer.

In the first round every agent points at the owner of a uniformly random house, independently of everyone else, so the arrows form a uniformly random function from the agents to themselves. The agents who trade in the first round are exactly the points lying on that function’s cycles, and a random function on $n$ points has on average about $\sqrt{\pi n/2}$ of them — the same count that sets how long a random walk through a function takes to close its loop in Pollard’s method of factoring. At 3,000 agents about sixty-seven trade in the first round, a little over two per cent.

Later rounds are no longer random functions, because the arrows of agents who have already looked past departed houses are biased, and the counts are measured rather than derived. The market clears in a number of rounds growing roughly like a square root — about eighty-five rounds at 3,000 agents — and the typical agent gets a house ranked around seventh or eighth, the rank creeping up only like the logarithm of the market’s size. Alan Frieze and Boris Pittel analysed this random market in 1995; the figure’s later curves are measurements, not their formulas.

Kidneys, where cycles must be short #

The most consequential use of the idea has been in medicine. A patient who needs a kidney may have a relative or friend willing to donate one whose kidney is incompatible with the patient’s blood or tissue type. Two such pairs may be able to swap — each donor giving to the other pair’s patient — and longer cycles of pairs can do more. Roth, Tayfun Sönmez and M. Utku Ünver adapted top trading cycles to this market in 2004, and kidney exchange programmes in several countries now run on algorithms descended from that work, a contribution recognised when Roth and Shapley shared the 2012 Nobel memorial prize in economics.

The housing market lets cycles be any length, and the kidney market cannot. All the operations in a cycle are carried out at the same time, because a donor whose partner has already received a kidney may withdraw before giving one, and six or eight simultaneous operations strain any hospital. So the question becomes how much is lost by limiting cycles, and the figure answers it exactly for small pools. When compatibility is scarce the limit is costly: at a fifteen per cent chance that a donor suits a given patient, swaps between pairs help about 23 per cent of patients, cycles of up to three about 40 per cent, and unlimited cycles about 62 per cent. Allowing three-way exchanges captures much of the gain, which is why many programmes allow exactly that.

Finding the best set of short cycles is no longer the easy procedure of pointing at favourites. With cycles of length two it is a maximum matching problem, which is fast; with cycles of length three it is hard in the technical sense, and real programmes solve it with integer programming. The figure’s pools are small enough that every subset of patients can be examined exactly. Programmes also add chains that begin with an altruistic donor who has no patient of their own, which do not need to close into a cycle and can be carried out over weeks.

What the census cannot settle #

The census of the core and the census of lies are exhaustive for each market examined and random across markets. They show that no counterexample turned up among 1,120 markets for the core and 2,500 for lies, which supports the theorems and does not prove them; the theorems are proved, by the arguments sketched above, for markets of every size. The census is the right instrument for the contrast — it finds that the smallest-total-rank rule can be gamed, which no amount of theory about the cycles would have said — and the wrong instrument for the guarantee.

The assumptions also matter. Rankings here are strict. When an agent is indifferent between two houses the strict core can be empty or contain many allocations, and choosing among them strategy-proofly is a much harder problem, studied since the 2000s under the name of the housing market with indifferences. And everyone here owns exactly one house and wants exactly one. When some agents own nothing — newcomers in a dormitory, say — the rule has to be extended, and allocations made by lottery among those with no claim come back into the picture, with their own trade-offs between fairness, efficiency and incentives.

The kidney figure, finally, uses a crude model of compatibility, with every donor suiting every other patient independently. Real compatibility depends on blood type and on antibodies that make some patients nearly impossible to match, and the real gains from longer cycles are concentrated on those hard-to-match patients; the figure shows the shape of the trade-off, not the numbers a programme would see.

Still open: how much the short-cycle limit costs in large pools #

For large pools, analyses by Itai Ashlagi, Alvin Roth and others suggest that the gain from cycles longer than three shrinks as the pool grows and compatibility improves, while chains started by altruistic donors become increasingly valuable when many patients are hard to match. How the value of long cycles and long chains scales with the size and composition of a pool is not fully settled, and it is a live practical question, because every programme must choose its limits, and the national and international pools now being formed are larger than any studied when those limits were first set. The same tension between a guarantee that holds in every case and the instance a real market produces runs through every application of cycle-based exchange, and so far it is answered pool by pool rather than by theorem.

A market where the two guarantees meet #

In a market where everyone owns one house and ranks them all strictly, Gale’s top trading cycles — each agent points at the owner of its favourite remaining house, every cycle trades, repeat — produces the only allocation no group can improve with its own houses, and no agent can gain by lying about their ranking. Both guarantees come from the same fact: an agent who leaves in a round already holds the best house still available, and houses only ever leave. The marriage market cannot have both guarantees at once; the housing market has them in one procedure, and the procedure’s most important descendant matches kidneys.