The price of fairness for a two-agent scheduling game minimizing total completion time

Yubai Zhang, Zhao Zhang () and Zhaohui Liu ()
Additional contact information
Yubai Zhang: East China University of Science and Technology
Zhao Zhang: Zhejiang Normal University
Zhaohui Liu: East China University of Science and Technology

Journal of Combinatorial Optimization, No 0, 19 pages

Abstract: Abstract This paper studies the price of fairness in a two-agent single machine scheduling game. In this game, two agents compete to perform their jobs on a common single machine. Both of the two agents want to minimize their own total completion time. One of them has exactly two jobs. All processing times are positive. We show that all Kalai-Smorodinsky fair schedules can be found in linear time, and its price of fairness equals a half.

Keywords: Price of fairness; Scheduling problem; KS-fair (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00581-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00581-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00581-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().