Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Strong stability of Nash equilibria in load balancing games

Tools
- Tools
+ 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)

[img]
Preview
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/...

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:
DateEvent
2012Completion
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us