IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2405.12804.html

The Machiavellian frontier of stable mechanisms

Author

Listed:
  • Qiufu Chen
  • Yuanmei Li
  • Xiaopeng Yin
  • Luosai Zhang
  • Siyi Zhou

Abstract

The impossibility theorem in Roth (1982) states that no stable mechanism satisfies strategy-proofness. This paper explores the Machiavellian frontier of stable mechanisms by weakening strategy-proofness. For a fixed mechanism $\varphi$ and a true preference profile $\succ$, a $(\varphi,\succ)$-boost mispresentation of agent i is a preference of i that is obtained by (i) raising the ranking of the truth-telling assignment $\varphi_i(\succ)$, and (ii) keeping rankings unchanged above the new position of this truth-telling assignment. We require a matching mechanism $\varphi$ neither punish nor reward any such misrepresentation, and define such axiom as $\varphi$-boost-invariance. This is strictly weaker than requiring strategy-proofness. We show that no stable mechanism $\varphi$ satisfies $\varphi$-boost-invariance. Our negative result strengthens the Roth Impossibility Theorem.

Suggested Citation

  • Qiufu Chen & Yuanmei Li & Xiaopeng Yin & Luosai Zhang & Siyi Zhou, 2024. "The Machiavellian frontier of stable mechanisms," Papers 2405.12804, arXiv.org, revised Jul 2024.
    • Handle: RePEc:arx:papers:2405.12804
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2405.12804
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    2. Alcalde, Jose, 1996. "Implementation of Stable Solutions to Marriage Problems," Journal of Economic Theory, Elsevier, vol. 69(1), pages 240-254, April.
    3. Castillo, Marco & Dianat, Ahrash, 2016. "Truncation strategies in two-sided matching markets: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 98(C), pages 180-196.
    4. Takashi Akahoshi, 2014. "A necessary and sufficient condition for stable matching rules to be strategy-proof," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(3), pages 683-702, October.
    5. Hashimoto, Tadashi & Hirata, Daisuke & Kesten, Onur & Kurino, Morimitsu & Unver, Utku, 2014. "Two axiomatic approaches to the probabilistic serial mechanism," Theoretical Economics, Econometric Society, vol. 9(1), January.
    6. Kasajima, Yoichi & Toda, Manabu, 2024. "Singles monotonicity and stability in one-to-one matching problems," Games and Economic Behavior, Elsevier, vol. 143(C), pages 269-286.
    7. Coles, Peter & Shorrer, Ran, 2014. "Optimal truncation in matching markets," Games and Economic Behavior, Elsevier, vol. 87(C), pages 591-615.
    8. Yajing Chen & Zhenhua Jiao & Chenfeng Zhang & Luosai Zhang, 2021. "The Machiavellian frontier of top trading cycles," Papers 2106.14456, arXiv.org, revised Apr 2024.
    9. Barberà, S. & Dutta, B., 1995. "Protective behavior in matching models," Games and Economic Behavior, Elsevier, vol. 8(2), pages 281-296.
    10. Gary Charness & Dan Levin, 2009. "The Origin of the Winner's Curse: A Laboratory Study," American Economic Journal: Microeconomics, American Economic Association, vol. 1(1), pages 207-236, February.
    11. Ignacio Esponda Jr. & Emanuel Vespa Jr., 2014. "Hypothetical Thinking and Information Extraction in the Laboratory," American Economic Journal: Microeconomics, American Economic Association, vol. 6(4), pages 180-202, November.
    12. Yajing Chen, 2017. "New axioms for deferred acceptance," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 393-408, February.
    13. Ma Jinpeng, 1995. "Stable Matchings and Rematching-Proof Equilibria in a Two-Sided Matching Market," Journal of Economic Theory, Elsevier, vol. 66(2), pages 352-369, August.
    14. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    15. Mongell, Susan & Roth, Alvin E, 1991. "Sorority Rush as a Two-Sided Matching Mechanism," American Economic Review, American Economic Association, vol. 81(3), pages 441-464, June.
    16. Camilo J. Sirguiado & Juan Pablo Torres-Martinez, 2024. "Strategic Behavior Without Outside Options," Working Papers wp553, University of Chile, Department of Economics.
    17. Alvin E. Roth & Uriel G. Rothblum, 1999. "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, Econometric Society, vol. 67(1), pages 21-44, January.
    18. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    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. Troyan, Peter & Morrill, Thayer, 2020. "Obvious manipulations," Journal of Economic Theory, Elsevier, vol. 185(C).
    2. 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.
    3. Marco Castillo & Ahrash Dianat, 2021. "Strategic uncertainty and equilibrium selection in stable matching mechanisms: experimental evidence," Experimental Economics, Springer;Economic Science Association, vol. 24(4), pages 1365-1389, December.
    4. Pais, Joana & Pintér, Ágnes, 2008. "School choice and information: An experimental study on matching mechanisms," Games and Economic Behavior, Elsevier, vol. 64(1), pages 303-328, September.
    5. Rheingans-Yoo, Ross, 2024. "Large random matching markets with localized preference structures can exhibit large cores," Games and Economic Behavior, Elsevier, vol. 144(C), pages 71-83.
    6. Sonmez, Tayfun, 1996. "Implementation in generalized matching problems," Journal of Mathematical Economics, Elsevier, vol. 26(4), pages 429-439.
    7. 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.
    8. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    9. Ma, Jinpeng, 2010. "The singleton core in the college admissions problem and its application to the National Resident Matching Program (NRMP)," Games and Economic Behavior, Elsevier, vol. 69(1), pages 150-164, May.
    10. Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-689, June.
    11. Nobel Prize Committee, 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.
    12. 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.
    13. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    14. Jens Gudmundsson, 2014. "Sequences in Pairing Problems: A new approach to reconcile stability with strategy-proofness for elementary matching problems," 2014 Papers pgu351, Job Market Papers.
    15. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    16. 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.
    17. Pablo Guillen & Onur Kesten, 2012. "Matching Markets With Mixed Ownership: The Case For A Real‐Life Assignment Mechanism," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 53(3), pages 1027-1046, August.
    18. Atila ABDULKAD RO LU & Tayfun S NMEZ, 2014. "[School Choice: A Mechanism Desing Approach], Okul Se imi: Bir Mekanizma Tasar m Yakla m," Journal of Economics and Political Economy, EconSciences Journals, vol. 1(2), pages 302-326, December.
    19. EHLERS, Lars & MASSO, Jordi, 2018. "Robust design in monotonic matching markets: A case for firm-proposing deferred-acceptance," Cahiers de recherche 2018-02, Universite de Montreal, Departement de sciences economiques.
    20. Christian Haas & Margeret Hall, 2019. "Two-Sided Matching for mentor-mentee allocations—Algorithms and manipulation strategies," PLOS ONE, Public Library of Science, vol. 14(3), pages 1-27, March.

    More about this item

    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:arx:papers:2405.12804. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.