Online Roommate Allocation Problem

1 Introduction

Online allocation studies the problem in which input information is revealed step by step, and the algorithm is required to make irrevocable decisions in each step without the knowledge of future input items. Data come in an online fashion for certain resource allocation problems. For example, in the Google AdWords problem, keywords arrive sequentially in real time, and after observing a keyword query, Google needs to decide immediately and irrevocably what advertisement to display to maximize its revenue.

In this paper, we study the problem of online resource allocation in a roommate assignment setting proposed in [Chan et al., 2016]. The objective in a roommate market problem is to match rooms to applicants under certain budget constraints. In public massive housing program, applicants are required to fill in a form to state their preference over rooms and roommates. The model also applies to applications such as university accommodation and conference roommate arrangement.

∗This work was supported by Research Grants Council of the Hong Kong S.A.R. (Project no. CUHK14239416)

Formally, in the online roommate market model, there are n rooms, and also 2n persons that arrive online in random order (later we will generalize this to a general model with c-bed rooms). Each person has a valuation for each room and a happiness valuation of each potential roommate. An allocation is an assignment of each person to some room, such that each room contains exactly two persons. The utility of a person is defined as the sum of his/her happiness for roommate and valuation for the room.

There are several dimensions to measure the quality of an allocation. From a global perspective, a natural objective is to maximize the allocation's social welfare, which is the summation of utilities of all persons. However, such efficiency may come at the cost of unfairness, with some individuals allocated very little resource. In this regard, we focus on the stability of an allocation. An allocation is stable if no coalition of a small number of people can devise new trades to make everyone in the coalition better off.

Our goal is to design online algorithms on roommate market model that perform well in these two measures. Our main results are summarized as follows.

• (a) We give a polynomial-time online algorithm with a constant competitive ratio with respect to the optimal social welfare.
• (b) For the generalized c-bed model for any c ≥ 2, we extend our algorithm and obtain a Ω(1/c2 ) competitive ratio.
• (c) We show both positive and negative results on whether various stability conditions can be achieved in the online model.

1.1 RelatedWorks

Our model follows the work by Chan et al. [2016] on the roommate market. In their work, the authors focused on the offline 2-bed problem and presented constant approximation algorithms for social welfare maximization. They also proposed various solution concepts on stability and envy-freeness, and studied their existence and the computational complexity of the corresponding search problems. The biggest difference between our works is that we focus on the online version of the problem and also generalize the results to the c-bed setting.

Besides the work of Chan et al. [2016], there are two lines of work closely related to this paper: table matching and online bipartite matching. The stable matching problem has a long history dating back to 1960s [Gale and Shapley, 1962]. After decades of development the area grows into a rich theory with a vast body of literature; see surveys [Knuth, 1997; Iwama and Miyazaki, 2008]. The basic stable matching problem has been extended in many dimensions. One direction is to consider general matchings [Irving, 1985; Irving and Manlove, 2002] and higher dimensional matchings [Ng and Hirschberg, 1991; Eriksson et al., 2006; Huang, 2007]. Different stability notions have also been proposed, such as exchange stable [Cechl´arov´a and Manlove, 2005] and popular matching [Bir´o et al., 2010].

The study of online bipartite matching is originated from the secretary problem, which asks the best strategy to choose one secretary from n candidates coming in an online fashion with random arriving order. The optimal algorithm is 1e -competitive in expectation; see [Ferguson, 1989] for historical detail. The matroid generalization was introduced in the work [Babaioff et al., 2007], and inspired a line of works [Dimitrov and Plaxton, 2008; Im and Wang, 2011; Soto, 2013; Gharan and Vondr´ak, 2013]. The optimal competitive ratio of unweighted online bipartite matching with adversarial arrival order was proved to be 1 - 1e [Karp et al., 1990]. Later Kessel et al. [2013] extended the idea to weighted bipartite matching with random arrival order, and obtained optimal competitive ratio 1e for this model. Many variants were proposed and analyzed, such as vertexweighted matching [Aggarwal et al., 2011] and online packing [Kesselheim et al., 2014].

