Mechanism Design [ECO-3517]
Problem set 3 (Not for submission)
1. Construct preferences for 3 men and 3 women such that there is only one stable matching. Explain
why any other matching would have a blocking pair.
2. Consider the setting of 3 men and 3 women. Let P = (Pm1 , Pm2 , Pm3 , Pw1 , Pw2 , Pw3 ) be a fixed
preference profile.
Let P ′ be a new fixed preference profile in which all players (men and women) except m1 have
the same preferences as in P , and preferences of m1 in P ′ differ as follows. P ′ allows indifferences
for m1 , that is, a man m1 could be indifferent between two women. In other words, if m1 strictly
prefers wi over wj in the profile P , then either m1 strictly prefers wi over wj in the profile P ′ or
m1 is indifferent between wi and wj in the profile P ′ . Assume that other men (m2 , m3 ) and all
the women (w1 , w2 , w3 ) have same strict preferences in P ′ as in P .
Show that any matching which is stable with respect to preference profile P is also stable with
respect to profile P ′ .
3. Let there be n men and n women. Let µ be a stable matching. Show that there does not exist
any other matching µ′ (which is different from µ) such that, both statements simultaneously hold.
(1) For each man m, either µ′ (m) = µ(m) or µ′ (m)Pm µ(m).
(2) For each woman w, either µ′ (w) = µ(w) or µ′ (w)Pw µ(w).
4. Consider 3 men and 3 women.
(a) Is it possible for every individual (both men and women) to get their first choice in a stable
matching? If yes, construct such an instance of a preference profile P and respective stable
matching µ. If not, explain why.
(b) Is it possible for every individual (both men and women) to get their second choice in a
stable matching? If yes, construct such an instance of a preference profile P and respective stable
matching µ. If not, explain why.
(c) Is it possible for every individual (both men and women) to get their last choice in a stable
matching? If yes, construct such an instance of a preference profile P and respective stable
matching µ. If not, explain why.
(d) Is it possible for every men to get their second choice and every women to get their last choice
in a stable matching? If yes, construct such an instance of a preference profile P and respective
stable matching µ. If not, explain why.
5. For the given a preference profile, answer the following questions.
(a) Find stable matchings µM and µW which are outcomes of men-proposing DAA and women-
proposing DAA respectively.
1
m1 m2 m3 w1 w2 w3
w1 w2 w3 m2 m3 m1
w2 w3 w1 m3 m1 m2
w3 w1 w2 m1 m2 m3
Table 1: Profile 1 Table 2: Profile 2
Table 3: Profiles for question
(b) Find any other stable matching µ different from µM and µW .
(c) Show that all the men at least weakly prefer µM over µ and µ over µW .
(d) Show that all the women at least weakly prefer µW over µ and µ over µM .
6. Consider the setting with 3 men and 3 women, and men proposing DAA. Depending on which
preference profile of men and women we have, the total number of proposals (sum of proposals
made by all the men) is different. What is the minimum number of proposals that can be made?
Call that number a. What is the maximum number of proposals that can be made? Call that
number b. For each number k which satisfies a ≤ k ≤ b, construct a preference profile, such that
when we run men proposing DAA, total number of proposals is exactly k.