Access Restriction

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

   Open content in new tab
Source: ACM Digital Library