Online Roommate Allocation Problem

Online Roommate Allocation Problem

Guangda Huzhang, Xin Huang, Shengyu Zhang, Xiaohui Bei

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 235-241. https://doi.org/10.24963/ijcai.2017/34

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 Ω(1/c^2). Finally, we show both positive and negative results in satisfying different stability conditions in this online setting.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Planning under Uncertainty
Agent-based and Multi-agent Systems: Social Choice Theory