The Computation of Equilibria in Congestion Networks

The Computation of Equilibria in Congestion Networks

Abstract

We study a class of games in which a finite number of "selfish players" each controls a quantity of traffic to be routed through a congestion network in which n directed links are connected from a common source to a common destination. In particular, we investigate its equilibria in two settings.

Firstly, we consider a splittable flow model in which players are able to split their own flow between multiple paths through the network. Recent work on this model has contrasted the social cost of Nash equilibria with the best possible social cost. Here we show that additional costs are incurred in situations where a selfish "leader" player allocates its flow, and then commits to that choice so that other players are compelled to minimise their own cost based on the first player's choice. We find that even in simple networks, the leader can often improve its own cost at the expense of increased social cost. Focussing on a two-player case, we give upper and lower bounds on the worst-case additional cost incurred.

Secondly, we study the computation of pure Nash equilibrium for a load balancing game with variable-capacity links. In particular, we consider a simple generic algorithm for local optimisation; Randomised Local Search (RLS), which can simulate a network of selfish users that have no central control and only interact via the effect they have on the cost latency functions of links. It is known that an algorithm with series of self-improving moves will eventually reach the Nash equilibrium. Our contribution here is to show furthermore that Nash equilibria for this type of games are reached quickly by RLS.

Complete Paper