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

Strategy-proof and envy-free random assignment

Author

Listed:
  • Basteck, Christian
  • Ehlers, Lars

Abstract

We study the random assignment of indivisible objects among a set of agents with strict preferences. We show that there exists no mechanism which is unanimous, strategy-proof and envy-free. Weakening the first requirement to q-unanimity – i.e., when every agent ranks a different object at the top, then each agent shall receive his most-preferred object with probability of at least q – we show that a mechanism satisfying strategy-proofness, envy-freeness and ex-post weak non-wastefulness can be q-unanimous only for q≤2n (where n is the number of agents). To demonstrate that this bound is tight, we introduce a new mechanism, Random-Dictatorship-cum-Equal-Division (RDcED), and show that it achieves this maximal bound when all objects are acceptable. In addition, for three agents, RDcED is characterized by the first three properties and ex-post weak efficiency. If objects may be unacceptable, strategy-proofness and envy-freeness are jointly incompatible even with ex-post weak non-wastefulness.

Suggested Citation

  • Basteck, Christian & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    • Handle: RePEc:eee:jetheo:v:209:y:2023:i:c:s0022053123000145
    DOI: 10.1016/j.jet.2023.105618
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053123000145
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2023.105618?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. 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.
    2. Bogomolnaia, Anna, 2015. "Random assignment: Redefining the serial rule," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 308-318.
    3. Chambers, Christopher P., 2004. "Consistency in the probabilistic assignment model," Journal of Mathematical Economics, Elsevier, vol. 40(8), pages 953-962, December.
    4. Zhang, Jun, 2019. "Efficient and fair assignment mechanisms are strongly group manipulable," Journal of Economic Theory, Elsevier, vol. 180(C), pages 167-177.
    5. Bogomolnaia, Anna & Heo, Eun Jeong, 2012. "Probabilistic assignment of objects: Characterizing the serial rule," Journal of Economic Theory, Elsevier, vol. 147(5), pages 2072-2082.
    6. Erdil, Aytek, 2014. "Strategy-proof stochastic assignment," Journal of Economic Theory, Elsevier, vol. 151(C), pages 146-162.
    7. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    8. Mennle, Timo & Seuken, Sven, 2021. "Partial strategyproofness: Relaxing strategyproofness for the random assignment problem," Journal of Economic Theory, Elsevier, vol. 191(C).
    9. Basteck, Christian, 2018. "Fair solutions to the random assignment problem," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 163-172.
    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. 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. 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.
    13. 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.
    14. 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.
    15. McLennan, Andrew, 2002. "Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem," Journal of Economic Theory, Elsevier, vol. 105(2), pages 435-449, August.
    16. ,, 2009. "Asymptotic ordinal inefficiency of random serial dictatorship," Theoretical Economics, Econometric Society, vol. 4(2), June.
    17. Martini, Giorgio, 2016. "Strategy-proof and fair assignment is wasteful," Games and Economic Behavior, Elsevier, vol. 98(C), pages 172-179.
    18. 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.
    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. 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. 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.
    3. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).

    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 H., 2022. "Strategy-proof and envy-free random assignment," Discussion Papers, Research Unit: Market Behavior SP II 2022-208, WZB Berlin Social Science Center.
    2. Basteck, Christian & Ehlers, Lars, 2021. "Strategy-Proof and Envy-Free Random Assignment," Rationality and Competition Discussion Paper Series 307, CRC TRR 190 Rationality and Competition.
    3. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    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. Yajing Chen & Patrick Harless & Zhenhua Jiao, 2021. "The probabilistic rank random assignment rule and its axiomatic characterization," Papers 2104.09165, arXiv.org.
    10. 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.
    11. 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.
    12. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    13. Priyanka Shende & Manish Purohit, 2020. "Strategy-proof and Envy-free Mechanisms for House Allocation," Papers 2010.16384, arXiv.org.
    14. Youngsub Chun & Kiyong Yun, 2020. "Upper-contour strategy-proofness in the probabilistic assignment problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 667-687, April.
    15. Harless, Patrick, 2019. "Efficient rules for probabilistic assignment," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 107-116.
    16. Sulagna Dasgupta & Debasis Mishra, 2020. "Ordinal Bayesian incentive compatibility in random assignment model," Papers 2009.13104, arXiv.org, revised May 2021.
    17. Balbuzanov, Ivan, 2022. "Constrained random matching," Journal of Economic Theory, Elsevier, vol. 203(C).
    18. Haris Aziz & Yoichi Kasajima, 2017. "Impossibilities for probabilistic assignment," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 255-275, August.
    19. 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.
    20. Cho, Wonki Jo & Doğan, Battal, 2016. "Equivalence of efficiency notions for ordinal assignment problems," Economics Letters, Elsevier, vol. 146(C), pages 8-12.

    More about this item

    Keywords

    Random assignment; Strategy-proofness; Envy-freeness; q-unanimity;
    All these keywords.

    JEL classification:

    • D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
    • D70 - Microeconomics - - Analysis of Collective Decision-Making - - - General

    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:209:y:2023:i:c:s0022053123000145. 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.