## Game Theory

# Traffic in Networks

Travelling through a transportation network involves game-theoretic reasoning. Users of the network do not choose their route in isolation, but evaluate routes with respect to the congestion resulting from their own decisions and everybody else’s. Planning a transportation network is not an easy task, as adding capacity to a network can sometimes result in even slower traffic (this effect is known as Braess’s Paradox). More on Traffic in Networks can be found in chapter 8 of [Easley-Kleinman].

## Traffic at Equilibrium

A transportation network can be represented by a **directed graph**.
Here the edges correspond to roads, and the nodes correspond to exits,
where drivers can get on or off a road.

The model to be analyzed now, has two distinguished nodes, $A$ and $B$, an we assume that everybody wants to drive from $A$ to $B$. Moreover, each edge has a travel time associated to it. This travel time is a function of the amount of traffic passing through that edge.

**Example.** In the network below, $4000$ cars are to travel from $A$ to $B$.

This example is a game with $4000$ players, each having two strategies to choose from (travel through $C$ or travel through $D$).

The game has **no dominant strategy**: either route can be a best choice,
for example if everybody else is using the other route.

However, any choice of strategies with half of the drivers on each
route is a Nash **equilibrium**: no driver can improve on their total
travel time ($45 + \frac{2000}{100} = 65$) by switching to the other
route.

## Braess’s Paradox

Suppose now that the County Council decides to alleviate early morning traffic congestion by building a new, very fast highway from $C$ to $D$, as in the network below.

Contrary to what one might expect, this “upgrade” makes matters worse!

The new transportation network has a unique equilibrium, where each driver uses the new road from $C$ to $D$, with a resulting travel time of $\frac{4000}{100} + 0 + \frac{4000}{100} = 80$. No driver can benefit from changing their route, as this would now result in a travel time of $\frac{4000}{100} + 45 = 85$.

This paradox, that adding resources to a transportation network can sometimes lead to worse performance at equilibrium, has first been described by the German mathematician Dietrich Braess in 1968.

## The Price of Anarchy

Network traffic at equilibrium may not be socially optimal,
as illustrated for example by Braess’s paradox.
Under the assumption that the **travel-time functions**
$T_e(x)$ associated to the edges $e$ of a traffic network
are **linear and positive**, i.e., $T_e(x) = a_e x + b_e$
for certain real numbers $a_e, b_e \geq 0$,
one can quantify how far from optimal
traffic at equilibrium can be.

For this, a **traffic pattern** $P$ is a particular choice
of a path by each driver. The **social cost** $C(P)$ of a given
traffic pattern $P$
is the sum of all travel times of all drivers in that pattern.
A traffic pattern that achieves the minimum possible social
cost will be called **socially optimal**.

**Example.** This network provides an example of Braess’s Paradox, with smaller numbers. We assume that $4$ cars want to travel from $A$ to $B$.

One socially optimal traffic pattern $P_{o}$ has $2$ cars travelling through $C$ and another $2$ cars through $D$, at a travel cost of $7$ each, resulting in a social cost of $28$. (There may be other socially optimal patterns: if you see one, describe it in a comment!)

At the unique equilibrium $P_{eq}$, all $4$ cars travel through $C$ and $D$, at a cost of $8$ each, resulting in a social cost of $32$.

For an arbitrary traffic network with linear travel time functions and drivers travelling between arbitrary pairs of nodes, we can show the following:

- There is an equilibrium.
- The social cost of an equilibrium is at most
*twice*that of the social optimum.

(In fact one can show that the equilibrium costs at most $4/3$ of the optimum.)

The proof is based on a strategy of **best-response dynamics**:
Starting with a socially optimal pattern $P_{o}$, one
keeps updating the current pattern by allowing one player at
a time to switch to their best response to the strategies of the others
until no player can find an improvement anymore.
If the procedure ever stops, it must be in an equilibrium state.

In order to show that the procedure does actually stop,
we introduce the **potential energy** $E(P)$ of a traffic pattern $P$
as the sum $E(P) = \sum_e E(e)$ of the potential energies of all its edges,
where the **potential energy** $E(e)$ of an edge $e$ is defined
as

if that edge currently has $n$ drivers on it.

**Example.** Continuing the above example, best-response dynamics
leads to the following sequence of traffic patterns, from the social
optimum (with potential energy $E = 26$) to an equilibrium
(with energy $E = 20$). In each step, one driver improves their
travel time by switching strategy.

In the first step, a driver abandons the path through $C$ and thereby releases a potential energy of $2 + 5 = 7$, then adopts the path through $C$ and $D$, and thereby adds a potential energy of $2 + 0 + 3 =5$ back into the system.

Note that the net change in potential energy equals the net savings in travel time for that driver: If an edge forms part of both the old and the new path used by the driver, it does cause no net change at all, neither in the driver’s travel time, nor in the potential energy. The same is true for edges that are not used, neither in the old path nor in the new path.

If an edge $e$ (used by $n$ cars in the old pattern) is part of the old path but not of the new path, its elimination decreases both the travel time and the potential energy by the same amount $T_e(n)$. And if an edge $e$ (used by $n$ cars in the old pattern) is part of the new path but not of the old, then its introduction adds the same amount $T_e(n+1)$ to both the driver’s travel time and the potential energy.

The net change in the driver’s travel time is negative, otherwise they would not have switched to a different path.

As this is true for each step of the procedure, the potential energy strictly decreases with best-response dynamics until an equilibrium is reached. The procedure thus guarantees the existence of an equilibrium.

In order to compare, the cost of an equilibrium to the cost of the social optimum, recall that $T_e(n)$ describes the cost of edge $e$ when used by $n$ drivers, so that the total contribution of that edge to the cost of a traffic pattern is

Assuming, as we do, that $T_e(n)$ is positive and linear in $n$, that is

for real numbers $a_e, b_e \geq 0$, it follows that $T_e(i) \leq T_e(n)$ for $i \leq n$, whence

Moreover,

as $\binom{n+1}{2} \geq \frac12 n^2$. Taking both inequalities into account, we have

for each edge of the network, and thus

for the social cost $C(P)$ and the potential energy $E(P)$ of any traffic pattern $P$.

Now suppose that $P_o$ is a socially optimal pattern, and that is an equilibrium obtained from $P_o$ by best-response dynamics. Then and from previous inequalities we now conclude that

as claimed.