# National Resident Matching Program

Das National Resident Matching Program (NRMP), auch The Match genannt, ist eine in den Vereinigten Staaten ansässige, private nichtstaatliche Non-Profit-Organisation. Diese wurde 1952 gegründet, um Medizinstudenten einem Facharztausbildungsprogramm an Amerikanischen Universitätskliniken zuzuteilen. Zusätzlich zum jährlichen Main Residency Match, das mehr als 43.000 Bewerber und 31.000 Stellen umfasst, führt das NRMP Stipendienzuordnungen für mehr als 60 Unterspezialisierungen mittels seines Specialties Matching Service (SMS) durch.
Das NRMP wird von einem Direktorium, bestehend aus Dekanen medizinischer Fakultäten, Leitern der Unikliniken, Leitern medizinischer Ausbildungsprogramme und einem Mitglied der Öffentlichkeit, gefördert.
NRMP International, eine Tochtergesellschaft des National Resident Matching Program, wurde 2010 gegründet, um medizinische Matching-Dienstleistungen auch außerhalb der USA und Kanada anzubieten.

## Geschichte

Kurz nachdem die ersten Facharztausbildungsprogramme in den 1920er Jahren formell eingeführt wurden, war der Einstellungsprozess „geprägt von einem intensiven Wettbewerb zwischen den Krankenhäusern um (ein unzureichendes Angebot der) Fachärzte“. Im Allgemeinen profitierten die Krankenhäuser davon, ihre Stellen so früh wie möglich zu besetzen, und die Bewerber profitierten davon, die Zusage für Stellen hinauszuzögern. Die Kombination dieser Faktoren führte dazu, dass Angebote für Stellen bis zu zwei Jahre vor dem Beginn der postgradualen Ausbildung gemacht wurden.
1945 beschlossen die medizinischen Fakultäten, vor einem bestimmten Datum keine Zeugnisse zu veröffentlichen oder das Schreiben von Empfehlungsschreiben zu erlauben. Auf diese Weise schafften sie es, das Datum der Platzwahl für die Facharztausbildung in das vierte Studienjahr zurückzuverlegen. Jedoch nahm der Wettbewerb um Fachärzte lediglich eine andere Form an. Die Programme begannen, ihre Angebote mit einer zeitlichen Begrenzung, in der man eine Antwort senden kann, hinauszuschicken. Diese Grenze wurde zusehends von 10 Tagen im Jahr 1945 auf weniger als 12 Stunden im Jahr 1950 gesenkt. Die Studierenden bekamen „explodierende“ Angebote, die eine Entscheidung über ihre Ausbildung forderten, bevor aufgelegt wurde.
In den frühen 1950er Jahren untersuchte das National Interassociation Committee on Internships (NICI) bestehende Matching-Pläne und wählte den Boston Pool Plan, der zu dieser Zeit von Programmen in Bostons Umgebung genutzt wurde, als Modell für einen Testlauf eines neuen zentralisierten Systems. Im Oktober 1951 bildeten Studentenvertreter von 79 medizinischen Fakultäten das National Student Internship Committee (NSIC), um die Ergebnisse des NICI-Test-Matchverfahrens zu diskutieren und einen NICI-Vorschlag zu erwägen, den Boston Pool Plan auf nationaler Ebene zu replizieren. Das NSCI beantragte eine Modifikation des Algorithmus, sodass die Bewerber gleichmäßiger dargestellt werden. Der modifizierte Algorithmus wurde eingeführt und im ersten Match am 15. April 1952 verwendet. Dieser Match war ein Erfolg, weshalb das NICI die Einrichtung einer Organisation zur Verwaltung und Überwachung des Matching-Vorgangs empfahl. Diese Organisation, die als das National Intern Matching Program (NIMP) bekannt ist, wurde am 7. Januar 1953 gegründet.
Aufgrund von Bedenken darüber, dass der Matching-Prozess die Krankenhäuser gegenüber den Studenten bevorzuge, schlugen Studenten 1951 eine Modifikation des Algorithmus vor. Die Studenten waren der Meinung, dass der Algorithmus ihnen den Anreiz gebe, ihre wahren Präferenzen zu verschleiern. Eine Publikation von David Gale und Lloyd Shapley im Jahr 1962 stellte fest, dass es immer eine stabile Lösung gibt, wenn Hochschulen mit Studenten gematcht werden, aber es möglich sei, Hochschulen als Gruppe gegenüber Bewerbern als Gruppe zu bevorzugen (und umgekehrt). Das bedeutet, Gale und Shapley fanden heraus, dass es einen für Hochschulen optimalen stabilen Match und einen für Studenten optimalen stabilen Match gibt. Lloyd Shapley gewann zusammen mit Alvin Roth im Jahr 2012 den Nobelpreis für Wirtschaftswissenschaften für ihre Arbeit an stabilen Allokationen.
Es entstand eine Debatte darüber, ob das Matching-Programm manipulationsanfällig oder für Programme unangemessen fair war. In der Tat wurde gezeigt, dass der Algorithmus in einfachen Fällen (d. h. solche, die Paare, Zweitjahresprogramme und Spezialfälle für den Umgang mit nicht gefüllten Plätzen ausschließen), die mehrere „stabile“ Matchings hatten, eine Lösung zurückgab, die die Präferenzen von Programmen denen der Bewerber vorzog. Eine Korrespondenz im New England Journal of Medicine im Jahr 1981 erkannte, dass der verwendete Algorithmus für einzelne Bewerber programmoptimal war.
Spätere Forscher, wie Marilda Sotomayor 1983, Alvin Roth 1984 und Klaus et al. 2007, stellten fest, dass, wenn Paare gemeinsam zugeteilt werden dürfen, es möglicherweise kein stabiles Matching gibt.
Der NRMP-Algorithmus erfuhr nach seiner Einführung 1952 nur geringfügige und inkrementelle Veränderungen. Im Herbst 1995 gab der Verwaltungsrat des NRMP jedoch eine vorläufige Forschungsstudie zur Bewertung des aktuellen Algorithmus in Auftrag, sowie eine Studie, die einen neuen Algorithmus mit dem bestehenden vergleicht. Auch Empfehlungen zu Änderungen, die in seiner Funktionsweise und Beschreibung zu berücksichtigen sind, sollten erforscht werden. Im Mai 1997 wurde ein neuer Algorithmus zur Auswahl der Bewerber angewendet, der seit seiner ersten Anwendung im März 1998 in Verwendung ist. Und das obwohl die Studie zeigte, dass der Nettoeffekt der Änderung auf die tatsächlichen Matches minimal war.

