Strong Stability of Nash Equilibria in Load Balancing Games
Professor Bo Chen, Centre for Discrete Mathematics and its Applications, Warwick Business School, University of Warwick, UK
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.
English
官方微信