Selfish load balancing and atomic congestion games
- 27 June 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 47 (1), 188-195
- https://doi.org/10.1145/1007912.1007941
Abstract
We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with or, more generally, as the pth power of the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared to the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to 1 + 2/√3 ≈ 2.15. We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.Keywords
This publication has 14 references indexed in Scilit:
- How bad is selfish routing?Journal of the ACM, 2002
- Ancient and New Algorithms for Load Balancing in the l p NormAlgorithmica, 2001
- Scheduling Parallel Machines On-LineSIAM Journal on Computing, 1995
- The Competitiveness of On-Line AssignmentsJournal of Algorithms, 1995
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage DevicesJournal of the ACM, 1976
- Worst-Case Analysis of a Placement Algorithm Related to Storage AllocationSIAM Journal on Computing, 1975
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955