Shapley-Scarf Markets with Objective Indifferences

Technical Summary: Shapley-Scarf Markets with Objective Indifferences

Problem Statement
The paper addresses the allocation of indivisible objects (houses) among agents who are initially endowed with one object each, a setting known as the Shapley-Scarf market. In the classical model (Shapley and Scarf, 1974), agents possess strict preferences, and Gale's Top Trading Cycles (TTC) algorithm successfully identifies an allocation in the core, which is unique, Pareto efficient, and strategy-proof.

However, in many practical applications (e.g., dormitory assignments, school choice), agents are naturally indifferent between objects of the same "type" (e.g., identical floor plans). When general indifferences are introduced, the standard TTC algorithm with fixed tie-breaking (TTC$_\succ$) fails to maintain its desirable properties. Specifically, under general indifferences, TTC$_\succ$ is neither Pareto efficient nor group strategy-proof, and it may fail to select an allocation in the core even when the core is non-empty. The paper investigates whether there exists a structured domain of preferences where TTC$_\succ$ can recover these properties without resorting to more complex mechanisms.

Methodology and Model
The authors introduce a specific preference domain called Objective Indifferences. In this model:

• The set of houses $H$ is partitioned into blocks (types) $\mathcal{H} = \{H_1, \dots, H_K\}$.
• Agents are indifferent between any two houses within the same block ($h I_i h'$ if $\eta(h) = \eta(h')$) but have strict preferences between houses in different blocks.
• Crucially, the partition $\mathcal{H}$ is common to all agents; indifferences are "objective" rather than subjective.

The study analyzes the performance of TTC with fixed tie-breaking (TTC$_\succ$) on this domain. The mechanism resolves indifferences by using an exogenous tie-breaking profile $\succ = (\succ_1, \dots, \succ_n)$, where $\succ_i$ is a strict linear order over agents. This converts weak preferences into strict preferences, allowing the standard TTC algorithm to proceed.

The authors evaluate TTC$_\succ$ against three axioms:

1. Pareto Efficiency (PE): No other allocation makes someone better off without making anyone worse off.
2. Group Strategy-Proofness (GSP): No coalition can misreport preferences to make all members weakly better off and at least one strictly better off.
3. Core-Selecting (CS): If the core is non-empty, the mechanism selects an allocation within it.

The paper employs a maximality approach to characterize the domains. A domain is "maximal" for a property if the mechanism satisfies the property on that domain, but fails on any strictly larger domain. For GSP, the authors introduce the concept of symmetric-maximality, restricting attention to domains where if an agent can strictly prefer $h$ to $h'$, the reverse preference is also possible (a standard assumption in mechanism design to avoid arbitrary restrictions on preference directions).

Key Results
The paper establishes three primary theorems characterizing the limits of TTC$_\succ$:

1. Restoration of Properties: Under the domain of objective indifferences, TTC$_\succ$ satisfies Pareto efficiency, group strategy-proofness, and core selection.

   • The authors prove that if the core is non-empty under objective indifferences, it is "essentially single-valued," meaning all core allocations assign agents to the same indifference classes (house types).
   • Even if the core is empty, TTC$_\succ$ always selects an allocation in the weak core.

2. Characterization of Maximality (PE and CS):

   • Theorem 1: A domain is a maximal domain on which TTC$_\succ$ is Pareto efficient (or core-selecting) if and only if it is an objective indifferences domain.
   • This implies that any expansion beyond objective indifferences (allowing for subjective indifferences where agents differ on which objects are equivalent) inevitably causes TTC$_\succ$ to lose Pareto efficiency and core selection.

3. Characterization of Maximality (GSP):

   • Theorem 2: A domain is a symmetric-maximal domain on which TTC$_\succ$ is group strategy-proof if and only if it is an objective indifferences domain.
   • While there exist non-symmetric domains larger than objective indifferences where TTC$_\succ$ is GSP (e.g., domains where certain strict preferences are impossible), the authors argue that the symmetry restriction is natural and not onerous for market design.

Significance and Claims
The paper claims to provide a precise boundary for the applicability of the intuitive TTC$_\succ$ mechanism.

• Rationalization of TTC: The results suggest that in markets where indifferences are structural and shared (e.g., identical housing units), TTC$_\succ$ remains a robust solution, preserving efficiency, stability, and incentive compatibility.
• Identification of Failure Points: The paper argues that the failure of TTC$_\succ$ in general settings is not due to indifferences per se, but rather due to subjective indifferences (where agents disagree on which objects are equivalent).
• Domain Characterization: The authors demonstrate that objective indifferences is not just a sufficient condition but the most general setting (under symmetry for GSP) where TTC$_\succ$ retains its three core properties. This distinguishes the work from literature that either assumes strict preferences or studies general indifferences where TTC fails.

The paper concludes by noting that while it does not prescribe a specific mechanism for all markets, it clarifies exactly when the widely used TTC$_\succ$ is theoretically sound. It suggests that policymakers should assess whether indifferences in their specific market (e.g., school choice with language tracks) are objective (shared by all) or subjective (varying by family) to determine if TTC$_\succ$ is appropriate. The authors leave the axiomatic characterization of TTC$_\succ$ on objective indifferences and further exploration of constrained indifferences as future work.