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/10th of the traffic, or, if we have 100 cars, then each one of them controls 1/100th of the traffic. In general, suppose we have N cars, then each one of them controls 1/Nth 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.

pigousExample

We quantify the travel time of the arcs by latency functions: if a fraction x_1of 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.

http://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.