Two-Sided Matchings: An Algorithm for Ensuring They Are Minimax and Pareto-Optimal

Steven, Brams and Marc, Kilgour (2013): Two-Sided Matchings: An Algorithm for Ensuring They Are Minimax and Pareto-Optimal.

Abstract

Gale and Shapley (1962) proposed the deferred-acceptance algorithm for matching (i) college applicants and colleges and (ii) men and women. In the case of the latter, it produces either one or two stable matches whereby no man and woman would prefer to be matched with each other rather than with their present partners. But stable matches can give one or both players in a pair their worst match, whereas the minimax algorithm that we propose, which finds all assignments that minimize the maximum rank of players in matches, avoids such assignments. Although minimax matches may not be stable, at least one is always Pareto-optimal: No other matching is at least as good for all the players and better for one or more. If there are multiple minimax matches, we propose criteria for choosing the most desirable among them and also discuss the settings in which minimax matches seem more compelling than deferred-acceptance matches when they differ. Finally, we calculate the probability that minimax matches differ from deferred-acceptance matches in a simple case.

• Item Type: MPRA Paper
• Language: English
• Keywords: Deferred-acceptance algorithm; minimax algorithm; matchings; stability
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D7 - Analysis of Collective Decision-Making; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D78 - Positive Analysis of Policy Formulation and Implementation

References

Boudreau, James W., and Vicki Knoblauch (2013). “Preferences and the Price of Stability in Matching Markets.” Theory and Decision 74, no. 4 (December): 565-589.

Brams, Steven J., Michael A. Jones, and D. Marc Kilgour, and (2005). “Forming Stable Coalitions: The Process Matters.” Public Choice 125, nos. 1 and 2 (October): 67-94.

Brams, Steven J., and D. Marc Kilgour (2001). “Fallback Bargaining.” Group Decision and Negotiation 10, no. 4 (July): 287-316.

Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences (2012). “Stable Allocations and the Practice of Market Design.” Stockholm, Sweden. http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/advanced-economicsciences2012.pdf

Gale, D., and Lloyd S. Shapley (1962). “College Admissions and the Stability of Marriage.” American Mathematical Monthly 69, no. 1 (January): 9-15.

Gura, Ein-Ya, and Michael Maschler (2008). Insights into Game Theory: An Alternative Mathematical Experience. Cambridge, UK: Cambridge University Press.

Gusfield, Dan, and Robert W. Irving (1989). The Stable Marriage Problem: Structure and Algorithms. Cambridge, MA: MIT Press.

Hall, Philip (1935). “On Representatives of Sets.” Journal of the London Mathematical Society 10, no. 1: 26-30.

Hopcroft, John E., and Richard M. Karp (1973). “An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs,” SIAM journal of Computing 2, no. 4: 225-231.

Knuth, Donald E. (1997). Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. Providence, RI: American Mathematical Society.

Rawls, John (1971). A Theory of Justice. Cambridge, MA: Harvard University Press.

Roth, Alvin E. (2008). “Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions.” International Journal of Game Theory 36: 537-569.

Roth, Alvin E., and Marilda A. Oliveira Sotomayor (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge, UK: Cambridge University Press.

Sönmez, Tayfun, and M. Utku Ünver (2011). “Matching, Allocation, and Exchange of Discrete Resources,” in Jess Benhabib, Albert Bison, and Matthew O. Jackson (eds.), Handbook of Social Economics, Vol. 1A. Amsterdam: North Holland, pp. 781-852.