Solve Stable Marriage Problem with Gale-Shapley Algorithm
The stable marriage problem (or stable matching problem) aims to ensure that if there’s 2 equal sets, no pair of elements from both sets prefer each other compared to the partner they are currently matched with.
While taking my algorithms course I was interested in doing a python implementation for a question in the course.
So there’s a set of men and woman ordered according to preference.
mens_preferences = {
'm1':['w1','w3','w2'],
'm2':['w2','w3','w1'],
'm3':['w2','w1','w3']
}
womens_preferences = {
'w1':['m1','m2','m3'],
'w2':['m1','m3','m2'],
'w3':['m3','m2','m1']
}I wrote a Personclass that is able to make and receive proposals. When making proposals:
- recipient should not have been proposed to before
- recipient should not be less preferred to current mate, if the initiator is currently engaged (lower index in the python list is more preferred)
When considering proposals:
- accept if not currently engaged
- if engaged, accept if initiator (suitor) is more preferred to current mate
I added a bunch of print statements as logs to help with going through the logic as it runs.
class Person():
def __init__(self,name:str,gender:str, preferred_mates:list):
self.name = name
self.gender = gender
self.preferred_mates = preferred_mates
self.is_engaged = False
self.current_mate = None
def make_proposal(self):
for person in self.preferred_mates:
# don't propose to current mate
if self.current_mate==person:
continue
# don't propose if current mate is preferred
if self.is_engaged:
if self.preferred_mates.index(self.current_mate)<self.preferred_mates.index(person):
continue
print(f'{self.name} making proposal to {person}')
# get response for proposal
response = eval(person).consider_proposal(self.name)
if response:
self.current_mate = eval(person).name
self.is_engaged=True
return True
def consider_proposal(self, suitor):
print(f'{self.name} considering proposal from {suitor}')
if not self.is_engaged:
# accept if not engaged
print('Accepting: Not currently engaged.')
self.current_mate = suitor
self.is_engaged=True
return True
if self.is_engaged:
# accept if new suitor is more preferred than current mate
if self.preferred_mates.index(self.current_mate)>self.preferred_mates.index(suitor):
print(f'Accepting: current mate is {self.preferred_mates.index(self.current_mate)}, new suitor is {self.preferred_mates.index(suitor)}')
# reject current mate
self.reject_current_mate(self.current_mate)
# update current mate to new suitor
self.current_mate = suitor
return True
print(f'Rejecting: current mate is {self.preferred_mates.index(self.current_mate)}, new suitor is {self.preferred_mates.index(suitor)}')
return False
def reject_current_mate(self, current_mate):
eval(current_mate).is_engaged=False
eval(current_mate).current_mate=None
print(f'{current_mate} is now free')I use the eval() function on the strings identifying persons to get python to call the objects with equivalent names as the string passed to it.
Finally, loop through each initiator until none of the initiators is without a mate:
# create persons
m1, m2, m3 = Person('m1', 'male',mens_preferences['m1']), Person('m2', 'male',mens_preferences['m2']), Person('m3', 'male',mens_preferences['m3'])
w1, w2, w3 = Person('w1', 'male',womens_preferences['w1']), Person('w2', 'male',womens_preferences['w2']), Person('w3', 'male',womens_preferences['w3'])
# while any initiator has no mate:
while any([eval(man).current_mate is None for man in mens_preferences.keys()]):
print('\n*****New iteration*****')
for name in mens_preferences.keys():
print('\nEvaluating proposals for ',name)
eval(name).make_proposal()
# view final matching
for name in mens_preferences.keys():
print(name, '-', eval(name).current_mate)
