Gale-Shapley Example with Ten Stable Marriages

Prepared by:

Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk


1. Apply the Gale/Shapley Algorithm twice: once with the men proposing and once with the women proposing. (Can you find all 10(!!) stable matchings?)

Men's preferences:


m1 1 2 3 4
m2 2 1 4 3
m3 3 4 1 2
m4 4 3 2 1


Women's preferences:


w1 4 3 2 1
w2 3 4 1 2
w3 2 1 4 3
w4 1 2 3 4


Thus, for the men, m1 likes w1 best, next w2, w3 is 3rd in his ranking and w4 is has least favorite. In other words the further to the left in the men's preferences, the more a woman is liked.