On the difficulty of characterizing top trading cycles with identical houses

arXiv:2611.03251 · econ.TH · Submitted 2026-11-02 · Read on arXiv

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: "On the difficulty of characterizing top trading cycles with identical houses".

Warren: Here's the gist of the paper. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness, properties that need not hold under general weak preferences The paper studies Shapley–Scarf housing markets where agents are indifferent between houses of the same type but rank the types strictly, and investigates whether characterizations for strict or weak preferences extend to this domain Model and Properties The model defines a population with two house types, where agents own houses of specific types, and preferences are restricted to be indifferent between houses of the same type and strict between houses of different types The welfare equivalence between matchings is defined by whether they induce the same type allocation for each agent Key properties examined include individual rationality, Pareto efficiency, strategy-proofness, group strategy-proofness, non-bossiness, and consistency Group strategy-proofness is shown to be equivalent to the conjunction of strategy-proofness and welfare non-bossiness under strict preferences Characterization Limitations The paper demonstrates that neither the characterization of Ma (1994) nor that of Ehlers (2014) extends to the domain of objective indifferences This failure is explained by two main reasons: first, the set of possible reports is much smaller, as agents can only rank types Second, consistency can remove groups whose collective allotments are their collective endowments, which is not possible in this domain because a group can leave with other houses if each remaining agent can still be endowed with a house of his own type Counterexample Construction A five-agent counterexample is constructed where a rule satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency but is not welfare equivalent to any TTC rule with fixed tie-breaking This counterexample shows that the characterization of Ma (1994) fails because the rule coincides with a TTC rule except at a specific profile where reports are unavailable Furthermore, the rule is not welfare equivalent to any TTC rule with fixed tie-breaking because it differs from the TTC rule only at one specific problem (N, R∗) Minimality Results The paper establishes minimality results for the counterexample, showing that five agents are minimal for a fixed-population result with two types of houses For the characterization in Theorem B, four agents are minimal for a counterexample where the rule fails to be welfare equivalent to any TTC rule with fixed tie-breaking across all coalitions Robustness and Conclusion The rule constructed, denoted as ψ, satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency However, the characterizations of TTC rules for strict preferences and TTC rules with fixed tie-breaking for weak preferences do not single out TTC rules with fixed tie-breaking on this domain The conclusion is that a characterization of these rules requires properties beyond those used in the existing characterizations Appendix C Details The appendix confirms that for two-type populations with at most five agents and type compositions aab, aaab, aabb, or aaaab, the welfare rules satisfying individual rationality, Pareto efficiency, and group strategy-proofness are exactly those induced by TTC rules with fixed tie-breaking This confirms the fixed-population minimality statement The script used to determine these welfare rules shows that 528 of the 864 welfare rules in W are not induced by any TTC rule with fixed tie-breaking The results establish the fixed-population minimality statement and show that five agents are minimal for the fixed-population result The computer verification confirms that no fixed-population counterexample exists for populations with type composition aab, aaab, aabb, or aaaab The results establish the fixed-population minimality statement and show that five agents are minimal for the fixed-population result.

Ruth: Appendix B Details The four-agent counterexample in Appendix B shows that the rule ψe satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency This rule is not welfare equivalent to any TTC rule with fixed tie-breaking The analysis shows that the restriction of ψe to the coalition of all four agents is welfare equivalent to a TTC rule with fixed tie-breaking, but two coalitions require incompatible tie-breaking orders for agent 3 The paper concludes that although TTC rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness on the domain of objective indifferences, the properties that characterize the TTC rule for strict preferences and TTC rules with fixed tie-breaking for weak preferences do not single out TTC rules with fixed tie-breaking on this domain The rule ψ satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency but already for a fixed population of five agents it is not welfare equivalent to any TTC rule with fixed tie-breaking The same rule shows that several other characterizations of TTC for strict preferences do not extend either References Afacan, M.

Warren: O., Hu, G., and Li, J.

