IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i2p945-968.html

Dynamic Fair Resource Division

Author

Listed:
  • Shai Vardi

    (Krannert School of Management, Purdue University, West Lafayette, Indiana 47907)

  • Alexandros Psomas

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

  • Eric Friedman

    (International Computer Science Institute and Electrical Engineering and Computer Sciences Department, Berkeley, California 94704)

Abstract

A single homogeneous resource needs to be fairly shared between users that dynamically arrive and depart over time. Although good allocations exist for any fixed number of users, implementing these allocations dynamically is impractical: it typically entails adjustments in the allocation of every user in the system whenever a new user arrives. We introduce a dynamic fair resource division problem in which there is a limit on the number of users that can be disrupted when a new user arrives and study the trade-off between fairness and the number of allowed disruptions, using a fairness metric: the fairness ratio . We almost completely characterize this trade-off and give an algorithm for obtaining the optimal fairness for any number of allowed disruptions.

Suggested Citation

  • Shai Vardi & Alexandros Psomas & Eric Friedman, 2022. "Dynamic Fair Resource Division," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 945-968, May.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:2:p:945-968
    DOI: 10.1287/moor.2021.1155
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1155
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1155?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. Lindsley G. Boiney, 1995. "When Efficient Is Insufficient: Fairness in Decisions Affecting a Group," Management Science, INFORMS, vol. 41(9), pages 1523-1537, September.
    2. Peter C. Fishburn & Rakesh K. Sarin, 1994. "Fairness and Social Risk I: Unaggregated Analyses," Management Science, INFORMS, vol. 40(9), pages 1174-1188, September.
    3. Hervé Moulin & Richard Stong, 2002. "Fair Queuing and Other Probabilistic Allocation Methods," Mathematics of Operations Research, INFORMS, vol. 27(1), pages 1-30, February.
    4. Elisha A. Pazner & David Schmeidler, 1978. "Egalitarian Equivalent Allocations: A New Concept of Economic Equity," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 92(4), pages 671-687.
    5. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2007. "Fast, Fair, and Efficient Flows in Networks," Operations Research, INFORMS, vol. 55(2), pages 215-225, April.
    6. Woonghee Tim Huh & Nan Liu & Van-Anh Truong, 2013. "Multiresource Allocation Scheduling in Dynamic Environments," Manufacturing & Service Operations Management, INFORMS, vol. 15(2), pages 280-291, May.
    7. Reza H. Ahmadi & Sriram Dasu & Christopher S. Tang, 1992. "The Dynamic Line Allocation Problem," Management Science, INFORMS, vol. 38(9), pages 1341-1353, September.
    8. Frank Karsten & Marco Slikker & Geert-Jan van Houtum, 2015. "Resource Pooling and Cost Allocation Among Independent Service Providers," Operations Research, INFORMS, vol. 63(2), pages 476-488, April.
    9. 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.
    10. Tony Haitao Cui & Jagmohan S. Raju & Z. John Zhang, 2007. "Fairness and Channel Coordination," Management Science, INFORMS, vol. 53(8), pages 1303-1314, August.
    11. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    12. 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.
    13. Huseyin Topaloglu & Warren B. Powell, 2005. "A Distributed Decision-Making Structure for Dynamic Resource Allocation Using Nonlinear Functional Approximations," Operations Research, INFORMS, vol. 53(2), pages 281-297, April.
    14. Dragos Florin Ciocan & Vivek Farias, 2012. "Model Predictive Control for Dynamic Resource Allocation," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 501-525, August.
    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. 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.
    2. Gerdus Benadè & Daniel Halpern & Alexandros Psomas, 2025. "Dynamic Fair Division with Partial Information," Operations Research, INFORMS, vol. 73(4), pages 1876-1896, July.

    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. 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.
    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. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    5. Gur, Yonatan & Iancu, Dan & Warnes, Xavier, 2020. "Value Loss in Allocation Systems with Provider Guarantees," Research Papers 3813, Stanford University, Graduate School of Business.
    6. 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.
    7. Agnetis, Alessandro & Chen, Bo & Nicosia, Gaia & Pacifici, Andrea, 2019. "Price of fairness in two-agent single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 276(1), pages 79-87.
    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. Mackenzie, Andrew & Komornik, Vilmos, 2023. "Fairly taking turns," Games and Economic Behavior, Elsevier, vol. 142(C), pages 743-764.
    10. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Xie, Ying, 2022. "Service fairness and value of customer information for the stochastic container relocation problem under flexible service policy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    11. LAMAS, ALEJANDRO & CHEVALIER, Philippe, 2013. "Jumping the hurdles for collaboration: fairness in operations pooling in the absence of transfer payments," LIDAM Discussion Papers CORE 2013073, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Gülpınar, Nalan & Çanakoğlu, Ethem & Branke, Juergen, 2018. "Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities," European Journal of Operational Research, Elsevier, vol. 266(1), pages 291-303.
    13. Hyunwoo Lee & Seokhyun Chung & Taesu Cheong & Sang Hwa Song, 2018. "Accounting for Fairness in a Two-Stage Stochastic Programming Model for Kidney Exchange Programs," IJERPH, MDPI, vol. 15(7), pages 1-16, July.
    14. Hussein El Hajj & Douglas R. Bish & Ebru K. Bish, 2021. "Equity in genetic newborn screening," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(1), pages 44-64, February.
    15. Yinchu Zhu & Ilya O. Ryzhov, 2022. "Optimal data-driven hiring with equity for underrepresented groups," Papers 2206.09300, arXiv.org.
    16. Vahideh Manshadi & Rad Niazadeh & Scott Rodilitz, 2023. "Fair Dynamic Rationing," Management Science, INFORMS, vol. 69(11), pages 6818-6836, November.
    17. Puyao Ge & Vidyadhar G. Kulkarni & Jayashankar M. Swaminathan, 2026. "Optimal Allocation of Limited Inventory Among Multiclass Customers with Finite Populations," Operations Research, INFORMS, vol. 74(1), pages 25-35, January.
    18. 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.
    19. 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.
    20. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaia, 2019. "Dividing bads under additive utilities," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 52(3), pages 395-417, March.

    More about this item

    Keywords

    ;
    ;
    ;

    JEL classification:

    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:ormoor:v:47:y:2022:i:2:p:945-968. 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.