A solution to the Stable Marriage Problem; a classic bipartite matching problem, using the Gale-Shapley Algorithm.
The stable marriage problem is a classic, bipartite matching problem first introduced by Gale and Shapley, both of whose algorithm known as the Gale-Shapley algorithm won a Nobel prize [1] in Economics for solving this problem. The most basic setting of the stable marriage problem is as below: [2]
Given n men and n women, where each person has ranked all members of the opposite sex in order of preference,
marry the men and women together such that there are no two people of opposite sex who would both rather
have each other than their current partners. When there are no such pairs of people, the set of marriages is
deemed stable.
Gale and Shapley [3] proved that there is a set of engagements that is stable for any set of preferences. However, what makes me think about this is, more of a psychological thing, but the proposer will always get the optimal match whereas the person being asked out might or might not get their optimal pairing, and since the status quo in many solutions starts with men asking out the women, seems a bit iffy.
There are many implementations of this problem, such as the stable roommate problem, hospitals; assigning rooms to patients, and even matchmaking in online video games. What interested me, as always, in networking this has a practical application very important in the field of router design. A router needs to move a packet from some input port to some output port. Given a set of packets waiting to be moved from inputs to outputs, how does one find a matching of input and outputs such that a maximum number of packets can be moved in one round? This algorithm is also used by QuestBridge, to match low-income students to high-rank colleges. It is used by CDN’s (Content Delivery Networks) to deliver data as well.
I will first be making a list of men and women indicating each of their spousal preferences ranked in descending order, and will be implementing a solution of the Gale-Shapley algorithm in python.
Assumptions:
● The male proposes first to the female he finds the most attractive
● The female accepts the proposal of the male she finds most attractive
The way this works is:
● The males propose to the females they find the most attractive
● The females accept the best offer according to their list of preferences, becoming tentatively engaged to their priority in this cycle
● The males who get rejected will repeat this cycle going down their list of preferences, and the females again will accept the best offer, possibly rejecting the person they were already engaged to.
● This cycle continues until there are no single people left.
My Rough working and mind-map of the sample set: working
The time-complexity of this algorithm is O ( n^2 ) meaning the time complexity is directly proportional to the square of the input size.
Here is a pseudocode of the Gale-Shapley algorithm for a hospital and medical students assignment [4]: pseudocode
Another pseudocode specifically for SMP from Wikipedia:
Initialize all men and women to free
[while] there exist a free man m who still has a woman w to propose to
w = m's highest ranked such woman to whom he has not yet proposed
[if] w is free
(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
Bibliography:
[1] Wikipedia - Nobel Prize in Economic Sciences https://en.wikipedia.org/wiki/Nobel_Memorial_Prize_in_Economic_Sciences
[2] Wikipedia - Stable Marriage Problem https://en.wikipedia.org/wiki/Stable_marriage_problem
[3] ScienceDirect - The Stable Marriage Problem https://www.sciencedirect.com/science/article/pii/S0370157321000843#b
[4] Princeton - Stable Matching Problem https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf
Ons Ali
MIT License | Spring 2022