Introduction
In the study of microeconomics and multi-agent systems, the Shapley-Scarf housing market serves as a foundational model for indivisible good exchange. In this classic scenario, each agent is endowed with a single item and seeks to trade it for a more preferred one. The Top-Trading-Cycles (TTC) mechanism is famously strategyproof and Pareto efficient in this context. However, real-world markets often deviate from this simplicity. Agents frequently own multiple items, and central authorities may not have perfect knowledge of these "endowments."
This paper addresses the complexities of exchange economies where agents possess multiple private endowments. In such settings, agents can manipulate the outcome not only by misreporting their preferences but also by strategically withholding some of their items.
The Impossibility of Efficient Strategyproofness
The core challenge identified by the authors is a fundamental tension between efficiency and incentive compatibility. In standard models, strategyproofness focuses on preference revelation. With private endowments, the definition must expand to include "endowment-strategyproofness"—the requirement that no agent can benefit by hiding part of their initial holdings.
The authors prove a significant impossibility result: even in highly restricted preference domains, such as lexicographic preferences (where items are strictly ranked by priority), it is impossible to design a mechanism that is both Pareto efficient and strategyproof. This suggests that to ensure agents act honestly about what they own and what they want, some degree of social welfare (efficiency) must be sacrificed.
Methods and the Revelation Principle
To navigate this impossibility, the researchers first establish a theoretical foundation. They confirm that the Revelation Principle holds in this environment, provided we assume "no-fabrication." This means that while agents can hide items they own, they cannot claim to own items they do not possess.
The study analyzes four distinct preference domains:
- Monotonic: Agents always prefer more items to fewer.
- Responsive: Preferences over sets are consistent with an underlying ranking of individual items.
- Additive: The value of a set is the sum of the values of its components.
- Lexicographic: The most restrictive domain, where the highest-ranked item determines the preference between two sets.
Agreement Cycles Rules
To provide a solution that maintains strategyproofness despite the impossibility of Pareto efficiency, the authors introduce a new class of mechanisms called Agreement Cycles Rules. These rules operate on "one-for-one trading possibility graphs."
In these graphs, nodes represent the goods available in the market. A trade occurs only if it corresponds to a cycle in the graph and every agent involved in that cycle agrees that the exchange is strictly better than keeping their original items. By requiring unanimous agreement within these predefined cycles, the mechanism ensures that agents have no incentive to hide endowments or lie about preferences, as doing so would likely result in them being excluded from beneficial trades.
Key Results and Robustness
The paper provides several formal proofs regarding the properties of Agreement Cycles Rules:
- Strategyproofness: Theorems 3, 4, and 5 establish the conditions under which these rules are strategyproof across the different preference domains (Additive, Responsive, and Monotonic).
- Split-Proofness: Theorem 6 demonstrates that these rules are robust against "false-name" manipulations. In anonymous digital environments, an agent might attempt to split their identity into multiple accounts to gain an advantage. Agreement Cycles Rules prevent this, ensuring that "splitting" does not lead to a better outcome for the manipulator.
Conclusion and Future Directions
While the Agreement Cycles Rules provide a robust framework for strategyproof exchange with private endowments, they come with the cost of reduced efficiency. Because the rules are conservative—requiring unanimous agreement on specific cycles—they may leave many mutually beneficial trades unexecuted.
Future research could explore several avenues to bridge this gap. One possibility is the use of randomized mechanisms, which might achieve higher expected social welfare while maintaining incentive compatibility. Additionally, relaxing the assumption of strict preferences to include indifference or "unacceptable" items could make the model more applicable to diverse real-world scenarios. Finally, investigating the computational complexity of manipulating more efficient (but non-strategyproof) rules remains an open challenge.
Summary updated