Reference no: EM132374777

Assignment

1) Do Problem 4 in Chapter 1 on Pages 23-24 of the Kleinberg and Tardos text.

Problem 4. Gale and Shapley published their paper on the Stable Matching Problem in 1962; but a version of their algorithm had already been in use for ten years by the National Resident Matching Program, for the problem of assigning medical residents to hospitals.

Basically, the situation was the following. There were rn hospitals, each with a certain number of available positions for hiring residents.
There were tz. medical students graduating in a given year, each interested in joining one of the hospitals. Each hospital had a ranking of the students in order of preference, and each student had a ranking of the hospitals in order of preference. We will assume that there were more students graduating than there were slots available in the m hospitals.

The interest, naturally, was in finding a way of assigning each student to at most one hospital, in such a way that all available positions in all hospitals were filled. (Since we are assuming a surplus of students, there would be some students who do not get assigned to any hospital.) We say that an assignment of students to hospitals is stable if neither of the following situations arises.

• First type of instability: There are students s and s', and a hospital h,
so that

- s is assigned to tt, and
- s' is assigned to no hospital, and
- it prefers s' to s.

• Second type of instability: There are students s and s', and hospitals

It and le , so that

- s is assigned to h., and
- s' is assigned to le , and
- h prefers s' to s, and
- s' prefers h to h'.

So we basically have the Stable Matching Problem, except that (i) hospitals generally want more than one resident, and (ii) there is a surplus of medical students.

Show that there is always a stable assignment of students to hospitals, and give an algorithm to find one.

Specifically, implement Gale-Shapley Algorithm for computing the hospitals-residents matching Assignment in Python (or Java) using the approach and data structures described in the first two Chapters of Kleinberg and Tardos text (and reviewed in class).

Specifically, consider the residents as the “proposers” and the hospitals as the “disposers”. Note also that a hospital can have a number of slots and not all residency applicants will get a position. Watch the following video explaining the algorithm:

How the NRMP Matching Algorithm Works. (Youtube)

In your solution, make sure to:

(a) Assume that the input for an n-hospitals-m-residents problem is provided as a sequence of (n+1+m)-lines (encoding the preference lists – n lines for hospitals and m lines for residents with one empty line to separate the hospitals from residents) with each comma-separated line formatted as follows:

HOSPITAL_1, SLOTS, RESIDENT_a, …
…
**BLANK LINE**
RESIDENT_1, HOSPITAL_x, HOSPITAL_y, …
…

For example:
MERCY, 2, DARRIUS, JOSEPH
CITY, 2, DARRIUS, ARTHUR, SUNNY, LATHA, JOSEPH
…
ARTHUR, CITY
SUNNY, CITY, MERCY
…

For each hospital, we give the hospital name/id, the number of slots, and the preference list of residents. For each resident, we provide the resident id/name and the preference list of hospitals.

(b) Write the output after explicitly checking to see that it is a stable match. Note that writing and running a stability checker is a good debugging aid. When you turn in your solution, do include sample inputs and corresponding outputs in a separate file. Format the output as follows showing the matching of residents to hospitals:

HOSPITAL_1, RESIDENT_11, RESIDENT_12
HOSPITAL_2, RESIDENT_21, RESIDENT_22
…

(c) In your program, include pseudo-code of the modified Gale Shapley algorithm as a comment.

2) Do Problem 4 in Chapter 2 on Pages 67-68 of the Kleinberg and Tardos text. Justify your ordering of the growth rate functions in each case.