Gale Shapley Algorithm for Stable Matching problem

Reading time: 30 minutes | Coding time: 10 minutes

Gale Shapley Algorithm is an efficient algorithm that is used to solve the Stable Matching problem. It takes O(N^2) time complexity where N is the number of people involved.

Stable Matching problem

Introduction

We have 2 sets of people:

• The first set contains females
• The second set contains males.

Each person in each set has a list of preferences which includes all the people from the opposite set. That is, every woman in the set has a preference list that contains all the men in the other set. Similarly, every man has a preference list that contains all the women in the other set.

• We assume that females can be matched to only males and vice versa.
• Also, there is no male who also identifies as female and no female identifies as male.
• A person can be of the same preference to many people in the opposite set i.e A woman named QWERTY may be the first preference of 2 men Adelson and Velskii.
• The preferences are not reciprocated i.e If Qwerty is the first preference of Velskii, but Velskii need not be Qwerty's first preference.

Under these conditions, we need to perform a matching so that every person is engaged to his/her most preferable choice.
Before going on to solving this problem, we need to choose the proposers' side i.e the people who will be proposing to the other set.
The result obtained might vary slightly on this choice, but both the results will be stable matchings even if they are not the same.

Algorithm

1. All individuals have ranked members of opposite set in order of preference.
2. One of the 2 sets is chosen to make proposal.(Either set will produce stable matchings)
3. One individual from the proposing group who is not already engaged will propose to their most preferable option who has not already rejected them.
4. The person being proposed to will

• Accept if this is their first offer.
• Reject if this is worse than their current offer
• Accept if this is better than their current offer.In this case they will jilt their previous offer.

5. When all members of proposing group are matched the loop terminates.The currently engaged pairs are stably matched.

Example

Males = {A,B,C}
Females = {X,Y,Z}
And following is their preference list

First, let us consider the males as the proposing group.

I itertion

A proposes to X ,his first choice, as X does not have any offers at the moment ,she accepts.
B proposes to X, his first choice, as B is higher up in X's preference list, she declines the previously accepted offer by A and accepts B's offer.Hence, A does not have a partner presently.
C proposes to Y,his first choice,as Y does not have any offers at the moment, Y accepts his offer.

II iteration
B,C are already engaged but A needs to find a partner.
A proposes to Y, his second choice but as Y has a better offer (C), she declines A's offer.
B,C are happily engaged and hence we do not disturb their partners.
III iteration
A proposes to Z, his third and last choice,as Z does not have any better offers, she accepts A's offer.

As all the men are engaged with their respective partners, we stop iterating.
The resultant Matching is :
{A Z},{B X},{C Y}

Now, lets switch the sides and make the females the proposing group

I iteration
X proposes to B,her first choice, as B does not have any offers at this moment,he accepts her offer.
Y proposes to B, her first choice, but as B already has a better offer (X) he declines Y's offer.Hence, Y does not have a partner.
Z proposes to C,her first choice and as C does not have any offers, he accepts her offer.

II iteration
X and Z are engaged but Y needs to find a partner.
Y proposes to C, her second choice. As, Y is higher up in C's preference list,he accepts Y's offer and declines the previously accepted offer from Z.Hence, Z does not have a partner now.
Z proposes to her second choice A.As, A does not have any offers he accepts her offer.

As all the women are now engaged to their respective partners,we stop iterating.
The matching is:
{X B},{Y C},{Z B}

This matching is the same as the one obtained with men as the proposing group.

Pseudocode

Initialize all men and women to free
while there exist a man m who does not have a partner  
{
    w = m's most preferred woman to whom he has not proposed yet
    if w is does not have a partner
       (m, w) become engaged
    else some pair (m', w) already exists
       if w prefers m to m'
          (m, w) become engaged
           m' becomes free
       else
          (m', w) remain engaged    
}

Implementation

import java.util.*;
class person
{
    static int N = 3; 
    static boolean checkPreference(int preference[][], int w, int m, int m1) 
    { 
        for (int i = 0; i < N; i++) 
        { 
            if (preference[w][i] == m1) 
                return true; 
            if (preference[w][i] == m) 
                return false; 
        } 
        return false; 
} 

static void stableMatching(int preference[][]) 
{
    int wPartner[] = new int[N]; 
    boolean freeMen[] = new boolean[N]; 
    Arrays.fill(wPartner, -1); 
    int freeCount = N; 
    while (freeCount > 0) 
    { 
        int m; 
        for (m = 0; m < N; m++) 
            if (freeMen[m] == false) 
                break; 
        for (int i = 0; i < N && freeMen[m] == false; i++) 
        { 
            int w = preference[m][i]; 
            if (wPartner[w - N] == -1) //w does not have any offers at present,so she accepts m's offer
            { 
                wPartner[w - N] = m; 
                freeMen[m] = true; 
                freeCount--; 
            } 
            else //w is already engaged,hence we check the preference of the new offer
            { 
                int m1 = wPartner[w - N]; 
                if (checkPreference(preference, w, m, m1) == false) //the new offer (m1) is more favorable 
                { 
                    wPartner[w - N] = m; 
                    freeMen[m] = true; //free the previous partner(m)
                    freeMen[m1] = false;
                } 
            }
        } 
} 
System.out.println("Matching :");
for (int i = 0; i < N; i++) 
{ 
    System.out.print(" "); 
    System.out.println("W" + i + "	 " + "M" + wPartner[i]); 
}

} 
public static void main(String[] args) 
{ 
    int preference[][] = new int[][]{{1, 2, 3}, 
                                {1, 3, 2}, 
                                {2, 3, 1}};
    stableMatching(preference); 
} 
}

The function checkPreference() is used to check the preference of the two choices m,m1.To do this, we traverse the preference list of the woman w and check who is more preferable amongst m and m1.If we encounter m1 before m,we return true and if we encounter m before m1, we return false. The boolean value returned by this function helps in determining who is to be engaged with woman w.

The function stableMatching() keeps count of the number of free men at any given point in time. This is done using the variable freeCount and boolean array freeMen.

Output

Matching :
W1  M2
W2  M3
W3  M1

Time complexity

This algorithm takes O(n^2) time where n is the number of men/women.
For clarity, let us consider no of males = m and number of females = w.Note that m = w = n.
In the worst case, all men will be engaged with their least preferred choice,so we make w iterations for each man
Therefore,in the worst case scenario, we make a total of m * w iterations and as m = w = n , time complexity becomes O(n^2).

With this article at OpenGenus, you must have the complete idea of Gale Shapley Algorithm. Enjoy.