TTC Domains
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.
Ruth: We're looking at the paper: "TTC Domains".
Warren: Here's the gist of the paper. For the object reallocation problem, this paper studies whether characterizations of Top Trading Cycles (TTC) based on individual rationality, efficiency, and strategyproofness on the unrestricted domain extend to restricted preference domains.
Ruth: The condition requires that within every subset of objects, if two objects can each be ranked first, then they can also be ranked as the top two in both possible orders This paper investigates the object reallocation problem introduced by Shapley and Scarf (1974), focusing on whether characterizations of Top Trading Cycles (TTC) extend from the unrestricted domain to restricted preference domains The central question addressed is under what domain restrictions do the characterizations of TTC by Ma (1994) and Ekici (2024) continue to hold This is motivated by preference profiles where TTC may preclude arbitrarily long trading cycles, prompting an exploration of how limiting opportunities for misrepresentation can enrich the class of rules satisfying the axioms The Top-Two Condition and Sufficiency A key concept introduced is the top-two condition, which requires that within every subset of objects, if two objects can each be ranked first, then they can also be ranked as the top two in both possible orders The authors first show that this condition is sufficient: if a domain satisfies the top-two condition, then TTC is the unique rule satisfying individual rationality, pair efficient, and strategyproof This sufficiency is demonstrated by showing that if a rule satisfies the weaker requirement of pair efficiency under individual rationality and strategyproofness, it must coincide with TTC Necessity and Counterexamples The paper also explores necessity by constructing a non-TTC rule when the top-two condition fails in a specific way Specifically, if there exists a small subset of objects within which the failure occurs and every object outside this subset can be ranked first relative to the objects in the subset, then a non-TTC rule satisfying individual rationality, Pareto efficiency, and strategyproofness can be constructed Theorem 2 formalizes this partial converse for domains where the top-two condition fails within a small subset of objects Characterization of TTC Domains The sufficiency result establishes that TTC is the unique rule satisfying individual rationality, Pareto efficiency, and strategyproofness on any domain satisfying the top-two condition The authors then identify several important domains as TTC domains based on this condition, including the single-dipped domain and the partial-agreement domain Corollary 1 summarizes this equivalence for cases where n ≤ 4 Limitations and Future Directions For economies with n ≥ 5, the necessity of the top-two condition is not established in full generality, although it covers important domains like the single-peaked and circular domains which fail the condition The paper concludes by noting that a non-TTC rule satisfying the axioms exists for every domain covered by Theorem 2, and suggests future work should explore whether such rules can execute longer trading cycles precluded by TTC The top-two condition is introduced as a valuable tool for analyzing object reallocation problems under domain restrictions The authors establish that standard characterizations of TTC extend to every restricted domain that satisfies this condition They provide a partial converse showing that for domains failing the condition in a small subset, a non-TTC rule satisfying the axioms exists The paper concludes by presenting an example of a domain that fails the top-two condition but is not covered by Theorem 2 when n ≥ 5 References Abdulkadiroglu, A.
Warren: and T.
Ruth: S ˘ onmez ¨ (1999): “House allocation with existing tenants,” Journal of Economic Theory, 88, 233–260 Alcalde, J.
Title and authors: Ruth: So we're looking at this paper called TTC Domains, and it basically asks if the standard ways we define Top Trading Cycles, those characterizations based on individual rationality, efficiency, and strategyproofness, still hold when the preferences aren't totally unrestricted.
Warren: That’s the core question here. It’s about whether those rules for reallocating objects still work if we put some restrictions on how people rank things.
Iris: The paper introduces something new called the top-two condition to test this, and they show that this condition is actually enough to guarantee that Top Trading Cycles is the only rule satisfying individual rationality, pair efficiency, and strategyproofness on a domain that meets it.
Ruth: That’s a big claim because it means if your preference structure satisfies that top-two condition, you don't need to worry about other rules emerging.
Warren: It really simplifies things for anyone trying to classify these allocation rules; if the domain passes the test, TTC is the one and only option under those axioms.
Iris: But they also provide a partial converse, which means they can actually construct a rule that isn't Top Trading Cycles but still satisfies individual rationality, Pareto efficiency, and strategyproofness in specific cases.
Ruth: So it’s not just a black or white answer; there are some tricky spots where the characterization breaks down under certain conditions.
Warren: It sounds like they are showing us exactly where the limits of those standard incentive compatibility results lie when we start restricting the preference domain.
Iris: And they point to specific types of domains, like the single-peaked and single-dipped domains, as examples where this top-two condition is relevant.
Ruth: It suggests that understanding these specific geometric shapes of preferences can tell us a lot about whether standard models hold true in those settings.
Warren: It gives us a way to filter which preference environments we can trust for our analysis of trading cycles.
Iris: And they also mention that for larger systems, say when you have five or more objects, the necessity of that top-two condition isn't fully proven yet in general.
Ruth: So while it’s a great tool for smaller cases like n less than or equal to four, we still have some open questions about those bigger markets.
Title and authors: Warren: It seems like this whole TTC Domains paper is setting up a framework to distinguish between domains where the standard characterizations hold and those where they don't.
Iris: And that distinction is crucial because it helps us understand when we can rely on the unique rule being Top Trading Cycles for our analysis of these complex problems.
Ruth: So, moving on to how they actually frame their argument, this paper explores what happens when we limit the domain of preferences, which is a key part of this object reallocation problem.
Warren: They start by looking at the original problem introduced by Shapley and Scarf in one thousand nine hundred seventy-four and see if the characterizations for Top Trading Cycles extend beyond just unrestricted domains <ref:2501.15422#pg1>.
Iris: The paper lays out that they introduce this top-two condition as a richness condition, which they then use to show sufficiency—meaning if a domain satisfies it, TTC is the unique rule satisfying individual rationality, pair efficiency, and strategyproofness.
Ruth: That’s the main engine of the argument: showing that the top-two condition leads directly to uniqueness under those specific axioms.
Warren: And then they also handle necessity by showing that if you fail this top-two condition in a small subset of objects and meet some mild extension condition, you can build a rule different from TTC that still hits all those incentive compatibility targets.
Iris: They use the concept of pair efficiency, which is slightly weaker than pure Pareto efficiency, to strengthen their characterization by showing that under the top-two condition, this weaker requirement is enough.
Ruth: It’s interesting how they build up from the original characterizations by using these specific structural conditions on the preference domain to see what holds true.
Warren: And they use examples like a preference profile in Table one to show exactly when TTC fails to execute a longer trading cycle, which motivates why we need this condition in the first place <ref:2501.15422#pg2>.
Iris: For someone who only listens to this, the implication is that we can now rapidly check if our model's preference structure allows us to use the established characterizations for Top Trading Cycles.
Title and authors: Ruth: It’s a practical tool for economists trying to classify models based on their underlying assumptions about how people value things.
Warren: And it gives quantitative traders a way to think about the stability of rules when you introduce real-world constraints on agent preferences.
Iris: It highlights that the relationship between efficiency and strategyproofness is highly sensitive to the structure of the preference domain itself, not just the agents' individual choices.
Ruth: So, before we wrap up, what’s their view on how this changes our understanding of Top Trading Cycles in general?
Warren: They suggest that this condition gives us a much more precise way to identify which domains are guaranteed to be well-behaved under the standard incentive constraints.
Iris: It refines the existing characterizations by connecting them directly to geometric properties of the preference space, like whether it satisfies this top-two requirement.
Ruth: It’s basically providing a structural test for when we can claim that a unique rule exists based on these core axioms for object reallocation problems.
Warren: And they leave us with the nuance that even when things get complicated, like with five or more objects, we still need to be careful about fully proving this necessity.
Iris: It’s a lot of structural work showing how small local failures in the top-two condition can lead to entirely different reallocation rules that still look good on paper.
Ruth: So, if you take one thing away from this paper, it’s the top-two condition is a powerful litmus test for classifying preference domains in this area.
Warren: It's a useful tool for narrowing down which theoretical results apply to which real-world setups where preferences are constrained.
Iris: And it points toward future work exploring those cases where the condition fails, trying to figure out if non-TTC rules can still be incentive compatible in those tricky spots.
Ruth: It’s a solid step forward in understanding the boundaries of what we can expect from these classic results on Top Trading Cycles.
Warren: We’ll keep an eye on this because it helps us think more critically about the assumptions underlying our market models as we build them up.
The paper's summary: Ruth: So, to wrap up this part, the paper is essentially showing us how we can use this top two condition as a filter to decide if we can trust those standard rules for Top Trading Cycles when things get complicated with preference restrictions.
Warren: Right, it’s like they’re giving us a scorecard for preference domains. If your domain passes that top two check, then you know for sure that the unique rule we call Top Trading Cycles is the only one that fits all those basic rules we use—individual rationality, pair efficiency, and strategyproofness.
Ruth: Exactly. But they don't stop there because they also show a partial converse. That means they can actually build a different rule that isn't Top Trading Cycles but still manages to be individually rational and Pareto efficient as long as the top two condition fails in just a small group of objects, following some specific setup.
Warren: That’s the nuance, I guess. It tells us that even when standard theory breaks down because the condition fails somewhere tiny, you can still construct an incentive compatible outcome that isn't TTC. It shows where those standard axioms don't guarantee uniqueness anymore.
Ruth: And they point out some specific domains they have in mind—like the single-peaked or circular ones—where this top two condition is important because those are the kinds of preference shapes we see in real life, like preferences for a specific location or a certain type of product.
Warren: It’s useful for someone trying to classify their market model. If you see your preference structure, you can quickly check if it falls into a category where TTC is guaranteed to be the unique solution under those axioms.
Ruth: For me, what this means is that we have a new tool for structural analysis of preferences. Instead of just looking at the agents' choices, we can look at the shape of their ranking structure and see what kind of allocation rule is possible.
Warren: It’s not just about theory; it affects how we think about market stability. If you know your domain satisfies the top two condition, you have a very strong guarantee about how trading cycles will behave under those rules.
Ruth: And if it doesn't, as the paper shows, you have to be ready to construct alternative rules that still satisfy those basic incentive compatibility requirements.
Warren: It opens up a whole new way to test the robustness of these characterizations across different preference environments.
The paper's improvements: Tom: So, to recap where we are, the paper established that you can use that top two condition as a filter to see if standard Top Trading Cycles characterizations hold up when you restrict the preference domain.
Ruth: Exactly. And now they suggest some ways we can make this concept more practical for real-world applications and analysis.
Warren: They are proposing ways to distinguish between different kinds of efficiency requirements, like pair efficiency versus full Pareto efficiency, by looking at how the preference domain satisfies that top two condition in relation to some auxiliary profiles they built up in tables.
Iris: That’s interesting because it means we can pick the right set of axioms for our problem setting—do we need just pair efficiency, or do we need the stronger full Pareto efficiency?
Ruth: And they are suggesting that for domains that fail the top two condition in a small subset, if that failure happens under certain conditions, you can actually construct a rule that isn't Top Trading Cycles but still passes those core tests.
Warren: It’s like giving us a roadmap for when to expect standard results to break down and what kind of alternative rules might pop up instead.
Iris: The implication is that for cases with less than or equal to four objects, checking the top two condition is enough to determine if those standard characterizations are valid at all.
Ruth: That’s a big win for rapid analysis in smaller markets, because you don't have to run a huge simulation just to know if you can rely on TTC.
Warren: But they also flag that for systems with five or more objects, this full necessity of the top two condition isn't proven in general yet.
Iris: So while it’s great for smaller economies, we still need more work to fully establish this across the board, especially for those complex domains like single-peaked ones.
Ruth: It means they are setting up a clear path forward: use this condition as your first check, and if it passes, you have a unique answer under those axioms.
Warren: And if it fails in a small spot, you know you can't rely on the standard TTC rule, but the paper gives you a starting point for building something else that still works nicely.
Conclusion: Ruth: So we've covered how the paper "TTC Domains" uses that top two condition to filter preference domains for object reallocation problems, showing when those standard Top Trading Cycles rules hold true and when they don't.
Warren: Right, it’s essentially a way to use a geometric property of preferences—that top two condition—to decide if we can trust the unique rule we call Top Trading Cycles.
Iris: And they showed that for smaller systems, like when you have four or fewer objects, checking that top two condition is enough to confirm the standard characterizations are valid.
Ruth: That’s a solid point for quick model checks in simpler environments. But they also pointed out the necessity of that condition isn't proven in full generality when you move up to five or more objects, which is where things get trickier for us.
Warren: So the limitation is that we can't fully guarantee that condition holds for every single setup when you have a larger market size.
Iris: And they did give us a way to construct a non-TTC rule if the condition fails in just a small subset of objects, provided those specific extension conditions are met.
Ruth: It means that even when the standard framework breaks down locally, you can still find an incentive compatible allocation that isn't TTC.
Warren: That tells us about where the actual strategy costs are coming from—sometimes it’s not a huge systemic failure, but a small local breakdown in preference structure.
Iris: So for someone who only listens to this, it means we need to look closely at the shape of preferences when we analyze these reallocation problems instead of just assuming unrestricted domains.
Ruth: It refines our understanding of what's possible under different constraints on agent preferences, which is really important for modeling real markets.
Warren: It gives us a tool to quickly assess the stability and uniqueness of allocation rules based on the structure of the preference domain.
Iris: We'll keep an eye out for future work that tackles those larger systems where the top two condition isn't fully established as necessary, because that’s where a lot of complex behavior might emerge.
Ruth: Exactly. Now, next week we look at how AI is changing things in R andD and innovation, which is a totally different kind of structural constraint on incentives.
Sumit Goel, §Yuki Tamura
University of Essex · Ecole Polytechnique, CREST, IP Paris
econ.TH, cs.GT
Submitted: 2025-01-26
Updated: 2026-11-16
Comments: 25 pages, 3 tables. v5: proves that the top-two condition is also necessary, yielding a full characterization of TTC domains
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: For the object reallocation problem, this paper studies whether characterizations of Top Trading Cycles (TTC) based on individual rationality, efficiency…
Key concepts
- Top Trading Cycles (TTC)
- A rule describing how objects are reallocated in a market, often related to trading cycles. The paper examines whether standard characterizations of this rule hold true even when the preferences of the participants are restricted to certain types of domains.
- Top-Two Condition
- A specific requirement for a set of objects: if any two objects can each be ranked first within that set, then those two objects must also be rankable as the top two in both possible orderings. This condition is crucial for determining when TTC is the unique rule satisfying certain axioms.
- Individual Rationality, Pareto Efficiency, Strategyproofness
- These are standard desirable properties for an allocation rule. Individual rationality means participants prefer their outcome over not participating. Pareto efficiency means no one can be made better off without making someone else worse off. Strategyproofness means participants cannot benefit by misrepresenting their true preferences.
Terminology
Summary
For the object reallocation problem, this paper studies whether characterizations of Top Trading Cycles (TTC) based on individual rationality, efficiency, and strategyproofness on the unrestricted domain extend to restricted preference domains. p. 0 TTC Domains∗
Sumit Goel† Yuki Tamura‡
June 23, 2026
(Link to latest version)
Abstract
For the object reallocation problem, we study whether characterizations of Top
Trading Cycles (TTC) based on individual rationality, efficiency, and strategyproofness
on the unrestricted domain extend to restricted preference domains. We introduce the
top-two condition and show that it offers a useful criterion for answering this question.Where the paper says it
Introduction to the Core Problem
This paper investigates the object reallocation problem introduced by Shapley and Scarf (1974), focusing on whether characterizations of Top Trading Cycles (TTC) extend from the unrestricted domain to restricted preference domains The central question addressed is under what domain restrictions do the characterizations of TTC by Ma (1994) and Ekici (2024) continue to hold This is motivated by preference profiles where TTC may preclude arbitrarily long trading cycles, prompting an exploration of how limiting opportunities for misrepresentation can enrich the class of rules satisfying the axioms
The Top-Two Condition and Sufficiency
A key concept introduced is the top-two condition, which requires that within every subset of objects, if two objects can each be ranked first, then they can also be ranked as the top two in both possible orders The authors first show that this condition is sufficient: if a domain satisfies the top-two condition, then TTC is the unique rule satisfying individual rationality, pair efficient, and strategyproof This sufficiency is demonstrated by showing that if a rule satisfies the weaker requirement of pair efficiency under individual rationality and strategyproofness, it must coincide with TTC
Necessity and Counterexamples
The paper also explores necessity by constructing a non-TTC rule when the top-two condition fails in a specific way Specifically, if there exists a small subset of objects within which the failure occurs and every object outside this subset can be ranked first relative to the objects in the subset, then a non-TTC rule satisfying individual rationality, Pareto efficiency, and strategyproofness can be constructed Theorem 2 formalizes this partial converse for domains where the top-two condition fails within a small subset of objects
Characterization of TTC Domains
The sufficiency result establishes that TTC is the unique rule satisfying individual rationality, Pareto efficiency, and strategyproofness on any domain satisfying the top-two condition The authors then identify several important domains as TTC domains based on this condition, including the single-dipped domain and the partial-agreement domain Corollary 1 summarizes this equivalence for cases where n ≤ 4
Limitations and Future Directions
For economies with n ≥ 5, the necessity of the top-two condition is not established in full generality, although it covers important domains like the single-peaked and circular domains which fail the condition The paper concludes by noting that a non-TTC rule satisfying the axioms exists for every domain covered by Theorem 2, and suggests future work should explore whether such rules can execute longer trading cycles precluded by TTC
Conclusion
The top-two condition is introduced as a valuable tool for analyzing object reallocation problems under domain restrictions The authors establish that standard characterizations of TTC extend to every restricted domain that satisfies this condition They provide a partial converse showing that for domains failing the condition in a small subset, a non-TTC rule satisfying the axioms exists The paper concludes by presenting an example of a domain that fails the top-two condition but is not covered by Theorem 2 when n ≥ 5
References
Abdulkadiroglu, A. and T. S ˘ onmez ¨ (1999): “House allocation with existing tenants,” Journal of Economic Theory, 88, 233–260
Alcalde, J. and S. Barbera (1994): “Top dominance and the possibility of strategyproof stable solutions to matching problems,” Economic Theory, 4, 417–435
Anno, H.: “A short proof for the characterization of the core in housing markets,” Economics Letters, 126, 66–67
Aswal, N., S. Chatterji, and A. p. 3 We refer to a set of
agents, their endowments, and their preferences over these objects as an economy. 2
In a similar spirit, Alcalde and Barbera (1994) propose the top-dominance criterion for two-sided matching, and Aswal, Chatterji, and Sen (2003) introduce the notion of linked domains in social choice.Where the paper says it
Bade, S.: “Matching with single-peaked preferences,” Journal of Economic Theory, 180, 81–99
Bird, C. G.: “Group incentive compatibility in a market with indivisible goods,” Economics Letters, 14, 309–313
Carroll, G.: “A general equivalence theorem for allocation of indivisible objects,” Journal of Mathematical Economics, 51, 163–177
Chatterji, S. and A. Sen (2011): “Tops-only domains,” Economic Theory, 46, 255–282
Ehlers, L.: “Top trading with fixed tie-breaking in markets with indivisible goods,” Journal of Economic Theory, 151, 64–87
Ekici, O.: “Pair-efficient reallocation of indivisible objects,” Theoretical Economics, 19, 551–564
Ekici, O. and J. Sethuraman ¨ (2024): “Characterizing the TTC rule via pair-efficiency: A short proof,” Economics Letters, 234, 111459
Elkind, E., M. Lackner, and D. p. 3 In early
work, Sen and Pattanaik (1969) identify domain restrictions ensuring transitivity of the majority relation. A survey by Elkind, Lackner, and Peters (2022) reviews a wide range of domain restrictions, some of which
may be relevant in our context. In early
work, Sen and Pattanaik (1969) identify domain restrictions ensuring transitivity of the majority relation. A survey by Elkind, Lackner, and Peters (2022) reviews a wide range of domain restrictions, some of which
may be relevant in our context.Where the paper says it
Where the paper says it
Fujinaka, Y. and T. Wakayama (2018): “Endowments-swapping-proof house allocation,” Games and Economic Behavior, 111, 187–202
Hu, X. and J. Zhang (2024): “Characterization of Top Trading Cycles with single-dipped preferences,” Economics Letters, 241, 111822
Hylland, A. and R. Zeckhauser (1979): “The efficient allocation of individuals to positions,” Journal of Political Economy, 87, 293–314
Ma, J.: “Strategy-proofness and the strict core in a market with indivisibilities,” International Journal of Game Theory, 23, 75–83
Miyagawa, E.: “Strategy-proofness and the core in house allocation problems,” Games and Economic Behavior, 38, 347–361
Morrill, T.: “An alternative characterization of top trading cycles,” Journal of Mathematical Economics, 112, 102984
Morrill, T. and A. E. Roth (2024): “Top trading cycles,” Journal of Mathematical Economics, 112, 102984
Nicolo, A. and C. Rodriguez-Alvarez (2017): “Age-based preferences in paired kidney exchange,” Games and Economic Behavior, 102, 508–524
Papai, S.: “Strategyproof assignment by hierarchical exchange,” Econometrica, 68, 1403–1433
Pycia, M. and M. U. Unver ¨ (2017): “Incentive compatible allocation and exchange of discrete resources,” Theoretical Economics, 12, 287–329
Roth, A. E.: “Incentive compatibility in a market with indivisible goods,” Economics Letters, 9, 127–132
Roth, A. E., T. Sonmez, and M. U. ¨ Unver ¨ (2004): “Kidney exchange,” The Quarterly Journal of Economics, 119, 457–488
Sato, S.: “Circular domains,” Review of Economic Design, 14, 331–342
Schummer, J. and R. V. Vohra (2013): “Assignment of arrival slots,” American Economic Journal: Microeconomics, 5, 164–185
Sen, A. and P. K. Pattanaik (1969): “Necessary and sufficient conditions for rational choice under majority decision,” Journal of Economic Theory, 1, 178–202
Sethuraman, J.: “An alternative proof of a characterization of the TTC mechanism,” Operations Research Letters, 44, 107–108
Shapley, L. and H. Scarf (1974): “On cores and indivisibility,” Journal of Mathematical Economics, 1, 23–37
Sonmez, T. ¨ (1999): “Strategy-proofness and essentially single-valued cores,” Econometrica, 67, 677–689
Svensson, L.-G.: “Strategy-proof allocation of indivisible goods,” Social Choice and Welfare, 16, 557–567
Takamiya, K.: “Coalition strategy-proofness and monotonicity in Shapley–Scarf housing markets,” Mathematical Social Sciences, 41, 201–213
Tamura, Y.: “Object reallocation problems with single-dipped preferences,” Games and Economic Behavior, 140, 181–196
Tamura, Y. and H.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can now verify if a rule is Top Trading Cycles (TTC) by checking if it satisfies individual rationality, Pareto efficiency, and strategyproofness under a top-two condition on preference domains. This allows for automatic classification of allocation rules based on domain restrictions.
-
The system can distinguish between characterizations of TTC based on pair efficiency and those based on Pareto efficiency by analyzing whether the preference domain satisfies the top-two condition in relation to auxiliary profiles like Table 2 and Table 3. This enables the selection of the most appropriate axiom combination for a given problem setting.
-
For domains that fail the top-two condition, AI systems can construct a non-TTC rule satisfying individual rationality, Pareto efficiency, and strategyproofness if the failure occurs within a small subset of objects and meets specific extension conditions. This provides a mechanism to identify when TTC is not uniquely characterized by these axioms in complex environments.
-
The system can check if a domain is a TTC domain for cases with n less than or equal to four by verifying the top-two condition, which is equivalent to the existence of a unique individually rational, Pareto efficient, and strategyproof rule. This allows for rapid determination of whether standard characterizations hold in small economies under specific domain constraints.
Abstract
The Top Trading Cycles (TTC) rule is fundamental to object reallocation: it is the only rule that is individually rational, pair efficient, and strategyproof on the unrestricted domain. Despite its desirable properties, at some profiles, TTC precludes longer trading cycles that could lead to more appealing allocations. We explore restricted preference domains as an avenue for finding alternative rules satisfying the three axioms. Our main contribution is to introduce a richness condition on domains, the top-two condition, and show that it characterizes TTC domains: domains to which the above characterization of TTC extends. The condition requires that, within every subset of objects, any two objects that can each be ranked first can also be ranked as the top two, in both possible orders. For every domain that fails the top-two condition, we construct a rule distinct from TTC that is individually rational, Pareto efficient, and strategyproof, and that executes longer trading cycles that TTC precludes.