Stable Roommates Problem (Irving's Algorithm)

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

We are given an even-sized set in which each member has a preference list which consists of all other members of the set. We need to match the members of the set such that every member has his/her most preferred choice as their roommate. If such a matching exists, we say that a stable matching exists otherwise not.
This problem is along the lines of the Stable Marriage Problem or the Gale Shapley Algorithm.

Gale Shapley Algorithm for Stable Matching problem (Related problem)

Irving's Algorithm

To solve the Stable Roommates problem, Robert W. Irving developed an algorithm back in 1985.This algorithm has 2 phases :

Platonic Proposal
Rotation Elimination
This algorithm helps in determing whether or not a stable matching exists and if it does what is it.

Algorithm

Participants order the other memebers by preference and then propose to everyone on their list in order continuing to the next person if their proposal is rejected.
A proposal is rejected when a person holds a proposal from someone they prefer. A proposal can also be rejected when a person of higher preference proposes and we reject the previously accepted offer.
If a person is the last preference of all others and is rejected by eveyone, a stable matching does not exist. An example of this is shown in the next section.
Phase one ends when everyone has made a proposal and received a proposal from someone else.
Now, we eliminate all the preferences which are lower than the one who's proposal has been accepted and symmetrically.
Next, we eliminate rotations. Check the detailed algorithm for that in the example mentioned below.
When all members have only one person remaining on their list, we stop. This is the stable roommates matching.

Example

Let us consider a set of 4 people {A,B,C,D} where A,D are females and B,C are males and following is their preference list :

A	B	C	D
C	A	D	B
B	C	B	A
D	D	A	C

Let's see how the algorithm works with the help of this example.

Phase I
Part 1

A proposes to C,her most preferred choice. As C does not have any proposal till now, he accepts. So, A has proposed but does not have an offer and C has not proposed but has received an offer.
Next, B proposes to A, his most preferred choice and as A has not received an offer till now(A has only proposed), she accepts. So, B has proposed but has not received a proposal and A has now received a proposal and has also proposed.
Now, C proposes to D, his first choice,and as D has not received a proposal till now, she accepts. So, C has proposed and has also received one (from A) and D received a proposal but has not proposed yet.
Now, its D's turn to propose, so she proposes to B, her first choice and as B has not received a proposal till now, he accepts.So, D and B both have proposed and have been proposed.

Now that all the members of the set have proposed to their first choice and have also been proposed, we proceed towards finishing phase 1 completely.To complete phase 1, we need to remove/cross out all those members who are listed below the one whose proposal has been accepted. Remember this exercise is symmetrical.
Let's see how this is done:
Part II

A	B	C	D
C	A	D	B
B	C	B	A
D	D	A	C

This is how the table looks after completing Part I of Phase I.

In every member's list, the person whose initials have been written in italics is the one who has been proposed by that person and those written in bold, has proposed to that person.
To make things clear, we see from the table that, A has proposed to C and has been proposed by B. Similarly,B has proposed to A and has been proposed by D.

We have to remove all those who are listed below the one whose proposal has been accepted by that person.This has to be done symmetrically.
So, we see here in the table that D is listed below B in A's list of prefernece and hence should be removed and although A is listed above C in D's list of preference, we need to remove A from D's list because this exercise is symmetrical.So, we remove D from A's list and A from D's list.

A	B	C	D
C	A	D	B
B	C	B	X
X	D	A	C

STABLE TABLE

After doing this, we move to B, but here we see that D is B's last preference and there is no one listed below him. So, we move on to the next peron C and find that the same situation exists. Same is true for D.
Hence,the table does not change and remains the same. We call this table the Phase I table or the Stable Table.

//////////////////////NOTE//////////////////////
**Cases where Stable table does not exist
Suppose that the preference list were :

A	B	C	D
C	A	B	A
B	C	A	B
D	D	D	C

Here we see that D is the last preference of all other members of the group.Hence,D will not receive a proposal from any other member. If we run the algorithm on this preference list, we will clearly see this situation.
Example :
A proposes to C, C accepts.
B proposes to A, A accepts.
C proposes to B, B accepts.
D proposes to A, A declines the proposal as B who is higher up in her preference list has already proposed to her.
D proposes to B, B declines as C who is higher up in his preference list has alredy proposed to her.
D proposes to C, C declines as C has already been proposed by A who is preferred over D by C.
Hence, D has neither received a proposal nor has she got his proposals accepted.Therefore, a stable matching does not exist in this scenario.

When such a scenario surfaces, we say that a stable table does not exist and hence there will never be a stable matching among the given members and the given preference lists.
/////////////////////////////////////////////////////

Now that we have a Stable table,Let's move to the next phase which is rotation elimination:
Phase II
We will maintain 2 lists which will keep track of the person in consideration and the corresponding entry in the second list will keep track of the second available choice of that person. We start with the first person in the set who has atleast 2 choices which are not crossed off and continue forward by taking the last choice of that person as the next person in consideration.This is done until either all the members are left with only one uncrossed choice in their preference list(Final Matching is obtained) or if we see a person being considered again in the same iteration.
Let's see how it works by taking forward our example:
Let's name the 2 lists as P and Q.
Start with P(1) as the first person who has atleast 2 available choices.Then, Q(1) becomes the second choice of P(1) and P(2) becomes the last choice of Q(1) and so on.
P(i) is the last preference of Q(i)
Q(i) is the second choice of P(i). where i=1,2,3...

P : A D A
Q : B C B
From the stable table we see that,
A's(P1) second choice is B (Q1)
B's(Q1) last choice is D (P2)
D's(P2) second choice is C (Q2)
C's(Q2) last choice is A (P3)

A occurs again in list P and hence indicates the presence of a cycle. To get rid of this cycle we eliminate diagonal pairs (Q(i), P(i+1)) : (B,D) and (C,A) are removed.

A	B	C	D
X	A	D	X
B	C	B	X
X	X	X	C

Now, B and C are the only one's left in the table with more than 1 entries which are not crossed out.

P : B B
Q : C C

B's (P1) second choice is C (Q1)
C's (Q1) last choice is B (P2)
B is entered again in the List P. Hence, we have encountered a cycle.
Eliminating diagonal pairs (B,C) symmetrically,we get

A	B	C	D
X	A	D	X
B	X	X	X
X	X	X	C

Now, every member has only one entry left in their preference list and so, we reach the final matching which is : (A,B) and (C,D)

Pseudocode

while (there are unmatched people) do{
       let ai be the first unmatched person
       ai proposes to their favourite roomate aj who has not rejected him
           if(aj has received no proposal then
               aj acccepts ai
           else if(aj prefers ai over his current match ak then
           {    aj accepts ak
               reject symmetrically(ak,aj) 
           }
           else
              reject symmetrically(aj,ai)
     }
      for all aj holding proposal from ai do
          reject symmetrically all(aj,ak) where aj prefers ai over ak

      for all cycles in (p1,...pn) and (q1..qn)such that
          qi is second preference of pi and pi+1 is last preference of qi do
          for i=1...n-1 do
              reject symmetrically(qi,pi+1)

Difference between Stable Marriage Problem and Stable Roommates Problem (Gale Shapley Algorithm V.S Irving's Algorithm)

In Stable Marriage Problem, matching is done between 2 disjoint sets (Males and Females) whereas in Stable Rommates Problem, matching is done in one single set.
There is always a stable matching possible in the Stable Marriage Problem but in case of Stable Roommates Problem, there is a possiblity of not having a stable matching at all.

Time Complexity

The algorithm can be divided into 3 parts:

Initialization - Every member will initialise their preference list which consists of every other member in the set. Hence, it might take O(n^2) time.
Phase 1 - In the worst case scenario, i.e when a stable matching does not exist, one person(the one who is least preferred by all others in the set)will propose to all the members of the set.Hence, it might take O(n) time at most.
Phase 2 - Eliminating rotations might require traversing the entire list for all the members of the set.Hence, we might have require O(n^2) time at most.

The resultant time complexity can be calculated as : O(n^2) + O(n) + O(n^2) = O(n^2)