Mathematics for Computer Science

11.11. Forests & Trees 349

Homework Problems

Problem 11.18.
The most famous application of stable matching was in assigning graduating med-
ical students to hospital residencies. Each hospital has a preference ranking of
students and each student has a preference order of hospitals, but unlike the setup
in the notes where there are an equal number of boys and girls and monogamous
marriages, hospitals generally have differing numbers of available residencies, and
the total number of residencies may not equal the number of graduating students.
Modify the definition of stable matching so it applies in this situation, and explain
how to modify the Mating Ritual so it yields stable assignments of students to resi-
dencies.
Briefly indicate what, if any, modifications of the preserved invariant used to
verify the original Mating are needed to verify this one for hospitals and students.

Problem 11.19.
Give an example of a stable matching between 3 boys and 3 girls where no person
gets their first choice. Briefly explain why your matching is stable.

Problem 11.20.
In a stable matching betweennboys and girls produced by the Mating Ritual, call
a personluckyif they are matched up with one of theirdn=2etop choices. We will
prove:

Theorem.There must be at least one lucky person.

To prove this, define the following derived variables for the Mating Ritual:

q.B/Dj, where j is the rank of the girl that boyBis courting. That is to say,

boyBis always courting thejth girl on his list.

r.G/is the number of boys that girlGhas rejected.

(a)Let

SWWD

X

B 2 Boys

q.B/

X

G 2 Girls

r.G/: (11.4)

Show thatSremains the same from one day to the next in the Mating Ritual.

(b)Prove the Theorem above. (You may assume for simplicity thatnis even.)

Hint:A girl is sure to be lucky if she has rejected half the boys.