### Algorithms for pure Nash equilibria in weighted congestion gamesAlgorithms for pure Nash equilibria in weighted congestion games

Access Restriction
Subscribed

 Author Panagopoulou, Panagiota N. ♦ Spirakis, Paul G. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Congestion games ♦ Game theory ♦ Pure Nash equilibria Abstract 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 on $\textit{single-commodity}$ networks where selfish users select paths to route their loads (represented by arbitrary integer $\textit{weights}).$ 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 finding $\textit{pure}$ Nash equilibria in such networks. A superficial analysis of this algorithm gives an upper bound on its time, which is polynomial in $\textit{n}$ (the number of users) and the sum of their weights $\textit{W}.$ This bound can be exponential in $\textit{n}$ when some weights are exponential. We provide strong experimental evidence that this algorithm actually converges to a pure Nash equilibrium in polynomial time. More specifically, our experimental findings suggest that the running time is a polynomial function of $\textit{n}$ and log $\textit{W}.$ 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 are $\textit{exponential}$ to their loads. This asserts the existence of pure Nash equilibria for these delay functions and extends the result of Fotakis et al. [2005]. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2007-02-09 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 11

#### Open content in new tab

Source: ACM Digital Library