Please use this identifier to cite or link to this item:
Title: Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
Authors: Wu, Y
Cheng, TCE 
Ji, M
Keywords: Hierarchy
Nash equilibrium
Price of anarchy
Price of stability
Issue Date: 2015
Publisher: Elsevier
Source: Information processing letters, 2015, v. 115, no. 11, p. 838-844 How to cite?
Journal: Information Processing Letters 
Abstract: Abstract This paper studies the selfish scheduling game on two hierarchical uniform machines where the jobs are correspondingly classified into two hierarchical classes. The cost of a job is defined as the completion time of the machine to which it is assigned. Each selfish job is interested in minimizing its own cost, while the game seeks to meet the social objective of maximizing the machine cover. We obtain the (strong) price of anarchy and the (strong) price of stability as functions of the ratio between the speeds of the two machines s. We show that all the derived bounds are tight for any value of s, thus completely solving the problem of measuring the inefficiency of the Nash equilibrium on two hierarchical uniform machines.
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2015.06.005
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 11, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.