Fast load balancing via bounded best response

ABSTRACT

It is known that the dynamics of best response in an environment of non-cooperative users may converge to a good solution when users play sequentially, but may cycle far away from the global optimum solution when users play concurrently. We introduce the notion of bounded best response where users react with best response subject to rules that are forced locally by the system. We investigate the problem of load balancing tasks on machines in a bipartite graph model and show that the dynamics of concurrent bounded best response converges to a near-optimum solution quickly, i.e., with poly-logarithmic number of rounds. This is in contrast to the concurrent best response dynamics which cycles far away from the optimum and to any sequential dynamics which requires at least a linear number of rounds to get to a reasonable solution.

REFERENCES

• 1: Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281140]
• 2: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 3: G. Christodolou, V. S. Mirrokni, and A. Sidiropolous. Convergence and approximation in potential games. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, pages 349--360, 2006.
• 4: 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
• 5: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 6: S. Fischer and B. Vöcking. On the evolution of selfish routing. In 12th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 3221, pages 323--334, 2004.
• 7: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073868]
• 8: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 9: V. Mirrokni and A. Vetta. Convergence issues in competitive games. In 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Lecture Notes in Computer Science 3122, pages 183--194, 2004.
• 10: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, Cornell University, Ithaca, NY, 2002
• 11: A. Skopalik and B. Vöcking. Inapproximability of convergence in congestion games. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2007.