# Minimizing catastrophic risk in Gale-Shapley matching

In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much larger than the total number of residency slots available - several students are left unmatched.

If a particular student's primary concern is simply matching somewhere, is there any strategy they can adopt that outperforms ranking hospitals according to their true preference?

• Is the student allowed to list all of the hospitals on their ranked list? Can we assume the student knows how the hospitals will rank everyone? Did you try reading references 20 and 21 in the Wikipedia article? Based on the way the Wikipedia article refers to them, it sounds like they might be relevant. – D.W. Mar 14 '19 at 5:28
• A useful search term will be "truthful mechanism". A truthful mechanism is one where the players get their best payoff by saying what they really want rather than trying to game the system by reporting false preferences. – David Richerby Mar 14 '19 at 10:20
• @DavidRicherby A related term is Strategy proofness. – Discrete lizard Mar 14 '19 at 10:23
• This looks very similar to the stable marriage problem, with the only difference that the hospitals have multiple positions (that can be represented by several 'women' with the same preference.) If we assume that preference lists give an order over all options, then no, strategy proofness holds for the 'male' side (here the students) of stable matching, see this answer – Discrete lizard Mar 14 '19 at 10:26
• I want to be clear that the objective for this student isn't to match with the best hospital (which is what Gale-Shapely optimizes for). It's only to avoid being unmatched - all hospitals are equal (despite the fact that she submits a ranked list to the match algorithm). – dranxo Mar 14 '19 at 20:18

(In theory) No, no other strategy will help. In the student-proposing version of the deferred acceptance algorithm, it is a theorem[0] that each student's optimal action is to report her true preference order. It's a dominant strategy, meaning this is optimal regardless of what others submit. This implies that if the student is unmatched when submitting her true preferences, then there is no other submission she could make that would have gotten her matched[1].

Note deferred acceptance still works for weak preference orderings (see [0]), so e.g. here the student is indifferent between all hospitals and prefers them all to being unmatched. The dominant-strategy guarantee of deferred acceptance still holds.

(In practice) In practice, students don't interview or rank all possible hospitals. So a student could likely improve her chances by trying to interview and rank mostly lower-prestige programs where the competition is lower.

[0] e.g. Theorem 8 of the survey by Al Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. https://web.stanford.edu/~alroth/papers/GaleandShapley.revised.IJGT.pdf

[1] I am assuming she prefers any match to being unmatched.

• A citation to this theorem would be nice. – David Richerby Mar 14 '19 at 19:18
• I'm having trouble convincing myself that the known results about perfect matching can be reused directly here. The objective for this student isn't to match with the best hospital (which is what Gale-Shapely optimizes for). It's only to avoid being unmatched - all hospitals are equal. – dranxo Mar 14 '19 at 20:13

The following is not rigorous, but I believe it illustrates why the student's preferences should be true.

The relevant conditions can be reduced to the following. For every program with N slots, a student will be ranked either 1) in the first N slots, 2) in the remaining slots, or 0) not at all. If the student is in group 2, then the outcome is "conditional" - it depends how many of the program's preferred students matched elsewhere.

If we make a table of two programs' grouping for a given student, and designate a definite match with a capital letter, and a conditional match with a lower case letter, we get the following:

If student ranks A over B

B\A 1   2   0
1   A   aB  B
2   A   ab  b
0   A   a   -


If student ranks B over A

B\A 1   2   0
1   B   B   B
2   bA  ba  b
0   A   a   -


You can see that each table has the same number of matches and the same number of conditional matches. The only difference is that 4 of the 9 scenarios end with a preference for the program ranked highest.

Even if you have an oracle and can predict in which programs a conditional acceptance will succeed or fail, there is no advantage to switching order. If you change all the conditionals to either guarantees or no-matches, the total chance of matching still does not change. What changes is the chance of getting the school you want. If for example 'a'->'-' and 'b'->'B', then putting B first means matching with A in only 1 of 7 successful scenarios instead of in 3 of 7.

This should generalize to more than 2 programs. If B is the program being ranked higher than the true preference, then A stands for any other program which may rank the student.

The only way to maximize chance of matching is to maximize the number of programs applied for. (And attempt to maximize one's position on each program's ranking of candidates, but that's not a science problem).