Matching algorithm

The link below describes a widely applied matching algorithm which takes preference lists from applicants and prospective employers and assigns these applicants to jobs.

The algorithmic matches are considered binding on medical residents and hospitals in the U.S., Canada, and possibly elsewhere. The question is: can the order in which applicants are considered affect the results? Can you prove your answer?
http://www.aafp.org/student/match/section6.html

(You might want to skip to 'The Matching Algorithm at Work' near the bottom; the whole rest of the document is an attempt to clarify this kernel, many r.p. types won't need it.)

Jonathan Dushoff

No.

Yes.

The algorithm will produce what is known as a 'stable matching'

This all looks good to me, but of course a simple proof of the 'well-known fact' is part of the intended puzzle challenge.

Jonathan Dushoff

This seems contradicted by a simple counter-example. I don't have an example where order matters, but here's one where one of two different stable matchings will be selected depending on a catalyst:

Rankings for Programs M, P: M) b c a P) c b Rankings for Applicants A, B, C: A) m p p m C) m

Applicant C ends up rejected, but his presence causes the others to switch from one stable matching (with each applicant getting first choice) to another (with each program getting first choice). Doesn't this contradict the 'Well Known Fact'? ... or am I confused?

Oops, one typing error in the example I posted. Substitute M) b c a P) a b

P) a b As updated by your other post

The matching where a and b both get their first choice is NOT a stable matching! With the matching M:a, P:b, c unmatched, consider the person c and the institution M. M prefers c to the person assigned to M and c prefers M to being unassigned and hence, the matching is not stable.

This example demonstrates that the residents may do better in some non-stable matching but it doesn't contradict the fact that there is no *stable* matching in which the residents do

All true, but when do we get a proof of the 'well-known fact'? This was intended as a puzzle, and the desired answer is a neat, complete proof of order-independence.

Jonathan Dushoff

To me this sounded like a classroom exercise instead of a puzzle but if you insist.

Terminology: Call a resident-hospital pair (r,h) a 'stable pair' if r is assigned to h in some stable matching. Call r a 'stable partner' of h and vice-versa.

Lemma: During the algorithm, No hospital ever rejects a stable partner.

Proof: By Contradiction. Suppose (r1,h1) is the first stable pair rejected by the algorithm. Let r2 be the resident for which h1 rejected r1. Since (r1,h1) is a stable pair, there is some stable matching which includes this pair. In some such stable matching, let h2 be the stable partner for r2. claim: A matching that includes both (r1,h1) and (r2,h2) is NOT stable! (1) h1 prefers r2 over r1 (since h1 rejects r1 for r2). Since (r1,h1) is the first stable pair rejected, r2 proposed to h1 prior to any other stable partner. (if r2 proposed to some other stable partner before h1, then that other stable partner must at some point have rejected r2 contradicting the fact that (r1,h1) was the *first* stable pair rejected). (2)Since r2 proposed to h1 before any other stable partner, r2 prefers h1 over h2. (1) + (2)

I wonder why. I also wonder why you solved it, if that's what you thought.

I especially wonder what you thought was the point of the trivial half-proof you posted originally.

It's a simple problem, with a cute, simple (but not trivial) answer. Is r.p. no longer interested in this sort of thing?

Jonathan Dushoff

The problem in itself looks interesting. But understanding the algorithm involves translating the bureaucratese in which it is written. This reminds me of lawyers, tax forms, and other such unpleasant things, enough to deter me from attempting the translation.

Which it is, of course.

The stable marriage problem is a standard one from computer science. See, for example,