Fast Convergence of Routing Games with Splittable Flows
George B. Mertzios
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.