Cookies

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.

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.

Item Type:Conference item (Paper)
Full text:Full text not available from this repository.
Publisher Web site:http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
Record Created:22 Feb 2012 16:05
Last Modified:09 Mar 2012 10:54

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library