Please prove if this is stable or not stable Theorem 222 In

Please prove if this is stable or not stable

Theorem 2.22: In a market (M,W, P) with strict preferences, the set of people who are single is the same for all stable matchings.

One strategy of proof: What can we say about the number and identity of men and women matched (and hence the number and identity unmatched) at µM and at µW?

i.e. denoting MµM = µM(WM), etc. what can we say about the relative sizes and containment relations of the sets MµM , WµM, MµW, and WµW ?

µM |MµM| |WµM|

µW |MµW| |WµW|

Solution

Players: Men: M = {m1, .., mn}, Women: W = {w1, ..,wp }. The market is two-sided: Man mi can only have preferences over the set of W > {mi }. Similarly for women’s preferences. Preferences: (complete and transitive): P(mi) = wk ,wl, ..., mi,wj... [wk >mi wl] If mi prefers to remain single rather than to be matched to wj, i.e. if mi >mi wj, then wj is said to be unacceptable to mi. If an agent is not indifferent betweome of the theorems we prove will only be true for strict preferences. Indifferences: P(mi) = wk , [wl,wm], ..., mi,where mi is different between wl and wm.

An outcome of the game is a matching µ : M union W - M union W such that w = µ(m) implies that µ(w) = m .µ(w) subset M union {w} and µ(m) subset W union {m}. (two-sided).

An outcome of the game is a matching µ : M union W implies that M union W such that w = µ(m) which implies that µ(w) = m µ(w) subset M union {w} and µ(m) subset W union {m}. (two-sided). A matching µ is blocked by an individual k : k prefers being single to being matched with µ(k), i.e. k > k µ(k).

An outcome of the game is a matching µ : M union W implies that M .W such that which implies w = µ(m) which implies that µ(w) = m µ(w) subset M union {w} and µ(m) subset W union {m}. (two-sided). A matching µ is blocked by an individual k : k prefers being single to being matched with µ(k), i.e. k >k µ(k). blocked by a pair of agents (m,w) if they each prefer each other to their current outcome, i.e. w >m µ(m) and m >w µ(w).