Figure 2
Allocation: Top Trading Cycle (2018)
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
Matching markets involve the use of a centralized organization to match two disjoint groups A and B where the members of B have preferences over the elements of A and the elements of A have preferences over the elements of B. One widely studied example is the issue of matching medical school graduates (group A) to hospitals (group B) which have residencies that the students must complete to finish their medical school education. The hospitals need the expertise of these students to deliver care to the patients at the hospitals, and the students need additional clinical training opportunities. In the simplest version of this problem there are equal numbers of elements in A and B. Each element of A ranks each element of B without ties (no omissions allowed) and each element of B ranks each element of A without ties.
In some situations however, the preferences only go in one direction - that is, the members of A have preferences for the elements of B but B's members have no "feelings" about who the elements of B get assigned to.
While perhaps not a particularly important example, this example may be one students can relate to. Collection A consists of m people who are the winners of a school mathematics contest - the winners are not "ranked." All winners get the same recognition. The school authorities have purchased m all different prizes (perhaps mathematics books) to give to the winners of the contest. How should the prizes be allocated? Presumably students may prefer one prize to another but the prizes don't care which student wins them! A similar but perhaps more important example is that College X has dorm rooms for the 9 students participating in a research summer camp for high school students in mathematics. Again the students have preferences for the rooms based on what they can read and see in online descriptions of the rooms but the rooms don't care who occupies them. In problems of this kind we will assume the prizes are not things that "spoil" like food. Much of the work on the algorithm we will discuss below was developed to deal with fair allocation of dormitory rooms by colleges to students who apply for on campus housing. (More complications occur when one is assigned both a room (which may vary according to whether it is near a bathroom, the lounge, the elevator, high versus low floor, etc.) and one or more roommates to share the room (or suite of rooms with a shared common space).
One approach might be to just match the students to the prizes at random - that way one might argue that the students can't complain because the allocation scheme is "fair." However, this approach is very inefficient because in some cases each student might get the prize they least preferred.
It turns out that there is a way to proceed from this initial allocation to one which will typically be much better. The basic idea is to take the rankings of the prizes that the students produce and use these to create swaps (trades) between the "players" which will make them happier.
The algorithm often used to solve allocation problems of this kind is known as the Top Trading Cycle algorithm, is due to David Gale and was published in an article by Herbert Scarf and Lloyd Shapley.
Input for the algorithm consists of asking each of the "players" to rank the objects being allocated, including the one they might have at the moment. I will assume that the players give their honest evaluations of the their choices rather than listing choices "strategically" in the hope that this will help them get a room they prefer more. One begins by constructing a directed graph (dot and line segment diagram, with arrows on the line segments) which has as vertices (dots) the players involved in the allocation situation. Now, for each player i insert an edge into a directed graph by putting an arrow (directed line segment) from the vertex which represents i to the player who currently has i's most desired object. Note, this means that one can get a loop, since if i already has his/her most valued thing, we have an edge from vertex i to itself. When a player states which room they like "best" among those currently available (including the one they currently have been assigned), this is called "pointing" to their best choice.
In the table below the names of the 9 players (agents) are 1 to 9 and they are listed in the first column. The ith row entries show, for each of the 9 "prizes," which rank this prize has for the person named i. Thus, for row 2, agent (player) 2 prefers prize 9 most, and prize 2 least, with prize 4 being agent i's 6th favorite choice.
| 1st | 2nd | 3rd | 4th | 5th | 6th | 7th | 8th | 9th | |
| 1 | 5 | 4 | 7 | 8 | 9 | 3 | 2 | 6 | 1 |
| 2 | 9 | 6 | 3 | 8 | 1 | 4 | 7 | 5 | 2 |
| 3 | 5 | 8 | 2 | 3 | 6 | 4 | 9 | 1 | 7 |
| 4 | 2 | 6 | 8 | 3 | 7 | 9 | 1 | 5 | 4 |
| 5 | 4 | 9 | 6 | 5 | 1 | 3 | 7 | 2 | 8 |
| 6 | 8 | 9 | 7 | 5 | 1 | 4 | 2 | 3 | 6 |
| 7 | 3 | 1 | 6 | 9 | 7 | 5 | 8 | 2 | 4 |
| 8 | 5 | 1 | 3 | 2 | 9 | 8 | 4 | 6 | 7 |
| 9 | 4 | 6 | 8 | 1 | 3 | 7 | 2 | 9 | 5 |
Rather than give a very abstract description of how Top Trading Cycles works, I will use the example above to describe how the algorithm works, and then hopefully it will be apparent how it works in general.
The Top Trading Cycle algorithm is carried out in a series of "rounds" where the players who have not already been given a "lasting" assignment based on the trading state which is "honestly" their favorite for the rooms currently available. So, we begin by having each of the players point to the room which they would most like to have. The results of this "procedure" are shown in Figure 2. For example, where will player 6 point? Since Room 8 is in the first column of the table above, player 6 would most like to be in Room 8. Thus, this is indicated by creating a directed line segment from the dot labeled 6 in Figure 2 to the dot labeled 8 in that diagram. While it might happen that a player would point to his/her own room, thereby creating a directed "loop" (cycle) in the directed graph being generated, this does not happen (initially) for the Table in Figure 1. The completed result of carrying out the pointing process by each of the 9 players is shown in the directed graph (digraph for short) in Figure 2. Note there are 9 players and hence exactly 9 directed line segments (edges) in Figure 2, the result of one edge for each of the players carrying out "pointing." The fact that three different players like room 5 best is reflected by the fact that there are three edges pointing into vertex 5 in Figure 2. The fact that rooms 1, 6, and 7 are not the favorite of any player is reflected in the digraph by the fact that no arrow points into these vertices and by the fact that 1, 6, and 7 don't appear in the first column of the table in Figure 1.
What is important is that there must be one or more directed circuits (cycles) in the directed graph generated by this process. A directed cycle C is a "tour" of some vertices and edges, where one can start at any vertex can get back to where one started passing through distinct vertices. The first round is completed by giving the players who are in a directed cycle the room they pointed to as their "final" assignment. In this example as part of Round 1, player 2 gets Room 9, player 4 gets Room 2 and player 9 gets Room 4.
We will remove these three players from consideration and in the next round only players, 1, 3, 5, 6, 7, and 8 participate.
Round 2 will work in an identical way but active players can't point to rooms which have been taken out of consideration in prior rounds. Figure 3 shows the results of the pointing process for the remaining 6 players. When player 5 is asked to point to the room he wants, he can no longer point towards his favorite room 4 because it has been assigned, and for the same reason can't point to Room 9. Hence, player 5 points to his/her 3rd favorite room, Room 6. This time (see Figure 3) we have a directed cycle involving players 5, 6 and 8.
Because we have the directed cycle 5, 6, 8, 5 (which could also be written 8, 5, 6, 8 or 6, 8, 5, 6) we assign player 5 to Room 6, player 6 to Room 8, and player 8 to Room 5. So after two Round 3 we have rooms 2, 4, 5, 6, 8 and 9 out of consideration for the remaining three players.
Round 3 is carried out resulting in the pointing digraph in Figure 4
In Figure 4 the only directed cycle is the directed self-loop involving 3. So player 3, currently occupying Room 3 is assigned Room 3. This is not his favorite room, it is his 4th favorite, but given the preferences of the other players he winds up with the room that he is in!
For Round 4, the only players left are players 1 and 7. Since player 1 will point to Room 7 since choices 5 and 4 are not available, and player 7 will point to Room 1, since Room 3 is no longer available now player 1 will be assigned Room 7 and Player 7 will be assigned Room 1. (The pointing digraph not drawn for this round.)
| Room number | |
| Player 1 | 7 (3rd best) |
| Player 2 | 9 (favorite) |
| Player 3 | 3 (4th best) |
| Player 4 | 2 (favorite) |
| Player 5 | 6 (3rd best) |
| Player 6 | 8 (favorite) |
| Player 7 | 1 (2nd best) |
| Player 8 | 5 (favorite) |
| Player 9 | 4 (favorite) |
As you can see in Figure 5, 6 of the 9 players get rooms which are their favorite choices. Though the students ranked all of the rooms, notice that we did not have to look all that deeply into their rankings to get an "assignment."
So what properties does the Top Trading Cycle algorithm obey?
a. There is no incentive for the students to produce rankings of the rooms that are not honest if they know that the Top Trading Cycles algorithm will be used to decide the room allocation. To lie about one's preferences will mean one can only do worse.
b. No group of students can cooperate with each other in trying to, as a group, get a "better deal" for this group. In the language of "mechanism design" (the study of procedures that encourage honesty on the part of the participants) the Top Trading Cycles mechanism is "truthful," in the sense just mentioned. This is a result proven by Alvin Roth, who won the Nobel Memorial Prize in Economics for his work on designing "practical" systems for 2-sided markets and related mechanism design problems.
While the example involving matching students to rooms is truly "one sided" because rooms don't have preferences for students, there are examples where the situation regarding the two groups A and B (framework developed at the start) is more complex. For example, consider the situation which occurs in school choice problems. School choice refers to the "policy" of not requiring students to go to specific public schools (usually the one "closest" to where the student lives) but allowing students to at least apply to whatever public school they wish. Some believe this will encourage schools to "compete" with each other and, thus, improve public education for all students. While the students have preferences for the schools they want to attend, the schools, while they may not be allowed to "rank" the students, sometimes have "priorities" for which students they admit. Sometimes these priorities are related to the students applying via parental "convenience." For example, if a student is part of a family which has a sibling who attends school X, the school might be able to give "priority" to students who apply in this situation.
For school choice problems one can use the Top Trading Cycles algorithm or the Deferred Acceptance algorithm of Gale and Shapley. The trade-offs between the two system are fascinating and complex, and variants of each have been tried in actual school choice problems. The major fairness issues concern stability, envy, truthfulness, and efficiency (Pareto optimality). In this domain, modeling questions involving fairness have resulted in improved systems of solving allocation and school choice problems as well as fascinating new mathematics. Much of this mathematics is accessible in K-11 classrooms.
References
A good place to begin for the topics above are Wikipedia articles related to the topic.
Abdulkadiroglu A, Sönmez T. School choice: A mechanism design approach. American economic review. 2003 Jun;93(3):729-47.
Abdulkadirogu, Atila, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. "The Boston public school match." American Economic Review 95, no. 2 (2005): 368-371.
Abdulkadiroglu A, Pathak Parag A, Roth Alvin E. The new york city high school match. American Economic Review. 2005 May;95(2):364-7.
D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9–14, 1962.
Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press.
Roth, Alvin E., and Marilda Sotomayor. "Two-sided matching." Handbook of game theory with economic applications 1 (1992): 485-541.
Shapley, Lloyd and Scarf, Herbert (1974). "On cores and indivisibility". Journal of Mathematical Economics. 1: 23