Related Tags

algorithms

# What is the Gale-Shapely Algorithm?

Abdul Monum

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The Gale-Shapely Algorithm is an intuitive algorithm that solves the stable matching problem. Let’s take the example of hospitals that need to find medical students according to their preference list and students who want to get into hospitals according to their preference list. Then, a stable match is a perfect match with no unstable pairs. For example, a hospital $h$ that prefers student $s'$ over a matched student $s$, and a student $s$ who prefers hospital $h'$ over matched hospital $h$. In both scenarios, $h-s$ is an unstable pair because in either case, both parties have reason to trade up, as they have a better preference available. Given these preference lists of hospitals and students, the Gale-Shapely Algorithm guarantees to find a stable match (if one exists).

## Pseudocode

Gale-Shapely(hospital preference list, student preference list)

INITIALIZE $M$ to an empty match

WHILE (unmatched hospital $h$ that hasn’t proposed to every student)

$s$ <-- First preferred student on $h$'s list to whom $h$ has not yet proposed

IF ($s$ is unmatched)

Add pair $h-s$ to $M$.

ELSE IF ($s$ prefers $h$ to current matched hospital $h'$)

Replace $h'-s$ with $h-s$ in matching $M$.

ELSE

$s$ rejects $h.$

RETURN M

## Analysis

• Hospitals propose in decreasing order of preference.

• Once a student is matched, they don’t get unmatched. Student only trades up for a preferred hospital.

• Only unmatched hospitals propose; this means hospitals match to <= 1 student.

• Students only keep the most preferred hospital that prefers them as well. This means students match to <=1 hospitals.

## Proof of stable matching

In Gale-Shapely output matching M, there are no unstable pairs.

Consider any pair $h-s$ that is not in Matching M.

Scenario 1: $h$ never proposed to s.

• $h$ prefers $s'$ over $s$. (Hospitals propose in decreasing order of preference.)
• $h-s$ is not unstable.

Scenario 2: $h$ proposed to s.

• Either $s$ rejected $h$, or
• $s$ prefers $h'$ over $h$. (Students only trade up for a preferred hospital.)
• $h-s$ is not unstable.

In both scenarios, we see that $h-s$ is not unstable, and therefore Gale-Shapely guarantees to find a stable match.

## Code

Below is a Python program that implements the Gale-Shapely Algorithm, where there is a higher number of students than the number of hospitals and each hospital has a certain number of vacancies. Since there is a surplus of students, not all students will get matched. Similarly, all hospital vacancies need to be filled. However, all pairs $h-s$ will be stable, as guaranteed by the Gale-Shapely Algorithm.

def galeShapely(n_h, n_s, vacancy_list, h_pref, s_pref):    matching = [-1]*n_s    while (vacancy_list):        s = h_pref[vacancy_list[0]][0]        if matching[s] == -1: #s is unmatched            matching[s] = vacancy_list.pop(0)        elif s_pref[s][vacancy_list[0]] < s_pref[s][matching[s]]: #s prefers h to current partner h'            prev_h = matching[s]            matching[s] = vacancy_list.pop(0)            vacancy_list.append(prev_h)        else:            _ = h_pref[vacancy_list[0]].pop(0) # s rejects h     return matching

## Explanation

• The function galeShapely takes the following arguments:

• n_h: Number of hospitals.
• n_s: Number of students.
• h_pref: List indexed by hospital IDs; value is student preference list in decreasing order.
• s_pref: List indexed by student IDs; value is hospital preference list in decreasing order.
• vacancy_list: List containing all vacancies for every hospital. For example, if there are two hospitals with IDs $0$ and $1$, respectively, and each has two vacancies for students available, then vacancy_list = [0,0,1,1].
• The function initializes the list matching, which is indexed by student IDs, and the value is the hospital ID. Since no students are initially matched to hospitals, it is initialized with -1.

• The while loop runs while we still have vacancies available.

• Inside the loop, we follow the above pseudocode. For each hospital vacancy, we get the first preferred student s to whom $h$ has not proposed.

• If s is unmatched, we add them to matching by indexing it with s and assigning the hospital ID. (Recall that vacancy_list contains hospital ID).

• If s prefers $h$ (vacancy_list[0]) over current partner $h'$ (matching[s]), then we replace $h'-s$ with $h-s$ (matching[s] = vacancy_list.pop(0)).

• Otherwise, s rejects $h$ by removing $h$ from the hospital preference list (h_pref[vacancy_list[0]].pop(0)).

RELATED TAGS

algorithms

CONTRIBUTOR

Abdul Monum