
The Library
Strong stability of Nash equilibria in load balancing games
Tools
Chen, Bo, Li, Song-Song and Zhang, Yu-Zhong (2012) Strong stability of Nash equilibria in load balancing games. In: International Symposium on Combinatorial Optimization 2012, Oxford, UK, 17-19 Sep 2012 pp. 1-14. (Unpublished)
|
Text
WRAP_Chen_9471193-wbs-261212-strong_stability_2012-11-18.pdf - Submitted Version Download (279Kb) | Preview |
Official URL: http://www.sbs.ox.ac.uk/newsandevents/conferences/...
Abstract
We study strong stability of Nash equilibria in the load balancing games of m (m >= 2) identical servers, in which every job chooses one of the m servers and each job wishes to minimize its cost, given by the
workload of the server it chooses.
A Nash equilibrium (NE) is a strategy profile that is resilient to unilateral deviations. Finding an NE in such a game is simple. However, an NE assignment is not stable against coordinated deviations of several jobs, while a strong Nash equilibrium (SNE) is. We study how well an
NE approximates an SNE.
Given any job assignment in a load balancing game, the improvement ratio (IR) of a deviation of a job is defined as the ratio between the pre-and post-deviation costs. An NE is said to be a ρ-approximate SNE (ρ >= 1) if there is no coalition of jobs such that each job of the coalition
will have an IR more than ρ from coordinated deviations of the coalition.
While it is already known that NEs are the same as SNEs in the 2-server load balancing game, we prove that, in the m-server load balancing game for any given m >= 3, any NE is a (5=4)-approximate SNE, which together with the lower bound already established in the literature implies that the approximation bound is tight. This closes the final gap in the literature on the study of approximation of general NEs to SNEs in the load balancing games. To establish our upper bound, we apply with novelty a powerful graph-theoretic tool.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences | ||||
Library of Congress Subject Headings (LCSH): | Game theory, Client/server computing -- Mathematical models | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Page Range: | pp. 1-14 | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | International Symposium on Combinatorial Optimization 2012 | ||||
Type of Event: | Other | ||||
Location of Event: | Oxford, UK | ||||
Date(s) of Event: | 17-19 Sep 2012 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year