Fast convergence of routing games with splittable flows

Mertzios, G.B.

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, July). Fast convergence of routing games with splittable flows. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09), Orlando, Florida

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09)
• Start Date: Jul 13, 2009
• End Date: Jul 16, 2009
• Publication Date: Jul 1, 2009
• Deposit Date: Dec 8, 2011
• Pages: 28-33
• Public URL: https://durham-repository.worktribe.com/output/1158570
• Publisher URL: http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
• Additional Information: Conference dates: July 13-16, 2009