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|
|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|