Stable Matching - Propose-And-Reject Algorithm (Gale-Shapely)

propose-and-reject.py

# Stable Matching Problem

# Preference Profile
prefs = {
	'Xavier': ['Amy', 'Bertha', 'Clare'],
	'Yancey': ['Bertha', 'Amy', 'Clare'],
	'Zeus': ['Amy', 'Bertha', 'Clare'],
	'Amy': ['Yancey', 'Xavier', 'Zeus'],
	'Bertha': ['Xavier', 'Yancey', 'Zeus'],
	'Clare': ['Xavier', 'Yancey', 'Zeus']
}

# Engaged (by woman)
engaged = {
	'Amy': False,
	'Bertha': False,
	'Clare': False
}

# Create lookup table to compare rankings
rankings = {
	'Xavier': {'Amy': 1, 'Bertha': 2, 'Clare': 3},
	'Yancey': {'Bertha': 1, 'Amy': 2, 'Clare': 3},
	'Zeus': {'Amy': 1, 'Bertha': 2, 'Clare': 3},
	'Amy': {'Yancey': 1, 'Xavier': 2, 'Zeus': 3},
	'Bertha': {'Xavier': 1, 'Yancey': 2, 'Zeus': 3},
	'Clare': {'Xavier': 1, 'Yancey': 2, 'Zeus': 3}
}

# Propose-And-Reject Algorithm (Gale-Shapely)
'''
Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
	Choose such a man m
	w = 1st woman on m's list to whom m has not yet proposed
	if (w is free)
		assign m and w to be engaged
	else if (w prefers m to her fiance m')
		assign m and w to be engaged, and m' to be free
	else
		w rejects
}
'''

# Initialize each person to be free.
free_men = {'Xavier', 'Yancey', 'Zeus'}
free_women = {'Amy', 'Bertha', 'Clare'}

def get_engaged(m, w):
	
	m_prime = engaged[w]

	# break off existing engagements
	if m_prime != False:
		free_men.add(m_prime)

	# update to engaged
	engaged[w] = m
	free_men.remove(m)
	
	if w in free_women:
	  free_women.remove(w)

# while (some man is free and hasn't proposed to every woman) {
while len(free_men) > 0:
	# Choose such a man m
	m = list(free_men)[0]

	# w = 1st woman on m's list to whom m has not yet proposed
	w = prefs[m][0]

	# if (w is free)
	if engaged[w] == False:
		# assign m and w to be engaged
		get_engaged(m, w)
	#else if (w prefers m to her fiance m')
	elif rankings[w][m] < rankings[w][engaged[w]]:
		#assign m and w to be engaged, and m' to be free
		get_engaged(m, w)
	#else w rejects
	else: 
		prefs[m].remove(w)

for woman in engaged:
	print(woman, '->', engaged[woman])