User:Mcstrother/match
National Resident Match Program Algorithm[edit]
The National Resident Match Program Algorithm is the algorithm used by the National Resident Match Program to assign medical student applicants to residency programs. It is very similar to the Gale-Shapely algorithm to solve the stable marriage problem.
History[edit]
The National Resident Match Program began in 1952[1] in response to dissatisfaction with the process and results of matching applicants to residency programs via the decentralized, competitive market.[2] From shortly after the first residency programs were formally introduced, the hiring process was "characterized by intense competition among hospitals for (an inadequate supply) of interns."[3] In general, hospitals benefited from filling their positions as early as possible, and applicants benefited from delaying acceptance of positions. The combination of these factors lead to offers being made for positions up to two years in advance. While efforts made to delay the start of the application process were somewhat effective, they ultimately resulted in very short deadlines for responses by applicants, and the opportunities for dissatisfaction on the part of both applicants and hospitals remained.[3]
After its institution in 1952, the NRMP algorithm saw only minor and incremental changes[3] until 1995, when controversy arose regarding whether the program was susceptible to manipulation or unreasonably fair to employers.[4] Indeed, it was shown that in simple cases (i.e. those that exclude couples, second-year programs, and special cases for handling unfilled slots) that had multiple "stable" matchings, the algorithm would return the solution that was best for the hospitals and worst for the applicants.[5][6] It is also susceptible to collusion on the part of hospitals: if hospitals were to organize their preference lists properly, the result returned would be completely unaffected of the preference lists of the residents. As a result, "in the fall of 1995 the Board of Directors of the NRMP comissioned the design of a new algorithm for conducting the match [that would be as favorable as possible to the applicants][7], and a study comparing it to the existing NRMP algorithm."[8] The new algorithm was adopted in May of 1997 and has been in use since its first application in March of 1998,[8] although the study showed that the effects of the change on actual matches is minimal.[9].
Matching Algorithm[edit]
The problem of matching hospitals to residents is a generalization of the stable marriage problem, and as a result the solutions to the two problems are very similar. A simplified version of the algorithm that is used to perform the match is described on the NRMP website. However, this description does not describe the handling of couples (pairs of applicants who wish to stay in the same geographic location), second-year positions, or special handling of residency positions that remain unfilled. The full algorithm is described in Roth, Alvin (September 1999). "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design". The American Economic Review. 89 (4): 756–757. doi:10.1257/aer.89.4.748. PMID 29115787. Retrieved 14 October 2010. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)CS1 maint: date and year (link)
Simple Case: No couples or Secondary Programs[edit]
As in the stable marriage problem, the basic goal in the simple case of the hospitals/residents problem is to match applicants to hospitals so that the final result is "stable". "Stability" in this case means that there is no applicant A and hospital H such that:
- A is unmatched or would prefer to go to H over the hospital he is currently matched with
- H has a free slot or would prefer A over one of the candidates currently filling one of its slots.[10]
It can be shown that for any instance of the problem, there is at least one valid solution[11]. Under the old (pre-1995) NRMP algorithm, which favored hospitals over residents, in certain cases hospitals could benefit from lying about their preferences, but that is no longer true under the new system. In neither system could a resident or coalition of residents benefit from lying about their preferences.[12] (Of course, both systems are susceptible to other forms of collusion. For example, if two applicants apply to the same program, the weaker is still capable of bribing the stronger into ranking the program lower on his list than he would otherwise.)
Under the current system, it is impossible for an applicant to be harmed by including more residency programs at the bottom of his list if those programs are indeed preferable to not being matched.[13]
Couples[edit]
Adding couples who submit joint preference lists as described by the NRMP website complicates the problem significantly. In some cases there exists no stable solution (with stable defined similarly to the way it is in the simple case). In fact, the problem of determining whether there is a stable solution and finding it if it exists has been proven NP-complete.[14] However in initial testing of the algorithm over 5 years of residency match data and a variety of different initial conditions, the current NRMP algorithm always terminated quickly on a stable solution.[15]
By choosing to match as a couple, individuals essentially constrain the number of matches that they consider acceptable, which in the absence of factors outside of the algorithm, makes it much more likely that matching as a couple will result in a less favorable match than a more favorable match compared to matching alone. However couples may benefit from programs viewing applicants who decide to match in couples favorably.[16]
References[edit]
- ^ http://www.nrmp.org/about_nrmp/index.html
- ^ Roth, Alvin (September 1999). "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design". The American Economic Review. 89 (4): 748–780. doi:10.1257/aer.89.4.748. PMID 29115787. Retrieved 14 October 2010.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)CS1 maint: date and year (link) - ^ a b c Gusfield, Dan (1989). "1.1.1". The Stable Marriage Problem: Structure and Algorithms. The MIT Press. pp. 3–4. ISBN 0-262-07118-5.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)- Description of market based on Roth, A.E. (1984). "The evolution of the labor market for medical interns and residents: a case study in game theory". Journal of Political Economy. 92 (6): 991–1016. doi:10.1086/261272.
- ^ Roth "Redesign" 748
- ^ Robinson, Sara (April 2003). "Are Medical Students Meeting Their (Best Possible) Match?" (PDF). SIAM News (3): 36. Retrieved 14 October 2010.
{{cite journal}}: CS1 maint: date and year (link) - ^ Gusfield "Stable Marriage" 64 references Roth, A.E. (1984). "The evolution of the labor market for medical interns and residents: a case study in game theory". Journal of Political Economy. 92 (6): 991–1016. doi:10.1086/261272. as proving that the pre-1995 algorithm is essentially the hospital-optimal algorithm described in Gusfield 39. Gusfield 41 demonstrates that the hospital-optimal algorithm is also applicant-pessimal.
- ^ Roth "Redesign" 751
- ^ a b Roth "Redesign" 749
- ^ Roth "Redesign" 752
- ^ Gusfield "Stable Marriage" 38
- ^ Gusfield "Stable Marriage" 41
- ^ Gusfield "Stable Marriage" 59
- ^ http://tedlab.mit.edu/~dr/nrmp.html
- ^ Gusfield "Stable Marriage" 54, which states that proof of NP completeness comes from Ronn, Eytan (June 1990). "NP-complete stable matching problems". Journal of Algorithms. 11 (2): 285–304. doi:10.1016/0196-6774(90)90007-2. ISSN 0196-6774.
{{cite journal}}: CS1 maint: date and year (link) - ^ Roth "Redesign" 757
- ^ http://www.urmc.rochester.edu/smd/gme/prospective/radiation_oncology/applicant_information/documents/couplesmatchguide.doc