Ruth: (2024): “Housing Markets since Shapley and Scarf.” Journal of Mathematical Economics, 111: 102967 Altunta¸s, A., Phan, W., and Tamura, Y.

Title and authors: Ruth: So this paper is called "On the difficulty of characterizing top trading cycles with identical houses." It deals with those housing markets where agents are indifferent between houses of the same type but rank the types strictly.

Warren: That sounds like a pretty specific setup. It’s looking at how well we can define these top trading cycle rules when you add that strict ranking constraint on types.

Iris: And it starts by saying that on this domain of objective indifferences, the top trading cycles with fixed tie-breaking do regain Pareto efficiency and group strategy-proofness, which isn't always true under general weak preferences.

Ruth: Exactly. The authors are asking if the established characterizations for strict preferences by Ma and Ehlers extend over to this domain of objective indifferences.

Warren: It seems they aren't extending them, which is the main point they make about the limitations of those existing rules when you restrict how people perceive things.

Iris: The paper constructs a specific rule that satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency for five agents and two house types.

Ruth: That's the core result they establish: they have this rule that works under those specific conditions but isn't equivalent to any top trading cycle rule with fixed tie-breaking.

The paper's summary: Ruth: So what’s the big picture here? The paper summarizes how their constructed rule behaves—it meets a lot of nice criteria, but it just doesn't map onto the existing characterizations for top trading cycles.

Warren: Basically, they show that those existing rules are too restrictive because they assume more freedom in reporting than what happens in this housing market scenario.

Iris: The summary points out two main reasons why the characterization of Ma and Ehlers fail to extend: first, the set of possible reports is much smaller than for strict or general weak preferences.

Ruth: That makes sense. If you can only report on a limited set of things, it puts a constraint on what kind of rule you can even define successfully.

Warren: And the second reason they give is that consistency can remove groups whose collective allotments are their collective endowments, which isn't possible in this domain because a group can leave with other houses if each remaining agent can still be endowed with a house of his own type.

Iris: That’s an important distinction. It shows that the structure of the market itself—the ability to leave and still get what you need—affects what kind of rules are possible.

The paper's improvements: Ruth: The authors suggest some improvements by showing that their rule, which satisfies all those individual properties, is not welfare equivalent to any top trading cycle rule with fixed tie-breaking across the board.

Warren: They found a five agent counterexample where this rule fails to be welfare equivalent to any TTC rule with fixed tie-breaking because it differs from it only at one specific profile.

Iris: Furthermore, the paper establishes minimality results for that counterexample. They find that five agents are minimal for a fixed-population result with two types of houses.

Ruth: And they also showed that four agents are minimal when looking at the characterization in Theorem B, where the rule fails to be welfare equivalent to any top trading cycle rule with fixed tie-breaking across all coalitions.

Warren: They even verified that for specific type compositions like aab, aaab, aabb, or aaaab and with at most five agents, the welfare rules satisfying individual rationality and Pareto efficiency are exactly those induced by top trading cycles with fixed tie-breaking.

Conclusion: Ruth: To wrap up the main point of "On the difficulty of characterizing top trading cycles with identical houses," it’s that even when we impose objective indifferences, the established characterizations for strict preferences and weak preferences don't single out those fixed tie-breaking rules.

Warren: The rule they construct satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency but isn't welfare equivalent to any top trading cycle rule with fixed tie-breaking.

Iris: It shows that a characterization of these rules requires properties beyond what we currently use in the existing literature.

Ruth: The implication is that we need new properties to characterize these rules when dealing with this specific type of market structure.

Bettina Klaus

Faculty of Business and Economics, University of Lausanne

econ.TH

Submitted: 2026-11-02

Updated: 2026-11-02

Comments: 33 pages, 3 tables. The Python scripts for the computer search in Appendix C are available as ancillary files

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 74/100

The gist: On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness…

Key concepts

