Strong stability of Nash equilibria in load balancing games

DOI10.1007/S11425-014-4814-2MaRDI QIDQ477108zbMATH OpenOpenAlexFDO

Authors Song-Song Li, Yuzhong Zhang, Bo Chen

Publication date 2 December 2014

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3139273 (Why is no real title available?)
• scientific article; zbMATH DE number 2119691 (Why is no real title available?)
• A linear time approximation algorithm for multiprocessor scheduling
• Approximate equilibria and ball fusion
• Approximate strong equilibrium in job scheduling games
• Efficiency analysis of load balancing games with and without activation costs
• Equilibria in load balancing games
• On the value of coordination in network design
• Selfish load balancing
• Strong price of anarchy
• Worst-case equilibria

Cited in

(7)

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

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)