NASH EQUILIBRIA IN LOAD BALANCING IN DISTRIBUTED COMPUTER SYSTEMS

Abstract

The use of game theoretical techniques has been quite successful in describing routing in networks, both in road traffic applications as well as in telecommunication networks applications. We study in this paper a third area of applications of such games, which is load balancing in distributed computer systems. One of the most important questions that arise in all applications of routing games is the existence and uniqueness of equilibrium. Whereas the existence of Nash equilibrium is known for general models of networks under weak assumptions, uniqueness results are only known for very special applications, i.e., either for very special cost functions or for very special topologies. We establish in this paper the uniqueness of an equilibrium for routing games with topologies that model well distributed computer systems, under quite general assumptions on the costs.