Title:

Strong Stability of Nash Equilibria in Load Balancing Games

Speaker:

Professor Bo Chen, Centre for Discrete Mathematics and its Applications, Warwick Business School, University of Warwick, UK

Abstract:

We study strong stability of Nash equilibria in the load balancing game of m (m ≥2) identical servers, in which every job chooses one of the m servers and each jobwishes 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, NE-configurations are not stable against coordinated deviations of several jobs, while a strong Nash equilibrium (SE) is. We study how well an NE approximates an SE.

Given any job assignment in the load balancing game, the improvement ratio (IR)of a deviation of a job is defined as the ratio between the pre- and post-deviationcosts. An NE is said to be ρ-approximate SE (ρ≥ 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 SEs 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 1.25-approximate SE, and the bound is tight. To establish this result, we apply a powerful graph-theoretic tool.

时间: 2012年9月13日下午4:00

地点: 致远楼 107室