By Jessica Kang
Given a set of men and women whose preferences are in the opposite gender, how should we form pairs such that no agent has the incentive to rematch? This question was originally proposed and answered by Gale and Shapley in 1962; since then, the solutions to the variants of the question have been applied to school choice, medical residency matching, and the assignment of cadets to military branches. Gale and Shapley tried to find a one-to-one stable matching (a set of pairings in which (1) all men and women find their partners acceptable and (2) no man/woman pair prefers each other to their assigned partners. By a process called the deferred acceptance algorithm, Gale and Shapley proved that a stable matching exists for any finite set of men and women and their preferences. The algorithm is described as follows:
Each man proposes to his most preferred woman. Each woman selects her most preferred man out of those who proposed to her and puts him on her waiting list; the rest are rejected.
Each man that was rejected proposes to his next preferred woman. Each woman selects her most preferred man among those that proposed to her, including the man on the waiting list.
Repeat Step 2 until no men who are available to propose are left.
For example, consider the following situation with 5 men and 4 women:
P(mi) denotes the preference relation of mi: for instance, m5 prefers w1 over w2, w2 over w4, and w4 over staying single. m5 would rather stay single than be matched with w3 or w5. Assume that the preferences of the women are as
follows:
If we apply the deferred acceptance algorithm to this specific example,
1. m1, m4, and m5 propose to w1, who only holds m1; m2 and m3 propose
to w4, who only holds m2. This yields a tentative matching
2. m3 , m4 , and m5 propose to w3 , w4 , and w2, respectively; w4 rejects
m2 and holds m4 . The tentative matching is thus revised to
3. m2 proposes to w2, who rejects m5 and holds m2. The tentative
matching is thus revised to
4. m5 proposes to w4, who rejects m5 and holds m4, which stops the
procedure and results in
Stableness
A stable matching is a matching where no pair of agents would mutually prefer to be matched to each other than to their assigned partners.
Pareto-Optimality
A stable matching is Pareto-optimal if there is no other matching that makes some agents better off without making anyone worse off.
Strategy-Proofness
A matching mechanism is strategy-proof if each agent has a dominant strategy of truthfully reporting his/her preference.
In the economic theory of two-sided many-to-one matching, a particular problem of interest is the mechanism of school assignment. Ever since the deferred acceptance algorithm was first proposed by Gale and Shapley (1962), there has been much research about mechanisms that optimally match students to schools in real-world situations. Applications of matchings in school choice have been made to mimic real-life scenarios. Ehlers, Hafalir, Yenmez, and Yildirim studied controlled choice over public schools; Benabbou, Chakraborty, Ho, Sliwinski, and Zick investigated the impact of diversity constraints on public housing allocation. Pathak and Sönmez compared various mechanisms by their susceptibility to manipulation.
In 1962, Gale and Shapley proposed a solution to the problem of pairing men and women in stable relationships. Their solution, called the deferred acceptance algorithm, has since been applied to various real-world situations such as school choice and medical residency matching. Researchers continue to study and improve upon this algorithm to find the best way to match students to schools. The work of Gale and Shapley continues to be an important area of study in the field of matching.
References
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747.
Roth, A. E., & Sotomayor, M. (1992). Two-sided matching. Handbook of game theory with economic applications, 1, 485-541.
Sönmez, T., & Switzer, T. B. (2013). Matching with (branch‐of‐choice) contracts at the United States Military Academy. Econometrica, 81(2), 451-488.
Ehlers, L., Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic theory, 153, 648-683.
Benabbou, N., Chakraborty, M., Ho, X. V., Sliwinski, J., & Zick, Y. (2018, July). Diversity constraints in public housing allocation. In 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018).
Pathak, P. A., & Sönmez, T. (2013). School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability tomanipulation.American Economic Review, 103(1),80-106.
Comments