Traffic congestion: Pigou’s example

In network congestion models, we make some simplifying assumptions that make our life easier. In a large-scale system, each individual driver contributes a tiny amount to congestion, if we assume that every car controls the same amount of traffic.

That is, when we have 10 cars, we say that each one of them controls $1/10$ th of the traffic, or, if we have $100$ cars, then each one of them controls $1/100$ th of the traffic. In general, suppose we have $N$ cars, then each one of them controls $1/N$ th of the traffic. This way, as N becomes very large, the fraction $1/N$ becomes very small, hence, an individual driver has negligible influence on the system, only large groups of cars have. This reasoning allows us to aggregate drivers' decisions by only considering what fraction of the flow goes into each path. These fractions determine flows on the road sections. Just like a water flow splits and merges when traversing bifurcations in a river.

Two car flows with different levels of congestion (figures by Neil Olver).

The second assumption we make is that all drivers have full information of the state of the network. This will allow them to make informed (selfish) decisions. As mentioned in the introduction, the availability of real-time navigation systems makes this assumption reasonable. However, a fair amount of research is focused on what happens when this assumption does not hold, which is beyond the scope of this article.

To introduce some of the challenges of modeling congestion and selfish behavior, let us begin with the simplest example: a double arc parallel network (also known as Pigou's example), as in Figure 2. In this network, the two arcs $a_1$ and $a_2$ connect an origin $O$ with a destination $D$ , however, these two ways of traveling might lead to different travel times, this due to different congestion levels, but also because the two roads may be qualitatively different.

We quantify the travel time of the arcs by latency functions: if a fraction $x_1$ of the drivers use arc $a_1$ , then $l_1(x_1)$ represents the time it will take to them to reach their destination; similarly, if a fraction $x_2$ of the drivers use the alternative arc $a_2$ , then $l_2(x_2)$ represents their travel time. Naturally, the higher the fraction of users on a road the higher its travel time, so we will assume that $l_1(x_1)$ and $l_2(x_2)$ are increasing with respect to $x_1$ and $x_2$ , respectively.

Let us think for a moment on what the government would want to happen in this network. An efficient use of the network means to minimize the average travel time, which in this case can be expressed as the minimization of $x_1 l_1(x_1) + x_2 l_2(x_2)$ , where $x_1$ is the fraction of travelers that use $a_1$ , and $x_2$ is the fraction of travelers that use $a_2$ ; as they are fractions, we may impose that $x_1 + x_2 = 1$ and that they are non-negative, i.e., $x_1\geq 0$ and $x_2\geq 0$ . This situation is what we call the social optimum.

For our example let us take $l_1(x_1)= 1\cdot x_1+0$ and $l_2(x_2)= 0\cdot x_2+1$ . In this way, we get $l_1(x_1)= x_1$ and $l_2(x_2)= 1$ .

https://networkpages.nl/CustomMedia_old/Animations/SimpleStuff/TrafficPigousExample.html

Exercise 1: What values of $x_1$ and $x_2$ minimize the average travel time, i.e., give the social optimum?

Show solution

Solution to Exercise 1:
We can compute the average latency of choosing fractions $x_1$ and $x_2$ as follows: first, notice that $x_2=1-x_1$ so that the average travel time is

$x_1\cdot l_1(x_1)+x_2\cdot l_2(x_2) =x_1\cdot l_1(x_1)+(1-x_1)\cdot l_2(1-x_1)= x_1^2 -x_1+1.$

This is a quadratic function on $x_1$ , whose minimum over $0\leq x_1\leq 1$ is given by $x_1=1/2$ . This means the traffic is split half and half, and the average travel time is $1/2\cdot 1/2+1/2\cdot 1=3/4$ .

Drivers in general do not care about the social optimum. They are only interested in minimizing their individual travel time. What type of flow can we expect to see in the network as a result of this selfish behavior? Or said differently, how will the flow spread out over the network if we assume all drivers are selfish? Suppose a driver uses arc $a_1$ , but that the latency on $a_2$ is lower. As a result the driver could improve its travel time by switching to $a_2$ . A driver will not switch if the latency on $a_1$ is lower or the same as that of $a_2$ . Therefore, this means that if there are drivers on $a_1$ , then the latency on $a_1$ must be lower or the same as that of arc $a_2$ . Mathematically speaking, if $x_1 > 0$ , then $l_1(x_1) \leq l_2(x_2)$ . The same holds for arc $a_2$ : if $x_2 > 0$ , then $l_2(x_2) \leq l_1(x_1)$ . These are called equilibrium conditions, and a flow satisfying them is called an equilibrium flow.

Exercise 2: For what values of $x_1$ and $x_2$ do we have $l_1(x_1) = l_2(x_2)$ ? It turns out that these values of $x_1$ and $x_2$ give an equilibrium. Check this using the equilibrium conditions. What is the average travel time?

Show solution

Solution to Exercise 2: We want $x_1 = l_1(x_1) = l_2(x_2) = 1$ , so we find that $x_1 = 1$ . This then implies that $x_2 = 0$ , using the fact that $x_1 + x_2 = 1$ . Note that only arc $a_1$ contains a positive amount of flow, so we have to check that $l_1(x_1) \leq l_2(x_2)$ , but this is indeed true since $l_1(x_1) = l_2(x_2)$ . The average travel time is $1$ (using formula of Exercise 1).

As you can see from Exercises 1 and 2, the travel time in the case of selfish drivers is worse than that of the social optimum (which is preferred by the government). This inefficient usage of the road network is expressed by the Price of Anarchy (PoA), defined as the ratio of the average travel time in the (selfish) equilibrium, and the average travel time in the social optimum.

Exercise 3: What is the Price of Anarchy for the latency functions as in Exercise 1 and 2? Now, choose different latency functions in the animation, and determine the social optimum and equilibrium. Can you get the Price of Anarchy worse than that of Exercise 1 and 2?

Show solution

Solution to Exercise 3:
The Price of Anarchy for the latencies in Exercise 1 and 2 is $1/(3/4) = 4/3$ , i.e., the average travel time in the equilibrium is 33% worse than that of the social optimum. An interesting theorem states that for general directed networks (which can be much larger than the two arcs given here) and affine latency functions, which are of the form $l_a(x) = c_a x+d_a$ for $c_a, d_a \geq 0$ , the Price of Anarchy is at most $4/3$ (see $[1]$ ). Furthermore, as we have illustrated, there even exists a network for which the Price of Anarchy is $4/3$ , meaning that (in general) we cannot find a better upper bound than $4/3$ .