## The Gale-Shapley Algorithm for the Stable Marriage Problem

Suppose there are 4 men and 4 women. Each man and each woman has an internal mental list of who their preferred mate would be. You want to match the men and women in marriage so that the marriages are “stable”. Stable does not mean optimal. Stable means that you cannot find a man-woman pair when the man prefers a different woman than his mate, and that different-woman also prefers the man to her current mate.

For example, suppose Adam is matched with Barb, and Carl is matched with Dina. But Adam prefers Dina over Barb, and also Dina prefers Adam over Carl. The marriages are not stable because Adam would dump Barb and Dina would dump Carl, so that Adam and Dina could hook up.

Given a set of men’s preferences and a set of women’s preferences, the Gale-Shapley algorithm can find a set marriages that are stable. The algorithm given on the Wikipedia article on the topic is:

```algorithm stable_matching is
Initialize all m in M and w in W to free
while exists free man m who still has a woman w to propose to do
w := first woman on m's list to whom m has not yet proposed
if w is free then
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m' then
m' becomes free
(m, w) become engaged
else
(m', w) remain engaged
end if
end if
repeat
```

On a recent weekend, one of my two puppies wasn’t feeling good so I didn’t want to take my usual walks in the park next to my house. Instead I chose the obvious alternative: code up the Gale-Shapley algorithm for fun.

The implementation was a bit trickier than I expected. As is often the case, there are many alternatives based on what choice of data structures to use, and also trade-offs between clarity and terseness.

In my demo, I used N = 4 men and 4 women, each numbered 0 to 3. I set up arbitrary preferences for the men and women:

```Mens preferences:
[[1 2 3 0]
[1 2 0 3]
[1 0 2 3]
[0 1 2 3]]

Womens preferences:
[[2 0 1 3]
[0 1 3 2]
[2 0 3 1]
[2 0 1 3]]
```

This means man [0] prefers woman [1] then woman [2] then [3] then [0]. And woman [3] prefers man [2] then man [0] then [1] then [3]. To implement Gale-Shapley you need to track the men’s marriage proposals to the women, and the current engagements. In Gale-Shapley, a woman who is engaged to a man will ditch that man if she gets a proposal from a different preferred man.

In general there is more than one possible set of stable marriages. I got:

```[[0 1 0 0]
[0 0 0 1]
[1 0 0 0]
[0 0 1 0]]
```

This means man [0] is matched with woman [1], man [1] is matched with woman [3], man [2] is matched with woman [0], and man [3] is matched with woman [2].

Notice man [1] is matched with woman [3] who is his last choice. But if man [1] tries to “steal” woman [0], [1], or [2]:

man [1] tries to steal woman [0]: she currently has man [2], and she prefers [2] to [1] (moderately).
man [1] tries to steal woman [1]: she currently has man [0], and she prefers [0] to [1] (slightly).
man [1] tries to steal woman [2]: she currently has man [3], and she prefers [3] to [1] (slightly).

Good fun.

There’s general consensus and solid social science research results that indicate men and women, in general, use different criteria for preferences. Left: Billionaire Rupert Murdoch and Wendi Deng. Center: Billionaire Francois-Henri Pinault and Salma Hayek. Right: Billionaire Robert Kraft and Ricki Noel Lander. I don’t think there is an algorithm that works with preferences in real life.

```# stable_marriage.py

import numpy as np

N = 4  # number men and also number women

def man_is_free(m, engaged_to):
for w in range(0, N):
if engaged_to[m][w] == 1:
return False
return True

def woman_is_free(w, engaged_to):
for m in range(0,N):
if engaged_to[m][w] == 1:
return False
return True

def womans_fiance(w, engaged_to):
for m in range(0,N):
if engaged_to[m][w] == 1:
return m
return -1  # woman is not engaged

def woman_prefers(w, m1, m2, women_prefer):
# does m1 come before m2?
for m in range(0,N):
if women_prefer[w][m] == m1: m1_idx = m
if women_prefer[w][m] == m2: m2_idx = m
if m1_idx < m2_idx:
return True
else:
return False

def next_pair(men_prefer, engaged_to, proposed_to):
for m in range(0,N):
for j in range(0,N):
w = men_prefer[m][j]  # most preferred woman
if man_is_free(m, engaged_to) and proposed_to[m][w] == 0:
return (m, w)
return (-1, -1)  # no free man with unproposed woman

def main():
print("\nBegin stable marriage Gale-Shapely demo ")

men_prefer = np.array(
[[1,2,3,0], [1,2,0,3], [1,0,2,3], [0,1,2,3]], dtype=np.int32)
women_prefer = np.array(
[[2,0,1,3], [0,1,3,2], [2,0,3,1], [2,0,1,3]], dtype=np.int32)

print("\nMens preferences:")
print(men_prefer)
print("\nWomens preferences:")
print(women_prefer)

engaged_to = np.array(
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
dtype=np.int32)

proposed_to = np.array(
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
dtype=np.int32)

print("\nExecuting the Gale-Shaply algorithm")
while True:
(m, w) = next_pair(men_prefer, engaged_to, proposed_to)

if m == -1: break  # no free man with unproposed-to woman
proposed_to[m][w] = 1  # m proposes to w

if woman_is_free(w, engaged_to):
engaged_to[m][w] = 1
else:
curr_fiance = womans_fiance(w, engaged_to)  # m'
if woman_prefers(w, m, curr_fiance, women_prefer) == True:
engaged_to[m][w] = 1  # w has new fiance
engaged_to[curr_fiance][w] = 0  # w ditches old fiance

print("\nDone. Final proposals matrix:")
print(proposed_to)

print("\nFinal engagements / matches: ")
print(engaged_to)

print("\nEnd demo ")

if __name__ == "__main__":
main()
```
This entry was posted in Miscellaneous. Bookmark the permalink.

### 1 Response to The Gale-Shapley Algorithm for the Stable Marriage Problem

1. Thorsten Kleppe says:

You make your blog to the best place on the internet, thank you. 🙂

There is an interesting effort from men’s to understand woman on a practical way, the scene around Pick-Up and some better descendants. Algorithms for better relationships. ^^