## Matching-Algorithmus

Das Matching von Bewerbern mit Programmen ist eine Generalisierung des Stable Marriage Problems; daher sind die Lösungen sehr ähnlich. Eine vereinfachte Version des Algorithmus, der zur Durchführung des Matching-Prozesses verwendet wird, ist nachfolgend und auf der NRMP-Website beschrieben. Diese Beschreibung beinhaltet jedoch nicht den Umgang mit Paaren (Paare von Bewerbern, die gemeinsam an einem Match teilnehmen, um vielleicht am gleichen geografischen Ort zu bleiben), Zweitjahrespositionen oder einen besonderen Umgang mit Facharztstellen, die nicht besetzt sind. Der vollständige Algorithmus wird in Alvin Roth, Elliott Peranson (September 1999) beschrieben.

### Input

Der Bewerbungsprozess für die Facharztausbildung beginnt vor der Eröffnung des Main Residency Match im September. Bewerbungen werden normalerweise über den Electronic Residency Application Service (ERAS), einem Dienst der Association of American Medical Colleges, an die Programme weitergeleitet. Nachdem sich die Bewerber für Programme beworben haben, prüfen die Programme die Bewerbungen und laden ausgewählte Bewerber zu Interviews ein. Die Interviews finden zwischen Oktober und Februar statt. Nach Ablauf des Interviewzeitraums erstellen Programme und Bewerber jeweils „Ranglisten“, die sie beim NRMP einreichen. Die Programme listen alle Bewerber, die sie ausbilden möchten, geordnet in der Reihenfolge von den am meisten zu den am wenigsten bevorzugten. Entsprechend ordnen die Bewerber die Programme ein, in denen sie ausgebildet werden möchten. Für Bewerber, die als Paar gematcht werden möchten, enthalten die Ranglisten Paare von ausgewählten Programmen, die simultan von dem Matching-Algorithmus berücksichtigt werden. Die Ranglisten der Bewerber können eine Kombination kategorischer Programme enthalten (Ausbildung, die 3–5 Jahre dauert und im ersten Postgraduiertenjahr beginnt); vorbereitende Programme (Ausbildung, die ein Jahr dauert und im ersten Postgraduiertenjahr beginnt); oder fortgeschrittene Programme (Ausbildung, die 3–4 Jahre dauert und nach einem oder mehreren Jahren vorbereitender Ausbildung beginnt). Für fortgeschrittene Programme auf der Rangliste können Bewerber eine ergänzende Liste vorbereitender Programme anfügen, um somit einem vollständigen Ausbildungskurs zugeteilt zu werden.

### Einfacher Fall

Der Matching-Prozess beginnt mit dem Versuch, einen Bewerber dem Programm zu matchen, das er laut seiner Rangliste am meisten präferiert. Kann der Bewerber nicht dem Programm seiner ersten Wahl zugeteilt werden, so wird versucht, den Bewerber in dem Programm seiner zweiten Wahl unterzubringen, und so weiter, bis der Bewerber vorläufig einem Programm zugeteilt ist, das eine offene Stelle hat und diesen Bewerber bevorzugt oder alle Auswahlmöglichkeiten aus der Rangliste des Bewerbers erschöpft sind. Dieser Prozess wird für alle Bewerber durchgeführt, bis jeder Bewerber entweder vorläufig seiner am meisten präferierten möglichen Wahl zugeordnet wurde oder alle Auswahlmöglichkeiten aller Bewerber ausgeschöpft wurden. Anschließend werden vorläufige Matches endgültig.
Um zu verstehen, wie der aktuelle NRMP-Algorithmus funktioniert, ist es hilfreich, zunächst den einfacheren Fall, in dem es keine Paare oder sekundären Programme gibt, zu betrachten.
Wie auch beim Stable Marriage Problem, besteht das grundlegende Ziel darin, Bewerber mit Programmen zu matchen, sodass die Ergebnisse „stabil“ sind. „Stabilität“ bedeutet in diesem Fall, dass es keinen Bewerber A und kein Programm P gibt, sodass beide der folgenden Aussagen zutreffen:
* A ist keinem Programm zugeteilt oder würde es vorziehen, im Programm P zu sein, als dem Programm, mit dem A gematcht wurde
* P hat einen freien Platz oder würde A einem anderen Bewerber vorziehen, der dem Programm zugeteilt wurde.
Es ist möglich zu zeigen, dass es für jedes Beispiel des Problems mindestens eine gültige Lösung gibt. Nach dem alten (vor 1995) NRMP-Algorithmus, der die Präferenzen der Programme gegenüber den Bewerbern bevorzugte, konnten Programme in bestimmten Fällen davon profitieren, über ihre Präferenzen zu lügen. Unter dem aktuellen Algorithmus gilt dies nicht mehr. Weder Bewerber noch Programme können davon profitieren, indem sie ihre Präferenzen unwahrheitsgemäß angeben, selbst wenn sie über die Präferenzen aller perfekt informiert sind.
Nach dem derzeitigen System ist es auch nicht möglich, dass sich ein Bewerber schlechter stellt, indem er mehr Facharztausbildungsprogramme am Ende einer Liste aufnimmt, wenn diese Programme tatsächlich gegenüber einer Nicht-Zuteilung bevorzugt werden.

### Paare

Die Ranglisten von Paaren werden simultan von dem Matching-Algorithmus verarbeitet, wodurch das Problem komplizierter wird. In einigen Fällen gibt es keine stabile Lösung (stabil wie im einfachen Fall definiert). In der Tat hat sich das Problem der Frage, ob es eine stabile Lösung gibt und die Bestimmung derer Existenz, als NP-vollständig erwiesen. Auch wenn es im NRMP-Algorithmus keine Randomisierung gibt, so liefert er immer die gleiche Ausgabe, wenn er genau die gleiche Eingabe erhält. So können unterschiedliche Ergebnisse durch Änderung trivialer Merkmale der Daten, wie zum Beispiel die Reihenfolge in der Bewerber und Programme verarbeitet werden sollen, erzeugt werden. Beim ersten Test des Algorithmus mit Facharzt-Matching-Daten aus 5 Jahren und einer Vielzahl unterschiedlicher Anfangsbedingungen endete der aktuelle NRMP-Algorithmus jedoch immer schnell in einer stabilen Lösung. Tests zeigten auch, dass „keine der [trivialen] Sequenzierungsentscheidungen einen großen oder systematischen Effekt auf das Matching hatte“ – die maximale Anzahl an Bewerbern, die jemals in einem einzigen Durchgang betroffen waren, war 12 von 22.938.
Nachdem die Ranglisten der Programme festgelegt wurden, besteht für einen Bewerber in der Regel keine Möglichkeit, einer besseren Position zugeteilt zu werden, wenn er sich entschließt, als Teil eines Paares gematcht zu werden. Wenn zum Beispiel ein sehr starker Bewerber und ein sehr schwacher Bewerber sich als Paar matchen lassen, gibt es im Algorithmus keinen Mechanismus, der es dem stärkeren Bewerber ermöglicht, die Attraktivität des schwächeren Bewerbers in irgendeiner Weise zu verbessern. Wenn die Programme vor der Bearbeitung des Matching-Algorithmus natürlich wissen, dass der stärkere und der schwächere Bewerber als Paar am Match teilnehmen, steht es ihnen frei, ihre Listen entsprechend zu ändern. Dies könnte sich wiederum auf das Endergebnis auswirken.

## Versagen beim Matching

