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)

Preview

Text WRAP_Chen_9471193-wbs-261212-strong_stability_2012-11-18.pdf - Submitted Version Download (279Kb) | Preview

Request Changes to record.

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:	Date Event 2012 Completion
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