Online Housing Market

Julien LescaIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of designing fair and efficient online housing market mechanisms where agents arrive and depart dynamically. They adapt classic algorithms like serial dictatorship and top trading cycles to this online setting, proving that achieving all desirable properties (Pareto efficiency, individual rationality, and strategy-proofness) simultaneously is impossible. The work offers several variants that achieve different subsets of these properties, providing a nuanced understanding of the trade-offs involved.

What Problem Does This Paper Address?

The paper addresses the problem of allocating indivisible resources (like houses) among agents who have preferences over these resources. This is a classic problem in computational social choice and economics, often referred to as the "housing market problem." The key challenge here is extending existing solutions to an online setting. In the traditional "offline" setting, all agents are present simultaneously, and their preferences are known. However, in many real-world scenarios, agents arrive and depart at different times, and their presence in the market is temporary. This dynamic nature introduces significant complexities: how do you ensure fairness and efficiency when you don't know who will show up or when they will leave? The authors aim to adapt established mechanisms like the serial dictatorship and top trading cycle (TTC) procedures to this online environment, while preserving their desirable properties such as Pareto efficiency (no one can be made better off without making someone else worse off), individual rationality (no agent ends up with something worse than their initial endowment), and strategy-proofness (agents have no incentive to lie about their preferences).

Methods

The core of the paper involves adapting two well-known offline mechanisms to the online setting:

  • Serial Dictatorship: In the offline version, agents choose items sequentially based on a fixed order. The authors extend this by introducing a permutation function that can depend on the instance (e.g., agents' arrival/departure times). They propose an "online serial dictatorship procedure" (Algorithm 1) that processes agents as they depart, making allocation decisions based only on agents present up to that point. They analyze different permutation functions, such as "ascending departure" and "ascending arrival," to see how they impact the properties of the resulting allocation.
  • Top Trading Cycle (TTC): The TTC procedure is known for achieving all desirable properties in the offline setting. The authors extend it by using a "partition function" that divides the agents into subsets. The TTC procedure is then applied independently to each subset. This allows for a more modular approach to handling the online dynamics. They introduce various partition functions, such as the "departing agent excluded partition" (Algorithm 5) and "scheduled departure partition" (Algorithm 6), to manage agent arrivals and departures.

A crucial aspect of their methodology is the formalization of "online compatibility" for partition functions and the analysis of various "incentive compatibility" notions (a-IC, d-IC, SIC) that capture strategic behavior related to arrival and departure times.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanisms and their properties, using illustrative examples rather than empirical datasets.

Key Insights and Ideas

  • Impossibility Result: The paper establishes that it's impossible to achieve Pareto efficiency, individual rationality, and strategy-proofness simultaneously in the online housing market setting. This highlights a fundamental trade-off introduced by the dynamic nature of agent arrivals and departures.
  • Nuanced Trade-offs: Different variants of the serial dictatorship and TTC procedures achieve different subsets of these desirable properties. For instance, the serial dictatorship with an ascending departure permutation yields Pareto-efficient outcomes but isn't individually rational or strategy-proof.
  • Importance of Permutation/Partition Functions: The choice of how agents are ordered (permutation) or grouped (partition) is critical in adapting these algorithms to the online setting. These functions directly influence the mechanism's properties and its susceptibility to strategic manipulation.
  • Incentivizing Truthful Departure Times: Some proposed mechanisms, like the departing agent excluded partition with TTC, can incentivize agents to truthfully report their departure times, which is a novel aspect of strategy-proofness in this online context.

Key Results

The paper presents several theoretical results, often in the form of propositions and corollaries:

  • Serial Dictatorship Variants:
    • Algorithm 1 with the ascending departure permutation is online and weakly incentive compatible (WIC) and produces Pareto-efficient allocations (M(I)-PO). It's also shown to be the only online algorithm that always returns an M(I)-PO allocation.
  • Algorithm 1 with the ascending arrival permutation is online and d-IC (incentive compatible with respect to departure times).
  • No permutation function can make Algorithm 1 a-IC (incentive compatible with respect to arrival times).
  • TTC Variants:
    • Algorithm 4 with an online compatible partition function is online and WIC.
  • The departing agent excluded partition (Algorithm 5) is online compatible and leads to a d-IC mechanism.
  • The scheduled departure partition (Algorithm 6) leads to an a-IC mechanism.
  • A specific construction (earliest departure partition) can lead to a strongly incentive compatible (SIC) mechanism, though it might limit exchanges.
  • Summary Table: Table 1 provides a concise overview of the properties achieved by the different proposed mechanisms.

Limitations and Future Work

  • Limitations:
    • The paper explicitly states that achieving all three properties (Pareto efficiency, individual rationality, and strategy-proofness) simultaneously is impossible in the online setting.
  • Some proposed mechanisms, while achieving certain properties, might limit the number of exchanges or not be as efficient as desired. For example, the SIC mechanism based on the earliest departure partition might result in few exchanges.
  • Future Work:
    • Dynamic Allocations: Explore mechanisms where an agent's allocation can evolve even after an item has been initially assigned.
  • Stronger Incentive Compatibility: Design mechanisms that achieve more exchanges than the current SIC variants.
  • Relaxed Properties: Investigate relaxed forms of efficiency and strategy-proofness, potentially incorporating probabilistic assumptions about agent arrivals and departures. This could involve looking into online stochastic matching problems.
  • Fair Assignment of Public Goods: Extend these ideas to related problems like the fair assignment of public goods.

Summary updated

BibTeX
@inproceedings{lesca2025online,
  author = {Julien Lesca},
  title = {{Online Housing Market}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/437},
}
Figure