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?

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.

Would you like to stay up to date when a new post appears on the Network Pages?

Subscribe to our mailing list

Follow us

Related articles

• 

  Article

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

  September 30 2024, by Roshan Mahes

  Elisabeth already has an idea in mind: she would like to find the fastest possible route that goes to each address exactly once before finally returning to the station. This task is a well-known mathematical problem, namely the Traveling Salesman Problem (TSP)! How can she solve it?

  Read article

• 

  Article

  Could the Future of Artificial Intelligence be Self-Organising?••

  July 2 2024, by Marcello Barylli

  One of the main building blocks of modern AI-tools are artificial neural networks, abstract models inspired by the structure and functions of biological neural networks which enable machines to "learn". In this article, I will discuss some thoughts on this topic.

  Read article

• 

  Article

  What is the chance of throwing six with a fair die?•

  May 13 2024, by Twan Koperberg

  If, after reading the title, your immediate response is to shout "1/6-th", then you have correctly answered the question. Well done! However, in this article we will focus on the meaning of this question. What exactly is this "chance" of which you've just exclaimed it equals 1/6-th?

  Read article

• 

  Article

  Maximising efficiency is risky business (Part 1) - Logistics chains and cascading small delays••

  December 2 2024, by Frank Pijpers

  Think of a local car dealer selling cars in your region. To make sure new cars are delivered on time a whole mechanism involving various people, factories, and transport companies, must operate in coordination. This is a highly complex process where mathematics plays an important role.

  Read article

• 

  Article

  AI thinks my dog is a Pig! Want to know why?••

  March 10 2023, by Bharti

  Applications of machine learning models are everywhere, with many online platforms and major science fields using tools relying on machine learning. Take, for example, image recognition and computer vision. But did you know that the results of supposedly perfect and accurate machine learning models can be deceived by slight perturbations in the data?

  Read article