Objective Indifferences
This is a market setting where agents are indifferent among houses of the same type but have a strict ranking between different types. It simplifies the preference structure compared to general weak preferences, allowing researchers to test how standard market rules behave under this specific condition.
Group Strategy-Proofness
This property ensures that no group of agents can benefit by colluding against the mechanism. The paper explores its relationship with individual strategy-proofness and non-bossiness, finding that under strict preferences, these concepts are linked.
TTC Rules with Fixed Tie-Breaking
These are specific rules for allocating houses based on Top Trading Cycles where ties between options of the same type are broken using a fixed order. The paper examines whether these rules maintain key properties like Pareto efficiency and group strategy-proofness in objective indifference settings.

Terminology

Summary

On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness, properties that need not hold under general weak preferences The paper studies Shapley–Scarf housing markets where agents are indifferent between houses of the same type but rank the types strictly, and investigates whether characterizations for strict or weak preferences extend to this domain

Model and Properties

The model defines a population with two house types, where agents own houses of specific types, and preferences are restricted to be indifferent between houses of the same type and strict between houses of different types The welfare equivalence between matchings is defined by whether they induce the same type allocation for each agent Key properties examined include individual rationality, Pareto efficiency, strategy-proofness, group strategy-proofness, non-bossiness, and consistency Group strategy-proofness is shown to be equivalent to the conjunction of strategy-proofness and welfare non-bossiness under strict preferences

Characterization Limitations

The paper demonstrates that neither the characterization of Ma (1994) nor that of Ehlers (2014) extends to the domain of objective indifferences This failure is explained by two main reasons: first, the set of possible reports is much smaller, as agents can only rank types Second, consistency can remove groups whose collective allotments are their collective endowments, which is not possible in this domain because a group can leave with other houses if each remaining agent can still be endowed with a house of his own type

Counterexample Construction

A five-agent counterexample is constructed where a rule satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency but is not welfare equivalent to any TTC rule with fixed tie-breaking This counterexample shows that the characterization of Ma (1994) fails because the rule coincides with a TTC rule except at a specific profile where reports are unavailable Furthermore, the rule is not welfare equivalent to any TTC rule with fixed tie-breaking because it differs from the TTC rule only at one specific problem (N, R∗)

Minimality Results

The paper establishes minimality results for the counterexample, showing that five agents are minimal for a fixed-population result with two types of houses For the characterization in Theorem B, four agents are minimal for a counterexample where the rule fails to be welfare equivalent to any TTC rule with fixed tie-breaking across all coalitions

Robustness and Conclusion

The rule constructed, denoted as ψ, satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency However, the characterizations of TTC rules for strict preferences and TTC rules with fixed tie-breaking for weak preferences do not single out TTC rules with fixed tie-breaking on this domain The conclusion is that a characterization of these rules requires properties beyond those used in the existing characterizations

Appendix C Details

The appendix confirms that for two-type populations with at most five agents and type compositions aab, aaab, aabb, or aaaab, the welfare rules satisfying individual rationality, Pareto efficiency, and group strategy-proofness are exactly those induced by TTC rules with fixed tie-breaking This confirms the fixed-population minimality statement The script used to determine these welfare rules shows that 528 of the 864 welfare rules in W are not induced by any TTC rule with fixed tie-breaking The results establish the fixed-population minimality statement and show that five agents are minimal for the fixed-population result The computer verification confirms that no fixed-population counterexample exists for populations with type composition aab, aaab, aabb, or aaaab The results establish the fixed-population minimality statement and show that five agents are minimal for the fixed-population result.

Appendix B Details

The four-agent counterexample in Appendix B shows that the rule ψe satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency This rule is not welfare equivalent to any TTC rule with fixed tie-breaking The analysis shows that the restriction of ψe to the coalition of all four agents is welfare equivalent to a TTC rule with fixed tie-breaking, but two coalitions require incompatible tie-breaking orders for agent 3

Conclusion Summary

The paper concludes that although TTC rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness on the domain of objective indifferences, the properties that characterize the TTC rule for strict preferences and TTC rules with fixed tie-breaking for weak preferences do not single out TTC rules with fixed tie-breaking on this domain The rule ψ satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency but already for a fixed population of five agents it is not welfare equivalent to any TTC rule with fixed tie-breaking The same rule shows that several other characterizations of TTC for strict preferences do not extend either

References

Afacan, M. O., Hu, G., and Li, J. (2024): “Housing Markets since Shapley and Scarf. p. 1

Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

” Journal of Mathematical Economics, 111: 102967 Altunta¸s, A. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

, Phan, W., and Tamura, Y. p. 2
Where the paper says it

Proofs of the characterization of Ma (1994) rely on auxiliary profiles that contain such reports. For restricted domains of strict preferences, Goel and Tamura (2026) show that this characterization extends whenever their top-two condition guarantees these reports, and that it fails on many domains that violate the condition, including all such domains with at most four houses.

p. 2
Where the paper says it

Proofs of the characterization of Ma (1994) rely on auxiliary profiles that contain such reports. For restricted domains of strict preferences, Goel and Tamura (2026) show that this characterization extends whenever their top-two condition guarantees these reports, and that it fails on many domains that violate the condition, including all such domains with at most four houses.

(2023): “Some Characterizations of Generalized Top Trading Cycles. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Games and Economic Behavior, 141: 156–181 Alva, S. p. 3
Where the paper says it

In Appendix B, we show that a counterexample to extending the characterization of Ehlers (2014) already exists with four agents. This four-agent counterexample does not apply to the characterization of Ma (1994): on the problems with all four agents, the rule is welfare equivalent to a TTC rule with fixed tie-breaking, and its failure of welfare equivalence arises only through its behavior on a problem with three agents; with two types, four agents are minimal for such a counterexample.

(2017): “When Is Manipulation All About the Ones and Twos? p. 6
Where the paper says it

A rule f is welfare non-bossy if for each problem (N, R), each i ∈ N, and each R′ i ∈ R(HN ), if fi(N,(R′ i , R−i)) Ii fi(N, R), then for each j ∈ N, fj (N,(R′ i , R−i)) Ij fj (N, R). For strict preferences, a rule is group strategy-proof if and only if it is strategy-proof and non-bossy (P´apai, 2000; Alva, 2017).

” Working paper, https://samsonalva. p. 4
Where the paper says it

The paper is organized as follows. In Section 2, we introduce the model and the properties, establish the relation between group strategy-proofness and welfare non-bossiness (the proof is given in Appendix A), introduce TTC rules with fixed tie-breaking, and state the characterizations of Ma (1994) and Ehlers (2014).

com/PWSP.pdf Bird, C. p. 1
Where the paper says it

