Abstract
We study the online allocation problem under a roommate market model introduced in [Chan et al., 2016]. Consider a fixed supply of $n$ rooms and a list of $2n$ applicants arriving sequentially in an online fashion. The problem is to assign a room to each person upon her arrival, such that after the algorithm terminates, each room is shared by exactly two people. We focus on two objectives: (1) maximizing the social welfare, which is defined as the sum of valuations that applicants have for their rooms, plus the happiness value between each pair of roommates; (2) the allocation should satisfy certain stability conditions, such that no group of people would be willing to switch roommates or rooms. We first show a polynomial-time online algorithm that achieves constant competitive ratio for social welfare maximization. We then extend it to the case where each room is assigned to $c > 2$ people, and achieve a competitive ratio of $\Omega(1/c^2)$. Finally, we show both positive and negative results in satisfying different stability conditions in this online setting.
Introduction
In a classic "roommate market," the goal is to pair individuals in rooms to maximize total happiness (social welfare) while ensuring stability—a state where no group of individuals has an incentive to "revolt" and swap assignments. While well-understood in offline scenarios where all preferences are known, real-world applications like university housing or conference registrations often occur online.
In the online version, applicants arrive sequentially in a random order. An algorithm must assign each person a room immediately and irrevocably upon arrival. A critical constraint in this model is "no-rejection": every room must end up with exactly two people (or $c$ people in generalized cases), and every arrival must be housed. This makes the problem significantly more complex than standard online matching, where an algorithm can simply leave an agent unmatched if they are a poor fit.
Algorithmic Framework
The authors propose a solution built upon Online Bipartite Matching, specifically introducing a modified "No-Rejection" matching algorithm. The primary strategy, Algorithm 2 (OnlineRoommate), utilizes a multi-phase approach to handle the sequential arrivals:
- Phase 1: For the first $n$ arrivals, the algorithm treats each room as a single slot and uses no-rejection matching to assign exactly one person to each room.
- Phase 2: For the remaining $n$ arrivals, the algorithm updates the value of each room. The new value for a late arrival is their personal valuation of the room plus the happiness derived from the roommate already assigned in Phase 1.
- Phase 3: The matching algorithm is run again to fill the second slot in each room.
This block-based approach allows the algorithm to "learn" the landscape of the first half of the population before committing to final pairings. This is generalized in Algorithm 3 for rooms with $c$ beds by dividing arrivals into $c$ distinct blocks.
Theoretical Analysis and Results
As a theoretical study, the results are proven mathematically for arbitrary valuations and happiness scores, assuming a uniformly random arrival order.
Social Welfare
For the 2-person roommate problem, the algorithm achieves a competitive ratio of $c_b/4 \approx 0.04$. While $4\%$ of the optimal welfare may appear low, achieving any constant ratio (independent of $n$) under no-rejection constraints is a major theoretical milestone. For generalized rooms with $c$ beds, the ratio achieved is $\Omega(1/c^2)$. The authors also prove that if the total number of agents $n$ is unknown, achieving a constant competitive ratio is impossible.
Stability Conditions
The paper highlights a fundamental tension between maximizing welfare and ensuring stability. The authors categorize stability into different types and evaluate their feasibility in an online setting.
As shown in the table above, while strict "4-person stability" (where no two pairs want to swap members) is impossible to guarantee, "Weak Room Stability" can be achieved alongside a constant welfare guarantee ($c_b/8$). Conversely, while "Room Stability" is achievable via simple mechanisms like Serial Dictatorship, such methods offer no social welfare guarantees.
Limitations and Future Work
The primary limitation of this work is the assumption of a random arrival order. If an adversary were to choose the arrival sequence, the constant competitive ratios would likely not hold. Furthermore, while the ratios are theoretically constant, they remain numerically small.
Future research directions include closing the gap between current ratios and theoretical upper bounds, exploring truthful mechanisms where applicants cannot benefit from misrepresenting preferences, and considering stochastic arrival models where agents arrive according to specific probability distributions.
Summary updated