Bezoek de website voor leraren en scholieren →

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?

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?

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?

#### Referenties

1. Tim Roughgarden and Éva Tardos. 2002. How bad is selfish routing?. J. ACM 49, 2 (March 2002), 236-259.
• Article

### Ding-Dong! Finally, your delivery driver is at your door••

Why your packages arrive too late: the challenges (and solutions) behind last-mile delivery.
• Article

### Predicting optimal routes in unpredictable networks•

How does your navigation system find the fastest route in a road network, if it does not know where traffic jams occur and how long they last?
• Article

### Enigma: a complexity titan••

In times of war, secure communication can be the difference between life and death, or even winning or losing a war. The first to patent a rotor machine in Europe was Arthur Scherbius in 1918. Scherbius’ version of the rotor machine became a commercial success, unlike the other patented machines. Scherbius named his machine Enigma.