research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:PNP
TitleEfficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games
Bibtex cite IDRACTI-RU1-2005-2
Booktitle 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005)
Series Lecture Notes in Computer Science
Year published 2005
Month May
Volume 3503
Pages 203-215
Publisher Springer-Verlag
Location Santorini Island, Greece
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 the concepts of Nash equilibria and Congestion Games [8] are a suitable framework for analyzing the equilibrium effects of selfish routes selection to network delays. We focus here on layered networks where selfish users select paths to route their loads (represented by arbitrary integer weights). We assume that individual link delays are equal to the total load of the link. We focus on the algorithm suggested in [2], i.e. a potential-based method for finding pure Nash equilibria (PNE) in such networks. A superficial analysis of this algorithm gives an upper bound on its time which is polynomial in n (the number of users) and the sum of their weights. This bound can be exponential in n when some weights are superpolynomial. We provide strong experimental evidence that this algorithm actually converges to a PNE in strong polynomial time in n (independent of the weights values). 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 exponential to their loads. This asserts the existence of PNE for these delay functions and extends the result of
Panagopoulou, Panagiota
Spirakis, Paul
wea05.pdf (main file)
Publication ID41