Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithms

What is the Gale-Shapely Algorithm?

Abdul Monum

Grokking Modern System Design Interview for Engineers & Managers

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 hh that prefers student ss' over a matched student ss, and a student ss who prefers hospital hh' over matched hospital hh. In both scenarios, hsh-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 MM to an empty match

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

      ss <-- First preferred student on hh's list to whom hh has not yet proposed

      IF (ss is unmatched)

            Add pair hsh-s to MM.

      ELSE IF (ss prefers hh to current matched hospital hh')

            Replace hsh'-s with hsh-s in matching MM.

      ELSE

            ss rejects h.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 hsh-s that is not in Matching M.

Scenario 1: hh never proposed to s.

  • hh prefers ss' over ss. (Hospitals propose in decreasing order of preference.)
  • hsh-s is not unstable.

Scenario 2: hh proposed to s.

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

In both scenarios, we see that hsh-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 hsh-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 00 and 11, 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 hh 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 hh (vacancy_list[0]) over current partner hh' (matching[s]), then we replace hsh'-s with hsh-s (matching[s] = vacancy_list.pop(0)).

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

RELATED TAGS

algorithms

CONTRIBUTOR

Abdul Monum
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

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.

Keep Exploring