Braess’s Paradox as a Routing Problem

Written by Luca M. Tittel

Motivation

Braess’s Paradox is a phenomenon rarely witnessed in street-networks or even similar networks like power-networks or some mechanical Systems. It describes the occurrence of the overall flow of a network increasing while the ”capacity” decreases. Or conversely, it describes the decrease in flow for an increase in ”capacity”.

In 1990 Lucius J. Riccio, the transportation commissioner of New York City, decided to close 42nd street for the festivities of Earth Day that year. As 42nd street seemed to always be congested, the common conception was, that this was going to be a horrible experience for the motorists in New York City. However, the traffic on Earth Day seemed to flow better than before [5]. How is this possible? Can we recreate this in other networks? Can we adapt routing-strategies to abuse this phenomenon?

Analysing the Paradox

User vs. Socially Optimized States

To understand how this is possible, we need to understand the difference between a user optimized (UO) state and a socially optimized (SO) state. The first one being a state of a street-network in which a change in strategy of a user, i.e., that user taking a different route, would result in them taking longer to get to the destination. An SO state is when a change in user strategy would result in the average travel time of all users increasing. These two states not always being compatible is what allows for Braess’s Paradox to occur. There is a simple example for the UO state not being the SO state within a 4-intersection-network.

A network is made up of intersections (vertices) and streets (edges) between them. Each edge has a latency or travel time function associated with it. This function tells us the time it takes a driver to travel the respective street, given the number of drivers choosing to also travel on this street. These functions are of the form \(\text{latency}_{e}(f)=a\cdot f + b \), where \(e\) is the street’s name and \(f\) is the amount of drivers taking this street. The constants \(a\) and \(b\) can be understood as indicators of capacity and length of the street, respectively. A long street with very high capacity may have a low \(a\)-value but a high \(b\)-value, as it is not that sensitive to the amount of drivers on it, but in any case takes a lot of time to travel. Note that we can easily define the travel time for a path \(e_0 \dots e_n\) by defining:

\(\text{latency}_{e_0\dots e_n} = \text{latency}_{e_0} +\dots + \text{latency}_{e_n}\)

The argument \(f=(f_\alpha)_{\alpha\in A}\) is the family that saves how many drivers are taking which path in the system. Here A is the set of all possible paths between all allowed start- destination combinations. If we know this, we also know how many drivers are going to take which street in the system. So we especially know how many drivers are taking which street on the path \(e_0 \dots e_n\). That is, we know \((f_0,\dots ,f_n)\). Here it is important to take away that for computing \(\text{latency}_{e_0\dots e_n}(f)\) we need to know how many drivers are taking which path in the system, and not just how many drivers are taking \(e_0 \dots e_n\).

In our street network with 4 intersections, let’s say 4000 drivers are trying to get from intersection a to intersection b. Every state is defined by a strategy profile, which for each driver determines which exact path they are going to take to reach their destination. Figure 2-left shows a version of the graph, where the SO state is the UO state. In both states all drivers divide equally between paths a1b and a2b. The proof is straightforward:

Proof: In the first step, we demonstrate that we have a UO state. We call the number of drivers taking path a1b or a2b, \(f_1\) or \(f_2\) respectively.
Let’s say the network is in the state \(f_1=2000=f_2\). If one user changes their strategy for example from taking path a1b to taking path a2b, their travel time would increase. Their former travel time would have been:

\(\text{latency}_{a1b}(f_1=2000,f_2=2000)=\frac{f_1}{100}+45=\frac{2000}{100} + 45=65\)

Their new travel time would be

\(\text{latency}_{a2b}(f_1=1999,f_2=2001)=\frac{f_2}{100}+45=\frac{2001}{100} + 45=65.01\)

So we have a UO state because any strategy change from the strategy profile \(f_1=f_2\) would increase that users travel time. Now we check whether we have an SO state, which we do by analysing the average travel time. The average travel time is the total travel time of all drivers added up and divided by the number of drivers. Using \(f_1+f_2=4000\) we get:

\(\text{latency}_{\text{total}}(f_1,f_2)= \frac{\text{latency}_{a1b}(f_1)\,\cdot f_1 + \text{latency}_{a2b}(f_2)\,\cdot f_2}{4000}\)
\(\dots = \frac{f_1^2}{400000}+ \frac{f_2^2}{400000}+45\)
\(\dots = \frac{f_1^2}{2000}-2\cdot f_1+4045\)

Basic optimisation tells us, that this travel time function has a minimum for \(f_1=2000\) and \(f_2=2000\). And again we have an SO state for the strategy profile \(f_1=2000\) and \(f_2=2000\).
Notice that in this optimised state, every driver takes 65 minutes to travel from a to b.

☐