2 Preliminary

We are given a set of 2n agents I = {1, 2, ..., 2n}, a set of n rooms R = {r1, r2, ..., rn}, a happiness matrix H = {hij | i, j ∈ I, i ̸= j} in which hij denotes the happiness of agent i when she is assigned to live with agent j, and a valuation matrix V = {vir | i ∈ I, r ∈ R} in which vir denotes the valuation of agent i to room j. We assume that all happiness and valuation values are nonnegative. The outcome of the roommate market is an allocation A = {(i, j, r)} which consists of n disjoint triple. Triple (i, j, r) means agent i and j are assigned together to room r. We require that every agent is assigned to one room and every room is assigned to exactly 2 agents.

The social welfare of an allocation A is defined as SW(A) = ∑(i,j,r)∈A(hij + hji + vir + vjr).

We assume an online setting where all agents arrive online in uniformly random order. When agent i arrives, her valuation vir to every room r, as well as her happiness value hij to all agents j that have already arrived, are revealed to the algorithm, and the algorithm needs to assign agent i to some available room immediately. Note that since there are exactly 2n agents and n rooms, we are not allowed to leave any agent unassigned. Our goal is to find an allocation A that can maximize E[SW(A)], where the expectation is taken over both the randomness of the algorithm and the random arriving order of the agents.

An online algorithm is said to be c-competitive (or to have competitive ratio c), if its output allocation has expected social welfare no less than c · SW(Aopt), where Aopt is the optimal offline allocation.

3 Online Roommate Market

In this section, we present an online roommate market allocation algorithm that achieves constant competitive ratio.

3.1 Online No-Rejection Bipartite Matching

Our algorithm is built on an online bipartite matching algorithm with a no-rejection condition. Recall that in the standard online bipartite matching setting, we are given a weighted complete bipartite graph G = (L, R, E) with |L| = |R| = n. The vertices in R are given in advance. The vertices in L arrive online in a random order and the edges incident to each vertex l ∈ L are revealed when l arrives. An algorithm should either assign the current vertex to an unmatched adjacent vertex in R immediately, or leave it unassigned. The objective is usually to maximize the total weight of the resulting matching.

This online bipartite matching problem has been studied extensively in the literature [Aggarwal et al., 2011; Kalyanasundaram and Pruhs, 1993; Kesselheim et al., 2014]. However, the problem we consider here has an important difference: we do not allow the algorithm to leave any agent unassigned. Such no-rejection feature brings new challenges to the online algorithm design. Next we present our algorithm, which can be viewed as an extension of the online bipartite algorithm proposed in [Kesselheim et al., 2013].

Algorithm 1 ONLINEMATCHING(n, R)

1: counter ← 0 2: L← ∅ 3: A← ∅ 4: for every person v comes do 5: L←L∪ {v} 6: counter ← counter + 1 7: if counter ≥ n/5 then 8: M v ←Optimal matching on G[L∪R] 9: ev ← The matching edge that contains v in M v 10: if A ∪ ev is a matching then 11: A ← A ∪ ev 12: else 13: Randomly choose an available vertex v′ . 14: A ← A ∪ (v, v′ ) 15: else 16: Randomly choose an available vertex v′ . 17: A ← A ∪ (v, v′ ) 18: return A

The proof is similar to that of Algorithm 1 in [Kesselheim et al., 2013] and is omitted here due to space constraint.

3.2 Constant Approximation Algorithm for Online Roommate Market

We now present our constant competitive ratio algorithm for the online roommate market problem. It uses the online norejection bipartite matching algorithm as a key ingredient. The high level idea is that we first apply Algorithm ONLINEMATCHING on the first n people arrived. After this stage, each room contains exactly one agent. Then we combine each room-person pair as one new "room", and apply Algorithm ONLINEMATCHING again on the last n people with adjusted valuations to match them to the n room-person pairs.

Algorithm 2 ONLINEROOMMATE (n, H, V )

