Introduction
In a classic housing market, agents each own an initial endowment (a house) and seek to trade for a more preferred one. The Top-Trading-Cycles (TTC) algorithm is the standard solution, providing a unique, stable allocation known as the strict core. However, extending this to multi-type markets—where agents trade bundles of different items, such as a house and a car—introduces significant challenges. In these settings, the strict core may be empty, and the desirable properties of single-item markets often fail to generalize.
This paper addresses these challenges by introducing a specific set of assumptions regarding agent preferences. By leveraging lexicographic preferences and AI-based preference representation (specifically CP-nets), the authors propose the Multi-Type Top-Trading-Cycles (MTTC) mechanism, which restores efficiency and stability to multi-type markets.
The MTTC Algorithm
The core of the proposed solution is the assumption of lexicographic preferences. Under this model, agents rank item types by importance (e.g., "House is more important than Car"). An agent will always prefer a bundle with a better house, regardless of the car included. The authors use CP-nets (Conditional Preference Networks) to model how agents value items within a type, conditioned on their current holdings.
The MTTC algorithm extends the classic TTC logic to handle these bundles through a multi-round process:
- Graph Construction: In each round, a graph is built where agents point to their most preferred available item of their highest-priority remaining type.
- Ownership Links: Items point back to their current owners.
- Cycle Execution: When a cycle is identified, the corresponding trades are executed.
- Persistence: Unlike standard TTC, agents remain in the pool until they have acquired one item of every type.
As shown in the illustrative example above, the algorithm iteratively resolves preferences across multiple types, ensuring that agents eventually receive a full bundle.
Computational Complexity
While the MTTC algorithm itself is efficient, the general problem of multi-type market allocation is computationally demanding. As a theoretical paper, no empirical datasets were used; instead, the authors provide mathematical proofs of hardness. They demonstrate that checking whether a specific allocation belongs to the strict core is co-NP-complete. Furthermore, determining if a stable allocation even exists under general preferences is NP-hard.
These hardness results underscore the importance of the lexicographic assumption, which provides the necessary structure to make the problem tractable.
Key Results and Axiomatic Properties
The MTTC algorithm operates in polynomial time, specifically $O(np)$ where $n$ is the number of agents and $p$ is the number of types. Under the assumption of lexicographic preferences, the mechanism satisfies several critical axiomatic properties:
- Strict-core-selection: It always identifies a stable allocation.
- Pareto Optimality: No agent can be made better off without making another worse off.
- Individual Rationality: Agents are guaranteed a bundle at least as good as their initial endowment.
- Strong Group Strategy-Proofness: No group of agents can benefit by misreporting their preferences, provided their importance order over types remains fixed.
However, the authors also established an impossibility result: no mechanism can be perfectly strategy-proof if agents are permitted to lie about the relative importance of the item types themselves.
Conclusion and Future Work
The reliance on lexicographic preferences is a primary limitation, as it may be too restrictive for some real-world applications. Future research could explore markets where agents require multiple items of the same type or investigate alternative preference structures like LP-trees. Additionally, the complexity of manipulating type-importance orders remains an open question for further study.
Summary updated