📈 economics

TTC Domains

This paper introduces the "top-two condition" to characterize when the Top Trading Cycles (TTC) mechanism remains the unique strategyproof, efficient, and individually rational solution for object reallocation on restricted preference domains, thereby unifying existing results and extending them to new domains like circular and partial-agreement preferences.

Original authors: Sumit Goel, Yuki Tamura

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sumit Goel, Yuki Tamura

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends who all own different items they don't want anymore—maybe a bike, a guitar, a video game, or a rare stamp. They want to trade these items so everyone ends up with something they like more. This is the "object reallocation problem."

The most famous way to solve this is a method called Top Trading Cycles (TTC). Think of it like a giant game of "musical chairs" where everyone points to the item they want most. If Person A wants Person B's item, and Person B wants Person C's, and Person C wants Person A's, they form a circle (a cycle) and swap. This process repeats until everyone is happy.

For a long time, economists knew that if people could have any preference they wanted (the "unrestricted" world), TTC was the only fair way to trade that was also:

Safe: No one could lie about what they wanted to get a better deal (Strategyproofness).
Fair: No one would end up with something worse than what they started with (Individual Rationality).
Efficient: You couldn't make someone better off without making someone else worse off (Pareto Efficiency).

The Big Question
The authors of this paper asked: What if people can't have just any preference? What if their choices are limited by the environment? For example, maybe in a kidney exchange, you can't prefer an old kidney over a young one. Does TTC still remain the only fair and safe way to trade in these restricted worlds?

The "Top-Two" Rule
The authors invented a new test called the "Top-Two Condition." Here is the analogy:

Imagine a menu of dishes. The Top-Two Condition says: "If you can put Dish A as your #1 choice, and you can also put Dish B as your #1 choice, then you must also be able to order them as 'A then B' AND 'B then A' at the very top of your list."

If a group of friends follows this rule: The paper proves that TTC is still the only way to trade. You can't invent a new, different trading system that is also fair and safe. The "Top-Two" rule acts like a lock that keeps the door shut on any other solutions.
If a group of friends breaks this rule: The paper shows that you can invent a different trading system that is still fair and safe. The lock is broken, and other doors open.

Real-World Examples from the Paper

The authors tested this "Top-Two" rule on different types of worlds:

The "Single-Dipped" World (The Valley): Imagine preferences look like a valley. You hate the middle items and love the extremes (the very best or the very worst).
- Result: This world passes the Top-Two test. So, TTC is still the only fair solution here.
The "Partial Agreement" World (The Hierarchy): Imagine there is a strict rule that some items are objectively better than others (e.g., a diamond is always better than a pebble).
- Result: This world passes the Top-Two test. TTC remains the unique solution.
The "Single-Peaked" World (The Mountain): Imagine preferences look like a mountain. You love the items in the middle and hate the extremes.
- Result: This world fails the Top-Two test. Because of this, the authors proved you can create a different trading rule (like the "Crawler" rule mentioned in the paper) that is also fair and safe. TTC is no longer the only boss.
The "Circular" World (The Clock): Imagine items are arranged in a circle, and you can only move clockwise or counter-clockwise.
- Result: This world fails the Top-Two test. Again, this means there are other fair trading rules besides TTC.

The "Small Subset" Discovery
The paper also found a specific way to break the system. If the "Top-Two" rule fails in a very small group of items (4 or fewer), and the rest of the items are flexible, you can build a "cheat code" rule. This rule acts like TTC most of the time, but in those specific tricky situations where the Top-Two rule fails, it swaps things differently to make more people happy, without anyone being able to lie to cheat the system.

Summary
The paper provides a simple "litmus test" (the Top-Two Condition) to decide if the famous TTC trading method is the only fair way to trade in a specific environment.

Pass the test? TTC is the only game in town.
Fail the test? There are other fair and safe ways to trade, and the paper shows you how to build them.

This helps economists understand exactly when the standard trading rules work and when we need to look for new, creative solutions.

Technical Summary: TTC Domains

Problem Statement
This paper investigates the object reallocation problem, originally introduced by Shapley and Scarf (1974), in which agents are endowed with indivisible objects and possess strict preferences over all objects. The central focus is on the Top Trading Cycles (TTC) rule. While Ma (1994) and Ekici (2024) established that TTC is the unique rule satisfying individual rationality, efficiency (Pareto or pair), and strategyproofness on the unrestricted domain of preferences, this paper asks whether these characterizations extend to restricted preference domains. Specifically, the authors seek to identify the conditions under which the axioms continue to uniquely pin down TTC, and conversely, when they allow for alternative rules.

