Stability and fairness in the job scheduling problem
Eric Bahel () and
Christian Trudeau ()
No 1803, Working Papers from University of Windsor, Department of Economics
The job scheduling problem is a classic operational research problem in which agents have jobs to be executed by machines in given time slots, with each machine being able to process only one job at a time. We study this problem using cooperative game theory, focusing on how to divide the minimum cost (of executing all jobs) between the agents. First, we characterize the set of stable allocations, which all charge only users whose jobs are executed in peak-demand time periods. Second, using properties designed to avoid strategic mergers or splits of the jobs, we offer axiomatizations for two remarkable stable allocation rules. Third, observing that all stable rules fail Unanimity Lower Bound (ULB), a property requiring that everybody pay an equal share of the first machine (since it is needed by all), we study and axiomatize the Shapley value, which satisfies ULB. A compromise is then proposed between Stability and ULB.
Keywords: game theory; cost sharing; job scheduling; stability; unanimity lower bound; Shapley value. (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-des and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
http://web2.uwindsor.ca/economics/RePEc/wis/pdf/1803.pdf First version, 2018 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:wis:wpaper:1803
Access Statistics for this paper
More papers in Working Papers from University of Windsor, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Christian Trudeau ().