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.