The Price of Stability in Selfish Scheduling Games
Game theory has gained popularity as an approach to analysing and understanding distributed systems with selfinterested 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...
Saved in:
Main Authors: | , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2007
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/261 https://ink.library.smu.edu.sg/context/sis_research/article/1260/viewcontent/The_Price_of_Stability_in_Selfish_Scheduling_Games.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-1260 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-12602018-12-07T02:07:13Z The Price of Stability in Selfish Scheduling Games AGUSSURJA, Lucas LAU, Hoong Chuin Game theory has gained popularity as an approach to analysing and understanding distributed systems with selfinterested 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 characteristic 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. And second, any\in-approximation algorithm for finding the optimum can be transformed into an \in-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. We left the bounding of this gap for future work. 2007-11-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/261 info:doi/10.1109/IAT.2007.98 https://ink.library.smu.edu.sg/context/sis_research/article/1260/viewcontent/The_Price_of_Stability_in_Selfish_Scheduling_Games.pdf Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Artificial Intelligence and Robotics Business Operations Research, Systems Engineering and Industrial Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Artificial Intelligence and Robotics Business Operations Research, Systems Engineering and Industrial Engineering |
spellingShingle |
Artificial Intelligence and Robotics Business Operations Research, Systems Engineering and Industrial Engineering AGUSSURJA, Lucas LAU, Hoong Chuin The Price of Stability in Selfish Scheduling Games |
description |
Game theory has gained popularity as an approach to analysing and understanding distributed systems with selfinterested 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 characteristic 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. And second, any\in-approximation algorithm for finding the optimum can be transformed into an \in-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. We left the bounding of this gap for future work. |
format |
text |
author |
AGUSSURJA, Lucas LAU, Hoong Chuin |
author_facet |
AGUSSURJA, Lucas LAU, Hoong Chuin |
author_sort |
AGUSSURJA, Lucas |
title |
The Price of Stability in Selfish Scheduling Games |
title_short |
The Price of Stability in Selfish Scheduling Games |
title_full |
The Price of Stability in Selfish Scheduling Games |
title_fullStr |
The Price of Stability in Selfish Scheduling Games |
title_full_unstemmed |
The Price of Stability in Selfish Scheduling Games |
title_sort |
price of stability in selfish scheduling games |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2007 |
url |
https://ink.library.smu.edu.sg/sis_research/261 https://ink.library.smu.edu.sg/context/sis_research/article/1260/viewcontent/The_Price_of_Stability_in_Selfish_Scheduling_Games.pdf |
_version_ |
1770570358749921280 |