Convergence time to Nash equilibrium in load balancing

ABSTRACT

We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights, k distinct weights, and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). A by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. We show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.

REFERENCES

• 1: Eitan Altman , Tamer Başar , Tania Jiménez , Nahum Shimkin, Routing into two parallel links: game-theoretic distributed algorithms, Journal of Parallel and Distributed Computing, v.61 n.9, p.1367-1381, September 2001 [doi>10.1006/jpdc.2001.1754]
• 2: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 3: Yossi Azar, On-line Load Balancing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.178-195, January 1998
• 4: Boulogne, T., Altman, E., and Pourtallier, O. 2002. On the convergence to nash equilibrium in problems of distributed computing. Ann. Oper. Res. 109, 1--4, 279--291.
• 5: Peter Brucker , Johann Hurink , Frank Werner, Improving local search heuristics for some scheduling problems. Part II, Discrete Applied Mathematics, v.72 n.1-2, p.47-69, Jan. 10, 1997 [doi>10.1016/S0166-218X(96)00036-4]
• 6: Peter Brucker , Johann Hurink , Frank Werner, Improving local search heuristics for some scheduling problems—I, Discrete Applied Mathematics, v.65 n.1-3, p.97-122, March 7, 1996 [doi>10.1016/0166-218X(95)00030-U]
• 7: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 8: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 9: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Feldmann, R., Gairing, M., Lcking, T., and B. Monien, M. R. 2003. Nashification and the coordination ratio for a selfish routing game. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 514--526.
• 11: Finn, G., and Horowitz, E. 1979. A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19, 3, 312--320.
• 12: Fotakis, D., Kontogiannis, S., and Spirakis, P. 2004. Selfish unsplittable flows. In Proceedings of the 31th International Colloquium on Automata, Languages and Programming (ICALP). 593--605.
• 13: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 14: Fudenberg, D., and Levine, D. 1998. The Theory of Learning in Games. MIT Press, Cambridge, MA.
• 15: Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011787]
• 16: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 17: Kearns, M., and Mansour, Y. 2002. Efficient nash computation in large population games with bounded influence. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI).
• 18: Koutsoupias, E., and Papadimitriou, C. H. 1999. Worst-Case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413.
• 19: Littman, M., Kearns, M., and Singh, S. 2002. An efficient exact algorithm for singly connected graphical games. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).
• 20: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 21: Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Econom. Behav. 13, 111--124.
• 22: Mirrokni, V., and Vetta, A. 2004. Convergence issues in competitive games. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization.
• 23: Monderer, D., and Shapley, L. S. 1996. Potential games. Games Econom. Behav. 14, 124--143.
• 24: Nash, J. F. 1951. Non-Cooperative games. Ann. Math. 54, 286--295.
• 25: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 26: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 27: Rosenthal, R. W. 1973. A class of games possessing pure-strategy nash equilibria. Int. J. Game Theory 2, 65--67.
• 28: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 29: Petra Schuurman , Tjark Vredeveld, Performance Guarantees of Local Search for Multiprocessor Scheduling, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.370-382, June 13-15, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Nash equilibrium, convergence time, game theory