IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v177y2018icp405-425.html
   My bibliography  Save this article

Stable matching mechanisms are not obviously strategy-proof

Author

Listed:
  • Ashlagi, Itai
  • Gonczarowski, Yannai A.

Abstract

Many two-sided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicant-proposing deferred acceptance algorithm, which is well known to be strategy-proof for the applicants. Nonetheless, a growing amount of empirical evidence reveals that applicants misrepresent their preferences when this mechanism is used. This paper shows that no mechanism that implements a stable matching is obviously strategy-proof for any side of the market, a stronger incentive property than strategy-proofness that was introduced by Li (2017). A stable mechanism that is obviously strategy-proof for applicants is introduced for the case in which agents on the other side have acyclical preferences.

Suggested Citation

  • Ashlagi, Itai & Gonczarowski, Yannai A., 2018. "Stable matching mechanisms are not obviously strategy-proof," Journal of Economic Theory, Elsevier, vol. 177(C), pages 405-425.
    • Handle: RePEc:eee:jetheo:v:177:y:2018:i:c:p:405-425
    DOI: 10.1016/j.jet.2018.07.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053118303454
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2018.07.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bó, Inácio & Hakimov, Rustamdjan, 2022. "The iterative deferred acceptance mechanism," Games and Economic Behavior, Elsevier, vol. 135(C), pages 411-433.
    2. Klijn, Flip & Pais, Joana & Vorsatz, Marc, 2019. "Static versus dynamic deferred acceptance in school choice: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 113(C), pages 147-163.
    3. Ran I. Shorrer & Sandor Sovago, 2017. "Obvious Mistakes in a Strategically Simple College Admissions Environment," Tinbergen Institute Discussion Papers 17-107/V, Tinbergen Institute.
    4. Inácio Bó & Rustamdjan Hakimov, 2020. "Iterative Versus Standard Deferred Acceptance: Experimental Evidence," The Economic Journal, Royal Economic Society, vol. 130(626), pages 356-392.
    5. Parag A. Pathak & Tayfun Sonmez, 2008. "Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism," American Economic Review, American Economic Association, vol. 98(4), pages 1636-1652, September.
    6. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the New York City High School Match," NBER Working Papers 14864, National Bureau of Economic Research, Inc.
    7. Chen, Yan & Sonmez, Tayfun, 2006. "School choice: an experimental study," Journal of Economic Theory, Elsevier, vol. 127(1), pages 202-231, March.
    8. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    9. Kagel, John H & Harstad, Ronald M & Levin, Dan, 1987. "Information Impact and Allocation Rules in Auctions with Affiliated Private Values: A Laboratory Study," Econometrica, Econometric Society, vol. 55(6), pages 1275-1304, November.
    10. Avinatan Hassidim & Déborah Marciano & Assaf Romm & Ran I. Shorrer, 2017. "The Mechanism Is Truthful, Why Aren't You?," American Economic Review, American Economic Association, vol. 107(5), pages 220-224, May.
    11. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2005. "The Boston Public School Match," American Economic Review, American Economic Association, vol. 95(2), pages 368-371, May.
    12. 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.
    13. Segal, Ilya, 2007. "The communication requirements of social choice rules and supporting budget sets," Journal of Economic Theory, Elsevier, vol. 136(1), pages 341-378, September.
    14. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Boston College Working Papers in Economics 639, Boston College Department of Economics.
    15. Itai Ashlagi & Yash Kanoria & Jacob D. Leshno, 2017. "Unbalanced Random Matching Markets: The Stark Effect of Competition," Journal of Political Economy, University of Chicago Press, vol. 125(1), pages 69-98.
    16. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    17. Umut Dur & Robert G. Hammond & Thayer Morrill, 2018. "Identifying the Harm of Manipulable School-Choice Mechanisms," American Economic Journal: Economic Policy, American Economic Association, vol. 10(1), pages 187-213, February.
    18. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    19. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    20. Alvin E. Roth, 2002. "The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics," Econometrica, Econometric Society, vol. 70(4), pages 1341-1378, July.
    21. Bogomolnaia, Anna & Deb, Rajat & Ehlers, Lars, 2005. "Strategy-proof assignment on the full preference domain," Journal of Economic Theory, Elsevier, vol. 123(2), pages 161-186, August.
    22. Avinatan Hassidim & Assaf Romm & Ran I. Shorrer, 2016. ""Strategic" Behavior in a Strategy-Proof Environment," Working Paper 413411, Harvard University OpenScholar.
    23. 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.
    24. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-1978, December.
    25. Peter Chen & Michael Egesdal & Marek Pycia & M. Bumin Yenmez, 2016. "Manipulability of Stable Mechanisms," American Economic Journal: Microeconomics, American Economic Association, vol. 8(2), pages 202-214, May.
    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. 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. Bó, Inácio & Hakimov, Rustamdjan, 2022. "The iterative deferred acceptance mechanism," Games and Economic Behavior, Elsevier, vol. 135(C), pages 411-433.
    3. Avinatan Hassidim & Assaf Romm & Ran I. Shorrer, 2021. "The Limits of Incentives in Economic Matching Procedures," Management Science, INFORMS, vol. 67(2), pages 951-963, February.
    4. Parag A. Pathak & Tayfun Sönmez, 2013. "School Admissions Reform in Chicago and England: Comparing Mechanisms by Their Vulnerability to Manipulation," American Economic Review, American Economic Association, vol. 103(1), pages 80-106, February.
    5. Dur, Umut & Hammond, Robert G. & Kesten, Onur, 2021. "Sequential school choice: Theory and evidence from the field and lab," Journal of Economic Theory, Elsevier, vol. 198(C).
    6. Chen, Yan & Jiang, Ming & Kesten, Onur & Robin, Stéphane & Zhu, Min, 2018. "Matching in the large: An experimental study," Games and Economic Behavior, Elsevier, vol. 110(C), pages 295-317.
    7. Zhang, Jun, 2021. "Level-k reasoning in school choice," Games and Economic Behavior, Elsevier, vol. 128(C), pages 1-17.
    8. Basteck, Christian & Klaus, Bettina & Kübler, Dorothea, 2021. "How lotteries in school choice help to level the playing field," Games and Economic Behavior, Elsevier, vol. 129(C), pages 198-237.
    9. 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.
    10. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    11. 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.
    12. Harless, Patrick, 2014. "A School Choice Compromise: Between Immediate and Deferred Acceptance," MPRA Paper 61417, University Library of Munich, Germany.
    13. Rustamdjan Hakimov & Dorothea Kübler, 2021. "Experiments on centralized school choice and college admissions: a survey," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 434-488, June.
    14. Yan Chen & Peter Cramton & John A. List & Axel Ockenfels, 2021. "Market Design, Human Behavior, and Management," Management Science, INFORMS, vol. 67(9), pages 5317-5348, September.
    15. 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.
    16. Tommy Andersson & Umut Dur & Sinan Ertemel & Onur Kesten, 2024. "Sequential school choice with public and private schools," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(2), pages 231-276, September.
    17. Featherstone, Clayton R. & Niederle, Muriel, 2016. "Boston versus deferred acceptance in an interim setting: An experimental investigation," Games and Economic Behavior, Elsevier, vol. 100(C), pages 353-375.
    18. Hoyer, B. & Stroh-Maraun, N., 2020. "Matching strategies of heterogeneous agents under incomplete information in a university clearinghouse," Games and Economic Behavior, Elsevier, vol. 121(C), pages 453-481.
    19. Pablo Guillen & Róbert F. Veszteg, 2021. "Strategy-proofness in experimental matching markets," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 650-668, June.
    20. Afacan, Mustafa Og̃uz & Dur, Umut Mert, 2017. "When preference misreporting is Harm[less]ful?," Journal of Mathematical Economics, Elsevier, vol. 72(C), pages 16-24.

    More about this item

    Keywords

    Stable matching; Obviously strategy-proof; Obvious strategy-proofness; Matching; Mechanism;
    All these keywords.

    JEL classification:

    • D4 - Microeconomics - - Market Structure, Pricing, and Design
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:eee:jetheo:v:177:y:2018:i:c:p:405-425. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622869 .

    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.