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 assume that every car controls the same amount of traffic. That is, when we have 10 cars, we say each one of them controls th of the traffic, or, if we have cars, then each one of them controls th of the traffic. In general, suppose we have cars, then each one of them controls th of the traffic. This way, as N becomes very large, the fraction 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.
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 and connect an origin with a destination , 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 of the drivers use arc , then represents the time it will take to them to reach their destination; similarly, if a fraction of the drivers use the alternative arc , then represents their travel time. Naturally, the higher the fraction of users on a road the higher its travel time, so we will assume that and are increasing with respect to and , 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 , where is the fraction of travelers that use , and is the fraction of travelers that use ; as they are fractions, we may impose that and that they are non-negative, i.e., and . This situation is what we call the social optimum.
For our example let us take and . In this way, we get and .
Exercise 1: What values of and minimize the average travel time, i.e., give the social optimum?
Solution to Exercise 1:
We can compute the average latency of choosing fractions and as follows: first, notice that so that the average travel time is
This is a quadratic function on , whose minimum over is given by . This means the traffic is split half and half, and the average travel time is .
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 is on arc , but that the latency on is lower. As a result the driver could improve its travel time by switching to . A driver will not switch if the latency on is lower or the same as that of . Therefore, this means that if there are drivers on , then the latency on must be lower or the same as that of arc . Mathematically speaking, if , then . The same holds for arc : if , then . These are called equilibrium conditions, and a flow satisfying them is called an equilibrium flow.
Exercise 2: For what values of and do we have ? It turns out that these values of and give an equilibrium. Check this using the equilibrium conditions. What is the average travel time?
Solution to Exercise 2: We want , so we find that . This then implies that , using the fact that . Note that only arc contains a positive amount of flow, so we have to check that , but this is indeed true since . The average travel time is (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 in 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?
Solution to Exercise 3:
The Price of Anarchy for the latencies in Exercise 1 and 2 is , 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 for , the Price of Anarchy is at most (see ). Furthermore, as we have illustrated, there even exists a network for which the Price of Anarchy is , meaning that (in general) we cannot find a better upper bound than .
- Tim Roughgarden and Éva Tardos. 2002. How bad is selfish routing?. J. ACM 49, 2 (March 2002), 236-259.