Skip to content
Back to search results

Top Trading Cycles

Introduced by
Lloyd Shapley, Herbert Scarf
Year
1974
Type
algorithm
Family
Game-theoretic
Font size

What does it do?

Top Trading Cycles (TTC) is an algorithm for allocating indivisible goods to agents such that the allocation is Pareto efficient and individually rational. Developed by Lloyd Shapley and Herbert Scarf in 1974, the algorithm identifies cycles of trades in a preference digraph, executes those trades, and iteratively repeats until no further trades are beneficial. TTC is widely used in kidney exchange and housing allocation due to its efficiency and implementation simplicity.

The intuition behind the method

Imagine a group of people each owning one house, and each person ranking all houses by preference. The TTC algorithm asks: who is my favorite? Point to them. Now look at who pointed to you. If it is a cycle (A points to B, B points to C, C points to A), execute those trades—A gets B's house, B gets C's house, C gets A's house. Everyone in the cycle is happy because they got someone's house they prefer to their current one. Remove the cycle and repeat until no more cycles exist. The result is efficient because all beneficial trades are made.

History

Lloyd Shapley and Herbert Scarf introduced the Top Trading Cycles algorithm in 1974 as a solution to the housing market problem, proving it yields unique Pareto-efficient allocations. The algorithm gained practical importance through Alvin Roth's work on kidney exchange, where it became central to matching donors and recipients. The 2012 Nobel Prize to Roth validated TTC's importance for real-world market design, particularly in organ transplantation.

When to use it

Apply TTC when allocating indivisible goods (houses, organs, school seats) among agents with strict preferences over bundles. Use when Pareto efficiency is essential and no monetary transfers are available or desirable. TTC is ideal for decentralized markets where agents can identify beneficial trades locally. Works best when agents have complete, acyclic preference information.

Limitations and considerations

  • Requires strict preference orders without indifference; extensions to weak preferences are complex
  • Not coalition-proof: coalitions of agents can misrepresent preferences to improve collective outcome
  • Sensitivity to preference cycles: nonexistence of cycles can leave some agents untraded
  • Limited to matching without monetary transfers; inefficient for heterogeneous valuations

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Pareto efficient: no trade-free improvements exist; all mutually beneficial swaps are executed
  • Individually rational: each agent weakly prefers the final allocation to their initial endowment
  • Strategy-proof for certain settings: agents cannot improve by misreporting preferences
  • Computationally efficient: polynomial time with simple implementation
  • Transparent: agents understand how their pointed choice leads to allocation

Applications

  • Kidney exchange: matching organ donors and recipients to increase transplant compatibility through multi-party swaps
  • Housing allocation: assigning university dormitory rooms or public housing units efficiently
  • School choice: assigning students to schools with capacity constraints and preference diversity
  • Liver lobe exchange: facilitating paired donation exchanges for living-donor liver transplantation
  • Furniture and goods swaps: organizing efficient barter exchanges in community sharing platforms

How it works

How it works

1

Create a directed graph where each agent points to their most-preferred agent among those still in the market.

2

Find all cycles in the digraph (sequences where A points to B, B points to C, ..., back to A).

3

For each cycle identified, execute the trades: each agent receives the endowment of the agent they pointed to.

4

Remove traded agents and their endowments from the market. Reconstruct the preference digraph among remaining agents and repeat until no further cycles exist.

Common pitfalls

  • Confusing Pareto efficiency with fairness or equity; TTC maximizes efficiency but not equality of outcomes
  • Assuming strategy-proofness in all settings; TTC is truthful only in certain contexts (e.g., housing markets, not kidney exchange with prioritization)
  • Overlooking that the algorithm terminates when no more profitable cycles exist, potentially leaving agents unmatched
  • Forgetting that TTC requires strict preferences without indifference; applying it with weak preferences requires extension

Frequently asked questions

Why is Pareto efficiency important in resource allocation?

Pareto efficiency ensures no agent can be made better off without making another worse off. It is a minimal requirement for a 'good' allocation; violating it means resources are being wasted and could be reallocated to benefit someone.

Can TTC produce multiple different allocations?

No. The TTC algorithm, with its unique preference digraph, produces a unique Pareto-efficient allocation. The path to that allocation (order of cycle identification and trade execution) may vary, but the final outcome is always the same.

How is TTC modified for kidney exchange when not all donor-recipient pairs are compatible?

In kidney exchange, the preference digraph is constructed only over compatible pairs. The algorithm then identifies cycles and chains of swaps among compatible agents, extending the original TTC to account for biological constraints.

Related methods

Sources

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Open DOI reference
    Copied.
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    Open DOI reference
    Copied.