Methodology and Framework
The authors analyze the problem within a formal model where $N$ is a set of agents, $O$ is a set of objects (where $o_i$ is agent $i$ 's endowment), and $D \subset P$ is a restricted domain of strict linear orders. A rule $\phi$ maps preference profiles to allocations. The analysis relies on three standard axioms:

Individual Rationality: Agents receive objects at least as good as their endowment.
Efficiency: The paper utilizes both Pareto efficiency and the weaker pair efficiency (no two agents can mutually benefit by swapping).
Strategyproofness: No agent can benefit by misreporting preferences.

The core methodological contribution is the introduction of a richness condition on the preference domain called the top-two condition.

Key Contributions: The Top-Two Condition
The authors define the top-two condition as follows: For any subset of objects $O' \subseteq O$ , if two distinct objects $a$ and $b$ can each be ranked first within $O'$ by some preference in the domain, then there must exist preferences in the domain that rank $a$ first and $b$ second, as well as preferences that rank $b$ first and $a$ second.

This condition is distinct from and weaker than existing richness conditions like "free pair at the top" (FPT) or Assumption B (Sönmez, 1999). The authors demonstrate that the top-two condition is sufficient to ensure that the standard characterizations of TTC hold.

Main Results

Sufficiency (Theorem 1):
If a domain $D$ satisfies the top-two condition, then TTC is the unique rule satisfying individual rationality, strategyproofness, and either Pareto efficiency or pair efficiency.
- Proof Mechanism: The proof constructs auxiliary preference profiles where agents in a TTC trading cycle report their endowments as their second-ranked objects. The top-two condition guarantees the existence of such preferences. Using individual rationality and pair efficiency, the authors show that the rule must execute the trading cycle at these auxiliary profiles. Strategyproofness then forces the rule to execute the cycle at the original profile. This argument iterates through all cycles of the TTC algorithm.
Partial Necessity (Theorem 2):
The paper provides a partial converse. If a domain fails the top-two condition within a small subset of objects ( $|O'| \le 4$ ) and satisfies a mild extension condition (every object outside $O'$ can be ranked first relative to $O'$ ), then there exists a rule distinct from TTC that satisfies individual rationality, Pareto efficiency, and strategyproofness.
- Construction: The authors construct a baseline rule for small economies that deviates from TTC on specific profiles where the top-two condition fails (specifically, where an agent cannot rank their endowment second). This deviation is "sustainable" because the domain restrictions prevent the construction of the auxiliary profiles required to force the TTC outcome. This construction is then extended to arbitrary economy sizes.
Characterization for Small Economies (Corollary 1):
For economies with $n \le 4$ agents, the top-two condition is both necessary and sufficient for TTC to be the unique rule satisfying the axioms.

Applications to Specific Domains
The results unify and extend findings on several specific domains:

TTC Domains (Satisfy Top-Two):
- Single-dipped domain: Previously shown to be a TTC domain by Tamura (2023) and Hu and Zhang (2024).
- Partial-agreement domain: Preferences consistent with a predefined partial order. The authors show this is a TTC domain, a result not previously established in this context.
Non-TTC Domains (Fail Top-Two):
- Single-peaked domain: The authors confirm this is not a TTC domain, consistent with Bade (2019) who proposed the "crawler" rule as an alternative.
- Circular domain: Previously studied in social choice (Sato, 2010), this domain is shown to fail the top-two condition, implying TTC is not uniquely characterized by the axioms.
- One-pair exclusion domain: The authors note this domain fails the top-two condition but is not covered by their partial converse theorem for $n \ge 5$ , leaving the characterization open for this specific case.

Significance and Claims
The paper claims to provide a unifying perspective on existing findings regarding TTC characterizations under domain restrictions. By establishing the top-two condition as a sufficient criterion, the authors identify a broad class of domains where the strong properties of TTC (uniqueness under standard axioms) are preserved.

The authors are modest regarding the necessity of the condition. They explicitly state that while they provide a partial converse for domains failing the condition on small subsets, they do not establish necessity in full generality for all domains (e.g., the one-pair exclusion domain for $n \ge 5$ ). Consequently, the paper does not claim a complete characterization of all TTC domains but rather establishes the top-two condition as a valuable tool for analyzing object reallocation problems. The authors suggest that future research should focus on understanding the structure of rules satisfying the axioms on domains that fail the top-two condition, particularly whether such rules can execute the longer trading cycles that TTC precludes.

More like this