Please use this identifier to cite or link to this item: https://doi.org/10.3233/WIA-2009-0171
DC FieldValue
dc.titleThe price of stability in selfish scheduling games
dc.contributor.authorAgussurja, L.
dc.contributor.authorLau, H.C.
dc.date.accessioned2014-11-28T08:43:00Z
dc.date.available2014-11-28T08:43:00Z
dc.date.issued2009
dc.identifier.citationAgussurja, L.,Lau, H.C. (2009). The price of stability in selfish scheduling games. Web Intelligence and Agent Systems 7 (4) : 321-332. ScholarBank@NUS Repository. <a href="https://doi.org/10.3233/WIA-2009-0171" target="_blank">https://doi.org/10.3233/WIA-2009-0171</a>
dc.identifier.issn15701263
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/112994
dc.description.abstractGame theory has gained popularity as an approach to analysing and understanding distributed systems with self-interested agents. Central to game theory is the concept of Nash equilibrium as a stable state (solution) of the system, which comes with a price - the loss in efficiency. The quantification of the efficiency loss is one of the main research concerns. In this paper, we study the quality and computational characteristics of the best Nash equilibrium in two selfish scheduling models: the congestion model and the sequencing model. In particular, we present the following results: (1) In the congestion model: first, the best Nash equilibrium is socially optimum and consequently, computing the best Nash is NP-hard; second, any ε-approximation algorithm for finding the optimum can be transformed into an ε-approximation algorithm for the best Nash. (2) In sequencing model: for identical machines, we show that the best Nash is no better than the worst Nash and it is easy to compute; for related machines, we show that there is a gap between the worst and the best Nash equilibrium, and leave the analytical bound of this gap for future work. © 2009 - IOS Press and the authors. All rights reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.3233/WIA-2009-0171
dc.sourceScopus
dc.subjectPrice of stability
dc.subjectScheduling games
dc.typeArticle
dc.contributor.departmentTHE LOGISTICS INSTITUTE - ASIA PACIFIC
dc.description.doi10.3233/WIA-2009-0171
dc.description.sourcetitleWeb Intelligence and Agent Systems
dc.description.volume7
dc.description.issue4
dc.description.page321-332
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Feb 1, 2023

Page view(s)

105
checked on Feb 2, 2023

Google ScholarTM

Check

Altmetric


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