IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/48113.html
   My bibliography  Save this paper

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

Author

Listed:
  • Steven, Brams
  • Marc, Kilgour

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.

Suggested Citation

  • Steven, Brams & Marc, Kilgour, 2013. "Two-Sided Matchings: An Algorithm for Ensuring They Are Minimax and Pareto-Optimal," MPRA Paper 48113, University Library of Munich, Germany.
    • Handle: RePEc:pra:mprapa:48113
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/48113/1/MPRA_paper_48113.pdf
    File Function: original version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    2. Gura,Ein-Ya & Maschler,Michael, 2008. "Insights into Game Theory," Cambridge Books, Cambridge University Press, number 9780521696920, October.
    3. Gura,Ein-Ya & Maschler,Michael, 2008. "Insights into Game Theory," Cambridge Books, Cambridge University Press, number 9780521874229, October.
    4. James Boudreau & Vicki Knoblauch, 2013. "Preferences and the price of stability in matching markets," Theory and Decision, Springer, vol. 74(4), pages 565-589, April.
    5. Tayfun Sönmez & M. Utku Ünver, 2009. "Matching, Allocation, and Exchange of Discrete Resources," Boston College Working Papers in Economics 717, Boston College Department of Economics.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lars Ehlers & Bettina Klaus, 2012. "Strategy-Proofness Makes the Difference : Deferred-Acceptance with Responsive Priorities," Cahiers de recherche 15-2012, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    2. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.
    3. Hakan İnal, 2015. "Core of coalition formation games and fixed-point methods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 745-763, December.
    4. Fuhito Kojima & M. Ünver, 2014. "The “Boston” school-choice mechanism: an axiomatic approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 55(3), pages 515-544, April.
    5. Hatfield, John William & Kojima, Fuhito & Narita, Yusuke, 2016. "Improving schools through school choice: A market design approach," Journal of Economic Theory, Elsevier, vol. 166(C), pages 186-211.
    6. Fuhito Kojima & M. Utku Ünver, 2010. "The 'Boston' School-Choice Mechanism," Boston College Working Papers in Economics 729, Boston College Department of Economics, revised 08 Oct 2010.
    7. Péter Biró & Flip Klijn, 2013. "Matching With Couples: A Multidisciplinary Survey," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1-18.
    8. Kojima, Fuhito, 2012. "School choice: Impossibilities for affirmative action," Games and Economic Behavior, Elsevier, vol. 75(2), pages 685-693.
    9. Encarna Esteban & Ariel Dinar, 2013. "Cooperative Management of Groundwater Resources in the Presence of Environmental Externalities," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 54(3), pages 443-469, March.
    10. Pereyra, Juan Sebastián, 2013. "A dynamic school choice model," Games and Economic Behavior, Elsevier, vol. 80(C), pages 100-114.
    11. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    12. Kawagoe, Toshiji & Matsubae, Taisuke & Takizawa, Hirokazu, 2018. "The Skipping-down strategy and stability in school choice problems with affirmative action: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 109(C), pages 212-239.
    13. Kojima, Fuhito & Tamura, Akihisa & Yokoo, Makoto, 2018. "Designing matching mechanisms under constraints: An approach from discrete convex analysis," Journal of Economic Theory, Elsevier, vol. 176(C), pages 803-833.
    14. ANDERSSON, Tommy & EHLERS, Lars, 2016. "Assigning refugees to landlords in Sweden: stable maximum matchings," Cahiers de recherche 2016-08, Universite de Montreal, Departement de sciences economiques.
    15. M. Bumin Yenmez, 2013. "Incentive-Compatible Matching Mechanisms: Consistency with Various Stability Notions," American Economic Journal: Microeconomics, American Economic Association, vol. 5(4), pages 120-141, November.
    16. Lars Ehlers & Bettina Klaus, 2014. "Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 949-966, November.
    17. Yun Liu, 2017. "On the welfare effects of affirmative actions in school choice," Review of Economic Design, Springer;Society for Economic Design, vol. 21(2), pages 121-151, June.
    18. Muriel Niederle & Alvin E. Roth, 2009. "The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices," NBER Chapters, in: Studies of Labor Market Intermediation, pages 235-271, National Bureau of Economic Research, Inc.
    19. Itai Ashlagi & Flip Klijn, 2012. "Manipulability in matching markets: conflict and coincidence of interests," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(1), pages 23-33, June.
    20. Yokote, Koji, 2021. "Consistency of the doctor-optimal equilibrium price vector in job-matching markets," Journal of Economic Theory, Elsevier, vol. 197(C).

    More about this item

    Keywords

    Deferred-acceptance algorithm; minimax algorithm; matchings; stability;
    All these keywords.

    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 Formulation and Implementation

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pra:mprapa:48113. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.