Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/9891
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
Scheduling
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.
URI: http://hdl.handle.net/10397/9891
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2015.06.005
Appears in Collections:Journal/Magazine Article

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

Page view(s)

47
Last Week
5
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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