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

Analyzing the price of fairness in scheduling problems with two agents

Author

Listed:
  • Yu, Jin
  • Liu, Peihai
  • Lu, Xiwen
  • Gu, Manzhan

Abstract

This paper focuses on the price of fairness in several scheduling problems with two agents, each with a set of nonpreemptive jobs, competing to execute their respective jobs on a single machine. Each agent expects to minimize its objective function, which depends on the completion times of its own jobs. Several objective functions are considered, including makespan, total (weighted) completion time and maximum tardiness. We focus on problems in which both agents pursue the same objective function. For each problem, we analyze the price of fairness and the complexity to find the fairness schedules among the Pareto optimal schedules. When the objective functions of both agents are total completion time, we design an algorithm to generate a near-fair solution and analyze its price of fairness.

Suggested Citation

  • Yu, Jin & Liu, Peihai & Lu, Xiwen & Gu, Manzhan, 2025. "Analyzing the price of fairness in scheduling problems with two agents," European Journal of Operational Research, Elsevier, vol. 321(3), pages 750-759.
    • Handle: RePEc:eee:ejores:v:321:y:2025:i:3:p:750-759
    DOI: 10.1016/j.ejor.2024.10.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724007987
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.10.023?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. 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.
    2. Šůcha, Přemysl & Agnetis, Alessandro & Šidlovský, Marko & Briand, Cyril, 2021. "Nash equilibrium solutions in multi-agent project scheduling with milestones," European Journal of Operational Research, Elsevier, vol. 294(1), pages 29-41.
    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. 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.
    5. Phosavanh, Johnson & Oron, Daniel, 2024. "Two-agent single-machine scheduling with a rate-modifying activity," European Journal of Operational Research, Elsevier, vol. 312(3), pages 866-876.
    6. Peter Bohm & Bjorn Larsen, 1994. "Fairness in a tradeable-permit treaty for carbon emissions reductions in Europe and the former Soviet Union," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 4(3), pages 219-239, June.
    7. Allesandro Agnetis & Pitu B. Mirchandani & Dario Pacciarelli & Andrea Pacifici, 2004. "Scheduling Problems with Two Competing Agents," Operations Research, INFORMS, vol. 52(2), pages 229-242, April.
    8. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    9. 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.
    10. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    11. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    12. Wellman, Michael P. & Walsh, William E. & Wurman, Peter R. & MacKie-Mason, Jeffrey K., 2001. "Auction Protocols for Decentralized Scheduling," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 271-303, April.
    13. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    14. 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.
    15. 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.
    16. Alessandro Agnetis & Dario Pacciarelli & Andrea Pacifici, 2007. "Multi-agent single machine scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 3-15, March.
    17. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    18. Dixit, Aasheesh & Choi, Tsan-Ming & Kumar, Patanjal & Jakhar, Suresh K., 2024. "Roles of reciprocity and fairness concerns in airline-airport systems with environmental considerations," European Journal of Operational Research, Elsevier, vol. 312(3), pages 1011-1023.
    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. 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.
    2. 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.
    3. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    4. 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.
    5. 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.
    6. 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.
    7. Gutjahr, Walter J., 2021. "Inequity-averse stochastic decision processes," European Journal of Operational Research, Elsevier, vol. 288(1), pages 258-270.
    8. 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.
    9. Zhang, Xingong, 2021. "Two competitive agents to minimize the weighted total late work and the total completion time," Applied Mathematics and Computation, Elsevier, vol. 406(C).
    10. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    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.
    12. Ö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.
    13. 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.
    14. Akoluk, Damla & Karsu, Özlem, 2022. "Ensuring multidimensional equality in public service," Socio-Economic Planning Sciences, Elsevier, vol. 80(C).
    15. Byung-Cheon Choi & Myoung-Ju Park, 2015. "A Batch Scheduling Problem with Two Agents," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-19, December.
    16. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    17. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    18. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    19. Yuan Zhang & Jinjiang Yuan, 2019. "A note on a two-agent scheduling problem related to the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 989-999, April.
    20. Nong, Q.Q. & Cheng, T.C.E. & Ng, C.T., 2011. "Two-agent scheduling to minimize the total cost," European Journal of Operational Research, Elsevier, vol. 215(1), pages 39-44, November.

    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:321:y:2025:i:3:p:750-759. 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.