IDEAS home Printed from https://ideas.repec.org/p/lau/crdeep/16.08.html
   My bibliography  Save this paper

Equilibria of Deferred Acceptance with Complete Lists

Author

Listed:
  • Bettina Klaus
  • Flip Klijn

Abstract

We study the structure of the set of (Nash) equilibria of a deferred acceptance game with complete lists: for a given marriage market with complete lists, men propose to women truthfully while women can accept or reject proposals strategically throughout the deferred-acceptance algorithm. Zhou (1991) studied this game and showed that a matching that is stable with respect to the true preferences can be supported by some preference profile (possibly a non-equilibrium one) if and only if it can be supported by an equilibrium as well. In particular, this result implies the existence of equilibria since the men-optimal stable matching is supported by true preferences and hence an equilibrium outcome. We answer an open question Zhou posed by showing that there need not exist an equilibrium matching that weakly dominates all other equilibrium matchings from the women's point of view (Theorem 2). We complement Zhou's and our findings by showing that the set of equilibrium matchings also need not be "connected" (Example 2).

Suggested Citation

  • Bettina Klaus & Flip Klijn, 2016. "Equilibria of Deferred Acceptance with Complete Lists," Cahiers de Recherches Economiques du Département d'économie 16.08, Université de Lausanne, Faculté des HEC, Département d’économie.
    • Handle: RePEc:lau:crdeep:16.08
    as

    Download full text from publisher

    File URL: http://hec.unil.ch/attachments/deep/series/2016/16.08.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Jaramillo, Paula & Kayı, Çaǧatay & Klijn, Flip, 2013. "Equilibria under deferred acceptance: Dropping strategies, filled positions, and welfare," Games and Economic Behavior, Elsevier, vol. 82(C), pages 693-701.
    2. Vulkan, Nir & Roth, Alvin E. & Neeman, Zvika (ed.), 2013. "The Handbook of Market Design," OUP Catalogue, Oxford University Press, number 9780199570515.
    3. Klaus, Bettina & Klijn, Flip, 2016. "Equilibria of deferred acceptance with complete lists," Economics Letters, Elsevier, vol. 144(C), pages 98-101.
    4. Roth, Alvin E & Xing, Xiaolin, 1994. "Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions," American Economic Review, American Economic Association, vol. 84(4), pages 992-1044, September.
    5. Roth, Alvin E., 1984. "Misrepresentation and stability in the marriage problem," Journal of Economic Theory, Elsevier, vol. 34(2), pages 383-387, December.
    6. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    7. Chung-Piaw Teo & Jay Sethuraman & Wee-Peng Tan, 2001. "Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications," Management Science, INFORMS, vol. 47(9), pages 1252-1267, September.
    8. Zhou, Lin, 1991. "Stable matchings and equilibrium outcomes of the Gale-Shapley's algorithm for the marriage problem," Economics Letters, Elsevier, vol. 36(1), pages 25-29, May.
    9. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Klaus, Bettina & Klijn, Flip, 2016. "Equilibria of deferred acceptance with complete lists," Economics Letters, Elsevier, vol. 144(C), pages 98-101.

    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. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    2. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    3. 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.
    4. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    5. Ergin, Haluk & Sonmez, Tayfun, 2006. "Games of school choice under the Boston mechanism," Journal of Public Economics, Elsevier, vol. 90(1-2), pages 215-237, January.
    6. Lars Ehlers & Jordi Massó, 2004. "Incomplete Information and Small Cores in Matching Markets," Working Papers 147, Barcelona School of Economics.
    7. Pais, Joana, 2008. "Incentives in decentralized random matching markets," Games and Economic Behavior, Elsevier, vol. 64(2), pages 632-649, November.
    8. 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.
    9. Kóczy Á., László, 2009. "Központi felvételi rendszerek. Taktikázás és stabilitás [Central admission systems. Stratagems and stability]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(5), pages 422-442.
    10. Roth, Alvin E., 1985. "Common and conflicting interests in two-sided matching markets," European Economic Review, Elsevier, vol. 27(1), pages 75-96, February.
    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. 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.
    13. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
    14. Ehlers, Lars, 2004. "In search of advice for participants in matching markets which use the deferred-acceptance algorithm," Games and Economic Behavior, Elsevier, vol. 48(2), pages 249-270, August.
    15. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    16. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    17. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    18. Halaburda, Hanna, 2010. "Unravelling in two-sided matching markets and similarity of preferences," Games and Economic Behavior, Elsevier, vol. 69(2), pages 365-393, July.
    19. Estelle Cantillon & Li Chen & Juan Sebastian Pereyra Barreiro, 2022. "Respecting priorities versus respecting preferences in school choice: When is there a trade-off ?," Working Papers ECARES 2022-39, ULB -- Universite Libre de Bruxelles.

    More about this item

    Keywords

    matching; stability; complete lists; Nash equilibria;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:lau:crdeep:16.08. 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: Christina Seld (email available below). General contact details of provider: https://edirc.repec.org/data/deelsch.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.