Let’s take a look at Figure 2-right. Here we just added a very quick and large one- directional street between intersections 1 and 2 resulting in \(\text{latency}_{12}(f)=0\cdot f + 0\). Due to us just adding capacity to the network the new SO state can only have the same or a smaller average travel time. Our SO average travel time must be smaller than 65 minutes. The UO state of this network is that all 4000 drivers take the path a12b to their destination. This results in everybody’s travel time being:

\(\text{latency}_{a12b}(f_1=0,f_2=0,f_{12}=4000)=\frac{4000}{100} + 0 + \frac{4000}{100}=80\)

Is this true? I will outline the proof concept again for a better understanding of what a UO state is:

Proof (Outlined): What would happen if a single adventurous driver chose a different path, for example a1b. We encode this in \(f_{12}=3999\) and \(f_{1}=1\). The adventurer would have a travel time of:

\(\text{latency}_{a1b}(f_1,f_{12})=\frac{4000}{100}+45=85\)

This is to say, it is not worth it for an individual to change from taking the route a12b. A change in strategy from everybody taking a12b would be an increase in travel time for that specific driver, hence we have a UO state. Notice our UO average travel time is 80 minutes and our SO tavel time is smaller than 65 minutes.

☐

Simple Model for Analysing Street Networks

The difference between the UO and SO state can be explained via game theory. We can understand the process of every driver choosing the quickest path to their destination as an egotistical, rational, uncooperative and time absent strategy game with perfect information. Such a game consists of a set of players (users or drivers), a set of strategies for each player (paths to take from their start to their destination) and for each player a preference function. In our case this function is given by all the travel time functions that tell us the time it takes to travel a path in the current network state. So the preference function tells us which state of the game, i.e., strategy profile, i.e., which driver taking which path, the specified player prefers to other strategy profiles [8, p.11]. Within this model a UO state is called a Nash-Equilibrium.

The description ”egotistical, rational, uncooperative, time absent strategy game with perfect information” means that our players are looking for the quickest route for themselves and do not care about the travel times of others. They always choose the quickest route disregarding of qualitative factors, like the view along the route. They do not cooperate before choosing their paths to, for example, split up traffic evenly. They all choose at once and do not change their route while traveling. And they always know how long every route takes to the destination and how many players are choosing that route.

All of these assumptions might seem random, but as is written by Osborne: ”As always, the proof of the pudding is in the eating: if a model enhances our understanding of the world, then it serves its purpose.” [8, p.7]. And modern routing algorithms, while avoiding traffic jams for you, do look for YOUR ”best” route [6]. Google does take into account a variety of factors while planning your quickest route, like traffic state, predicted traffic state, road conditions and route efficiency, such as authoritative data on speed limits, etc. [6]. So one might be misled in thinking their algorithms are cooperative. It is true that they are interacting, in sending positional data or broadcasting traffic jams and so on, but they do not follow a common plan to decrease everybody’s travel times and instead choose routes egotistically. Their method is UO and fits the description: ”egotistical, rational, uncooperative and with perfect information”. The method for the greater good (and often also individual good), i.e., socially optimized, is a problem of multi-variable optimization [7, p.5-6].

Finding the UO State Algorithmically

Now that we have a fitting model, we can look for an algorithmic approach to exploring this phenomenon. To better understand when Braess’s Paradox occurs, I wanted an algorithm that for a given small street network determines the UO state, or the Nash-Equilibrium. Then, I could experiment with some capacity changes and see if this would have the paradoxical effect on the average travel time I was hoping for. Let’s take a look at the pseudo code: (implementation available in github)

Algorithm 1 Find Equilibrium
procedure EQUILIBRIUM(streetNetwork: Graph, demands: Demand[])
  while network not in equilibrium do
    for demand ∈ demands do
      quickestRoute ← dijkstraSearch(streetNetwork, demand.start, 
          demand.destination)
      for route ∈ demand do
        demand.redistribute(streetNetwork, route, quickestRoute)

The Graph saves the information about the street network, i.e., intersections and streets along with their travel time functions and drivers using them. A demand keeps track on how many drivers are traveling from a specified demand.start to a specified demand.destination. It also knows how many drivers are taking which route to the destination. The “dijkstraSearch”-function finds the quickest path from demand.start to a demand.destination given the current distribution of drivers in the street network. And the procedure “demand.redistribute” allows drivers taking “route” to their destination to change their strategy to taking ”quickestRoute” instead. Drivers will start changing onto “quickestRoute” till “quickestRoute” becomes so slow, that change is not viable anymore. The “quickestRoute” slows down, when drivers change onto it, because of the travel time functions having components proportionate to the amount of drivers taking a street within the route.

The idea is, that for every start-destination pair, we allow drivers not taking the quickest route, to change onto the quickest route, till it is slowed down.

Believable Real World Scenarios

We are now able to compute a UO state for a given street network with certain demands. We will look at two examples and try to understand when Braess’s Paradox is likely to occur in the real world.

