Research Article
Convergence of population dynamics in symmetric routing games with a finite number of players
@INPROCEEDINGS{10.1109/GAMENETS.2009.5137459, author={Eitan Altman and Vijay Kamble and Vivek Borkar}, title={Convergence of population dynamics in symmetric routing games with a finite number of players}, proceedings={1st International Conference on Game Theory for Networks}, publisher={IEEE}, proceedings_a={GAMENETS}, year={2009}, month={6}, keywords={}, doi={10.1109/GAMENETS.2009.5137459} }- Eitan Altman
Vijay Kamble
Vivek Borkar
Year: 2009
Convergence of population dynamics in symmetric routing games with a finite number of players
GAMENETS
IEEE
DOI: 10.1109/GAMENETS.2009.5137459
Abstract
Routing games, as introduced in the pioneering work of Orda, Rom and Shimkin (1993), are very closely related to the traffic assignment problems as already studied by Wardrop and to congestion games, as introduced by Rosenthal. But they exhibit more complex behavior: often the equilibrium is not unique, and computation of equilibria is typically harder. They cannot be transformed in general into an equivalent global optimization problem as is the case with congestion games and in the traffic assignment problem which possess a potential under fairly general conditions. In this paper we study convergence of various learning schemes to an equilibrium in the problem of routing games. We are able to considerably extend previous published results that were restricted to routing into two parallel links. We study evolutionary-based learning algorithms and establish their convergence for general topologies.