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

The Domain of RSD Characterization by Efficiency, Symmetry, and Strategy-Proofness

Author

Listed:
  • Maor Ben Zaquen
  • Ron Holzman

Abstract

Given a set of $n$ individuals with strict preferences over $m$ indivisible objects, the Random Serial Dictatorship (RSD) mechanism is a method for allocating objects to individuals in a way that is efficient, fair, and incentive-compatible. A random order of individuals is first drawn, and each individual, following this order, selects their most preferred available object. The procedure continues until either all objects have been assigned or all individuals have received an object. RSD is widely recognized for its application in fair allocation problems involving indivisible goods, such as school placements and housing assignments. Despite its extensive use, a comprehensive axiomatic characterization has remained incomplete. For the balanced case $n=m=3$, Bogomolnaia and Moulin have shown that RSD is uniquely characterized by Ex-Post Efficiency, Equal Treatment of Equals, and Strategy-Proofness. The possibility of extending this characterization to larger markets had been a long-standing open question, which Basteck and Ehlers recently answered in the negative for all markets with $n,m\geq5$. This work completes the picture by identifying exactly for which pairs $\left(n,m\right)$ these three axioms uniquely characterize the RSD mechanism and for which pairs they admit multiple mechanisms. In the latter cases, we construct explicit alternatives satisfying the axioms and examine whether augmenting the set of axioms could rule out these alternatives.

Suggested Citation

  • Maor Ben Zaquen & Ron Holzman, 2026. "The Domain of RSD Characterization by Efficiency, Symmetry, and Strategy-Proofness," Papers 2602.01224, arXiv.org.
    • Handle: RePEc:arx:papers:2602.01224
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Bogomolnaia, Anna, 2015. "Random assignment: Redefining the serial rule," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 308-318.
    2. 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.
    3. Christian Basteck & Lars Ehlers, 2025. "On (Constrained) Efficiency of Strategy‐Proof Random Assignment," Econometrica, Econometric Society, vol. 93(2), pages 569-595, March.
    4. Christian Basteck, 2025. "An Axiomatization of the Random Priority Rule," Papers 2506.17997, arXiv.org.
    5. Christian Basteck, 2025. "An Axiomatization of the Random Priority Rule," Rationality and Competition Discussion Paper Series 502, CRC TRR 190 Rationality and Competition.
    6. Erdil, Aytek, 2014. "Strategy-proof stochastic assignment," Journal of Economic Theory, Elsevier, vol. 151(C), pages 146-162.
    7. Basteck, Christian, 2025. "An axiomatization of the random priority rule," Discussion Papers, Research Unit: Market Behavior SP II 2024-201r, WZB Berlin Social Science Center, revised 2025.
    8. Mennle, Timo & Seuken, Sven, 2021. "Partial strategyproofness: Relaxing strategyproofness for the random assignment problem," Journal of Economic Theory, Elsevier, vol. 191(C).
    9. Nesterov, Alexander S., 2017. "Fairness and efficiency in strategy-proof object allocation mechanisms," Journal of Economic Theory, Elsevier, vol. 170(C), pages 145-168.
    10. Bade, Sophie, 2016. "Fairness and group-strategyproofness clash in assignment problems," Journal of Economic Theory, Elsevier, vol. 165(C), pages 257-262.
    11. 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.
    12. Sophie Bade, 2020. "Random Serial Dictatorship: The One and Only," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 353-368, February.
    13. Basteck, Christian & Ehlers, Lars, 2025. "On (Constrained) Efficiency of Strategy‐Proof Random Assignment," EconStor Open Access Articles and Book Chapters, ZBW - Leibniz Information Centre for Economics, vol. 93(2), pages 569-595.
    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, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    2. 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.
    3. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    4. 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.
    5. 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.
    6. Chen, Yajing & Jiao, Zhenhua & Zhao, Fang, 2025. "The equivalence between random priority and probabilistic serial rule on restricted preference domains," Economics Letters, Elsevier, vol. 251(C).
    7. 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.
    8. Huang, Chao & Tian, Guoqiang, 2017. "Guaranteed size ratio of ordinally efficient and envy-free mechanisms in the assignment problem," Games and Economic Behavior, Elsevier, vol. 105(C), pages 1-8.
    9. Christian Basteck, 2025. "An Axiomatization of the Random Priority Rule," Rationality and Competition Discussion Paper Series 502, CRC TRR 190 Rationality and Competition.
    10. Christian Basteck, 2025. "An Axiomatization of the Random Priority Rule," Papers 2506.17997, arXiv.org.
    11. Feizi, Mehdi & Ramezanian, Rasoul, 2023. "A new impossibility result for random assignments," Journal of Mathematical Economics, Elsevier, vol. 107(C).
    12. Zhang, Jun, 2023. "Strategy-proof allocation with outside option," Games and Economic Behavior, Elsevier, vol. 137(C), pages 50-67.
    13. Jun Zhang, 2023. "On wastefulness of random assignments in discrete allocation problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(1), pages 289-310, July.
    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, 2025. "An axiomatization of the random priority rule," Discussion Papers, Research Unit: Market Behavior SP II 2024-201r, WZB Berlin Social Science Center, revised 2025.
    16. 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.
    17. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    18. Ping Zhan, 2023. "A Simple Characterization of Assignment Mechanisms on Set Constraints," SN Operations Research Forum, Springer, vol. 4(2), pages 1-15, June.
    19. Yoshio Sano & Ping Zhan, 2021. "Extended Random Assignment Mechanisms on a Family of Good Sets," SN Operations Research Forum, Springer, vol. 2(4), pages 1-30, December.
    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

    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:2602.01224. 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.