Mechanism Design for Multi-Type Housing Markets

Sujoy Sikdar, Sibel Adali, Lirong Xia

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:

  1. Graph Construction: In each round, a graph is built where agents point to their most preferred available item of their highest-priority remaining type.
  2. Ownership Links: Items point back to their current owners.
  3. Cycle Execution: When a cycle is identified, the corresponding trades are executed.
  4. Persistence: Unlike standard TTC, agents remain in the pool until they have acquired one item of every type.
An illustrative example of the MTTC algorithm with 3 agents and 2 item types (H and C).

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.

A reduction used to prove the computational hardness of checking stability in multi-type markets.

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

Abstract

We study multi-type housing markets, where there are $p\ge 2$ types of items, each agent is initially endowed one item of each type, and the goal is to design mechanisms without monetary transfer to (re)allocate items to the agents based on their preferences over bundles of items, such that each agent gets one item of each type. In sharp contrast to classical housing markets, previous studies in multi-type housing markets have been hindered by the lack of natural solution concepts, because the strict core might be empty. We break the barrier in the literature by leveraging AI techniques and making natural assumptions on agents' preferences. We show that when agents' preferences are lexicographic, even with different importance orders, the classical top-trading-cycles mechanism can be extended while preserving most of its nice properties. We also investigate computational complexity of checking whether an allocation is in the strict core and checking whether the strict core is empty. Our results convey an encouragingly positive message: it is possible to design good mechanisms for multi-type housing markets under natural assumptions on preferences.
BibTeX
@inproceedings{sikdar2017mechanism,
  author = {Sujoy Sikdar and Sibel Adali and Lirong Xia},
  title = {{Mechanism Design for Multi-Type Housing Markets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10601},
}
Figure