2004 | OriginalPaper | Chapter
On the Evolution of Selfish Routing
Authors : Simon Fischer, Berthold Vöcking
Published in: Algorithms – ESA 2004
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which is one of the most fundamental paradigms in classical Game Theory. By adopting a generalised approach of Evolutionary Game Theory we extend the model of selfish routing to study the dynamical behaviour of agents.For symmetric games corresponding to singlecommodity flow, we show that the game converges to a Nash equilibrium in a restricted strategy space. In particular we prove that the time for the agents to reach an ε-approximate equilibrium is polynomial in ε and only logarithmic in the ratio between maximal and optimal latency. In addition, we present an almost matching lower bound in the same parameters.Furthermore, we extend the model to asymmetric games corresponding to multicommodity flow. Here we also prove convergence to restricted Nash equilibria, and we derive upper bounds for the convergence time that are linear instead of logarithmic.