Es ist möglich, dass ein Bewerber mit keinem Programm gematcht wird. Bis zum Main Residency Match im Jahr 2010 durchliefen Bewerber, die keine Stelle erhalten hatten, einen Prozess namens Scramble. Um 12:00 Uhr am Montag der Match Week teilte das NRMP den Bewerbern mit, ob sie einem Programm zugeteilt wurden (aber ohne den Namen des Programms bekannt zu geben) und veröffentlichte eine Liste der unbesetzten Programme. Die Bewerber bewarben sich dann massenweise auf Programme mit offenen Positionen, wobei sie häufig ihre bevorzugte Spezialisierung in diesem Prozess wechseln mussten. Der Scramble galt weithin als chaotisch, desorganisiert und wenig transparent. Der Scramble endete am Match Day, dem Donnerstag der Match Week. Die meisten Positionen wurden innerhalb der ersten Stunden und beinahe alle in den ersten 48 Stunden besetzt. Scrambling war extrem hart umkämpft: Im Jahr 2008 konkurrierten rund 10.600 Bewerber, von denen viele im Ausland ausgebildet wurden, um nur 1.392 Facharztstellen.
Nach dem Main Residency Match im Jahr 2010 wurde das Scramble durch das Supplemental Offer and Acceptance Program oder SOAP ersetzt. Im SOAP werden, durch eine Reihe von Durchgängen, nicht zugeteilten Bewerbern Stellen in unbesetzten Programmen angeboten, wodurch eine systematische Möglichkeit für Bewerber geschaffen wird, Ausbildungsplätze ohne das Chaos des Scramble zu finden. Im SOAP werden alle Termine über das NRMP gemacht (im Gegensatz zum Scramble ist kein direktes Matching möglich). Daten über nicht gematchte Bewerber und unbesetzte Programme werden am Montag der Match Week zur gleichen Zeit veröffentlicht. Der Match Day ist jetzt Freitag der Match Week.

## Internationale Medizin-Absolventen

Um am NRMP teilnehmen zu können, muss ein internationaler Medizin-Absolvent die Anforderungen für die ECFMG-Zertifizierung bis zur „Rank Order List Certification Deadline“ im Februar des Matching-Jahres erfüllen (nicht erforderlich für Medizin-Absolventen kanadischer Medizinhochschulen, die in den USA nicht als internationale Medizin-Absolventen gelten).
Um eine ECFMG-Zertifizierung zu erhalten, müssen internationale Medizin-Absolventen:
* die notwendige Punktzahl bei USMLE Step 1, USMLE Step 2 Clinical Knowledge und USMLE Step 2 Clinical Skills erreichen.
* ein medizinisches Diplom über eine medizinische Ausbildung erhalten, das an einer, im International Medical Education Directory (IMED) registrierten Institution, abgelegt wurde.
Im Vergleich dazu, sind Studenten und Absolventen von medizinischen Fakultäten in den Vereinigten Staaten an die Abschlussvoraussetzungen der einzelnen Hochschulen gebunden. Sowohl in den USA als auch im Ausland ausgebildete Bewerber können an dem NRMP teilnehmen, während sie ihr letztes Jahr an der medizinischen Fakultät absolvieren, bevor sie ihr medizinisches Diplom erwerben.

## Gerichtsverfahren

Im Jahr 2002 haben 16 Anwaltskanzleien im Namen von 3 Fachärzten eine Klage eingereicht, um alle Fachärzte, die durch das NRMP gematcht werden, zu vertreten. Die Kläger legten einen Fall vor, in dem sie darlegen wollten, dass das NRMP mit anderen nationalen medizinischen Organisationen, Organisationen für medizinische Ausbildung und mit Institutionen, die die Facharztausbildung fördern, zusammenarbeitet, um die Löhne der Fachärzte zu senken, was gegen die Kartellgesetzgebung der Vereinigten Staaten verstößt.
Im Jahr 2004, nach einer Lobbyarbeit der American Medical Colleges und der American Hospital Association, wurde eine Zusatzklausel, die dem NRMP eine spezifische Immunität gewährte, zu einem Rentengesetz hinzugefügt, das von Präsident George W. Bush unterzeichnet wurde. Die Verordnung wurde von den Senatoren Edward M. Kennedy, Demokrat von Massachusetts, und Judd Gregg, Republikaner von New Hampshire, unterstützt. Anschließend wies ein Bundesbezirksgericht den Fall zurück.

## Implementierung in Softwarepaketen

* R: Der im NRMP verwendete Roth-Peranson-Algorithmus ist als Teil des Paketes matchingMarkets implementiert.
* API: Die MatchingTools-API stellt den Roth-Peranson-Algorithmus für das im NRMP verwendete Matching-Problem mit Paaren über eine freie Programmierschnittstelle zur Verfügung.