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 (70Kb)
|Publisher Web site:||http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html|
|Record Created:||22 Feb 2012 16:05|
|Last Modified:||08 Sep 2014 11:10|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|