(2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications. For housing markets with strict preferences, the TTC rule is individually rational and Pareto efficient (Shapley and Scarf, 1974; Roth and Postlewaite, 1977), strategy-proof (Roth, 1982), and group strategy-proof (Bird, 1984; Sandholtz and Tai, 2024).

G. (1984): “Group Incentive Compatibility in a Market with Indivisible Goods. p. 1
Where the paper says it

(2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications. For housing markets with strict preferences, the TTC rule is individually rational and Pareto efficient (Shapley and Scarf, 1974; Roth and Postlewaite, 1977), strategy-proof (Roth, 1982), and group strategy-proof (Bird, 1984; Sandholtz and Tai, 2024).

” Economics Letters, 14: 309–313 Chen, Y. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

, Jiao, Z., Zhang, C., and Zhang, L. (2025): “Some New Characterizations of Top Trading Cycles. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Journal of Mathematical Economics, 121: 103190 Chen, Y. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Zhao, F.: “Alternative Characterizations of the Top Trading Cycles Rule in Housing Markets. p. 1
Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

” Economics Letters, 201: 109806 Coreno, J. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Feng, D. p. 0
Where the paper says it

klaus@unil. I thank Jacob Coreno, Di Feng, and Mehmet Karakaya for helpful comments and suggestions.

: “Characterizing TTC via Endowments-Swapping-Proofness and Truncation-Proofness. p. 3
Where the paper says it

, 2025) do not extend to the domain of objective indifferences either: when their properties are formulated on this domain, treating houses of the same type as identical, our rule satisfies them. Since endowments-swapping-proofness (Fujinaka and Wakayama, 2018) compares problems with different assignments of houses to agents, we extend our rule to variable endowments; the extended rule satisfies endowments-swappingproofness (Proposition 2), and hence the characterizations of TTC that use this property do not extend either.

” Economics Letters, 247: 112159 Ehlers, L. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

: “Top Trading with Fixed Tie-Breaking in Markets with Indivisible Goods. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Journal of Economic Theory, 151: 64–87 Ekici, O. p. 1
Where the paper says it

Several authors refine this characterization by weakening Pareto efficiency or strategy-proofness or by replacing them with other properties (Takamiya, 2001; Fujinaka and Wakayama, 2018; Altunta¸s et al. , 2023; Ekici, 2024; Coreno and Feng, 2025, 2026; Chen et al.

: “Pair-Efficient Reallocation of Indivisible Objects. p. 1
Where the paper says it

Sandholtz and Tai (2026) study housing markets in which houses come in types, houses of the same type are identical, and each agent is indifferent between the houses of a type and ranks the types strictly. As they point out, such objective indifferences arise naturally when several available objects are effectively indistinguishable from the agents’ point of view, for example identical dorm rooms or school seats.

” ¨ Theoretical Economics, 19: 551–564 Ekici, O. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Sethuraman, J. p. 3
Where the paper says it

Several closely related characterizations of TTC for strict preferences (Takamiya, 2001; Altunta¸s et al. , 2023; Ekici, 2024; Ekici and Sethuraman, 2024; Coreno and Feng, 2026; Chen et al.

: “Characterizing the TTC Rule via Pair-Efficiency: A ¨ Short Proof. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Economics Letters, 234: 111459 Fujinaka, Y. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Wakayama, T. p. 1
Where the paper says it

Moreover, for strict preferences, Ma (1994) shows that the TTC rule is the only rule satisfying individual rationality, Pareto efficiency, and strategyproofness. Several authors refine this characterization by weakening Pareto efficiency or strategy-proofness or by replacing them with other properties (Takamiya, 2001; Fujinaka and Wakayama, 2018; Altunta¸s et al.

: “Endowments-Swapping-Proof House Allocation. p. 3
Where the paper says it

, 2025) do not extend to the domain of objective indifferences either: when their properties are formulated on this domain, treating houses of the same type as identical, our rule satisfies them. Since endowments-swapping-proofness (Fujinaka and Wakayama, 2018) compares problems with different assignments of houses to agents, we extend our rule to variable endowments; the extended rule satisfies endowments-swappingproofness (Proposition 2), and hence the characterizations of TTC that use this property do not extend either.

” Games and Economic Behavior, 111: 187–202 Goel, S. p. 2
Where the paper says it

Proofs of the characterization of Ma (1994) rely on auxiliary profiles that contain such reports. For restricted domains of strict preferences, Goel and Tamura (2026) show that this characterization extends whenever their top-two condition guarantees these reports, and that it fails on many domains that violate the condition, including all such domains with at most four houses.

and Tamura, Y.: “TTC Domains. p. 2
Where the paper says it

For restricted domains of strict preferences, Goel and Tamura (2026) show that this characterization extends whenever their top-two condition guarantees these reports, and that it fails on many domains that violate the condition, including all such domains with at most four houses. Our counterexample has a structure similar to that of their non-TTC rules: it coincides with a TTC rule except at a profile at which these reports are unavailable, and there one agent receives a house of his second-ranked type instead of his TTC allotment.

” Working paper, revised June 2026, arXiv:2501. p. 4
Where the paper says it

The paper is organized as follows. In Section 2, we introduce the model and the properties, establish the relation between group strategy-proofness and welfare non-bossiness (the proof is given in Appendix A), introduce TTC rules with fixed tie-breaking, and state the characterizations of Ma (1994) and Ehlers (2014).

15422v4 Hu, X. and Zhang, J.: “Local Unanimity in Shapley–Scarf Housing Markets. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Working paper, arXiv:2511. p. 4
Where the paper says it

The paper is organized as follows. In Section 2, we introduce the model and the properties, establish the relation between group strategy-proofness and welfare non-bossiness (the proof is given in Appendix A), introduce TTC rules with fixed tie-breaking, and state the characterizations of Ma (1994) and Ehlers (2014).

22027v1 Ignatiev, A., Morgado, A., and Marques-Silva, J.: “PySAT: A Python Toolkit for Prototyping with SAT Oracles.” In Theory and Applications of Satisfiability Testing – SAT 2018, Lecture Notes in Computer Science, 10929: 428–437 Karakaya, M. p. 0
Where the paper says it

I thank Jacob Coreno, Di Feng, and Mehmet Karakaya for helpful comments and suggestions. I gratefully acknowledge support from the Swiss National Science Foundation (SNSF) through Project 100018-231777.

and Klaus, B. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

: “Consistency of Top Trading Cycles Rules in Housing Markets with Identical Houses. p. 0
Where the paper says it

JEL classification: C78; D47. Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency.

” Working paper, University of Lausanne Klaus, B. p. 0
Where the paper says it

∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina. klaus@unil.

, Klijn, F., and Sethuraman, J. p. 3
Where the paper says it

Several closely related characterizations of TTC for strict preferences (Takamiya, 2001; Altunta¸s et al. , 2023; Ekici, 2024; Ekici and Sethuraman, 2024; Coreno and Feng, 2026; Chen et al.

: “A Characterization of the Top-TradingCycles Mechanism for Housing Markets via Respecting-Improvement. p. 0
Where the paper says it

JEL classification: C78; D47. Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency.

” Economics Letters, 247: 112145 Ma, J. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

: “Strategy-Proofness and the Strict Core in a Market with Indivisibilities. p. 0
Where the paper says it

On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences. We ask whether the characterization of the TTC rule for strict preferences by Ma (1994) and the characterization of TTC rules with fixed tie-breaking for weak preferences by Ehlers (2014) extend to this domain.

” International Journal of Game Theory, 23: 75–83 Morrill, T. p. 1
Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

and Roth, A. p. 1
Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

E.: “Top Trading Cycles. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Journal of Mathematical Economics, 112: 102984 P´apai, S. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

: “Strategyproof Assignment by Hierarchical Exchange.” Econometrica, 68: 1403–1433 Pycia, M. p. 6
Where the paper says it

We prove Proposition 1 in Appendix A. The first statement of Proposition 1 parallels Pycia and Unver (2025, Proposition 1), who show that, on rich domains, which allow for ¨ indifferences, group strategy-proofness is equivalent to strategy-proofness and non-bossiness formulated in terms of welfare.

and Unver, M. p. 6
Where the paper says it

We prove Proposition 1 in Appendix A. The first statement of Proposition 1 parallels Pycia and Unver (2025, Proposition 1), who show that, on rich domains, which allow for ¨ indifferences, group strategy-proofness is equivalent to strategy-proofness and non-bossiness formulated in terms of welfare.

U.: “Ordinal Simplicity in Discrete Mechanism Design.” ¨ International Economic Review, 66: 1665–1680 Roth, A. p. 1
Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

E.: “Incentive Compatibility in a Market with Indivisible Goods.” Economics Letters, 9: 127–132 Roth, A. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

E. and Postlewaite, A. p. 1
Where the paper says it

(2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications. For housing markets with strict preferences, the TTC rule is individually rational and Pareto efficient (Shapley and Scarf, 1974; Roth and Postlewaite, 1977), strategy-proof (Roth, 1982), and group strategy-proof (Bird, 1984; Sandholtz and Tai, 2024).

: “Weak versus Strong Domination in a Market with Indivisible Goods. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Journal of Mathematical Economics, 4: 131–137 Sandholtz, W. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Tai, A. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

: “Group Incentive Compatibility in a Market with Indivisible Goods: A Comment.” Economics Letters, 243: 111938 Sandholtz, W. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

and Tai, A.: “Shapley–Scarf Markets with Objective Indifferences. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

” Working paper, revised January 2026, arXiv:2503. p. 4
Where the paper says it

The paper is organized as follows. In Section 2, we introduce the model and the properties, establish the relation between group strategy-proofness and welfare non-bossiness (the proof is given in Appendix A), introduce TTC rules with fixed tie-breaking, and state the characterizations of Ma (1994) and Ehlers (2014).

18144v3 Scarf, H. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

E.: “My Introduction to Top-Trading Cycles. p. 1
Where the paper says it

1 Introduction Housing markets (Shapley and Scarf, 1974) and the top trading cycles (TTC) rule, which Shapley and Scarf (1974) attribute to David Gale, have been studied extensively; Afacan et al. (2024) survey the literature on housing markets since Shapley and Scarf (1974), and Morrill and Roth (2024) survey TTC and its applications.

” Games and Economic Behavior, 66: 630–631 Shapley, L. p. 3
Where the paper says it

In Appendix B, we show that a counterexample to extending the characterization of Ehlers (2014) already exists with four agents. This four-agent counterexample does not apply to the characterization of Ma (1994): on the problems with all four agents, the rule is welfare equivalent to a TTC rule with fixed tie-breaking, and its failure of welfare equivalence arises only through its behavior on a problem with three agents; with two types, four agents are minimal for such a counterexample.

S. and Scarf, H. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

E.: “On Cores and Indivisibility.” Journal of Mathematical Economics, 1: 23–37 Takamiya, K. p. 0
Where the paper says it

Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. ∗Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: bettina.

: “Coalition Strategy-Proofness and Monotonicity in Shapley–Scarf Housing Markets. p. 0
Where the paper says it

On the difficulty of characterizing top trading cycles with identical houses Bettina Klaus∗ November 3, 2026 Abstract We study Shapley–Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences.

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

  1. The AI system can be trained to distinguish between characterizations of Top Trading Cycles for strict preferences and those for weak preferences by analyzing whether a rule satisfies properties like individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency on the domain of objective indifferences.

  2. The system can be improved to identify when the characterization of Ma (1994) or Ehlers (2014) fails to extend to the domain of objective indifferences by detecting specific structural violations in a constructed counterexample, such as when the set of possible reports is much smaller than for strict or general weak preferences.

  3. The AI system can be enhanced to determine the minimality results for fixed-population counterexamples by performing computer searches, specifically identifying that five agents are minimal for this fixed-population result in two types when the type composition is aaabb.

  4. The system can be updated to recognize that certain characterizations of Top Trading Cycles, such as those based on pair-efficiency or truncation-proofness, do not extend to objective indifferences because the properties require adaptations from individual houses to types.

  5. The AI system can be equipped to verify if a welfare rule satisfies an endowments-swapping-proofness property by checking if it is equivalent to a TTC rule with fixed tie-breaking, as demonstrated by the extended rule psi satisfying this property for all endowment assignments.

Abstract

We study Shapley-Scarf housing markets (Shapley and Scarf, 1974) in which houses come in types and agents are indifferent between houses of the same type but rank the types strictly. On this domain of objective indifferences, top trading cycles (TTC) rules with fixed tie-breaking regain Pareto efficiency and group strategy-proofness (Sandholtz and Tai, 2026), properties that need not hold under general weak preferences. We ask whether the characterization of the TTC rule for strict preferences by Ma (1994) and the characterization of TTC rules with fixed tie-breaking for weak preferences by Ehlers (2014) extend to this domain. They do not. With five agents and two types of houses, we construct a rule that satisfies individual rationality, Pareto efficiency, group strategy-proofness, non-bossiness, and consistency, but whose restriction to the five-agent population is not welfare equivalent to any TTC rule with fixed tie-breaking. With two types, five agents are minimal for this fixed-population result. The same rule shows that several other characterizations of TTC for strict preferences do not extend either.

Sources

Related papers