• 1: Run ONLINEMATCHING on the first n agents arrived.
• 2: Let M1 be the output matching.
• 3: for every agent i arrived after the first n agents do
• 4: for each room r ∈ R do
• 5: Set v′ir ← vir + (hij + hji) where (j, r) ∈ M1
• 6: Run ONLINEMATCHING on the last n agents with valuation matrix V ′ .
• 7: Let M2 be the returned matching.
• 8: returnM1 ∪M2

Theorem1. AlgorithmONLINEROOMMATE is a polynomial time and cb 4 -competitive algorithm for the online roommate market problem, where cb = ln 5-0.8 5 ≈ 0.1618.

Proof. Let Aopt denote the optimal offline allocation with maximum social welfare. Let Mpp denote the maximum weight general graph matching between the 2n agents, where the weight between agent i and j is hij + hji. Let Mpr denote the maximum weight matching between 2n agents and n rooms where each room is duplicated into 2 vertices. By slight abuse of notations, in the following we use SW(M) to denote the summation of the edge weights in matching M.

The social welfare SW(Aopt) can be divided to two parts: the first part is the happiness between roommates, which will not exceed SW(Mpp); the other part is the valuations between agents and the rooms, which will not exceed SW(Mpr). Hence we have

Next we bound SW(Mpp) and SW(Mpr). Fix a particular agents arriving order. Let A1 be the set of first n agents, A2 be the set of last n agents, and E12 be the set of weighted edges between A1 and A2 (where again the weight of edge (i, j) between agent i and agent j is hij + hji). We further define the following notations:

• Mpb: the maximum weight matching in bipartite graph (A1, A2, E12).
• Mpr1: the maximum weight matching between the first n agents and n rooms
• Mpr2: the maximum weight matching between the last n agents and n rooms.

We will show in the following that

where the expection is over the random arriving order of the agents.

First we bound SW(Mpb). Since agents arrives in uniformly random order, every edge in Mpp will be present in E12 with probability at least 1 2 , and these edges together form a matching. We therefore have

Now we bound SW(Mpr) by SW(Mpr1) and SW(Mpr2). Let Mpr0 be the maximum weight bipartite matching between 2n people and n rooms and each room only has one slot. We have

The first inequality is because the edges in Mpr1 ∪Mpr2 can at least cover all edges inMpr0. Together with

we have

Back to our algorithm, the first call to ONLINEMATCHING gives us a matching with expected social welfare no less than cb · SW(Mpr1); the second call to ONLINEMATCHING gives us a matching with expected social welfare no less than cb · max{SW(Mpb), SW(Mpr2)}. Let A denote the allocation output by our algorithm. Together we have

The above results can also be generalized to the case where the number of agents is not exactly 2n. Note that in this case, we need to adjust the model to either allow that some room contains less than 2 people (when the number of agents is smaller than 2n), or that some agent is left unassigned (when the number of agents is more than 2n).

Corollary 2. There is a constant competitive ratio algorithm for online roommate market problem with n rooms and the number of agents p = O(n).

The proof details are omitted due to space constraints.

3.3 Online Roommate Market Problemwith Unknown Number of Agents

Note that a prerequisite for Corollary 2 to hold is that the algorithm must know the number of agents p beforehand. Perhaps surprisingly, this also turns out to be a necessary requirement. In this section we show that if the number of agents p is unknown to the algorithm, then no online algorithm that can achieve constant competitive ratio for the online bipartite matching problem as well as the online roommate market problem.

Lemma 3. If the number of the agents is unknown in an online bipartite matching problem, no online algorithm can achieve a constant competitive ratio.

Due to space constraints, we only present a sketch of the proof. Given any constant ϵ > 0, we prove the lemma by constructing a class of bipartite graphs such that no algorithm can achieve competitive ratio ϵ for all graphs.

We restrict ourself to the following type of bipartite graphs: there exists only one vertex r∗ ∈ R that has nonzero valuations for the online vertices, i.e., vir = 0 for all i ∈ L and r ̸= r∗ ∈ R. We can represent such a graph by a value multiset {v1r∗ , v2r∗ , . . . , vnr∗}. Thus the decision that the algorithm needs to make is to select upon arrival which vertex in L to match to r∗ , and the optimal offline solution is always maxi vir∗ .

