On the difficulty of characterizing top trading cycles with identical houses

summary

The gist

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

In short

The study investigates whether rules that work for top trading cycles (TTC) with fixed tie-breaking regain efficiency and strategy-proofness when agents are indifferent between houses of the same type but rank types strictly. The paper shows that existing characterizations for strict or weak preferences fail in this domain, meaning new properties are needed to characterize TTC rules here.

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 used across episodes

This episode discusses

The paper

On the difficulty of characterizing top trading cycles with identical houses · Read on arXiv

Bettina Klaus

Faculty of Business and Economics, University of Lausanne

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.

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.

More episodes

← Home