Publication Type

Journal Article

Version

acceptedVersion

Publication Date

2009

Abstract

Game 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.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Publication

Web Intelligence and Agent Systems

Volume

7

Issue

4

First Page

321

Last Page

332

ISSN

1570-1263

Identifier

10.3233/WIA-2009-0171

Publisher

IOS Press

Additional URL

http://dx.doi.org/10.3233/WIA-2009-0171

Download

Share

COinS