Mountain Cities

For the change to the street network seen in Figure 2 the algorithm finds our exact solutions. We can see the UO states determined by the algorithm in Figure 3:

We can see that the SO state seen on the left-hand side of the figure is actually faster for everybody than the UO state on the right-hand side, which is counter intuitive, because for it to exist, nobody is allowed to actively choose the quickest available path for themselves. If, for example, one driver would choose a12b, they would decrease their travel time to

\(\text{latency}_{a12b}(f_1=1999,f_2=2000,f_{12}=1)=\frac{2000}{100}+0+\frac{2001}{100}=40.01\)

but the average travel time would increase. But what scenario could lead to this exact situation? This graph fits the scenario of two cities on opposite sides of a Mountain depicted in Figure 3. Imagine you want to get from point a to point b. You can either first go through city A to point 1 and then take a long road with a lot of capacity to your destination b at the edge of city B. Or you could first take a long road with high capacity to city B and then move through the inner city to get to your destination on the other side. Looking at the algorithms results, we have learned that if we have a large demand between a and b and we have the option to connect the cities A and B via a big tunnel between 1 and 2 while a tunnel between a and b is not feasible for some reason, we should opt not to do it. Simply because such a tunnel would congest the cities so badly, traffic would flow worse overall.

To further understand our modeling approach we will now discuss in more detail, how we can compare our mountain cities to the 4-vertex-graph. Our first option (first city, then long road) corresponds to taking path a1b and the second is equal to taking path a2b. The travel time function of moving through the city can be interpreted as proportionate to the amount of drivers going through the city. This is because the inner city will congest quickly. Taking a big, long road on the other hand can be analysed as a constant travel time function, because it has high capacity, meaning it does not congest easily but still takes a certain amount of time to travel. This notion of adding linear components for signifying congestion and adding constant components is generally accepted in simple models. Look for example at this approach of analysing uncongested streets with congested intersections [9, p.419]. For understanding why congestion is analysed by linear components of the travel time function, it is helpful to visualise a traffic light with congestion.

Let’s say for each lane 2 cars can pass during every green phase and we have one lane. For the first two cars, the time to pass the green light will be the length of one red-green phase (\(l_r\) minutes). For the next car it will already take \(2\cdot l_r\) minutes. The fourth car will also take \(2\cdot l_r\) minutes and the fifth \(3\cdot l_r\) minutes. We can roughly say that for \(f\) cars approaching the light, it will take \(\frac{f}{2}\cdot l_r\) minutes for all cars to pass the light. The number of cars per lane being able to pass during a green phase is \(n_g=2\). And we can denote the number of lanes at the intersection with \(k=1\). This results in the rough total travel time for this intersection being proportionate to the amount of drivers on the intersection \(\text{latency}(f)=\frac{l_r}{k\cdot n_g}\cdot f\). An increase in capacity could be an increase of \(k\cdot n_g\) the number of lanes \(k\). Look at Figure 5 to see how the same amount of drivers move through intersections with different lanes at different times.

Congestion is a major part of Braess’s Paradox. It is possible to demonstrate that in uncongested networks Braess’s Paradox does not occur [7, p.7].

Bypass Outer City

When I found the following graph in [2, p.245] I was unsure of how the Paradox could occur. Starting with some first guesses, I received Figure 6-left in which 200 drivers want to go from a to c, 50 people want from a to b and 1000 drivers want to go from b to c:

The idea was to encounter Braess’s Paradox by, for example, decreasing the speed limit on the street ab. The intuition from the source was that ac would be some kind of bypass road. This means, it would be quiet long to get to the destination. And that bc would need to have high demand. Adjusting to these factors and changing demands to ac → 200, ab → 50, bc → 3650 led to the network in Figure 7:

The corresponding real world scenario would be bypassing a set of small congested streets (ab and bc) via a longer uncongested bypass (ac). Let’s say bc is some kind of main street, still fairly small but very important inside the city. The link ab could be a street for accessing the city, also prone to congestion but only used by drivers entering from your direction. To get to the point c on the edge of town, you can either take the combination of the access street ab and then the heavily congested main street bc, or you can take a long bypass bringing you directly to your destination. The values of the algorithm seen in Figure 8 tell us that if we artificially decrease capacity on our access street ab, by for example decreasing the speed limit, we can actually decrease everybody’s travel time. Everybody wanting to go from a to b now egotistically chooses the bypass. By making entering the city less appealing and slower, we avoid the new drivers further congesting our main street bc. Average travel time will then decrease.

Notice that for the first guess mentioned in Figure 6, Braess’s Paradox does not occur when changing the capacity of ab. In that case every driver who wants to go from a to c already takes the bypass. Additionally it would not be as bad for the average travel time if they further congested the main street bc, because it is not as busy. The algorithm underlines that in Figure 9:

