Practicing the Deferred Acceptance Algorithm for 2-Sided Matchings
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/
Imagine that 8 law students are applying to 8 law firms. Each student is willing to have a job with one of these firms and each firm wants to select one of these students. What follows is an activity based on an example due to Dan Gusfield and Robert Irving (The Stable Marriage Problem, MIT Press, 1989).
Information about the preferences of the students for the firms and the firms for the students is given in the tables below:
| Student | ||||||||
| 1 | 5 | 7 | 1 | 2 | 6 | 8 | 4 | 3 |
| 2 | 2 | 3 | 7 | 5 | 4 | 1 | 8 | 6 |
| 3 | 8 | 5 | 1 | 4 | 6 | 2 | 3 | 7 |
| 4 | 3 | 2 | 7 | 4 | 1 | 6 | 8 | 5 |
| 5 | 7 | 2 | 5 | 1 | 3 | 6 | 8 | 4 |
| 6 | 1 | 6 | 7 | 5 | 8 | 4 | 2 | 3 |
| 7 | 2 | 5 | 7 | 6 | 3 | 4 | 8 | 1 |
| 8 | 3 | 8 | 4 | 5 | 7 | 2 | 6 | 1 |
For example, Student 6 likes Law firm 1 best, and Law firm 3 least, that is, Law firm 3 is ranked 8th.
| Firm | ||||||||
| 1 | 5 | 3 | 7 | 6 | 1 | 2 | 8 | 4 |
| 2 | 8 | 6 | 3 | 5 | 7 | 2 | 1 | 4 |
| 3 | 1 | 5 | 6 | 2 | 4 | 8 | 7 | 3 |
| 4 | 8 | 7 | 3 | 2 | 4 | 1 | 5 | 6 |
| 5 | 6 | 4 | 7 | 3 | 8 | 1 | 2 | 5 |
| 6 | 2 | 8 | 5 | 3 | 4 | 6 | 7 | 1 |
| 7 | 7 | 5 | 2 | 1 | 8 | 6 | 4 | 3 |
| 8 | 7 | 4 | 1 | 5 | 2 | 3 | 6 | 8 |
For example, Firm 2 ranks Student 6 second best and Student 4 last (8th). Note for example that 7 appears twice in the first column. This means that Firms 7 and 8 rank Student 7 first.
A stable matching refers to finding student-firm pairs with each student and each firm in one of the pairs (8 pairs in this example), and where for none of these pairs (say (Si, Fj) - student i with firm j) would it be true that either of the members of the pair would prefer to be with a different "mate" who would prefer having that new pair form over the one they are currently asigned to.
Problem 1:
Use the deferred acceptance algorithm with the students proposing to find a stable matching.
Problem 2:
Use the deferred acceptance algorithm with the firms proposing to find a stable matching.
Problem 3:
Which of these two stable matchings (assuming they are different) seems more fair to you?
Problem 4:
Can you find other stable matchings for the two preference lists above?
Problem 5:
Among all stable marriages for this problem, which one seems fairest?
Problem 6:
What are the implications for "truth telling" in constructing preference schedules that arises when the deferred acceptance algorithm is being used to find a stable matching?