×

Strong stability of Nash equilibria in load balancing games. (English) Zbl 1307.91012

Summary: We study strong stability of Nash equilibria in load balancing games of \(m\) (\(m\geq 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 \(\rho\)-approximate SNE (\(\rho \geq 1\)) if there is no coalition of jobs such that each job of the coalition will have an IR more than \(\rho\) 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\geq 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.

MSC:

91A10 Noncooperative games
91A80 Applications of game theory
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albers S. On the value of coordination in network design. SIAM J Comput, 2009, 38: 2273-2302 · Zbl 1191.68025 · doi:10.1137/070701376
[2] Andelman, N.; Feldman, M.; Mansour, Y., Strong price of anarchy, 189-198 (2007), New Orleans · Zbl 1303.91017
[3] Aumann, R.; Luce, R. D (ed.); Tucker, A. W (ed.), Acceptable points in general cooperative n-person games, No. 40, 287-324 (1959), Princeton · Zbl 0085.13005
[4] Chen B. Equilibria in load balancing games. Acta Math Appl Sin Eng Ser, 2009, 25: 723-736 · Zbl 1180.91063 · doi:10.1007/s10255-009-8832-8
[5] Chen B, Gürel S. Efficiency analysis of load balancing games with and without activation costs. J Sched, 2012, 15: 157-164 · Zbl 1280.91095 · doi:10.1007/s10951-011-0247-8
[6] Czumaj, A.; Vöcking, B., Tight bounds for worst-case equilibria, 413-420 (2002), Francisco, CA · Zbl 1092.91508
[7] Feldman M, Tamir T. Approximate strong equilibrium in job scheduling games. J Artificial Intelligence Res, 2009, 36: 387-414 · Zbl 1192.68098
[8] Finn G, Horowitz E. A linear time approximation algorithm for multiprocessor scheduling. BIT, 1979, 19: 312-320 · Zbl 0413.68038 · doi:10.1007/BF01930985
[9] Fotakis, D.; Kontogiannis, S.; Mavronicolas, M.; etal., The structure and complexity of Nash equilibria for a selfish routing game, 510-519 (2002), Malaga
[10] Koutsoupias E, Mavronicolas M, Spirakis P. Approximate equilibria and ball fusion. Theory Comput Syst, 2003, 36: 683-693 · Zbl 1101.68336 · doi:10.1007/s00224-003-1131-5
[11] Koutsoupias, E.; Papadimitriou, C. H., Worst-case equilibria, 404-413 (1999), Trier · Zbl 1099.91501
[12] Vöcking B. Selfish Load Balancing. New York: Cambridge University Press, 2007 · Zbl 1151.91322
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.