The Matching Algorithm
Description of the Algorithm
The matching algorithm uses the preferences stated on the Rank Order Lists submitted by applicants and programs to place individuals into positions.
The algorithm starts with an attempt to place an applicant into the program that is most preferred on the applicant's list. If the applicant cannot be matched to this first choice program, an attempt is then made to place the applicant into the second choice program, and so on, until the applicant obtains a tentative match, or all the applicant's choices have been exhausted.
An applicant can be tentatively matched to a program in this algorithm if the program also ranks the applicant on its Rank Order List, and either:
- the program has an unfilled position available for the applicant. In this case there is room in the program to make a tentative match between the applicant and program.
- the program does not have an unfilled position, but the applicant is more preferred by the program to another applicant who is currently tentatively matched to the program. In this case the applicant who is the least preferred current match in the program is removed from the program to make room for a tentative match with the more preferred applicant.
Matches are referred to as tentative because an applicant who is matched to a program at one point in the process may later be removed from the program, to make room for an applicant more preferred by the program, as described in the second case above. When an applicant is removed from a previous tentative match, an attempt is then made to re-match this applicant, starting from the top of this applicant's list.
This process is carried out for all applicants, until each applicant has either been tentatively matched to the most preferred choice possible, or all choices submitted by the applicant have been exhausted. When all applicants have been considered, the matching algorithm is complete and tentative matches become final.
In summary, each applicant's Rank Order List is traversed "downwards", from most preferred program to least preferred, until the first program is reached at which the applicant can be tentatively matched, or until the applicant's list of choices is exhausted. Each program accepts applicants "upwards" on its Rank Order List, continually removing less preferred matches in favor of more preferred applicants, until the program is matched to the most preferred applicants who wish to be matched to the program.
An example of the matching process involving three applicants and three programs is described below.
The Rank Order Lists submitted by programs and applicants in this example are as follows:
Programs' Rank Order Lists
|Program A||Program B||Program C|
|(2 Positions)||(1 Position)||(1 Position)|
|1. Charles||1. Baker||1. Baker|
|2. Baker||2. Charles|
|3. Able||3. Able|
Applicants' Rank Order Lists
|1. Program B||1. Program A||1. Program B|
|2. Program A||2. Program B||2. Program A|
|3. Program C|
The actual matching is done on a computer. However, the matching algorithm itself could be completed as effectively by hand; the computer serves only to expedite the process. The computer is set up to process the lists in the following manner.
It first attempts to place Able into his first choice, Program B. Since Program B has an available position, Able is tentatively matched to Program B. Next an attempt is made to place Baker into Program A. Since Program A has an available position, Baker is tentatively matched to Program A.
The computer then attempts to place Charles into Program B. Program B's position is currently filled, but Program B prefers Charles to its current match with Able. Able is therefore removed from Program B, and Charles is tentatively matched into Program B.
Since Able has just been removed from a tentative match with Program B, an attempt is made to re-match Able. The computer first tries to place Able into Program B; however, this is unsuccessful because Program B's position is now filled with Charles, who is preferred by Program B. Next an attempt is made to place Able into his second choice, Program A. Since Program A has a second available position, Able is tentatively matched to Program A.
The matching algorithm is now complete as each applicant's list has been processed, and each applicant is tentatively matched to the most preferred choice possible. Tentative matches now become final.
Note that in the matching algorithm, no applicant or program can be forced into a final match until all applicant Rank Order Lists have been considered for the best possible tentative matches.
The following information will help resolve some common misunderstandings associated with the matching process.
The Match is a computerized assignment of applicants to programs that will interfere with or limit the freedom of choice of applicants and programs.
The Match does not involve an arbitrary or contrived assignment of applicants to programs. A program cannot be matched with an applicant who is not listed on the program's Rank Order List; similarly, an applicant cannot be matched with a program that is not listed on the applicant's Rank Order List.
Applicants and programs are free to obtain information about each other and to rank their choices according to their preferences without pressure and undue haste. The matching algorithm simply follows the instructions embodied in the Rank Order Lists to facilitate the placement of applicants into positions. However, the Match removes the time pressures from the traditional process of making offers, and accepting or rejecting offers.
The Match does not have to be computerized. The matching algorithm itself could be completed as effectively by hand. A computer system is used only to facilitate and ensure the accuracy of the matching process.
If a program wishes to recruit a particular distribution of applicants based on specific applicant characteristics, the program can attempt to do this within the matching process by dividing its available positions into separate types and submitting separate Rank Order Lists for each type of position. Furthermore, the matching algorithm can accommodate other special requirements, such as the matching of applicants as "couples", and the reversion of unfilled positions from one program to another in order to facilitate the filling of available positions.
To ensure a match, an applicant should rank those programs which seem to prefer the applicant higher on the Rank Order List than other programs which the applicant prefers, but which may prefer other applicants. Ranking these "likely" programs lower on the list may jeopardize the applicant's chance of matching, because the applicant may not be able to obtain a position at a more preferred but "less likely" program that he or she ranked higher. (The same logic applies to programs in making out their Rank Order Lists.)
Applicants and programs should make out their Rank Order Lists based on their true preferences. The likelihood of being able to obtain a position at a program, or being able to attract an applicant, should not be considered when listing preferences on a Rank Order List.
First consider the issue from the applicants' perspective. In the matching process, attempts are made to place an applicant into a program in sequence according to the applicant's stated preferences, as discussed in the illustrative example above. When attempting to place an applicant into a particular program, the only reasons an applicant will not match to the program are either the program did not rank the applicant, or the program has filled all its positions with more desirable applicants. The fact that an applicant could not match to a preferred program does not affect the applicant's chances of matching to the next program on the applicant's list. Similarly, ranking additional less preferred choices will not jeopardize or affect the applicant's chances of matching to a more preferred program.
For example, suppose Program A has one position. Both Applicants X and Y feel they have a very good chance of obtaining a position at Program A. However both in fact prefer other programs, Programs C and D, where they may be less desirable. Consider the Rank Order Lists below:
|Program A (1 Position)||Applicant Y|
|1. Applicant Y||1. Program C|
|2. Applicant X||2. Program D|
|3. Program A|
Applicant Y has listed programs according to his true preferences. Applicant X has listed programs according to likelihood of being able to obtain a position.
In the matching algorithm, Applicant X will first be tentatively matched with Program A. Next, attempts will be made to place Applicant Y into Program C, and if that is unsuccessful, into Program D. If Applicant Y cannot match with Programs C or D, an attempt will be made to place Applicant Y into Program A. Since Program A prefers Applicant Y to its current tentative match with Applicant X, Applicant X is removed from Program A and Applicant Y is matched with Program A.
Thus Applicant Y has not jeopardized his chances of matching with Program A by putting that program lower on his list. Similarly, Applicant X has not increased her chances of matching to Program A by putting that program higher on her list.
Similarly for programs, when an applicant is tentatively matched to a program, the program will retain that applicant until a more preferred applicant can be placed into the program. Only then will the program reject the less preferred applicant, and only then will that applicant attempt to match to a program lower on his or her list. A program cannot be bypassed by a less-preferred program on an applicant's Rank Order List, regardless of how the two programs ranked the applicant.
In the Match, it is important for applicants and programs to know how they will be ranked by each other.
As shown in the previous example, applicants and programs should make out their Rank Order Lists based on true preferences, regardless of how they will be ranked by other participants. For example, suppose Program A knows that Applicant Y is not going to rank the program first. If Program A feels Applicant Y is most preferred, it does not hurt Program A to put Applicant Y first. If Applicant Y cannot be matched with Programs C or D, Applicant Y will be placed into Program A. If Applicant Y is matched with either Program C or D, Program A's chances of matching with Applicant X have not been reduced because it ranked Applicant Y first. However, if Program A lists Applicant X first because it knows Applicant X is going to list Program A first, all that will be accomplished is that Program A will lose the opportunity of matching with Applicant Y, who it feels is in fact a more preferred applicant.
As a further extension of this logic, applicants and programs need not submit to inappropriate pressures in making out their Rank Order Lists (e.g., "I'll rank you high only if you rank me high"). Applicants and programs will not know how they are actually ranked by other parties. If, for example, a program has made this statement to an applicant, the applicant is in fact not disadvantaged by making out her list according to her true preferences. If the applicant matches to this program, the program may continue to think the applicant ranked it first, regardless of where she actually ranked the program. However, if the applicant matches to another program, the first program may not be pleased, but the applicant will in fact have received a position with a more preferred program. Therefore, trying to pressure applicants or programs into inappropriately high rankings does not necessarily help in the Match.
Applicants or programs can subvert the process or "beat the system" based on how they make out their Rank Order Lists. Conversely, some applicants or programs may be treated unfairly as a result of how other applicants or programs make out their lists.
The best strategy for applicants and programs to follow is to make out their lists based on their true preferences. Any other strategy may result in a worse result for the applicant or program that did not follow this "true preferences" strategy. For example, consider Applicant X in the previous example. If Program A in fact lists Applicant X first, Applicant X will match to Program A, because she has listed that program as her first choice. She will not match to Program C or D, which she in fact prefers, even if either of those programs prefers her to other applicants. Thus Applicant X will obtain a position with a program she prefers less because she has not made out her list according to her true preferences.