Next we construct graph sets B0, . . . , Bm for any value of m, where each Bk is a class of bipartite graphs that satisfy the following properties:

1. Every graph in Bk has the same number of online vertices, denoted by bk, and their value multiset is supported on the set {1, L, L2 , . . . , Lk }, where L is a large enough constant (say at least 2ϵ ). This implies that when given a graph in Bk as the input, in order to guarantee ϵ-competitive ratio, the algorithm needs to select an optimal online vertex (i.e., vertex with value Lk ) with probability at least ϵ2 .
2. b0 = 1 and bk+1 > bk for all k ≥ 0. Given any graph Gk+1 ∈ Bk+1 as the input, after seeing its bk random vertices, with high probability the values seen coincide with the value multiset of some graph in Bk. Therefore the algorithm will not be able to distinguish whether this input is fromGk+1 or from some graph in Bk.

The construction details are omitted. The technique is similar to the construction of a particular exponentially distributed probability distribution used in other contexts such as [Hajiaghayi et al., 2007; Gharan and Vondr´ak, 2013].

From these properties we know that to be ϵ competitive on any input graph Gm ∈ Bm, the algorithm must match some vertex to r∗ in time steps [bm-1 + 1, bm] with probability at least ϵ2 . By an induction argument, we can show that the algorithm must match some vertex to r∗ with probability at least ϵ2 from each time step interval [bk +1, . . . , bk+1] for all 0 ≤ k < m. However, when we set m > 2ϵ , the sum of these probabilities will be greater than 1, and the task becomes impossible because the algorithm can match at most one online vertex to r∗ .

Note that an algorithm for the online roommate market problem with constant competitive ratio would imply a constant competitive ratio algorithm for the online bipartite matching problem. Thus Lemma 3 implies that the former also cannot exist.

Corollary 4. If the number of the agents is unknown in an online roommate market problem, there is no online algorithm that can achieve a constant competitive ratio.

4 Generalized c-BedModel

Our algorithm can also be generalized to the case where each room can take more than 2 people. In a generalized online roommate market problem, there are cn people and n rooms, and we want to assign c people to every room, with the goal of maximizing the social welfare

The other settings are the same as the standard roommate market problem.

Similar to the original case, we divide the cn agents into c blocks with n agents in every block. Then we apply ONLINEMATCHING c times, each time assign a block of n agents to n rooms using an updated valuation matrix.

Algorithm 3 ONLINECBEDROOMMATE (n, H, V )

• 1: V ′ ← V
• 2: for g = 1, 2, . . . , c do
• 3: Run ONLINEMATCHING on the next n arriving agents with valuation matrix V ′ .
• 4: Let Mg be the returned matching.
• 5: for every agent i that is yet to arrive do
• 6: v′ir ← v′ir + hij + hji where (j, r) ∈ Mg
• 7: return ∪Mg

Theorem 2. ONLINECBEDROOMMATE has competitive ratio cb(c-1) c3 for the generalized online roommate market problem, where cb = ln 5-0.8 5 ≈ 0.1618.

Proof. The proof is along similar lines of that for Theorem 1. Let Aopt denote the optimal offline allocation with maximum social welfare. Let App denote the allocation of cn agents into n rooms that with maximum total happiness value between agents, and let Mpr denote the maximum bipartite matching between cn agents and n rooms where each each room is duplicated into c copies. Again it is easy to see that SW(Aopt) ≤ SW(App) + SW(Mpr).

Note that for each room r, the c agents in this room will have total happiness contributed by c(c-1) 2 pairs of relations. Let Cr be the general graph matching with maximum total happiness among the c agents allocated to room r in allocation App. We can show that SW(Arpp ) ≤ c · SW(Cr), where Arpp is the sum of happiness of all agents in room r in allocation App. This is because each clique of c vertices can always be covered by c matchings via the round-robin tournament algorithm.

