Universität Paderborn - Home Universität Paderborn
Die Universitä der Informationsgesellschaft

Selfish Routing



KP-Model

A special class of strategic games is the class of selfish routing games in which the strategy sets correspond to paths in a network. Koutsoupias and Papadimitriou introduced a very simple member of this class, now widely known as KP-model. The network consists of a single source and a single destination which are connected by parallel links. Each player, here called user, wants to ship some traffic from source to destination. The load on a link is the total traffic of users assigned to this link. Associated with each link is a capacity representing the rate at which the link processes load. Thus, the latency functions are linear. Each of the users chooses a probability distribution over the links, trying to minimize its private cost. In the KP-model, private cost is defined as the expected latency of the user. Social cost is defined as expected maximum latency on a link.



In contrast to general strategic games, there always exists a pure Nash equilibrium in the KP-model. A proof can be given with help of selfish steps. Here, a single user is allowed to decrease its private cost by changing its strategy. Clearly, selfish steps do not increase social cost. With help of a potential function one can show that every sequence of selfish steps eventually ends in a pure Nash equilibrium. Starting with an optimum assignment (that is, with minimum social cost among all possible assignments of the users) this shows that there always exists a pure Nash equilibrium with optimum social cost . Since every sequence of selfish steps eventually reaches a pure Nash equilibrium, selfish steps seem to be suitable to compute such a pure Nash equilibrium. However, the length of a sequence of selfish steps can be exponential in the number of users before ending in a pure Nash equilibrium. With help of the following applet, you can get a feeling of what might happen within such sequences. In this applet, always the user with largest traffic who can improve is moved to its best link.

Click here to start the applet


Wardrop-Model

The much older Wardrop-model has already been studied in the 1950's in the context of road traffic systems. It allows to split traffics into arbitrary pieces. Wardrop used the concept of equilibrium to describe user behavior in this kind of traffic networks. In this environment, unregulated traffic is modeled as network flow. Given an arbitrary network with edge latency functions, equilibrium flows have been classified as flows with all flow paths used between a given source-destination pair having equal latency. Equilibrium flows are optimal solutions to a convex program, if the edge latencies are given by convex functions. An equilibrium in this model can be interpreted as a Nash equilibrium in a game with infinitely many users, each carrying an infinitesimal amount of traffic from a source to a destination. The private cost of a user is defined to be the sum of the edge latencies on a path from the user's source to its destination, the social cost is defined to be the sum (over all edges in the network) of the edge latencies weighted by the flow on these edges.

Braess' Paradox

A lot of subsequent work on the Wardrop-model has been motivated by Braess's Paradox (see Figure below). Suppose one unit of flow is to be routed from source (left most node) to destination (right most node). The globally optimal solution is to route 1/2 along the upper path and 1/2 along the lower path, resulting in an overall social cost of 3/2. The unique Nash equilibrium in this environment is obtained when the total traffic is routed via the edge connecting the two intermediate nodes, resulting in a social cost of 2. The coordination ratio in this example is 4/3. The interesting fact justifying the title "Paradox" is that after removing the edge with latency 0 the globally optimal solution does not change and the unique Nash equilibrium coincides with the global optimal solution. The network performs better after deletion of an edge.



Contact

Rainer Feldmann (obelix@upb.de)
Martin Gairing (gairing@upb.de)
Thomas Lücking (luck@upb.de)
Karsten Tiemann

Index A – Z | Impressum | Webmaster | Modified: 11.05.2007