Problem set 2 solutions

Mechanism Design (ECO-3517-1)

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.
Solutions:
m1 m2 m3 w1 w2 w3
w1 w2 w3 m1 m2 m3
w2 w3 w1 m3 m1 m2
w3 w1 w2 m2 m3 m1

In the matching m1 −w1 , m2 −w2 , m3 −w3 , each individual gets their favourite match.
So, there are no blocking pairs. Hence, this is a stable matching.
Take any other matching. If m1 is matched with w2 or w3 , then neither of m1 and
w1 get their favourite match, and hence form a blocking pair. Similarly, if m2 is
matched with w1 or w3 , then m2 and w2 form a blocking pair, and if m3 is matched
with w1 or w2 , then m3 and w3 form a blocking pair. So there exists a unique stable
matching. ∎

2. Let there be n men and n women. Assume that all the men have the same preference
list over women. That is, each man ranks w1 the highest, w2 the second highest,
and so on..., wn the lowest. Women have arbitrary, possibly distinct, preferences.
Prove that men proposing and women proposing matchings are the same.
Compare this matching with a matching we studied in the object assignment model
(treat men side as objects and women side as agents).
Solutions:
We will show that the outcomes of both men proposing DAA and women proposing
DAA result into the outcome of fixed priority mechanism when Women side is
treated as individuals, and men side is treated as objects. The priority order in this
case will be w1 − w2 − . . . − wn . According to this order, fixed priority mechanism
assigns w1 her favourite man, w2 gets her favourite man among the remaining men
(all the men except the one chosen by w1 ), and so on. In particular, let Si ⊆ M be
the set of men chosen by women w1 , w2 , . . . , wi . Then next women in order, that
is wi+1 gets her favourite man among the set M ∖ Si , which is the set of remaining
men.
Consider men proposing DAA. Each man has the same preference order over women.
In the first step, each man proposes w1 . w1 keeps her favourite man, and rejects
all the other rest. In step 2, all the rejected men propose to w2 . Hence, w2 gets to

1
 pick her favourite man which is not chosen by w1 , and rejects all the other men.
With the same reasoning, in step i + 1, all the men rejected by wi in step i propose
to wi+1 . Hence, wi+1 gets to pick her favourite man which is not chosen by women
w1 , w2 , . . . , wi , that is. her favourite man among the set M ∖ Si . This outcome
coincides with the outcome of fixed priority mechanism outcome.
Now consider women proposing DAA. Consider w1 . In step 1, w1 proposes to her
favourite man, call mw1 . Since, mw1 ranks w1 at the top, he will accept the proposal
of w1 . Also note that, mw1 will not reject w1 even in any future rounds, since w1 is
his favourite match. So, in the final outcome w1 is matched with her favourite man
mw1 .
Now consider w2 . If she proposes mw1 in step 1, then she gets rejected, since mw1
also gets a proposal from w1 and mw1 prefers w1 over w2 . If w2 proposes any man
other than mw1 , call that man mw2 either in step 1 or step 2, then mw2 will accept
the proposal and moreover, will not reject w2 at any future rounds. This is because
although mw2 prefers w1 over w2 , we know that w1 will never propose to mw2 , since
w1 is matched with her favourite man mw1 . And, since mw1 never gets proposal from
w1 , w2 is his best available option. So, in the final outcome, w2 is matched with
mw2 , that is, w2 picks her favourite man that was available after w1 has picked her
favourite man. Important note: It is possible that mw2 had accepted the proposal
of a different woman, but since w2 proposes to mw2 in step 2, mw1 rejects the first
proposal and then accepts w2 .
Continuing with the same logic, for k = 1, 2, . . . , i assume wi will be matched with
mwi in the final outcome. We have Si = {mw1 , mw2 , . . . , mwi }. Let mwi+1 be the
favourite man of wi+1 among the set M ∖ Si = M ∖ {mw1 , mw2 , . . . , mwi }. We know
that proposal of wi+1 to any man in the set Si will be rejected right away, or at some
point in the future. So, at some step, wi+1 will propose to mwi+1 . Since mwi+1 will
not get proposal from any women w1 , w2 , . . . , wi , mwi+1 accepts the proposal from
wi+1 and never rejects her in the future. Hence, wi+1 get her favourite choice among
the set M ∖ Si . This coincides with the outcome of fixed priority mechanism. ∎

3. In the private endowment setting with n individuals, construct a TTC instance

2
In step 1, each agent points to himself. So there are n cycles of length 1, so all
agents are removed and the algorithm terminates.
(b) Choose Pi1 = 1 for each agent i, Pi2 = 2 for each agent i, and so on. In other
words, Pij = j for each agent i and for each j = 1, 2, . . . , n.
In step 1, every agent (including agent 1) points to agent 1. So, there is unique
cycle, agent 1 pointing to himself, so only agent 1 is removed. Agents remaining
are 2, 3, . . . , n.
In step 2, every agent (including agent 2) points to agent 2. So, there is unique
cycle, agent 2 pointing to himself, so only agent 2 is removed. Agents remaining
are 3, 4, . . . , n.
Similarly, in step j, every agent (including agent j) points to agent j. So, there
is unique cycle, agent j pointing to himself, so only agent j is removed. Agents
remaining are j + 1, j + 2, . . . , n. The algorithm terminates in n steps.
(c) Main idea: Imitate choice in sub question (b) for first k − 1 steps, and choice in
sub question (a) for step k.
Choose preference profile P as follows. For each j = 1, 2, . . . , k − 1, Pij = j for each
agent i. For each j = k, k + 1, . . . , n, Pij = i for each agent i.
For steps j = 1, 2, . . . , k − 1, every agent (including agent j) points to agent j. So,
there is unique cycle, agent j pointing to himself, so only agent j is removed. Agents
remaining at the end of step j are j + 1, j + 2, . . . , n.
In step k, every agent points to himself. So, there are n − (k − 1) = n − k + 1 cycles
for length 1. All the remaining n − (k − 1) = n − k + 1 agents are removed, and the
algorithm terminates at step k. ∎