Paper Info
Title
The price of anarchy for utilitarian scheduling games on related machines.
Abstract
We present bounds on the efficiency of Nash equilibria in a scheduling game where jobs are players who choose a machine out of a set of machines to be processed on. Machines may have different speeds, and sequence the jobs in shortest processing time first order. When players selfishly choose a machine to minimize their own completion time, we analyze the price of anarchy for the sum of the completion times of the jobs. We show that it is bounded from below by e∕(e−1)≈1.58 and from above by 2.
Year
DOI
Venue
2019
10.1016/j.disopt.2018.08.001
Discrete Optimization
Keywords
Field
DocType
Price of anarchy,Scheduling,Utilitarian,Related machines
Mathematical optimization,First order,Scheduling (computing),Price of anarchy,Nash equilibrium,Mathematics,Bounded function
Journal
Volume
ISSN
Citations 
31
1572-5286
0
PageRank 
References 
Authors
0.34
14
2
Name
Order
Citations
PageRank
Ruben Hoeksma1338.23
Marc Uetz245643.99