Strong stability of Nash equilibria in load balancing games

DOI10.1007/S11425-014-4814-2zbMATH Open1307.91012arXiv1311.1803OpenAlexW1973245644MaRDI QIDQ477108FDOQ477108

Authors: Song-Song Li, Yuzhong Zhang, Bo Chen 

Publication date: 2 December 2014

Published in: Science China. Mathematics (Search for Journal in Brave)

Abstract: We study strong stability of Nash equilibria in 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 r-approximate SNE (r >= 1) if there is no coalition of jobs such that each job of the coalition will have an IR more than r 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 yields a tight approximation bound. This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games. To establish our upper bound, we make a novel use of a graph-theoretic tool.

Full work available at URL: https://arxiv.org/abs/1311.1803

Recommendations

• Equilibria in load balancing games
• Approximate Strong Equilibrium in Job Scheduling Games
• Approximate strong equilibrium in job scheduling games
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Strong Price of Anarchy for Machine Load Balancing

zbMATH Keywords

Nash equilibriumstrong Nash equilibriumapproximate strong Nash equilibriumload balancing game

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Noncooperative games (91A10)

Cites Work

• Worst-case equilibria
• Title not available (Why is that?)
• Approximate equilibria and ball fusion
• Selfish load balancing
• On the value of coordination in network design
• Efficiency analysis of load balancing games with and without activation costs
• Title not available (Why is that?)
• Approximate strong equilibrium in job scheduling games
• A linear time approximation algorithm for multiprocessor scheduling
• Strong price of anarchy
• Equilibria in load balancing games

Cited In (7)

• Strong Price of Anarchy for Machine Load Balancing
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Approximate strong equilibrium in job scheduling games
• Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games
• Strategically supported cooperation in dynamic games with coalition structures
• Approximate Strong Equilibrium in Job Scheduling Games
• Equilibria in load balancing games

This page was built for publication: Strong stability of Nash equilibria in load balancing games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477108)