We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Fast convergence of routing games with splittable flows.

Mertzios, G.B. (2009) 'Fast convergence of routing games with splittable flows.', International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09) Orlando, Florida, 13-16 July 2009.


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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:No date available
Date deposited:08 September 2014
Date of first online publication:July 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar