Two-Sided Matchings: An Algorithm for Ensuring They Are Minimax and Pareto-Optimal
AbstractGale 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University Library of Munich, Germany in its series MPRA Paper with number 48113.
Date of creation: 07 Jul 2013
Date of revision:
Deferred-acceptance algorithm; minimax algorithm; matchings; stability;
Find related papers by JEL classification:
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- D7 - Microeconomics - - Analysis of Collective Decision-Making
- D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
- D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy-Making and Implementation
This paper has been announced in the following NEP Reports:
- NEP-ALL-2013-07-15 (All new papers)
- NEP-DEM-2013-07-15 (Demographic Economics)
- NEP-GTH-2013-07-15 (Game Theory)
- NEP-MIC-2013-07-15 (Microeconomics)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Alvin E Roth, 2007.
"Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions,"
843644000000000283, UCLA Department of Economics.
- Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer, vol. 36(3), pages 537-569, March.
- Roth, Alvin, 2008. "Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions," Scholarly Articles 2579651, Harvard University Department of Economics.
- Alvin E. Roth, 2007. "Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions," NBER Working Papers 13225, National Bureau of Economic Research, Inc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ekkehart Schlicht).
If references are entirely missing, you can add them using this form.