INFO 4220 – Networks II: Market Design
Spring 2025 – Problem Set 2
Due date: (Thursday) February 13, 11.59PM EST
Late submissions will be penalized with 1 point for every hour late.
Instructions: For each question, show all your work or you will lose some or all of the credit for
that question. Just showing the result without showing and explaining all steps you took to find
it does not count as a fully correct answer.
How to submit: Solutions must be submitted using Gradescope. For instructions on how to
submit the assignment, go to this guide or watch this video.
Important: You must select the pages for each question in Gradescope. Not doing this will lead
to delays and errors in your grades. If you don’t know how to do this, read this guide.
Asking questions in Ed Discussions: You can use Ed Discussions to ask clarification questions
about the problems. You cannot ask on Ed Discussions how to solve a particular problem, and
especially, you cannot post on Ed Discussions (or anywhere else) your solution to the problem
set (or a subset of it). Disclosing the solution of problems in Ed Discussions (or anywhere else)
will be considered an academic integrity violation and reported accordingly. If you don’t know
how to solve a problem, don’t ask on Ed Discussions, come to office hours! (Although, we will
not solve the problem for you)
Who did you work with to solve this PS, if anyone (remember each of
you must turn in their own solution, which has to be your own original
work)? (0 pt)
Are you using and slip day for this PS? Remember that you have 4 for
the entire semester (for both problem sets and assignments), they can
only be used in 1-day increments, and you can use up to 2 per PS. (0 pt)
Problem 1 (10 points)
Consider the following one-to-one matching problem with 2 musicians and 2 singers. The
preferences are as follows:
1 2 1 2
1 2 1 2
2 1 2 1
Assume the deferred acceptance algorithm with singers proposing. Is it a dominant strategy for
musicians to report truthfully their preferences? Why (do not use a theorem to explain? (hint:
consider carefully the definition of strategyproof)
Problem 2 (20 points, 5 pts each)
Consider a medical match problem with three hospitals: ℎ1,ℎ2,ℎ3 and four doctors
1,2,3, 4. The capacities of the hospitals are: ℎ1 = 2, ℎ2 = 1, ℎ3 = 1. The preferences of
doctors and hospitals are as follows:

1 2 3 4 ℎ1 ℎ2 ℎ3
ℎ3 ℎ2 ℎ1 ℎ1 1 1 3
ℎ1 ℎ1 ℎ3 ℎ2 2 2 1
ℎ2 ℎ3 ℎ2 ℎ3 3 3 2
4 4 4

a) Find the doctor-optimal matching
b) Find the hospital-optimal matching
c) Consider the following matching (ℎ1) = 2,4; (ℎ2) = 1, (ℎ3) = 3. If we use
deferred acceptance with hospitals proposing, is there a preference list over doctors that
hospitals have to submit to obtain this matching?
d) True/False (explain): The deferred acceptance algorithm with hospitals proposing is
strategyproof for hospitals, but it is not strategyproof for doctors.
Problem 3 (20 points, 10 pts each)
In a medical residence matching program there are 3 hospitals and 6 doctors. Hospital 1 can
admit up to 3 doctors. Hospitals 2 and 3 are smaller and can only admit 2 residents each. The
true preferences of doctors over hospitals and hospitals over doctors are given by the following
tables (assume hospitals preferences are responsive). Note that doctors 5 and 6 are a couple
and their preferences are expressed as pairs of hospitals: The first preference of 5 & 6 is to
both go to ℎ1, their second preference is to both go to ℎ3, and their third preference is to both
go to ℎ2.
&
ℎ1 ℎ1 ℎ1 ℎ1 (ℎ1,ℎ1)
ℎ3 ℎ2 ℎ3 ℎ2 (ℎ3,ℎ3)
ℎ2 ℎ3 ℎ2 ℎ3 (ℎ2,ℎ2)
5 5 6
4 3 2
1 1 3
2 2 1
3 4 4
6 6 5
a) Use the following algorithm to match hospitals and doctors (15 pts):
Step 1: Use the DA algorithm with doctors proposing excluding the couple (5 & 6) from the
problem
Step 2: Now manually match the couple to hospitals in order of their preferences (you must
match them as a couple). When doing this manual matching, consider that the couple can
displace doctors that are already matched as long as you leave hospital hiring them with a set
of doctors that is preferred to the matchings they had obtained in step 1.
Step 3: Now manually match the doctor(s) displaced in step 2 to a hospital in order of their
preferences. In this step unmatched doctors cannot displace doctors that have already been
matched, so they can only be matched to hospitals that have a vacancy.

b) For the doctor(s) displaced in step 2. Can you find a hospital that would be willing to form a
blocking pair with them? (Note that you must treat the couple as an indivisible couple: If
you want to remove one doctor of the couple from a hospital, you must remove both). (5
pts)