Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436599 | Theoretical Computer Science | 2014 | 12 Pages |
Abstract
In this paper, we revisit the inefficiency of Nash Equilibrium of scheduling games by considering the Price of Anarchy (PoA) as a function of r , which is the ratio between the maximum and minimum size of jobs. For the social costs of minimizing makespan and maximizing the minimum machine load of all machines, we obtain the PoA for two and three machines, and the bound is tight for any r⩾1r⩾1. Lower bounds on the PoA for general number of machines are also presented.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ling Lin, Zhiyi Tan,