Algorithms for pure Nash equilibria in weighted congestion games

In large-scale or evolving networks, such as the Internet, there is no authority possible to enforce a centralized traffic management. In such situations, game theory, and especially the concepts of Nash equilibria and congestion games [Rosenthal 1973] are a suitable framework for analyzing the equilibrium effects of selfish routes selection to network delays. We focus here onsingle-commoditynetworks where selfish users select paths to route their loads (represented by arbitrary integerweights). We assume that individual link delays are equal to the total load of the link. We then focus on the algorithm suggested in Fotakis et al. [2005], i.e., a potential-based method for findingpureNash equilibria in such networks. A superficial analysis of this algorithm gives an upper bound on its time, which is polynomial inn(the number of users) and the sum of their weightsW. This bound can be exponential innwhen some weights are exponential. We provide strong experimental evidence that this algorithm actually converges to a pure Nash equilibrium inpolynomial time. More specifically, our experimental findings suggest that the running time is a polynomial function ofnand logW. In addition, we propose an initial allocation of users to paths that dramatically accelerates this algorithm, compared to an arbitrary initial allocation. A by-product of our research is the discovery of a weighted potential function when link delays areexponentialto their loads. This asserts the existence of pure Nash equilibria for these delay functions and extends the result of Fotakis et al. [2005].