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

Efficient and Envy-free Random Assignment Beyond Expected Utility

Author

Listed:
  • Patrick Becker
  • Felix Brandt
  • Satyanand Rammohan

Abstract

We consider the random assignment problem with abstract continuous and convex preferences. In particular, we admit preference relations that are not constrained by independence or transitivity. By extending the Hylland--Zeckhauser pseudo-market mechanism, we show that weakly efficient and envy-free random assignments always exist. For preferences that can be represented via skew-symmetric bilinear (SSB) utility functions -- which generalize linear expected utility functions -- we prove the existence of efficient and approximately envy-free random assignments. Efficient and envy-free random assignments exist under a mild additional assumption on preferences. These findings have notable implications for ordinal random assignment, where ordinal preferences are extended to preferences over lotteries via the pairwise comparison (PC) extension. While the probabilistic serial rule and popular random assignments frequently and significantly violate PC-efficiency and PC-envy-freeness, respectively, random assignments that satisfy both conditions do exist.

Suggested Citation

  • Patrick Becker & Felix Brandt & Satyanand Rammohan, 2026. "Efficient and Envy-free Random Assignment Beyond Expected Utility," Papers 2606.13730, arXiv.org.
    • Handle: RePEc:arx:papers:2606.13730
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. David J. Butler & Ganna Pogrebna, 2018. "Predictably intransitive preferences," Judgment and Decision Making, Society for Judgment and Decision Making, vol. 13(3), pages 217-236, May.
    2. Gale, D. & Mas-Colell, A., 1979. "Corrections to an equilibrium existence theorem for a general model without ordered preferences," Journal of Mathematical Economics, Elsevier, vol. 6(3), pages 297-298, December.
    3. Rubinstein, Ariel & Segal, Uzi, 2012. "On the likelihood of cyclic comparisons," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2483-2491.
    4. Moulin, Herve, 1988. "Condorcet's principle implies the no show paradox," Journal of Economic Theory, Elsevier, vol. 45(1), pages 53-64, June.
    5. Shafer, Wayne & Sonnenschein, Hugo, 1975. "Equilibrium in abstract economies without ordered preferences," Journal of Mathematical Economics, Elsevier, vol. 2(3), pages 345-348, December.
    6. Brandt, Felix & Lederer, Patrick & Suksompong, Warut, 2023. "Incentives in social decision schemes with pairwise comparison preferences," Games and Economic Behavior, Elsevier, vol. 142(C), pages 266-291.
    7. 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.
    8. Yinghua He & Antonio Miralles & Marek Pycia & Jianye Yan, 2018. "A Pseudo-Market Approach to Allocation with Priorities," American Economic Journal: Microeconomics, American Economic Association, vol. 10(3), pages 272-314, August.
    9. Pavlo Blavatskyy, 2006. "Axiomatization of a Preference for Most Probable Winner," Theory and Decision, Springer, vol. 60(1), pages 17-33, February.
    10. H. W. Kuhn, 1955. "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2(1‐2), pages 83-97, March.
    11. Cole, Richard & Tao, Yixin, 2021. "On the existence of Pareto Efficient and envy-free allocations," Journal of Economic Theory, Elsevier, vol. 193(C).
    12. Kazuhiro Hara & Efe A. Ok & Gil Riella, 2019. "Coalitional Expected Multi‐Utility Theory," Econometrica, Econometric Society, vol. 87(3), pages 933-980, May.
    13. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    14. Aziz, Haris & Brandl, Florian & Brandt, Felix, 2015. "Universal Pareto dominance and welfare for plausible utility functions," Journal of Mathematical Economics, Elsevier, vol. 60(C), pages 123-133.
    15. Florian Brandl & Felix Brandt, 2020. "Arrovian Aggregation of Convex Preferences," Econometrica, Econometric Society, vol. 88(2), pages 799-844, March.
    16. Jugal Garg & Yixin Tao & L'aszl'o A. V'egh, 2025. "Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms," Papers 2507.03359, arXiv.org, revised Feb 2026.
    17. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    18. Florian Brandl & Felix Brandt & Hans Georg Seedig, 2016. "Consistent Probabilistic Social Choice," Econometrica, Econometric Society, vol. 84, pages 1839-1880, September.
    19. Cho, Wonki Jo & Doğan, Battal, 2016. "Equivalence of efficiency notions for ordinal assignment problems," Economics Letters, Elsevier, vol. 146(C), pages 8-12.
    20. Fishburn, Peter C, 1991. "Nontransitive Preferences in Decision Theory," Journal of Risk and Uncertainty, Springer, vol. 4(2), pages 113-134, April.
    21. Butler, David J. & Pogrebna, Ganna, 2018. "Predictably intransitive preferences," Judgment and Decision Making, Cambridge University Press, vol. 13(3), pages 217-236, May.
    22. Sato, Norihisa, 2010. "Satiation and existence of competitive equilibrium," Journal of Mathematical Economics, Elsevier, vol. 46(4), pages 534-551, July.
    23. Walker, Mark, 1979. "A Generalization of the Maximum Theorem," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 20(1), pages 267-272, February.
    24. Llinares, Juan-Vicente, 1998. "Unified treatment of the problem of existence of maximal elements in binary relations: a characterization," Journal of Mathematical Economics, Elsevier, vol. 29(3), pages 285-302, April.
    25. Carroll, Gabriel, 2010. "An efficiency theorem for incompletely known preferences," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2463-2470, November.
    26. Machina, Mark J, 1989. "Dynamic Consistency and Non-expected Utility Models of Choice under Uncertainty," Journal of Economic Literature, American Economic Association, vol. 27(4), pages 1622-1668, December.
    27. 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.
    28. Antonio Miralles, 2017. "Ex-ante efficiency in assignments with seniority rights," Review of Economic Design, Springer;Society for Economic Design, vol. 21(1), pages 33-48, March.
    29. P. C. Fishburn, 1984. "Probabilistic Social Choice Based on Simple Voting Comparisons," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 51(4), pages 683-692.
    30. Anand, Paul, 1993. "The Philosophy of Intransitive Preference," Economic Journal, Royal Economic Society, vol. 103(417), pages 337-346, March.
    31. Anand, Paul & Pattanaik, Prasanta & Puppe, Clemens (ed.), 2009. "The Handbook of Rational and Social Choice," OUP Catalogue, Oxford University Press, number 9780199290420.
    32. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    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. Florian Brandl & Felix Brandt, 2020. "Arrovian Aggregation of Convex Preferences," Econometrica, Econometric Society, vol. 88(2), pages 799-844, March.
    2. Brandl, Florian & Brandt, Felix & Hofbauer, Johannes, 2019. "Welfare maximization entices participation," Games and Economic Behavior, Elsevier, vol. 114(C), pages 308-314.
    3. Brandt, Felix & Lederer, Patrick & Suksompong, Warut, 2023. "Incentives in social decision schemes with pairwise comparison preferences," Games and Economic Behavior, Elsevier, vol. 142(C), pages 266-291.
    4. 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.
    5. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    6. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    7. Florian Brandl & Felix Brandt & Christian Stricker, 2022. "An analytical and experimental comparison of maximal lottery schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(1), pages 5-38, January.
    8. Brandl, Florian & Brandt, Felix, 2024. "A natural adaptive process for collective decision-making," Theoretical Economics, Econometric Society, vol. 19(2), May.
    9. Felix Brandt & Patrick Lederer & Warut Suksompong, 2022. "Incentives in Social Decision Schemes with Pairwise Comparison Preferences," Papers 2204.12436, arXiv.org, revised Aug 2024.
    10. Th`anh Nguyen & Alexander Teytelboym & Shai Vardi, 2025. "Efficiency, Envy, and Incentives in Combinatorial Assignment," Papers 2509.13198, arXiv.org, revised Oct 2025.
    11. Aziz, Haris & Brandl, Florian & Brandt, Felix, 2015. "Universal Pareto dominance and welfare for plausible utility functions," Journal of Mathematical Economics, Elsevier, vol. 60(C), pages 123-133.
    12. Florian Brandl & Felix Brandt, 2021. "A Natural Adaptive Process for Collective Decision-Making," Papers 2103.14351, arXiv.org, revised Mar 2024.
    13. Roberto-Rafael Maura-Rivero & Marc Lanctot & Francesco Visin & Kate Larson, 2025. "Jackpot! Alignment as a Maximal Lottery," Papers 2501.19266, arXiv.org.
    14. Felix Brandt & Marie Matthäus & Christian Saile, 2022. "Minimal voting paradoxes," Journal of Theoretical Politics, , vol. 34(4), pages 527-551, October.
    15. Chambers, Christopher P. & Echenique, Federico, 2025. "Empirical welfare economics," Theoretical Economics, Econometric Society, vol. 20(3), July.
    16. Jugal Garg & Yixin Tao & L'aszl'o A. V'egh, 2025. "Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms," Papers 2507.03359, arXiv.org, revised Feb 2026.
    17. Aziz, Haris & Brandl, Florian, 2022. "The vigilant eating rule: A general approach for probabilistic economic design with constraints," Games and Economic Behavior, Elsevier, vol. 135(C), pages 168-187.
    18. Daniel Kornbluth & Alexey Kushnir, 2024. "Undergraduate Course Allocation through Competitive Markets," Papers 2412.05691, arXiv.org, revised Dec 2025.
    19. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2017. "Competitive Division of a Mixed Manna," Econometrica, Econometric Society, vol. 85(6), pages 1847-1871, November.
    20. Schlee, Edward E. & Ali Khan, M., 2023. "Money-metrics in local welfare analysis: Pareto improvements and equity considerations," Journal of Economic Theory, Elsevier, vol. 213(C).

    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:2606.13730. 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: https://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.