HUL 212A: Microeconomics
IIT Delhi
Problem Set 5
March 25, 2026
1. Show that there are no individually rational matching strictly preferred by all men to
µM (i.e., even non-stable).
2. Prove that for any set of preferences, < {≻m }m∈M , {≻w }w∈W > a stable matching µ
exists (under DAA).
3. Consider three doctors {Alice, Bob, Charlie}, and three hospitals {X, Y, Z}. Suppose
that Alice prefers Y over X over Z, etc:
Table 1: Doctor preferences
Doctor Alice Bob Charlie
top choice Y X X
2nd choice X Y Y
last choice Z Z Z
On the hospital side, their preferences are:
Table 2: Hospital preferences
Hospital X Y Z
top choice Alice Charlie Bob
2nd choice Charlie Alice Charlie
last choice Bob Bob Alice
(a) Run the Deferred Acceptance algorithm with doctors proposing. Find the final
matching.
(b) Run the algorithm with hospitals proposing. Find the final matching.
(c) Given that hospital X misreports its preferences as in Table 3, verify that the
Deferred Acceptance algorithm now yields a unique stable matching.
1
Table 3: Hospital mis-reported preferences
Hospital X Y Z
top choice Alice Charlie Bob
2nd choice Bob Alice Charlie
last choice Charlie Bob Alice
4. Consider the following problems for a men-proposing DAA:
(a) Suppose that the boys all have different favorite girls. How many steps does it
take for the algorithm to converge?
(b) Suppose that the boys have identical preferences. How many steps does it take
for the algorithm to converge?
(c) Construct an example in which there is more than one stable matching.
5. Suppose preferences are given by the following tables:
BOY 1 2 3 4 5
Adam Beth Amy Diane Ellen Cara
Bill Diane Beth Amy Cara Ellen
Carl Beth Ellen Cara Diane Amy
Dan Amy Diane Cara Beth Ellen
Eric Beth Diane Amy Ellen Cara
Boys’ Preferences
GIRL 1 2 3 4 5
Amy Eric Adam Bill Dan Carl
Beth Carl Bill Dan Adam Eric
Cara Bill Carl Dan Eric Adam
Diane Adam Eric Dan Carl Bill
Ellen Dan Bill Eric Carl Adam
Girls’ Preferences
(a) Find a stable matchings using the Gale-Shapley algorithm with boys making
proposals and with girls making proposals.
(b) Are there other stable matchings ?
6. Consider the following “roommate” problem. There are four people, Pat, Chris, Dana,
and Leslie. They must pair off (each pair will share a two-bed suite). Each has
preferences over which of the others they would prefer to have as a roommate. The
preferences are:
Page 2
Leslie: Pat ≻ Chris ≻ Dana
Chris: Leslie ≻ Pat ≻ Dana
Pat: Chris ≻ Leslie ≻ Dana
Dana: Chris ≻ Leslie ≻ Pat
Show that no stable matching exists. (That is, no matter who you put together, there
will always be two potential roommates who are not matched, but prefer each other
to their current roommate.)
7. (Kidney Exchange) Consider a kidney exchange problem with five patient-donor pairs,
Figure 1: Caption
where Pi denotes the i-th patient and Hi denotes their own incompatible kidney donor.
The patients’ preferences over kidneys are given in the following table:
Patient 1st Choice
P1 H2
P2 H5
P3 H2
P4 H1
P5 H3
Table 4: Patient preferences over kidneys
The initial priority ordering over patients is P4 ≻ P1 ≻ P2 ≻ P3 ≻ P5 .
(a) Apply the Top Trading Cycles (TTC) algorithm. In each round, draw the graph
showing which patient points to their most preferred remaining kidney, identify
any cycles, remove the matched pairs, and repeat until all patients are matched.
(b) State the final allocation of kidneys to patients.
(c) Is the resulting allocation Pareto efficient? Briefly justify your answer.
Page 3