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

Partial strategyproofness: Relaxing strategyproofness for the random assignment problem

Author

Listed:
  • Mennle, Timo
  • Seuken, Sven

Abstract

We present partial strategyproofness, a new, relaxed notion of strategyproofness for studying the incentive properties of non-strategyproof assignment mechanisms. Informally, a mechanism is partially strategyproof if it makes truthful reporting a dominant strategy for those agents whose preference intensities differ sufficiently between any two objects. We demonstrate that partial strategyproofness is axiomatically motivated and yields a parametric measure for “how strategyproof” an assignment mechanism is. We apply this new concept to derive novel insights about the incentive properties of the probabilistic serial mechanism and different variants of the Boston mechanism.

Suggested Citation

  • Mennle, Timo & Seuken, Sven, 2021. "Partial strategyproofness: Relaxing strategyproofness for the random assignment problem," Journal of Economic Theory, Elsevier, vol. 191(C).
    • Handle: RePEc:eee:jetheo:v:191:y:2021:i:c:s002205312030137x
    DOI: 10.1016/j.jet.2020.105144
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S002205312030137X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2020.105144?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. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    2. Gabrielle Fack & Julien Grenet & Yinghua He, 2019. "Beyond Truth-Telling: Preference Estimation with Centralized School Choice and College Admissions," American Economic Review, American Economic Association, vol. 109(4), pages 1486-1529, April.
    3. Eric Budish & Estelle Cantillon, 2012. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," American Economic Review, American Economic Association, vol. 102(5), pages 2237-2271, August.
    4. 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.
    5. Alcalde, Jose, 1996. "Implementation of Stable Solutions to Marriage Problems," Journal of Economic Theory, Elsevier, vol. 69(1), pages 240-254, April.
    6. Gabrielle Fack & Julien Grenet & Yinghua He, 2019. "Beyond Truth-Telling: Preference Estimation with Centralized School Choice and College Admissions," American Economic Review, American Economic Association, vol. 109(4), pages 1486-1529, April.
    7. 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.
    8. Eduardo M Azevedo & Eric Budish, 2019. "Strategy-proofness in the Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(1), pages 81-116.
    9. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    10. 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.
    11. Ivan Balbuzanov, 2016. "Convex strategyproofness with an application to the probabilistic serial mechanism," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(3), pages 511-520, March.
    12. 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.
    13. Erdil, Aytek, 2014. "Strategy-proof stochastic assignment," Journal of Economic Theory, Elsevier, vol. 151(C), pages 146-162.
    14. , A. & ,, 2011. "Lotteries in student assignment: An equivalence result," Theoretical Economics, Econometric Society, vol. 6(1), January.
    15. Cho, Wonki Jo, 2016. "Incentive properties for ordinal mechanisms," Games and Economic Behavior, Elsevier, vol. 95(C), pages 168-177.
    16. Sulagna Dasgupta & Debasis Mishra, 2020. "Ordinal Bayesian incentive compatibility in random assignment model," Papers 2009.13104, arXiv.org, revised May 2021.
    17. 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.
    18. Dur, Umut Mert, 2019. "The modified Boston mechanism," Mathematical Social Sciences, Elsevier, vol. 101(C), pages 31-40.
    19. Bogomolnaia, Anna & Moulin, Herve, 2001. "A New Solution to the Random Assignment Problem," Journal of Economic Theory, Elsevier, vol. 100(2), pages 295-328, October.
    20. 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.
    21. 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.
    22. Atila Abdulkadiroglu & Yeon-Koo Che & Yosuke Yasuda, 2011. "Resolving Conflicting Preferences in School Choice: The "Boston Mechanism" Reconsidered," American Economic Review, American Economic Association, vol. 101(1), pages 399-410, February.
    23. Aziz, Haris & Brandt, Felix & Brill, Markus, 2013. "The computational complexity of random serial dictatorship," Economics Letters, Elsevier, vol. 121(3), pages 341-345.
    24. Zhou, Lin, 1990. "On a conjecture by gale about one-sided matching problems," Journal of Economic Theory, Elsevier, vol. 52(1), pages 123-135, October.
    25. 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.
    26. Lai, Fang & Sadoulet, Elisabeth & de Janvry, Alain, 2009. "The adverse effects of parents' school selection errors on academic achievement: Evidence from the Beijing open enrollment program," Economics of Education Review, Elsevier, vol. 28(4), pages 485-496, August.
    27. 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.
    28. 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.
    29. Wonki Jo Cho, 2018. "Probabilistic assignment: an extension approach," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 137-162, June.
    30. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    31. Gabriel Carroll, 2012. "When Are Local Incentive Constraints Sufficient?," Econometrica, Econometric Society, vol. 80(2), pages 661-686, March.
    32. repec:hal:cesptp:halshs-01215998 is not listed on IDEAS
    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. Christian Basteck, 2024. "An Axiomatization of the Random Priority Rule," Rationality and Competition Discussion Paper Series 502, CRC TRR 190 Rationality and Competition.
    2. Felix Brandt & Matthias Greger & Ren'e Romen, 2023. "Towards a Characterization of Random Serial Dictatorship," Papers 2303.11976, arXiv.org, revised Jul 2024.
    3. Feizi, Mehdi & Ramezanian, Rasoul, 2023. "A new impossibility result for random assignments," Journal of Mathematical Economics, Elsevier, vol. 107(C).
    4. Basteck, Christian, 2024. "An axiomatization of the random priority rule," Discussion Papers, Research Unit: Market Behavior SP II 2024-201, WZB Berlin Social Science Center.
    5. Geoffrey Pritchard & Mark C. Wilson, 2022. "Asymptotic welfare performance of Boston assignment algorithms," Papers 2205.15418, arXiv.org.
    6. Ramezanian, Rasoul & Feizi, Mehdi, 2022. "Robust ex-post Pareto efficiency and fairness in random assignments: Two impossibility results," Games and Economic Behavior, Elsevier, vol. 135(C), pages 356-367.
    7. Akyol, Ethem, 2023. "Inefficiency of Random Serial Dictatorship under incomplete information," Journal of Economic Theory, Elsevier, vol. 213(C).
    8. Lomakin, Artemii & Minibaev, Kamil & Nesterov, Alexander, 2024. "Modifications of Boston, Taiwanese and Chinese mechanisms are not comparable via counting manipulating students," Economics Letters, Elsevier, vol. 237(C).
    9. Basteck, Christian & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    10. Altuntaş, Açelya & Phan, William & Tamura, Yuki, 2023. "Some characterizations of Generalized Top Trading Cycles," Games and Economic Behavior, Elsevier, vol. 141(C), pages 156-181.
    11. Noda, Shunya, 2023. "A planner-optimal matching mechanism and its incentive compatibility in a restricted domain," Games and Economic Behavior, Elsevier, vol. 141(C), pages 364-379.
    12. Basteck, Christian & Ehlers, Lars H., 2022. "Strategy-proof and envy-free random assignment," Discussion Papers, Research Unit: Market Behavior SP II 2022-208, WZB Berlin Social Science Center.
    13. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    14. Sulagna Dasgupta & Debasis Mishra, 2022. "Ordinal Bayesian incentive compatibility in random assignment model," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 651-664, December.
    15. Mustafa Oguz Afacan & Umut Dur & A. Arda Gitmez & Ozgur Y{i}lmaz, 2022. "Improving the Deferred Acceptance with Minimal Compromise," Papers 2205.00032, arXiv.org, revised Sep 2023.
    16. Mehdi Feizi, 2023. "The object allocation problem with favoring upper ranks," International Journal of Economic Theory, The International Society for Economic Theory, vol. 19(2), pages 370-383, June.

    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. Abdulkadiroglu, Atila & Andersson, Tommy, 2022. "School Choice," Working Papers 2022:4, Lund University, Department of Economics.
    2. Onur Kesten & Morimitsu Kurino & Alexander S. Nesterov, 2017. "Efficient lottery design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 31-57, January.
    3. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    4. Tong Wang & Congyi Zhou, 2020. "High school admission reform in China: a welfare analysis," Review of Economic Design, Springer;Society for Economic Design, vol. 24(3), pages 215-269, December.
    5. Ha, Wei & Kang, Le & Song, Yang, 2020. "College matching mechanisms and matching stability: Evidence from a natural experiment in China," Journal of Economic Behavior & Organization, Elsevier, vol. 175(C), pages 206-226.
    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. Harless, Patrick, 2014. "A School Choice Compromise: Between Immediate and Deferred Acceptance," MPRA Paper 61417, University Library of Munich, Germany.
    8. Wu, Binzhen & Zhong, Xiaohan, 2014. "Matching mechanisms and matching quality: Evidence from a top university in China," Games and Economic Behavior, Elsevier, vol. 84(C), pages 196-215.
    9. 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.
    10. Nesterov, Alexander S., 2017. "Fairness and efficiency in strategy-proof object allocation mechanisms," Journal of Economic Theory, Elsevier, vol. 170(C), pages 145-168.
    11. Li, Mengling, 2020. "Ties matter: Improving efficiency in course allocation by allowing ties," Journal of Economic Behavior & Organization, Elsevier, vol. 178(C), pages 354-384.
    12. Afacan, Mustafa Oǧuz, 2018. "The object allocation problem with random priorities," Games and Economic Behavior, Elsevier, vol. 110(C), pages 71-89.
    13. 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.
    14. Han, Xiang, 2024. "On the efficiency and fairness of deferred acceptance with single tie-breaking," Journal of Economic Theory, Elsevier, vol. 218(C).
    15. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    16. Umut M. Dur & Scott Duke Kominers & Parag A. Pathak & Tayfun Sönmez, 2013. "The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice," NBER Working Papers 18981, National Bureau of Economic Research, Inc.
    17. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    18. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    19. Andrew McLennan & Shino Takayama & Yuki Tamura, 2024. "An Efficient, Computationally Tractable School Choice Mechanism," Discussion Papers Series 668, School of Economics, University of Queensland, Australia.
    20. Alexander Nesterov, "undated". "Fairness and Efficiency in a Random Assignment: Three Impossibility Results," BDPEMS Working Papers 2014006, Berlin School of Economics.

    More about this item

    Keywords

    Mechanism design; Random assignment; Matching; Strategyproofness; Probabilistic serial; Boston mechanism;
    All these keywords.

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design
    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism 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:191:y:2021:i:c:s002205312030137x. 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.