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

Simultaneous Envy and Equitability Guarantees

Author

Listed:
  • Hadi Hosseini
  • Shraddha Pathak
  • Lirong Xia
  • Chengkai Zhang

Abstract

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

Suggested Citation

  • Hadi Hosseini & Shraddha Pathak & Lirong Xia & Chengkai Zhang, 2026. "Simultaneous Envy and Equitability Guarantees," Papers 2608.26410, arXiv.org, revised Sep 2026.
    • Handle: RePEc:arx:papers:2608.26410
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Wentao He & Biaoshuai Tao, 2026. "EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence," Papers 2606.08872, arXiv.org, revised Jul 2026.
    2. Simon Mackenzie & Mashbat Suzuki, 2026. "Counterexamples to EFX for Submodular and Subadditive Valuations," Papers 2605.06451, arXiv.org.
    3. 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.
    4. Haris Aziz & Rupert Freeman & Nisarg Shah & Rohit Vaish, 2024. "Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation," Operations Research, INFORMS, vol. 72(4), pages 1674-1688, July.
    5. Sun, Ankang & Chen, Bo, 2025. "Randomized strategyproof mechanisms with best of both worlds fairness and efficiency," European Journal of Operational Research, Elsevier, vol. 324(3), pages 941-952.
    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. Th`anh Nguyen & Alexander Teytelboym & Shai Vardi, 2025. "Efficiency, Envy, and Incentives in Combinatorial Assignment," Papers 2509.13198, arXiv.org, revised Oct 2025.
    2. Ayumi Igarashi & Naoyuki Kamiyama & Yasushi Kawase & Warut Suksompong & Hanna Sumita & Yu Yokoi, 2025. "Two-Sided Fairness in Many-to-One Matching," Papers 2509.24111, arXiv.org.
    3. Ioannis Caragiannis & Panagiotis Kanellopoulos & Maria Kyropoulou, 2025. "On Interim Envy-Free Allocation Lotteries," Mathematics of Operations Research, INFORMS, vol. 50(4), pages 3257-3282, November.
    4. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.
    5. Aygün, Orhan & Turhan, Bertan, 2021. "How to De-reserve Reserves," ISU General Staff Papers 202103100800001123, Iowa State University, Department of Economics.
    6. Parag A. Pathak & Alex Rees-Jones & Tayfun Sönmez, 2025. "Immigration Lottery Design: Engineered and Coincidental Consequences of H-1B Reforms," The Review of Economics and Statistics, MIT Press, vol. 107(1), pages 1-13, January.
    7. Shai Vardi & Alexandros Psomas & Eric Friedman, 2022. "Dynamic Fair Resource Division," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 945-968, May.
    8. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    9. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Mar 2025.
    10. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    11. Eric Budish & Gérard P. Cachon & Judd B. Kessler & Abraham Othman, 2017. "Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation," Operations Research, INFORMS, vol. 65(2), pages 314-336, April.
    12. Bhaskar Ray Chaudhury & Jugal Garg & Kurt Mehlhorn & Ruta Mehta & Pranabendu Misra, 2024. "Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2323-2340, November.
    13. Parag A. Pathak & Tayfun Sönmez & M. Utku Ünver & M. Bumin Yenmez, 2024. "Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Healthcare Rationing," Management Science, INFORMS, vol. 70(6), pages 3999-4036, June.
    14. Anna Bogomolnaia & Hervé Moulin, 2023. "Guarantees in Fair Division: General or Monotone Preferences," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 160-176, February.
    15. Dur, Umut Mert & Wiseman, Thomas, 2019. "School choice with neighbors," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 101-109.
    16. Romero-Medina, Antonio & Triossi, Matteo, 2024. "Strategic priority-based course allocation," Journal of Economic Behavior & Organization, Elsevier, vol. 226(C).
    17. Eun Jeong Heo & Vikram Manjunath, 2017. "Implementation in stochastic dominance Nash equilibria," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 5-30, January.
    18. Antonio Miralles & Marek Pycia, 2017. "Large vs. Continuum Assignment Economies: Efficiency and Envy-Freeness," Working Papers 950, Barcelona School of Economics.
    19. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    20. Condorelli, Daniele, 2013. "Market and non-market mechanisms for the optimal allocation of scarce resources," Games and Economic Behavior, Elsevier, vol. 82(C), pages 582-591.

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