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 online in random order. 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) satisfying the stability property that no small
group of people would be willing to switch roommates or rooms.
We first show a polynomial-time online algorithm
that achieves a 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/c2). Finally, we
show both positive and negative results in satisfying
various stability conditions in this online setting