Question

2. [10 pts] Consider a stable marriage instance with men M = {m1,m2,m3} and women W ={w1, w2, w3} having the following preference lists:

m1 :w1 >w2 >w3m2 :w2 >w1 >w3m3 :w1 >w2 >w3

w1 :m2 >m1 >m3w2 :m1 >m2 >m3w3 :m1 >m2 >m3

1. If these preferences are given to the Gale-Shapley algorithm, what is the resulting set of marriages?

2. Now, suppose w1 decides to lie to the algorithm about her preferences and instead submits the list w1 : m2 > m3 > m1 to the Gale-Shapley algorithm (with everyone else’s preference lists remaining unchanged). What is the resulting set of marriages? Did w1 get a better, worse, or same partner according to her true preference by lying this way compared to the result in part a.?

Answer 1

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

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m1 m3 w2 m1 m2 m3 w3 m1 m2 m3

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.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m1 m3 w2 m1 m2 m3 w3 m1 m2 m3

m3 will be proposing to w1 but w1 has current proposal from m1 which is higher preference than m3 so m3 will be rejected.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m1 m3 w2 m1 m2 m3 w3 m1 m2 m3

m1 and m2 don't have to make proposal again as they are not rejected.

m3 will propose w2 now. w2 has current proposal from m2 which is higher in preference so m3 will be rejected by w2 as well.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m1 m3 w2 m1 m2 m3 w3 m1 m2 m3

lastly m3 will propose to w3 and w3 will accept it.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m1 m3 w2 m1 m2 m3 w3 m1 m2 m3

So stable matching is (m1, w1), (m2, w2) and (m3, w3)

Now, w1 lies about preference

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

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.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

m3 will make proposal to w1. w1 current proposal m1 has lower preference than m3 so w1 will accept proposal from m3 and reject m1.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

Now, m1 will make proposal to w2. w2 has current proposal from m2 which is lower preference than m1 so w2 will accept m1 and reject m2.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

Now, m2 will make proposal to w1. w1 has current proposal from m3 which has lower preference than m2. So w1 will accept m2 and reject m3.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

Now m3 will make proposal to w2 but w2 won't accept it as it has already accepted proposal from it's highest preference. Next m3 will propose w3 and w3 will accept it.

m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w2 w3

w1 m2 m3 m1 w2 m1 m2 m3 w3 m1 m2 m3

Stable matching is (m1, w2), (m2, w1) and (m3, w3)

After lying w1 has got better partner. Earlier w1 got m1 but this time w1 got m2 and m2 was highest preference earlier.