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)