IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v72y2024i4p1438-1452.html

Fair and Efficient Online Allocations

Author

Listed:
  • Gerdus Benadè

    (Questrom School of Business, Boston University, Boston, Massachusetts 02215)

  • Aleksandr M. Kazachkov

    (Department of Industrial & Systems Engineering, University of Florida, Gainesville, Florida 32611)

  • Ariel D. Procaccia

    (School of Engineering and Applied Sciences, Harvard University, Boston, Massachusetts 02134)

  • Alexandros Psomas

    (Department of Computer Science, Purdue University, West Lafayette, Indiana 47907)

  • David Zeng

    (Jane Street Capital, New York, New York 10281)

Abstract

We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another’s allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions, it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy free up to one good or envy free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto-efficient fractional allocation that is strongly envy free with respect to pairs of agents with substantially different utilities while allocating identical bundles to agents with identical utilities (up to multiplicative factors).

Suggested Citation

  • Gerdus Benadè & Aleksandr M. Kazachkov & Ariel D. Procaccia & Alexandros Psomas & David Zeng, 2024. "Fair and Efficient Online Allocations," Operations Research, INFORMS, vol. 72(4), pages 1438-1452, July.
    • Handle: RePEc:inm:oropre:v:72:y:2024:i:4:p:1438-1452
    DOI: 10.1287/opre.2022.0332
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2022.0332
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2022.0332?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. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy, 2022. "On the Fair Division of a Random Object," Management Science, INFORMS, vol. 68(2), pages 1174-1194, February.
    2. MohammadHossein Bateni & Yiwei Chen & Dragos Florin Ciocan & Vahab Mirrokni, 2022. "Fair Resource Allocation in a Volatile Marketplace," Operations Research, INFORMS, vol. 70(1), pages 288-308, January.
    3. Holmes E. Miller & William P. Pierskalla & Gustave J. Rath, 1976. "Nurse Scheduling Using Mathematical Programming," Operations Research, INFORMS, vol. 24(5), pages 857-870, October.
    4. Mor Armony & Amy R. Ward, 2010. "Fair Dynamic Routing in Large-Scale Heterogeneous-Server Systems," Operations Research, INFORMS, vol. 58(3), pages 624-637, June.
    5. Varian, Hal R., 1974. "Equity, envy, and efficiency," Journal of Economic Theory, Elsevier, vol. 9(1), pages 63-91, September.
    6. Shai Vardi & Alexandros Psomas & Eric Friedman, 2022. "Dynamic Fair Resource Division," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 945-968, May.
    7. 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.
    8. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    9. Xuanming Su & Stefanos A. Zenios, 2006. "Recipient Choice Can Address the Efficiency-Equity Trade-off in Kidney Transplantation: A Mechanism Design Model," Management Science, INFORMS, vol. 52(11), pages 1647-1660, November.
    10. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2013. "Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation," Operations Research, INFORMS, vol. 61(1), pages 73-87, February.
    11. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2012. "On the Efficiency-Fairness Trade-off," Management Science, INFORMS, vol. 58(12), pages 2234-2250, December.
    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. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    2. MohammadHossein Bateni & Yiwei Chen & Dragos Florin Ciocan & Vahab Mirrokni, 2022. "Fair Resource Allocation in a Volatile Marketplace," Operations Research, INFORMS, vol. 70(1), pages 288-308, January.
    3. Marta Boczoń & Alistair J. Wilson, 2023. "Goals, Constraints, and Transparently Fair Assignments: A Field Study of Randomization Design in the UEFA Champions League," Management Science, INFORMS, vol. 69(6), pages 3474-3491, June.
    4. Shai Vardi & Alexandros Psomas & Eric Friedman, 2022. "Dynamic Fair Resource Division," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 945-968, May.
    5. Refael Hassin & Adam Nathaniel, 2021. "Self-Selected Task Allocation," Manufacturing & Service Operations Management, INFORMS, vol. 23(6), pages 1669-1682, November.
    6. Gur, Yonatan & Iancu, Dan & Warnes, Xavier, 2020. "Value Loss in Allocation Systems with Provider Guarantees," Research Papers 3813, Stanford University, Graduate School of Business.
    7. Zongsen Yang & Xingyu Fu & Pin Gao & Ying-Ju Chen, 2024. "Fairness Regulation of Prices in Competitive Markets," Manufacturing & Service Operations Management, INFORMS, vol. 26(5), pages 1897-1917, September.
    8. John P. Dickerson & Ariel D. Procaccia & Tuomas Sandholm, 2019. "Failure-Aware Kidney Exchange," Management Science, INFORMS, vol. 65(4), pages 1768-1791, April.
    9. Shubham Akshat & Liye Ma & S. Raghavan, 2023. "Improving Broader Sharing to Address Geographic Inequity in Liver Transplantation," Manufacturing & Service Operations Management, INFORMS, vol. 25(4), pages 1509-1526, July.
    10. Yanhan (Savannah) Tang & Alan Scheller-Wolf & Sridhar Tayur & Emily R. Perito & John P. Roberts, 2025. "Split Liver Transplantation: An Analytical Decision Support Model," Operations Research, INFORMS, vol. 73(4), pages 1785-1804, July.
    11. Fedor Sandomirskiy & Erel Segal-Halevi, 2022. "Efficient Fair Division with Minimal Sharing," Operations Research, INFORMS, vol. 70(3), pages 1762-1782, May.
    12. Priyank Arora & Wei Wei & Senay Solak, 2021. "Improving Outcomes in Child Care Subsidy Voucher Programs under Regional Asymmetries," Production and Operations Management, Production and Operations Management Society, vol. 30(12), pages 4435-4454, December.
    13. Chen, Qingxin & Fu, Chenyi & Zhu, Ning & Ma, Shoufeng & He, Qiao-Chu, 2023. "A target-based optimization model for bike-sharing systems: From the perspective of service efficiency and equity," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 235-260.
    14. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2012. "On the Efficiency-Fairness Trade-off," Management Science, INFORMS, vol. 58(12), pages 2234-2250, December.
    15. 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.
    16. Yonatan Gur & Dan Iancu & Xavier Warnes, 2021. "Value Loss in Allocation Systems with Provider Guarantees," Management Science, INFORMS, vol. 67(6), pages 3757-3784, June.
    17. Thomas Breugem & Twan Dollevoet & Dennis Huisman, 2022. "Is Equality Always Desirable? Analyzing the Trade-Off Between Fairness and Attractiveness in Crew Rostering," Management Science, INFORMS, vol. 68(4), pages 2619-2641, April.
    18. Thomas Breugem & Luk N. Van Wassenhove, 2022. "The Price of Imposing Vertical Equity Through Asymmetric Outcome Constraints," Management Science, INFORMS, vol. 68(11), pages 7977-7993, November.
    19. Fadaki, Masih & Ansari, Sina & Abareshi, Ahmad & Lee, Paul Tae-Woo, 2025. "Sequential resource allocation for humanitarian operations using approximate dynamic programming," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 201(C).
    20. Rupert Freeman & Jens Witkowski & Jennifer Wortman Vaughan & David M. Pennock, 2024. "An Equivalence Between Fair Division and Wagering Mechanisms," Management Science, INFORMS, vol. 70(10), pages 6704-6723, October.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    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:inm:oropre:v:72:y:2024:i:4:p:1438-1452. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.