Identical houses complicate the case for top trading cycles

A familiar mechanism, with identical objects

In a Shapley–Scarf housing market, each participant initially owns one house, and an allocation reassigns those houses among the participants. Klaus studies a version in which houses belong to types. Every participant strictly ranks the types but is indifferent between individual houses of the same type. Identical dorm rooms or school seats motivate this kind of preference structure, which the paper calls objective indifferences.

The benchmark mechanism is top trading cycles, or TTC. Each remaining participant points to their favorite available house, and each house points to its owner. These arrows form cycles. Participants in each cycle receive the houses they point to, and those participants and houses leave the procedure. The process repeats until everyone has an assignment.

When houses are tied in someone’s preferences, fixed tie-breaking orders determine which individual house they point to. These orders are set independently of reported preferences.

Good properties do not establish uniqueness

The preprint distinguishes two questions: whether TTC has desirable properties, and whether those properties uniquely identify TTC. Klaus reports earlier results showing that, with objective indifferences, fixed-tie-breaking TTC is Pareto efficient and group strategy-proof. Pareto efficiency means nobody can be made better off without making someone else worse off. Group strategy-proofness rules out coordinated misreports that leave every coalition member at least as well off and make someone strictly better off.

For unrestricted strict preferences, Ma’s 1994 characterization identifies TTC through individual rationality, Pareto efficiency and strategy-proofness. Individual rationality protects participants from receiving something worse than their original house; strategy-proofness prevents an individual from benefiting by misreporting preferences. Ehlers’s 2014 characterization addresses general weak preferences using additional requirements.

Klaus’s main claim is that neither characterization extends to objective indifferences. Her counterexample satisfies not only the protections above but also non-bossiness and consistency. Non-bossiness prevents someone from changing others’ exact assignments through a report change that leaves their own assignment unchanged.

The five-person counterexample

Three participants, numbered 1, 2 and 3, own type-A houses. Participants 4 and 5 own type-B houses. Klaus defines a rule that follows one particular fixed-tie-breaking TTC rule everywhere except at one preference profile: everyone prefers the other type to their own.

At that exceptional profile, participant 1 keeps their house. Participant 2 receives participant 4’s house; participant 4 receives participant 3’s; participant 3 receives participant 5’s; and participant 5 receives participant 2’s. These four participants form a single trading cycle and all receive their preferred type.

The outcome is efficient despite participant 1’s disappointment. Both type-B houses have gone to participants who prefer them. Giving one to participant 1 would make one of those recipients worse off.

Crucially, the claim is stronger than disagreement with the original TTC rule at this one profile. Klaus proves that no fixed tie-breaking structure can reproduce her rule’s type assignments across all five-person preference profiles. Because participants care only about types, this rules out even welfare equivalence, not merely identical assignments of individual houses.

Why the usual arguments fail

Identical houses restrict the reports available to participants. Someone cannot rank one house above another identical house. According to Klaus, earlier characterization proofs rely on auxiliary reports that make precisely such distinctions.

Consistency also has a specific scope here. It requires unchanged assignments for remaining participants when a departing group takes exactly the set of houses its members originally owned. In the exceptional outcome, the permissible departures are participant 1 alone or the other four participants together. Consistency therefore does not connect that four-person cycle to problems involving only part of it.

What the result establishes—and leaves open

For two house types, Klaus reports computer verification that five participants are minimal for this fixed-population counterexample. The composition matters: three owners of one type and two of the other permit the construction, whereas four owners of one type and one of the other do not. The minimality calculations were checked with separate SAT-based and exhaustive-search scripts.

A four-person counterexample also appears, but its incompatibility with fixed tie-breaking emerges across different coalitions, not within the full population alone.

These are theoretical results, not evidence that TTC performs poorly in practice. The paper does not supply a replacement characterization or examine every existing characterization. Its conclusion is narrower: the properties considered cannot uniquely identify fixed-tie-breaking TTC when houses of the same type are identical.