1. (10 points) There are three men m1, m2, m3 and three women w1, w2, w3 in a marriage market. Their preferences are as follows:

P(m1):w1 w2 m1 w3,

P(m2):w1 w3 w2

P(m3):w3 w1 w2

P(w1):m3 m1 w1 m2

P(w2):m3 m2 m1

P(w3):m2 m3 m1

(a) What is the outcome of the man-proposing DA algorithm? Show each step of the algorithm.

(b) The man-proposing DA produces the man-optimal stable matching. Define the man-optimal stable matching.

(c) The man-proposing DA produces the woman-pessimal stable matching. Define the woman-pessimal stable matching.