Now go back to the online random arrival order. We call every n consecutively arriving vertices a block. The probability of any two vertices arrive in different blocks is cn-n cn-1 . Let M ij pp represent the maximum weight bipartite matching between agents in the ith block and jth block, and we can assume c > 2. We can distribute all matching edges in each Cr into someM ij pp if the two vertices of the edge are in different blocks, and every vertex will be involved in at most one matching edge. Hence by linearity we have

Put everything together, we have

Next we look at Mpr. Let M 1 pr be the matching induced fromMpr such that each room connects with only one agent who has the largest matching value. We have SW(Mpr) ≤ c · SW(M 1 pr ). Let Mir be the maximum weight matching between agents in i-th block and one slot of each room. We also have SW(M 1 pr ) ≤ ∑ci=1 SW(Mir). Combing these two inequalities gives us

Together with App, we have

Finally, let Mi be the maximum weight matching between the agents in i-th block and aggregated agent-room combinations according to the algorithm. We have

Since there are at most c items in the max bracket, we have c · SW(Mi) ≥ SW(Mir) + ∑i-1 j=1 SW(M ij pp ). Thus,

By Lemma 1, the algorithm computes M ∗ i which satisfies E[SW (M ∗ i )] ≥ cb · SW(Mi). Therefore, we have

This finishes the proof of this theorem.

4.1 Rooms with Different Capacities

The model can be further generalized to allow rooms to have different capacities. Assume we have n agents and k rooms with capacities ⃗c = (c1, c2, . . . , ck) such that ∑i ci = n.

Algorithm 4 ONLINEGENCBEDROOMMATE (⃗c, H, V )

• 1: c ←max{c1, . . . , ck}
• 2: V ′ ← V
• 3: for g = 1, 2, . . . , c do
• 4: Let ng be the number of available rooms.
• 5: Run ONLINEMATCHING on the next ng arriving agents with valuation matrix V ′ (only rooms with open capacities are used).
• 6: Let Mg be the returned matching.
• 7: for every agent i that is yet to arrive do
• 8: v′ir ← v′ir + hij + hji where (j, r) ∈ Mg
• 9: for every room i with ci > 0 do
• 10: ci ← ci - 1
• 11: return ∪Mi

Corollary 5. ONLINEGENCBEDROOMMATE achieves constant competitive ratio for the generalized online roommate market problem where every room has constant capacity.

The proof is similar to that for Theorem 2 and is omitted.

5 Stability Results

In this section we discuss different stability conditions in the online roommate market model.

We mainly focus on the stable notions introduced by Chan et al. [2016]. Note that it is always more difficult to achieve stability conditions in the online setting than in the offline setting. Thus we will only discuss stability notions that guarantee to exist in the offline setting. These notions are the 4person stability and room stability. In addition, we will also consider a new stable notion - weak room stability.

Our goal is to design online algorithms that can satisfy certain stability conditions together with strong social welfare guarantees. Note that this is not always achievable for all stability notions we mention above. Our results can be summarized in the following table.

5.1 4-Person Stable

Definition 1. [Chan et al., 2016] An allocation is 4-person stable if for any agents i and agent j in two different rooms, swapping them cannot make all 4 people in these two rooms strictly increase their utility.

In the offline setting, [Chan et al., 2016] gave an algorithm that can find a 4-person stable solution in O(n2 ) time. However, in the following we show that in the online setting, no algorithm can always guarantee a 4-person stable solution.

Lemma 6. No algorithm can always find a 4-person stable allocation in the online roommate market setting.

Proof. We prove this lemma by a simple example with 4 agents and 2 rooms. Assume every agent has valuation 0 for every room. Hence we only need to consider the happiness values between them. We also assume happiness values are symmetric, i.e., hij = hji for every agent i and j. Consider the following agents arrival sequence: let 1 and 2 be the first and second arriving agents with h12 = 1. When agent 2 arrives, any algorithm needs to make one of two choices:

