Top Trading Cycles
Also known as: TTC, Shapley-Scarf Algorithm, Efficient Exchange
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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.
Strengths & limitations
- 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
- 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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
- 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.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Top Trading Cycles. ScholarGate. https://scholargate.app/game-theory/top-trading-cycles