Braess's 'paradox' and a bit of game theory

I've recently begun revisiting some old course material and putting it online. Some of it regarding basic game theory, e.g. one example on iterated removal of dominated strategies and another on mixed strategies. That made me think of a file where I've kept a few fun puzzles to use as examples.

One of these is on the so called Braess's paradox, which I came across a few years ago while thinking about autonomous vehicles. Indeed Braess originally formulated it while studying traffic flows, though the phenomena is more general, and pops up here and there in different kind of network models. It is worth keeping in mind, especially for AI applications. The 'paradox' can be understood in terms of game theory as well, which is why I had some puzzle notes on it. I decided to dig up my notes and drop them in this blog post with a bit of extra text. Who knows, perhaps it will be revised further and upgraded to the tutorials section some day?


Imagine a large number of cars - \(N\) - going at rush-hour every day from some location \(S\) to \(G\). Assume that these are driven by the usual self-interested and perfectly rational beings of Nash-equilibrium game theory we have seen before. (Also let the cars be either full or that there is no car pooling, if you are nit-picky about details.)

So, this is an \(N\) player game. Each driver has a choice of two routes: they can either choose to take the road from \(S\) to point \(a\), and then to \(G\), or they can go from \(S\) to point \(b\) to \(G\). So, there are two strategies: \(SaG\) and \(SbG\). Moreover, for some roads there is congestion so that the cost of commuting (in for example time) is dependent on how many cars are using the road, while for others the cost is constant no matter how many cars are using that particular stretch.

Denote the costs associated with some road segment \(uv\) as \(t_{uv}\), and for the segments listed above associate the costs as in Figure 1 below. Namely

\begin{align*} &t_{Sa}(x) = \frac{x}{N}\\ &t_{aG} = 1\\ &t_{Sb} = 1\\ &t_{bG}(x) = \frac{x}{N}, \end{align*}

where \(x \in [0,N]\) is the number of cars on that road.

Figure 1: \(N\) vehicles going from \(S\) to \(G\) via either \(a\) or \(b\).

In this case each driver wants to minimize their cost (keep this in mind, as often games are thought of as maximizing reward).

Now, the value (= total cost) for strategy \(SaG\) is \(v(SaG) = t_{Sa}(x) + t_{aG} = \frac{x}{N} + 1\), and similarly \(v(SbG) = t_{Sb} + t_{bG}(x) = 1 + \frac{x}{N}\).

Question: What is the cost for every player at Nash equilibrium?

As you probably can guess from the symmetry of the game and the two value functions, each of the \(N\) players will minimize their cost by picking a route randomly and with equal probability. This is because when, \(x_a = \frac{N}{2}\) cars go over \(a\) and \(x_b = \frac{N}{2}\) over \(b\), then \[\left. v(SaG) \right|_{x = x_a} = \left. v(SbG) \right|_{x = x_b} = 1 + \frac{N}{2N} = 1.5.\]

If more than \(\frac{N}{2}\) cars take either \(Sa\) or \(bG\) then it is beneficial to change strategy because there will be less cost in going on the opposite. So, the best thing to do is to randomize over the two strategies.

The twist

All good this far. But now the traffic authority builds a new super-highway-tunnel from location \(a\) to \(b\). It is really efficient and adds no extra cost to the drivers \(t_{ab} = 0\), as in Figure 2.

This means that there is a new strategy available in addition to the previous two: \(SabG\). That is, first drive from \(S\) to \(a\) then to \(b\) and from there to \(G\).

Figure 2: A new road from \(a\) to \(b\) with cost 0 is added.

Question: Will this affect the Nash equilibrium? If so, what is the associated cost for each player?

The value function for the new strategy is quite straight forward: \(v(SabG) = \frac{x}{N} + 0 + \frac{x}{N} = \frac{2x}{N}\).

And, as you might have expected, the equilibrium shifts now that the game has changed. Assume that we start out as before with \(x_a = \frac{N}{2}\) cars driving route \(Sa\). Well, this means that the remaining \(\frac{N}{2}\) cars go \(Sb\), and thus \(x_b = \frac{N}{2}\). So, the best strategy for the cars over \(a\) is to go to \(b\), because the additional cost of this is merely \(0 + \frac{N}{2N} = \frac{1}{2}\) (and going straight \(aG\) costs 1). But now the players going \(Sb\) wants to change. Their total cost is still \(1.5\), while the other drivers get only a total of \(1\).

So, randomly going either \(Sa\) or \(Sb\) is not a Nash equilibrium any more. More drivers will want to go to \(a\). How many?

All of them.

The new equilibrium is simply that every player chooses strategy \(SabG\). The associated cost then \(v(SabG) = \frac{2N}{N} = 2\). You can check this by verifying that no other route will give a lower cost for an individual driver - it will only lower cost for others. There is thus no incentive to change for a perfectly rational driver.

Note that even the individual cost in this equilibrium is more than before (2 > 1.5). Still, nobody wants to change.

The above is an example of what is called Braess's paradox in the study of road networks and traffic flow. It might seem a bit contrived at first, but examples have been reported in traffic. For instance where closing roads or highway lanes might actually improve traffic flow. In general where more resources does not necessarily lead to better outcomes.

It is not quite a 'paradox'. In game theoretic terms it is an example of when the Nash equilibrium does not agree with other types of equilibria. Clearly everyone could be better off by (for example) agreeing not to use the new road, or say by allowing a central route planner to direct which road to use.

Question - is there a correlated equilibrium with better outcome than the Nash equilibrium?

You might even ask if there is a correlated equilibrium - where each driver accepts and respects the outcome of some random process assigning new route, leading to an even lower cost over time.

So, let's associate \(P(SaG) = p_1, P(SbG) = p_2, P(SabG) = p_3\), and \(p_1 + p_2 + p_3 = 1\). Given this distribution, let \(E[X_{Sa}], E[X_{bG}]\) denote the expected number of cars between points \(Sa\), and \(bG\) respectively.

Now we can write the expected commuting cost of a player as \(\bar{v} = p_1 v(SaG) + p_2 v(SbG) + p_3 v(SabG) = p_1 (\frac{E[X_{Sa}]}{N} + 1) + p_2 (1 + \frac{E[X_{bG}] + 1}{N}) + p_3 (\frac{E[X_{Sa}]}{N} + 0 + \frac{E[X_{bG}]}{N}).\)

Noting that \(\frac{E[X_{Sa}]}{N} = p_1 + p_3\), and similarly for route \(bG\), we can write the above as.

\(\bar{v} = p_1 ( p_1 + p_3 + 1) + p_2 (1 + p_2 + p3) + p_3 (p_1+p_3 + p_2+p_3) = (p_3 + p_1)^2 + (p_3 + p_2)^2 + p_1 + p_2.\)

Using, e.g. \(p_3 = 1 - p_2 - p_1\), this can be written as \(\bar{v} = 2 + p_1^2 + p_2^2 - p_1 - p_2\), which has a minimum at \(p_1 = p_2 = 0.5\). Thus, the correlated equilibrium is at \(p_1 = 0.5, p_2 = 0.5, p_3 = 0\).

That is, the best thing to do is to stop using the new road completely and allowing the traffic authority to randomly assign a route, which coincidentally happens to be exactly the same as letting every driver randomize without the \(ab\) connection.

In concluding this post

I think Braess's paradox is a pretty neat example of how the existence of choice or resources can result in less efficiency as a whole for systems of 'rational agents'.

It's related to more complex flow problems on graphs/networks, and to other applications than traffic.

That said, I think that this simple example might provide an intuition pump also closer to home, when discussing the future of autonomous vehicles. For it is easy to imagine that many potential instances of this paradox has been dampened by human driver 'irrationality'. Choice of route can be down to scenery, joy of driving, or simply overconfidence in knowing the 'best route', or many other things which makes perfect sense when it isn't thought too much about. But then, if everyone buys a car, wouldn't they want the 'best' car, taking the 'best route', just as all the other cars (and already seen with GPS route planners in many places).

But more on that, perhaps, some other time.