Consider extending the stable marriage problem to the case of fellowship program

Question

Consider extending the stable marriage problem to the case of fellowship programs in a given specialty (which doctors can complete as additional training after their residency). Each of m doctors ranks all the fellowship programs. Each of n programs ranks its applicants. Each doctor can be admitted to at most one fellowship program, but each program has a dierent number of slots to ll in its class. Assume that there may be more applicants than total slots, so some doctors might not be assigned to any fellowship. An assignment of doctors to programs is stable if neither of the following two instabilities exist:

- There are doctors d and d', and a program p, so that d is assigned to p, and d' is assigned to no program, and p prefers d' to d.

- There are doctors d and d', and programs p and p', so that d is assigned to p, and d' is assigned to p', and p prefers d' to d, and d' prefers p to p'.

Prove that a stable assignment of doctors to fellowship programs always exists.

Explanation / Answer

n integer program with a solution set that exactly corresponds to the set of stable matchings. This provides a generalization of the stable marriage linear program to the matching with contracts framework. We will now proceed to present the constraints that form the matching integer program, we will then present the stability constraints which combined with matching integer program forms the stable matching integer program,

Finally we discuss four possible objectives Interpret zx {0, 1} as an indicator variable which shows whether contract x is used. Let ya,B {0, 1} be whether the set B of contracts is allocated to agent a. Therefore ya,B = 1 is equivalent to B = µ(a) and zx = 1 is equivalent to x µ(a). We make the observation that any integer solution to this linear program is equivilant to a stable matching, and vice versa.

Set constraint. Each agent is allocated exactly one set of contracts (may be the emptyset).

X BQa ya,B = 1 a A

(1) Matching constraint. If a contract x X is used then all agents a xA must sign it. zx = X BQa:xB ya,B x X, a xA

(2) Non-negativity constraint. zx, ya,B 0

(3) Stability constraint. If a contract x X is unused then at least one agent a xA does not want to sign it. zx + X axA X BQa:x6Cha(Bx) ya,B 1 x X

(4) Constraint (1) and (3) guarantee that ya,B 1 and hence by (2) that zx 1.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.