On the difficulty of characterizing top trading cycles with identical houses
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 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. 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. 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. 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. 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. 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. 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). 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). (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). (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). 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. 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. 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. 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. 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. klaus@unil. I thank Jacob Coreno, Di Feng, and Mehmet Karakaya for helpful
comments and suggestions. , 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. , 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. 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. 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. 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). 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. 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). 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. 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. JEL classification: C78; D47. 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. klaus@unil. 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. JEL classification: C78; D47. Keywords: housing markets; identical houses; objective indifferences; top trading cycles; fixed tie-breaking; characterization; group strategy-proofness; consistency. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. (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). 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. 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. 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. 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. 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. 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. 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). 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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. -
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.
-
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
- Axioms for Top Trading Cycles in Multi-Object Reallocation
- TTC Domains
- Local unanimity in Shapley-Scarf housing markets
- Shapley-Scarf Markets with Objective Indifferences