• Assign agent 1 and 2 to the same room. In this case, assume that the next two arriving agents 3 and 4 have happiness values h13 = h24 = 100. All other unspecified happiness values are 0. It is easy to check that this already breaks the 4-person stable condition because swapping 1 and 3 would make every agent better off.
• Assign agent 1 and 2 to different rooms. In this case, assume that the next two arriving agents 3 and 4 have h34 = 1 and all other happiness values are 0. Here moving agent 1 and 2 to the same room can improve the utility of every agent.

Note that an online algorithm need to make an assignment decision at each moment some agent arrives. This means regardless of what this algorithm does, there always exists a problem instance and a particular agents arriving, such that the algorithm does not output a 4-person stable solution.

5.2 Room Stability andWeak Room Stability

Recall the definition of room stability as follows.

Definition 2. An allocation is room stable if for any two agents i, i′ in room ri and two agents j, j ′ in another room rj, switching their rooms cannot increase the sum of the two roommates' utilities for both rooms.

When discussing this condition, the happiness value between roommates can be ignored because the roommate relation will not be changed. It turns out that this room stable condition can be satisfied by an online algorithm.

Lemma 7. There is an online algorithm that always gives a room stable allocation.

Proof. The simple serial dictatorship algorithmworks as following: For every arriving agent, assign this agent to his/her most preferred room.

Now we show that the simple dictatorship algorithm that assigns every arriving agent her most preferred available room can produce a room stable allocation. Fixing any two rooms r1 and r2, let A, B, C, D denote the 4 agents assigned to these two rooms by this algorithm. Suppose the arriving order among them is A, B, C, D. If A and B both choose the same room, then they would not want to move to the other room. If A and B choose different rooms, without loss of generality, assume A chooses room r1 and B chooses room r2. If C chooses room r1, then A and C both prefer room r1 to r2; If C chooses r2, both B and C prefer room r2 to r1. In either case, there is a room in which the two tenants do not want to switch.

We comment that the above dictatorship algorithm, while always preserving the room stability, does not have any competitive ratio guarantees on social welfare. It remains an open question to design an algorithm that can achieve both room stability and constant competitive ratio on social welfare. However, as we will show below, if we are willing to weaken the room stablility condition, such goal indeed becomes achievable.

Definition 3. An allocation is weakly room stable if for any two agents i, i′ in room ri and two agents j, j ′ in another room rj, switching their rooms cannot increase all four agents' utilities.

Theorem 3. There is an online algorithm that can always produce a weakly room stable allocation with competitive ratio cb/8 on social welfare, where cb = ln 5-0.8 5 ≈ 0.1618.

Proof. Recall in the proof of Theorem 1, we showed

2E[SW(Mpr1) + SW(Mpb) + SW(Mpr2)] ≥ SW(Aopt). Note that we also have E[SW(Mpr1)] = E[SW(Mpr2)]. This means we can ignore one of these two terms and still get a constant competitive ratio solution. Thus we modify algorithm ONLINEROOMMATE as follows: for each of the first n arriving agents, we just choose the best empty room available to her. For the next n agent we still follow algorithm ONLINEMATCHING. After this change, our new algorithm will have competitive ratio cb/8. In addition, the output solution also satisfies weak room stability. This is because if we want to swap room ri and rj, and first slot of ri is assign before rj . Then the agent who is assigned to ri will not want to switch because she (weakly) prefers room ri to rj. Thus the output allocation is always weakly room stable.

6 Conclusion

This paper studies an online version of the roommate problem with stochastic arrivals, proposes a constant-factor competitive algorithm, and generalizes the results to the case of different number of agents per room. It also shows both positive and negative results in satisfying different stability conditions in this online setting. This model aims to capture a general online resource allocation scenario in which a resource can be assigned to multiple agents, and agents sharing the same resource exhibit positive externalities. That is, the valuation of an agent to a resource also depends on the identity of other agents who are assigned to the same resource.

The framework leaves a number of future working directions. For example, it remains open how close to optimal the provided algorithms are. It is also worth taking strategic behavior into consideration and study truthful mechanisms in the online roommate problem setting.