IDEAS home Printed from https://ideas.repec.org/a/wly/emetrp/v93y2025i2p569-595.html
   My bibliography  Save this article

On (Constrained) Efficiency of Strategy‐Proof Random Assignment

Author

Listed:
  • Christian Basteck
  • Lars Ehlers

Abstract

We study random assignment of indivisible objects among a set of agents, when each agent is to receive one object and has strict preferences over the objects. Random Serial Dictatorship (RSD) satisfies equal treatment of equals, ex post efficiency, and strategy‐proofness. Answering a longstanding open question, we show that RSD is not characterized by those properties—there are other mechanisms satisfying equal treatment of equals, ex post efficiency, and strategy‐proofness which are not welfare‐equivalent to RSD. On the other hand, we show that RSD is not Pareto dominated by any mechanism that is (i) strategy‐proof and (ii) boundedly invariant. Moreover, the same holds for all mechanisms that are ex post efficient, strategy‐proof, and boundedly invariant: no such mechanism is dominated by any other mechanism that is strategy‐proof and boundedly invariant.

Suggested Citation

  • Christian Basteck & Lars Ehlers, 2025. "On (Constrained) Efficiency of Strategy‐Proof Random Assignment," Econometrica, Econometric Society, vol. 93(2), pages 569-595, March.
    • Handle: RePEc:wly:emetrp:v:93:y:2025:i:2:p:569-595
    DOI: 10.3982/ECTA22762
    as

    Download full text from publisher

    File URL: https://doi.org/10.3982/ECTA22762
    Download Restriction: no
    File URL: https://libkey.io/10.3982/ECTA22762?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
    ---><---

    References listed on IDEAS

    as
    1. Szilvia Papai, 2000. "Strategyproof Assignment by Hierarchical Exchange," Econometrica, Econometric Society, vol. 68(6), pages 1403-1434, November.
    2. Basteck, Christian & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    3. Bogomolnaia, Anna, 2015. "Random assignment: Redefining the serial rule," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 308-318.
    4. 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.
    5. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    6. McLennan, Andrew, 2002. "Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem," Journal of Economic Theory, Elsevier, vol. 105(2), pages 435-449, August.
    7. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, September.
    8. Zhang, Jun, 2019. "Efficient and fair assignment mechanisms are strongly group manipulable," Journal of Economic Theory, Elsevier, vol. 180(C), pages 167-177.
    9. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    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. Katta, Akshay-Kumar & Sethuraman, Jay, 2006. "A solution to the random assignment problem on the full preference domain," Journal of Economic Theory, Elsevier, vol. 131(1), pages 231-250, November.
    12. Lars Ehlers, 2002. "Probabilistic allocation rules and single-dipped preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 19(2), pages 325-348.
    13. Zhang, Jun, 2023. "Strategy-proof allocation with outside option," Games and Economic Behavior, Elsevier, vol. 137(C), pages 50-67.
    14. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, 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. Basteck, Christian & Ehlers, Lars, 2024. "On (constrained) Efficiency of strategy-proof random assignment," VfS Annual Conference 2024 (Berlin): Upcoming Labor Market Challenges 302429, Verein für Socialpolitik / German Economic Association.
    2. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    3. Basteck, Christian & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    4. 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.
    5. Basteck, Christian & Ehlers, Lars H., 2023. "On the constrained efficiency of strategy-proof random assignment," Discussion Papers, Research Unit: Market Behavior SP II 2023-202, WZB Berlin Social Science Center.
    6. 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.
    7. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
    8. Athanassoglou, Stergios, 2011. "Efficiency under a combination of ordinal and cardinal information on preferences," Journal of Mathematical Economics, Elsevier, vol. 47(2), pages 180-185, March.
    9. Liu, Peng & Zeng, Huaxia, 2019. "Random assignments on preference domains with a tier structure," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 176-194.
    10. Cho, Wonki Jo, 2016. "Incentive properties for ordinal mechanisms," Games and Economic Behavior, Elsevier, vol. 95(C), pages 168-177.
    11. Harless, Patrick, 2019. "Efficient rules for probabilistic assignment," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 107-116.
    12. Christian Basteck, 2024. "An Axiomatization of the Random Priority Rule," Rationality and Competition Discussion Paper Series 502, CRC TRR 190 Rationality and Competition.
    13. Aziz, Haris & Brandl, Florian & Brandt, Felix & Brill, Markus, 2018. "On the tradeoff between efficiency and strategyproofness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 1-18.
    14. Anna Bogomolnaia, 2024. "On slots’ scheduling," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 77(3), pages 653-674, May.
    15. 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.
    16. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    17. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    18. Chang, Hee-In & Chun, Youngsub, 2017. "Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 80-92.
    19. Patrick Harless & William Phan, 2020. "On endowments and indivisibility: partial ownership in the Shapley–Scarf model," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 411-435, September.
    20. Yajing Chen & Patrick Harless & Zhenhua Jiao, 2024. "The fractional Boston random assignment rule and its axiomatic characterization," Review of Economic Design, Springer;Society for Economic Design, vol. 28(1), pages 21-43, February.

    More about this item

    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:wly:emetrp:v:93:y:2025:i:2:p:569-595. 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: Wiley Content Delivery (email available below). General contact details of provider: https://edirc.repec.org/data/essssea.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.