Bonus: Bypass Inner City

The Pigou Phenomenon [3] illustrates a similar problem. Imagine there to be two points in a city. We can either take a very short bottleneck to our destination. This might be a negligible distance, if there is nobody else on this road, but might turn into an hour long drive, if there are 1000 drivers on this stretch. An alternative could be taking a long bypass road. This might never congest for a reasonable amount of drivers, but takes 60 minutes in any case because of its length. This network is shown in Figure 10-left.

Let’s say 1000 driver want to get from a to b within the street network given in Figure 10-left. We can see, that the average travel time in Figure 11 only increases if the travel time on our bottleneck increases as seen in Figure 10-right. This is because the number of drivers on the bottleneck decreases with the decrease in capacity of it. This shows that we cannot increase the average travel time by decreasing capacity in this scenario.

However, there is a more socially optimal distribution of drivers, than seen in the user optimized state in Figure 11-left.

Let’s say, in the network seen in Figure 10-left, instead of just slowing down the bottleneck as in Figure 10-right, we only allow 500 drivers to pass through it. This means \(f_0=500\) drivers will take the bypass and \(f_1=500\) the bottleneck, because of their own egotistical need to take the quickest available route for themselves as in Figure 12. The resulting average travel time will be:

\(\frac{f_0\cdot \text{latency}_{\text{bypass}}(f_0,f_1)+ f_1\cdot \text{latency}_{\text{bottle}}(f_0,f_1)}{f_0+f_1} = 45 \)

Here we can see, that by changing the capacity of our network, we may try to change the egotistical routing strategies of drivers into a more social distribution, but by truly forcing egotistical drivers to route socially we can increase efficiency significantly. Can you define the multi-variable optimization problem of which the solution is the SO state of the network? The solution should be the pair \((f_0,f_1)\) of how many drivers are taking the bypass or the bottleneck.

Conclusion

Looking at the naive examples explored here, but also seeing the clearly visible effect of Braess’s Paradox, one could ask if this phenomenon is the key to effectively navigating our large and complex street networks. Some research suggests that the paradox occurs more likely in more complex graphs, and efforts are being made to better understand Braess’s Paradox in more natural settings. In [4], a proof is outlined that in a random network model, as the number of vertices goes to infinity, there is a set of edges whose removal decreases latencies in the system. In general [1, p.1] lists some sources in favor of Braess’s Paradoxes likelihood in real world scenarios.

One has to understand that Braess’s Paradox is simply tricking egotistical drivers into a more social behaviour. The reason we found good results in the first 4-vertex example by removing a street, was that the user optimized state changed to the socially optimized state. During our examples, we have to keep in mind that while the user optimized state might move closer to the socially optimized state after removing capacity from our network, we are still removing capacity. And removing capacity from our network can only have a negative or zero impact on its socially optimized state. Hence, we are actually worsening the social optimum, to trick egotistical drivers instead of changing them. This leads to the more important question. Instead of asking: ”How can we abuse Braess’s Paradox to trick egotistical drivers into a more social behaviour?”, we should be asking: ”How much better is socially optimised routing to user optimized routing? And how can we achieve socially optimised routing in a large scale?”

A next step would be to look at routing as a multi-variable optimization problem as discussed in [7] and compare this to the user optimized approach of modern routing algorithms. We have the infrastructure to allow our devices to communicate and follow common plans, so a change to social optimisation may be a very possible one in advancing quality of life, especially in cities and for commuters.

References:

1. Viktor Avrutin Arianna Dal Forno Ugo Merlone. “Dynamics in Braess Paradox with Nonimpulsive Commuters”. In: Discrete Dynamics in Nature and Society (2014).
2. Stefano Pallottino Caroline Fisk. “Empirical Evidence for Equilibrium Paradoxes with Implications for optimal Planning Strategies”. In: Centre de Recherche sur les Transports, Universite de Montreal (1979).
3. Étienne Ghys. “Les Applications GPS, plus lib ́erales que sociales”. In: L’Humanité Magazine (2023).
4. Tim Roughgarden Greg Valiant. “Braess’s Paradox in Large Random Graphs”. In: Random Structures Algorithms (2006).
5. Gina Kolata. “What if They Closed 42d Street and Nobody Noticed?” In: The New York Times, Dec. 25th, 1990 (1990).
6. Johann Lau. “Google Maps 101: How AI helps predict traffic and determine routes”. In: https://blog.google/ (2020).
7. Kenneth M Monks. “Braess’ Paradox in City Planning: An Application of Multi- variable Optimization”. In: MAA Convergence (2020).
8. Martin J. Osborne. An Introduction to Game Theory. Self-Published Draft, 2000.
9. M. J. Smith. “In a Road Network, Increasing Delay Locally can Reduce Delay Globally”. In: Transportation Research (1977).