IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v257y2017i3p933-943.html
   My bibliography  Save this article

Price of Fairness for allocating a bounded resource

Author

Listed:
  • Nicosia, Gaia
  • Pacifici, Andrea
  • Pferschy, Ulrich

Abstract

We study the problem faced by a decision maker who wants to allocate a scarce resource among several agents in order to maximize the total utility. An optimal solution may present a very unbalanced allocation of the resource to the agents and hence be perceived as unfair. On the other hand balanced allocations may be far from the optimum. In this paper we are interested in assessing the quality of fair solutions, i.e., in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the total utility. This indicator is called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai–Smorodinski and proportional fairness.

Suggested Citation

  • Nicosia, Gaia & Pacifici, Andrea & Pferschy, Ulrich, 2017. "Price of Fairness for allocating a bounded resource," European Journal of Operational Research, Elsevier, vol. 257(3), pages 933-943.
    • Handle: RePEc:eee:ejores:v:257:y:2017:i:3:p:933-943
    DOI: 10.1016/j.ejor.2016.08.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716306282
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.08.013?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. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    2. Dahmani, Isma & Hifi, Mhand & Wu, Lei, 2016. "An exact decomposition algorithm for the generalized knapsack sharing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 761-774.
    3. Kalai, Ehud & Smorodinsky, Meir, 1975. "Other Solutions to Nash's Bargaining Problem," Econometrica, Econometric Society, vol. 43(3), pages 513-518, May.
    4. M Butler & H P Williams, 2002. "Fairness versus efficiency in charging for the use of common facilities," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(12), pages 1324-1329, December.
    5. Fujimoto, Masako & Yamada, Takeo, 2006. "An exact algorithm for the knapsack sharing problem with common items," European Journal of Operational Research, Elsevier, vol. 171(2), pages 693-707, June.
    6. Butler, Martin & Williams, H. Paul, 2002. "Fairness versus efficiency in charging for the use of common facilities," LSE Research Online Documents on Economics 18399, London School of Economics and Political Science, LSE Library.
    7. George Kozanidis & Emanuel Melachrinoudis & Marius M. Solomon, 2005. "The linear multiple choice knapsack problem with equity constraints," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 1(1/2), pages 52-73.
    8. Darmann, Andreas & Nicosia, Gaia & Pferschy, Ulrich & Schauer, Joachim, 2014. "The Subset Sum game," European Journal of Operational Research, Elsevier, vol. 233(3), pages 539-549.
    9. George Kozanidis, 2009. "Solving the linear multiple choice knapsack problem with two objectives: profit and equity," Computational Optimization and Applications, Springer, vol. 43(2), pages 261-294, June.
    10. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yubai Zhang & Zhao Zhang & Zhaohui Liu, 0. "The price of fairness for a two-agent scheduling game minimizing total completion time," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-19.
    2. 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.
    3. Aringhieri, Roberto & Duma, Davide & Landa, Paolo & Mancini, Simona, 2022. "Combining workload balance and patient priority maximisation in operating room planning through hierarchical multi-objective optimisation," European Journal of Operational Research, Elsevier, vol. 298(2), pages 627-643.
    4. Aziz, Haris & Huang, Xin & Mattei, Nicholas & Segal-Halevi, Erel, 2023. "Computing welfare-Maximizing fair allocations of indivisible goods," European Journal of Operational Research, Elsevier, vol. 307(2), pages 773-784.
    5. Akoluk, Damla & Karsu, Özlem, 2022. "Ensuring multidimensional equality in public service," Socio-Economic Planning Sciences, Elsevier, vol. 80(C).
    6. 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.
    7. Gutjahr, Walter J., 2021. "Inequity-averse stochastic decision processes," European Journal of Operational Research, Elsevier, vol. 288(1), pages 258-270.
    8. Naldi, Maurizio & Nicosia, Gaia & Pacifici, Andrea & Pferschy, Ulrich, 2019. "Profit-fairness trade-off in project selection," Socio-Economic Planning Sciences, Elsevier, vol. 67(C), pages 133-146.
    9. Nahid Rezaeinia & Julio César Góez & Mario Guajardo, 2022. "Efficiency and fairness criteria in the assignment of students to projects," Annals of Operations Research, Springer, vol. 319(2), pages 1717-1735, December.
    10. Sun, Lishan & Lu, Huabo & Xu, Yan & Kong, Dewen & Shao, Juan, 2022. "Fairness-oriented train service design for urban rail transit cross-line operation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    11. Yubai Zhang & Zhao Zhang & Zhaohui Liu, 2022. "The price of fairness for a two-agent scheduling game minimizing total completion time," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2104-2122, October.
    12. Pferschy, Ulrich & Nicosia, Gaia & Pacifici, Andrea & Schauer, Joachim, 2021. "On the Stackelberg knapsack game," European Journal of Operational Research, Elsevier, vol. 291(1), pages 18-31.
    13. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.
    14. Roberto Aringhieri & Sara Bigharaz & Davide Duma & Alberto Guastalla, 2022. "Fairness in ambulance routing for post disaster management," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(1), pages 189-211, March.

    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. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2012. "On the Efficiency-Fairness Trade-off," Management Science, INFORMS, vol. 58(12), pages 2234-2250, December.
    2. Naldi, Maurizio & Nicosia, Gaia & Pacifici, Andrea & Pferschy, Ulrich, 2019. "Profit-fairness trade-off in project selection," Socio-Economic Planning Sciences, Elsevier, vol. 67(C), pages 133-146.
    3. 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.
    4. Tom Demeulemeester & Dries Goossens & Ben Hermans & Roel Leus, 2023. "Fair integer programming under dichotomous and cardinal preferences," Papers 2306.13383, arXiv.org, revised Apr 2024.
    5. Hrayer Aprahamian & Douglas R. Bish & Ebru K. Bish, 2019. "Optimal Risk-Based Group Testing," Management Science, INFORMS, vol. 65(9), pages 4365-4384, September.
    6. Breugem, Thomas & Van Wassenhove, Luk N., 2022. "The price of imposing vertical equity through asymmetric outcome constraints," Other publications TiSEM b6e85652-c54a-4597-a32e-d, Tilburg University, School of Economics and Management.
    7. Holland, Luke M. & Doole, Graeme J., 2014. "Implications of fairness for the design of nitrate leaching policy for heterogeneous New Zealand dairy farms," Agricultural Water Management, Elsevier, vol. 132(C), pages 79-88.
    8. Feimin Zhong & Jinxing Xie & Xiaobo Zhao, 2014. "The price of fairness with the extended Perles–Maschler solution," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 80(2), pages 193-212, October.
    9. Özlem Karsu & Hale Erkan, 2020. "Balance in resource allocation problems: a changing reference approach," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 297-326, March.
    10. 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.
    11. 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.
    12. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    13. Gur, Yonatan & Iancu, Dan & Warnes, Xavier, 2020. "Value Loss in Allocation Systems with Provider Guarantees," Research Papers 3813, Stanford University, Graduate School of Business.
    14. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.
    15. Wolbeck, Lena Antonia, 2019. "Fairness aspects in personnel scheduling," Discussion Papers 2019/16, Free University Berlin, School of Business & Economics.
    16. Alexandre Jacquillat & Vikrant Vaze, 2018. "Interairline Equity in Airport Scheduling Interventions," Transportation Science, INFORMS, vol. 52(4), pages 941-964, August.
    17. 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.
    18. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    19. 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.
    20. Rachmilevitch, Shiran, 2015. "Nash bargaining with (almost) no rationality," Mathematical Social Sciences, Elsevier, vol. 76(C), pages 107-109.

    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:ejores:v:257:y:2017:i:3:p:933-943. 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/eor .

    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.