IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2405.12804.html
   My bibliography  Save this paper

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. Alcalde, Jose, 1996. "Implementation of Stable Solutions to Marriage Problems," Journal of Economic Theory, Elsevier, vol. 69(1), pages 240-254, April.
    2. 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.
    3. Coles, Peter & Shorrer, Ran, 2014. "Optimal truncation in matching markets," Games and Economic Behavior, Elsevier, vol. 87(C), pages 591-615.
    4. Barberà, S. & Dutta, B., 1995. "Protective behavior in matching models," Games and Economic Behavior, Elsevier, vol. 8(2), pages 281-296.
    5. 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.
    6. 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.
    7. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    8. 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.
    9. 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.
    10. 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.
    11. Yajing Chen & Zhenhua Jiao & Chenfeng Zhang & Luosai Zhang, 2021. "The Machiavellian frontier of top trading cycles," Papers 2106.14456, arXiv.org, revised Apr 2024.
    12. 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.
    13. 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.
    14. 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.
    15. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    16. 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.
    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.
    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. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    2. Troyan, Peter & Morrill, Thayer, 2020. "Obvious manipulations," Journal of Economic Theory, Elsevier, vol. 185(C).
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Sonmez, Tayfun, 1996. "Implementation in generalized matching problems," Journal of Mathematical Economics, Elsevier, vol. 26(4), pages 429-439.
    8. José Alcalde & Antonio Romero-Medina, 2017. "Fair student placement," Theory and Decision, Springer, vol. 83(2), pages 293-307, August.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    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. 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.
    19. Ehlers, Lars & Massó, Jordi, 2015. "Matching markets under (in)complete information," Journal of Economic Theory, Elsevier, vol. 157(C), pages 295-314.
    20. 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.

    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.