# 226638 Generalizing Stable Marriage

Bajet N/A

Generalizing Stable Marriage OR Matching Problem

We generalize Stable Marriage simultaneously in two ways. Here is the intuitive specification

of this generalization. You will be asked to define it formally in your report.

(1) First we allow individuals to have preference lists where an individual instead of considering

a total ordering on her/his preferences she/he may be indifferent regarding some

choices. For example, a woman may have the following list over the men {1, 2, 3, 4, 5}:

{1} > {4, 5} > {2, 3}. We read this as follows. She prefers the man 1 better than any

other. Next in her preference are men 4 and 5 (who she considers as better matches than

2, 3), but she is indifferent whether she will be matched with 4 or 5; i.e. any of them is

equally good. In other words, instead of strictly ordering every individual we allow orderings

of groups of individuals, where individuals of the same group are preferred equally. We refer

to such an ordering of a set as an “ordering of groups of people”.

(2) The second generalization allows us an even more practical application of the “Stable

Marriage” problem. Instead of men and women let us consider the possibility of having

hospitals and young medical doctors who apply for residency (jobs) in the hospitals. There

are m hospitals, each hospital h with a given number of available positions ph for hiring

graduates. There are n medical students graduating in a given year, each interested in

joining one of the hospitals. Each hospital has a ranking for groups of students as we saw in

(1) above, and each student has a ranking of the hospitals again by considering an ordering of

groups of hospitals in order of preference. We assume that there are more students graduating

than the total number of slots available in the m hospitals.

We wish to find an assignment of every student to at most one hospital, in such a way

that all available positions in all hospitals are filled. (Since we are assuming that there are

more students than positions there would be some students who do not get assigned to any

hospital.)

We change the definition of the instability, i.e. we introduce another definition, which we

call “generalized instability”.

To define generalized instability we first have to define the notion of “preference”. We say

CSE 3101 OPTIONAL PROBLEM (Bonus to Assignment 1) Summer 2008

that a hospital h prefers student s to s0 if s comes strictly higher in preference than s0. That

is, if s and s0 are in the same group according to the ordering of h then it is not true that h

prefers s than s0.

We say that an assignment of students to hospitals is unstable if the first or the second type

(below) occurs:

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

– s is assigned to h, and

– there does not exist a hospital where s0 is assigned to, and

– h prefers s0 to s.

• Second type of instability: There are students s and s0 and hospitals h and h0 so that

– s is assigned to h, and

– s0 is assigned to h0, and

– h prefers s0 to s, and

– s0 prefers h to h0.

In other words we have the stable marriage problem except that (i) we allow the preference

lists to have groups of equally preferred hospitals or graduates, (ii) hospitals generally want

more that one graduate and (iii) there is a surplus of medical students.

(a) (5 points) Define the notion of “generalized stable matching” and also define the problem

(in the Input/Output form).

(b) (5 points) Why do you think this definition of the problem is more appropriate for the

real-life scenario compared to the standard stable marriage problem?

(c) (5 points) Prove or disprove: for every given input instance there exists a unique output

to the problem.

(d) (20 points) Present an algorithm for this problem.

(e) (40 points) Prove that your algorithm is correct.

(f) (10 points) Upper and lower bound the worst-case running time of your algorithm.

(g) (5 points) Does there always exist a “generalized stable matching” with respect to (wrt) your definition)?

** NEED BY TOMORROW **