Article

Fast convergence of selfish rerouting

Authors:

Yishay MansourAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 772 - 781

Published: 23 January 2005 Publication History

Abstract

We consider n anonymous selfish users that route their communication through m parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The different rerouting decisions are concurrent, randomized and independent. The rerouting process terminates when the system reaches a Nash equilibrium, in which no user can improve its state.We study the convergence rate of several migration policies. The first is a very natural policy, which balances the expected load on the links, for the case that all users are identical and apply it, we show that the rerouting terminates in expected O(log log n + log m) stages. Later, we consider the Nash rerouting policies class, in which every rerouting stage is a Nash equilibrium and the users are greedy with respect to the next load they observe. We show a similar termination bounds for this class. We study the structural properties of the Nash rerouting policies, and derive both existence result and an efficient algorithm for the case that the number of links is small. We also show that if the users have different weights then there exists a set of weights such that every Nash rerouting terminates in Ω(√n) stages with high probability.

References

[1]

S. Alpern and D. Reyniers, "Spatial Dispersion as a Dynamic Coordination Problem", Theory & Decision, 53:1, pp. 29--59, 2002.

[2]

D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18:155--193, 1979.

[3]

B. Awerbuh, Y. Azar, and Y. Richter, "Analysis of worse case Nash equilibria for restricted assignment", WOWA 2003.

[4]

L. E. J. Brouwer. Uber abbildung von mannig-faltigkeiten. Mathematische Annalen, 71:97--115, 1912.

[5]

A. Czumaj, P. Krysta and B. Vocking, "Selfish traffic allocation for server farms," in Proceedings of the 34th Symposium on Theory of Computing, pp. 287--296, 2002.

Digital Library

[6]

A. Czumaj and B. Vocking, "Tight bounds on worse case equilibria", In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 413--420, 2002.

Digital Library

[7]

Devdatt P. Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence, Random Structures and Algorithms, 13:2, pp, 99--124, 1998.

Digital Library

[8]

E. Even-Dar, A. Kesselman and Y. Mansour, "Convergence Time To Nash Equilibria," In Proceedings of the 30th ICALP, pp. 502--513, 2003.

Digital Library

[9]

Paul Goldberg, "Bounds for the convergence rate of randomized local search in multiplayer games, uniform resource sharing game", In Proceedings of the Twenty-Third PODC, pp. 131--140, 2004.

Digital Library

[10]

T. Grenager, R. Powers and Y. Shoham, "Dispersion games: general definitions and some specific learning results", In Eighteenth national conference on Artificial intelligence, pp 398--403, 2002.

Digital Library

[11]

D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis, "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game," In Proceedings of the 29th ICALP, Malaga, pp 123--134, 2002.

Digital Library

[12]

E. Koutsoupias, C. H. Papadimitriou, "Worst-case equilibria," in Proceedings of 16th STACS, pp. 404--413, 1999.

Digital Library

[13]

L. Libman and A. Orda, "Atomic Resource Sharing in Noncooperative Networks ", Telecommunication Systems, 17:4, pp 385--409, 2001.

[14]

P. Marbach "Priority service and max-min fairness", IEEE/ACM Trans. Netw., 11:5, pp 733--746, 2003.

Digital Library

[15]

M. Mitzenmacher, A. Richa and R. Sitaraman, "The power of two random choices: A survey of the techniques and results". In Handbook of Randomzied Computing, Rajasekaran et al., Kluuwer Academic Press, 2000.

[16]

V. Mirrokni and A. Vetta, "Convergence issues in competitive games", In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2004.

[17]

J. F. Nash, "Non-cooperative games," Annals of Mathematics, Vol. 54, pp. 286--295, 1951.

[18]

A. Orda, R. Rom and N. Shimkin, "Competitive routing in multi-user communication networks," IEEE/ACM Transaction on Networking, Vol 1, pp. 614--627, 1993.

Digital Library

[19]

T. Roughgarden and E, Tardos, "How Bad is Selfish Routing?," Journal of the ACM, 49(2):236--259, 2002.

Digital Library

Cited By

Panageas IPiliouras GConitzer VBergemann DChen Y(2016)Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of AttractionProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940784(703-720)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940784
Berenbrink PHoefer MSauerwald T(2014)Distributed Selfish Load Balancing on NetworksACM Transactions on Algorithms10.1145/262967111:1(1-29)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2629671
Hoefer MSauerwald TFatourou PTaubenfeld G(2013)Brief announcementProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484283(54-56)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484283
Show More Cited By

Fast convergence of selfish rerouting
1. Theory of computation

Recommendations

Routing selfish unsplittable traffic

We consider general resource assignment games involving selfish users/agents in which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the ...
Fast Convergence in the Double Oral Auction
Special Issue on Wine'15

A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent’s value or opportunity cost for the item is his private information, and preferences are quasilinear. Trade between agents ...
Network uncertainty in selfish routing
IPDPS'06: Proceedings of the 20th international conference on Parallel and distributed processing

We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of minimizing their latency. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
406
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Panageas IPiliouras GConitzer VBergemann DChen Y(2016)Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of AttractionProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940784(703-720)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940784
Berenbrink PHoefer MSauerwald T(2014)Distributed Selfish Load Balancing on NetworksACM Transactions on Algorithms10.1145/262967111:1(1-29)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2629671
Hoefer MSauerwald TFatourou PTaubenfeld G(2013)Brief announcementProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484283(54-56)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484283
Shah SKothari R(2013)Convergence of the dynamic load balancing problem to Nash equilibrium using distributed local interactionsInformation Sciences: an International Journal10.1016/j.ins.2012.09.004221(297-305)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.09.004
Feldman MTamir T(2012)Conflicting Congestion Effects in Resource Allocation GamesOperations Research10.1287/opre.1120.105160:3(529-540)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1287/opre.1120.1051
Awerbuch BKhandekar RRao S(2012)Distributed algorithms for multicommodity flow problems via approximate steepest descent frameworkACM Transactions on Algorithms10.1145/2390176.23901799:1(1-14)Online publication date: 26-Dec-2012
https://dl.acm.org/doi/10.1145/2390176.2390179
Adolphs CBerenbrink PKowalski DPanconesi A(2012)Distributed selfish load balancing with weights and speedsProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332460(135-144)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332460
Berenbrink PHoefer MSauerwald TRandall D(2011)Distributed selfish load balancing on networksProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133152(1487-1497)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133152
Liang KZimmermann ROoi WCandan KPanchanathan SPrabhakaran BSundaram HFeng WSebe N(2011)Peer-assisted texture streaming in metaversesProceedings of the 19th ACM international conference on Multimedia10.1145/2072298.2072326(203-212)Online publication date: 28-Nov-2011
https://dl.acm.org/doi/10.1145/2072298.2072326
Ackermann HFischer SHoefer MSchöngens M(2011)Distributed algorithms for QoS load balancingDistributed Computing10.1007/s00446-010-0125-123:5-6(321-330)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1007/s00446-010-0125-1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents