Skip to main content

Research Repository

Advanced Search

Fast convergence of routing games with splittable flows

Mertzios, G.B.

Authors



Abstract

In this paper we investigate the splittable routing game in a series-parallel network with two selfish players. Every player wishes to route optimally, i.e. at minimum cost, an individual flow demand from the source to the destination, giving rise to a non-cooperative game. We allow a player to split his flow along any number of paths. One of the fundamental questions in this model is the convergence of the best response dynamics to a Nash equilibrium, as well as the time of convergence. We prove that this game converges indeed to a Nash equilibrium in a logarithmic number of steps. Our results hold for increasing and convex player-specific latency functions. Finally, we prove that our analysis on the convergence time is tight for affine latency functions.

Citation

Mertzios, G. (2009). Fast convergence of routing games with splittable flows.

Conference Name International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09)
Conference Location Orlando, Florida
Start Date Jul 13, 2009
End Date Jul 16, 2009
Publication Date Jul 1, 2009
Deposit Date Dec 8, 2011
Publicly Available Date Mar 29, 2024
Pages 28-33
Publisher URL http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
Additional Information Conference dates: July 13-16, 2009