Consider an instance of the stable marriage problem for n 5

Consider an instance of the stable marriage problem for n = 5, with the men as M = {m_1, m_2, m_3, m_4} and the women as W = {w_1, w_2, w_3, w_4}. Consider the following preferences (each list is ranked from first to last choice): What is the matching produced by the Gale-Shapley algorithm? For each man/woman, also designate their partner\'s ranking on his/her preference list, respectively.

Solution

Final generated matchings are as follows.

m1 <---> w2 (m1 got w2 in second proposal who is his second preference but initially she was with m2)

m2 <---> w4 (m2 got w4 in 4^rth proposal who is his last preference but in the time he was with w2)

m3 <---> w1 (m3 got w1 in second proposal who is his second preference but initially he was with w3)

m4 <---> w3 (m4 got w3 in third proposal )

>>> At first w1 got two proposals but she has accepted m1 and rejects m4. but m2 and m3 got w2 and w3 respectively in the first round.