February 2, 1996, Revised 3/11/96
This interim progress report follows examination of information and data concerning the current NRMP algorithm including how it deals with the variety of special situations--"match variations"-- which have been introduced in the last decade or so. The first part of this report discusses these match variations, and their implications for any algorithm designed to produce a stable match. The second part briefly describes how the current NRMP algorithm handles these variations, and what kinds of comparisons and computational experiments will therefore be most helpful in assessing the effect of having applicants propose versus having residency programs propose. The final part of this report outlines the preliminary design of a applicant-proposing algorithm capable of handling the match variations.
The match variations:
The match variations are of two kinds: variations which cause two positions to be linked to one another, and variations which cause the number of positions in a given program to change. In the first category of variations are couples, who submit rank orders of pairs of positions and must be matched to two positions; and applicants who match to 2nd year positions and have supplemental lists which must then be consulted to match them to 1st year positions. In the second category are requests by residency programs to have an even or an odd number of matches, and reversions of unfilled positions from one program to another.
These variations change the character of any matching algorithm designed to produce a stable match. In the absence of these variations, it is possible to produce a stable matching by a `deferred acceptance' algorithm (with either applicants or programs proposing), in which no position-applicant pair has to be considered twice. (If one member of the pair proposes to the other, and is rejected, that pair can never form an instability, because the member who made the rejection will at all subsequent points of the algorithm be matched with a preferable partner.) But this is no longer the case when the match variations are present.
The first category of variations, involving couples and applicants with supplementary lists, can cause an applicant to be removed from a position to which he/she had been tentatively matched without being displaced by another applicant. For a couple, this can happen when one member of a couple is displaced in the usual way, with the consequence that the spouse is now inappropriately matched. The vacancy created by removing the spouse from her/his tentative match creates a potential instability involving the new vacancy and applicants who may have previously been rejected for that position (in the applicant proposing algorithm). (In the program-proposing algorithm, the related problem is that it cannot reliably be determined which offers a couple should reject until both members of the couple have received all the offers which will be forthcoming.) A similar potential instability occurs whenever a supplemental position is vacated by an applicant who has been displaced in his primary (2nd year) position.
In the second category of variations, if a tentatively filled position is deleted from a program (e.g. to give it an even number of matches) then an applicant is unmatched who may have rejected programs he/she would now prefer (in the hospital proposing version). And if an unfilled position reverts from one program to another, then the latter program has a vacancy which it may prefer to fill with an applicant who was earlier rejected (in the applicant proposing version).
Thus any algorithm to produce a stable match (when a stable match exists) in the presence of these match variations must be able to consider potential blocking pairs which can occur, and recur, at multiple points in the algorithm, and take into account that in resolving one instability another may be created. A natural way to proceed in such a case is with algorithms which resolve one instability at a time, and which seek to follow the chain of instabilities to a stable matching. Like the deferred acceptance algorithms, these algorithms have applicant-proposing and program proposing versions. (Any potential instability identifies an applicant and a hospital program. In the applicant proposing version, the applicant proposes down his Rank Order List until the first instability is reached, and this instability is resolved by matching the applicant to the indicated position. In the hospital proposing version the instability to be resolved next is identified by having the hospital propose down its ROL.)
Algorithms of this type are studied in Roth and Vande Vate (1990), along with methods to avoid unnecessary cycling. That paper shows that, in the simplest case, without any match variations, the applicant-proposing instability-chain algorithm, starting with all positions vacant, is equivalent to the applicant- proposing deferred acceptance algorithm, and produces the applicant optimal stable matching. Similarly, the program-proposing version of the chaining algorithm produces the hospital optimal stable match, when begun with all positions vacant. Of course, with the match variations, hospital and applicant optimal stable matchings need not exist (even when stable matchings themselves exist, which is no longer assured). However it appears from the experience of the match that stable matchings will typically exist, and a major focus of this study will be to determine the size of the advantage which the algorithm gives to the side of the market which proposes.
The current NRMP algorithm, and suggested comparisons:
The current NRMP algorithm deals with match variations through a three-stage process. The first stage produces an initial match by ignoring most match variations, using the program-proposing deferred acceptance algorithm, modified to let couples hold on to many offers until a late stage in the algorithm. The match produced in this way will in general not be stable (because of the way it handles couples, and because the other match variations are ignored), so the second phase of the program identifies potential instabilities. The third phase of the program uses an instability- chain algorithm to fix these instabilities and produce a stable match. Interestingly, the subroutines which implement this third stage do not always have hospitals proposing. Instead, couples propose in part of the algorithm designed to fix instabilities due to couples, and applicants also propose in part of the algorithm which fixes instabilities due to supplementary positions. Thus the current NMRP algorithm is a hybrid: it is program-proposing in its first phase (which presumably performs the bulk of the matching), and applicant-proposing in some parts of its third phase.
It therefore seems to me that, in order to get the best understanding of the effects of hospital versus applicant proposing, it will be useful to compare three algorithms: the current NRMP algorithm, an entirely applicant-proposing algorithm, and an entirely program-proposing algorithm (if an efficient program-proposing approach to couples can be devised). It can be anticipated that the current NRMP algorithm will produce a matching intermediate between the other two, but we will need computational experiments to get any idea of the magnitudes of the differences. Comparison of all three algorithms will allow us to see where the current NRMP algorithm falls on the continuum between entirely hospital proposing and entirely applicant proposing algorithms.
In the brief technical notes which follow, I outline a basic design for the applicant-proposing algorithm. At this point I am designing the algorithm both to produce an applicant-proposed match, and to be relatively easy to understand and explain. For this reason, I'm focusing a good deal of attention on the order in which instabilities will be resolved. When it comes time to code and run these algorithms, other considerations (such as coding complexity and run time) may come to the fore, which may call for the redesign of some details of the algorithm.
Outline of the preliminary design of a applicant-proposing algorithm capable of handling the match variations:
The algorithm described here is based on the general design of phase 3 of the current NRMP algorithm, and on the discussion of instability-chaining algorithms in Roth and Vande Vate (1990). As is the case with all preliminary designs, the design may change to resolve problems which appear in the course of implementing it, or to improve its computational efficiency.
The object of the algorithm is to produce a stable matching, by assembling a set A(k) of residency programs and applicants and a tentative matching M(k) with the property that there are no instabilities within the set A(k), and no applicant or program in A(k) is matched to anyone outside of A(k). When the set A(k) has grown to include all applicants and programs, the resulting match is stable, and the algorithm stops.
In the applicant-proposing algorithm, the initial set, A(0), consists of all positions offered in the match, and the initial tentative matching has all positions vacant. The algorithm begins by selecting an applicant S(1) from the set of applicants in the match (this selection to be done either randomly or in some manner to be specified later, after computational experiments) and adding S(1) to A(0) to make the new set A(1).
At any step k of the algorithm, at which a new applicant S(k) has just been added to form the set A(k), the new tentative matching M(k) is formed as follows. First, applicant S(k) (= S(k,1)) proposes down his/her Rank Order List (of programs which also rank S(k)), from the top, until the first program is reached which either has a vacant position or which prefers S(k) to its least preferred current tentative match. In the latter case, this least preferred applicant, S(k,2) is now rejected by the program in question, and this applicant now proposes down her ROL in a similar way, etc. Each applicant S(k,n) displaced in this way similarly proposes down her ROL.
At some point in this process, an applicant S(k,n) may be displaced who is a member of a couple, or who is displaced from a primary position for which she also holds a supplementary position. In either case, a second position now potentially becomes vacant, as the spouse of S(k,n) is withdrawn from his tentative match, or as S(k,n) is withdrawn from her supplementary match. In either case, add the program whose position is left vacant, P(k,n), to the "position stack". If S(k,n) is a couple, then both couple members (S(k,n,a) and S(k,n,b)) now propose down their joint ROL of pairs of positions, and any displaced applicants are handled as above. If S(k,n) had a supplementary position, she now proposes down her ROL, and if she has a supplementary ROL associated with her new tentative match, she proposes down it as well. So both couples and supplementary matches may displace two applicants, and one of these is added to the "applicant stack" while the other is processed.
Applicants propose down their ROL's in this way until the applicant stack is empty. (Applicants continue throughout to be able to propose to programs which may be on the program stack.) A residency program is then selected from the program stack, and all of the applicants in A(k) with whom it might form instabilities--i.e. all of the applicants in A(k) and preferred by the program to its least preferred current tentative match--are added to the applicant stack, which is processed as before, with applicants proposing down their ROL, from the top.
When both the applicant and program stacks are empty, the tentative matching thus produced is M(k): no instabilities for M(k) are contained in the set A(k), and no applicant or program in A(k) is matched by M(k) to anyone outside of A(k). The algorithm is now ready to pick a new applicant S(k+1), and start with the process again, for the set A(k+1).
When all applicants have been included in the set A(k), even-odd requests and program reversions are adjusted, which causes additions to the applicant and program stacks, which are handled as above. When these stacks are empty, the algorithm stops, and the last tentative match becomes final. In the match with no match variations, the applicant and position stacks would always become empty, and the final match would be the applicant optimal stable matching.
When the match variations are present, there is a possibility that at some stages of the algorithm the position stacks would never become empty--i.e. a cycle would occur, in which the same positions reappeared on the stack. So a "loop detector" needs to be added to each stage k. Every loop must involve a position becoming unmatched and made vacant either because a couple or a supplementary assignment has been withdrawn from the position. So a loop detector can work by keeping a log of when positions become unmatched in these ways--i.e. recording which applicant is unmatched from which position, during the processing of some step A(k). If the same pairs appear multiple times, a loop is in progress. How to proceed at this point may depend on the nature of the loop. (It is observed in Roth and Vande Vate (1990) that certain kinds of inessential loops can be rendered harmless by randomizing the order in which applicants and positions are processed from the stacks. Loops due to the non-existence of a stable matching would be more serious, but the prior experience of the NRMP suggests that these may be extremely rare.)
I suspect that the probability of loops can be reduced by having couples and applicants with supplementary lists added to the sets A(k) late in the process, when these sets are already large. This can be checked with computational experiments.
Reference:
Roth, A.E. and Vande Vate, J.H. "Random Paths to Stability in Two-Sided Matching," Econometrica, 58, 1990, 1475-1480.