Question

[10 pts] Consider an instance of the stable marriage problem for n = 4, with the men asM = {m1, m2, m3, m4} and the women as W = {w1, w2, w3, w4}. Consider the following preferences (each list is ranked from first to last choice):

men’s preferences

1. m1 :w1 >w2 >w3 >w4

2. m2 :w2 >w3 >w1 >w4

3. m3 :w3 >w1 >w2 >w4

4. m4 :w1 >w2 >w3 >w4

women’s preferencesw1 :m2 >m3 >m4 >m1w2 :m3 >m4 >m1 >m2w3 :m4 >m1 >m2 >m3w4 :m1 >m2 >m3 >m4

What is the matching produced by the Gale-Shapley algorithm? For each man/woman, also des- ignate their partner’s ranking on his/her preference list, respectively.

1

Answer 1

First let's make matrix for men and women separately showing their preferences.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

We will choose men's proposing to women

m1 will be proposing to w1 and w1 will accept it for now.

m2 will be proposing to w2 and w2 will accept it for now.

m3 will be proposing to w3 and w3 will accept it for now.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

m4 will propose to w1 and w1 will accept it as its preference for m4 is higher than m1. w1 will reject m1.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m1 will propose to w2 and w2 will accept it as its preference for m1 is higher than m2. w2 will reject m2.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m2 will propose to w3 and w3 will accept it as its preference for m2 is higher than m3. w3 will reject m3.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m3 will propose to w1 and w1 will accept it as its preference for m3 is higher than m4. w1 will reject m4.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m4 will propose to w2 and w2 will accept it as its preference for m4 is higher than m1. w2 will reject m1.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m1 will propose to w3 and w3 will accept it as its preference for m1 is higher than m2. w3 will reject m2.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m2 will propose to w1 and w1 will accept it as its preference for m2 is higher than m3. w1 will reject m3.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m3 will propose to w2 and w2 will accept it as its preference for m3 is higher than m4. w2 will reject m4.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m4 will propose to w3 and w3 will accept it as its preference for m4 is higher than m1. w3 will reject m1.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Now, m1 will propose to w4 and w4 will accept it.

m1 w1 w2 w3 w4 m2 w2 w3 w1 w4 m3 w3 w1 w2 w4 m4 w1 w2 w3 w4

w1 m2 m3 m4 m1 w2 m3 m4 m1 m2 w3 m4 m1 m2 m3 w4 m1 m2 m3 m4

Stable Matching produced by algorithm is

(m1, w4), (m2, w1), (m3, w2), (m4, w3)

Partner ranking for men m1 = 4, m2 = 3, m3 = 3, m4 = 3

Partner ranking for women w1 = 1, w2 = 1, w3 = 1, w4 = 1