# Definition(s)

The stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set.

A matching is not stable if:

• There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
• B also prefers A over the element to which B is already matched.

In other words, a matching is stable when there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched.

# Algorithm(s)

``````

In [1]:

from collections import deque, defaultdict

``````
``````

In [17]:

def gale_shapley(men, women):
free_men = deque(men)
marriages = defaultdict(lambda: None)

preferences = dict()
for jane in women:
for i, john in enumerate(women[jane]):
preferences[(jane, john)] = i

while free_men:
john = free_men.popleft()

for jane in men[john]:
fiance = marriages[jane]

if fiance is None or preferences[(jane, john)] < preferences[(jane, fiance)]:
marriages[jane] = john

if fiance is not None:
free_men.append(fiance)
break

return list(sorted((m, w) for w, m in marriages.items()))

``````

# Run(s)

``````

In [18]:

men = {
'bob': ['diana', 'claire']
}

women = {
}

gale_shapley(men, women)

``````
``````

Out[18]:

``````
``````

In [19]:

men = {
1: [2, 4, 1, 3],
2: [3, 1, 4, 2],
3: [2, 3, 1, 4],
4: [4, 1, 3, 2]
}

women = {
1: [2, 1, 4, 3],
2: [4, 3, 1, 2],
3: [1, 4, 3, 2],
4: [2, 1, 4, 3]
}

gale_shapley(men, women)

``````
``````

Out[19]:

[(1, 4), (2, 3), (3, 2), (4, 1)]

``````
``````

In [20]:

men = {
'bob': ['betty', 'claire', 'diana'],
'charlie': ['betty', 'claire', 'diana']
}

women = {
}

gale_shapley(men, women)

``````
``````

Out[20]:

[('adam', 'diana'), ('bob', 'claire'), ('charlie', 'betty')]

``````
``````

In [21]:

men = {
'alex': ['alice', 'beatrice', 'christina'],
'ben': ['beatrice', 'alice', 'christina'],
'charlie': ['beatrice', 'christina', 'alice']
}

women = {
'alice': ['alex', 'charlie', 'ben'],
'beatrice': ['charlie', 'alex', 'ben'],
'charlie': ['alex', 'charlie', 'ben']
}

gale_shapley(men, women)

``````
``````

Out[21]:

[('alex', 'alice'), ('ben', 'christina'), ('charlie', 'beatrice')]

``````