Braess’s paradox and quantum game theory
We have all experienced the effect of traffic congestion on the road at one time or another. We have lost time, become angry and perhaps, in desperation, demanded that new roads be built. However, did you know that building new roads can lead to more congestion and increased travel time? This counter-intuitive fact is known as the Braess's paradox.
Figure 1. Illustration showing the Braess's paradox on the route between points A and B. The time taken to travel each of the roads is shown in minutes. The letter c refers to the number of cars and is a means of modelling the phenomenon of congestion: the greater the number of cars, the longer the journey time. The sections where the time does not depend on c are sections where there is no congestion; we can think of them, for example, as roads with many lanes. a) Original situation. b) Situation with an extra road. |
To understand this paradox, let's focus on Figure 1. Let's imagine that there are 4000 cars trying to get from point A to point B along a lake. In situation a) they will have two identical options, so it makes sense to split them in half, 2000 cars driving on each road. In this situation, the total travel time for all of them will be 20 minutes. None of them will have any incentive to change their route, as the increased congestion will cause their travel time to increase. An equilibrium situation will thus have been reached, similar to Nash equilibrium, which will be discussed in future posts, also in the context of quantum game theory. Let us now consider situation b), where a bridge has been built across the lake to improve traffic flow. Drivers will now have the incentive to get from A to B using the bridge to connect the two c/400-time sections. If all 4000 drivers adopt this strategy, now the total time will be... 22 minutes! Moreover, it will also be an equilibrium situation, because if any of the drivers decide to unilaterally change their route to a different one, it will be much worse, taking 25 or 32 minutes. Although this is counter-intuitive, we can see that by increasing the number of roads, the traffic congestion worsens.
We have already seen that game theory and traditional equilibria are not able to provide an answer to this paradox. However, quantum game theory, making use of quantum phenomena such as entanglement or superposition, can introduce new equilibrium situations with a better outcome for each of the players - equilibria that have no classical analogue. We will delve deeper into this issue in future posts. For now, interested readers might want to have a look at some insightful articles on this topic [1]^{,[2],[3]}_{.}
There is no doubt that this phenomenon is relevant in economics – industries face numerous problems in dealing with traffic in networks. The conundrum should, therefore, be generalised, as illustrated in Figure 2. Beyond the problem of road traffic, we could also consider the transport of electric power, the transport of fuels or the transmission of information in data networks.
Can quantum game theory, through quantum computing, offer real answers to these problems?
Figure 2. Representation of the example in Figure 1 as a graph, showing the possibility of extending the results to more general graphs.
[1] Eisert, J., Wilkens, M., & Lewenstein, M. (1999). Quantum games and quantum strategies. Physical Review Letters, 83(15), 3077.
[2] Solmeyer, N., Dixon, R., & Balu, R. (2018). Quantum routing games. Journal of Physics A: Mathematical and Theoretical, 51(45), 455304.
[3] Silva, A., Zabaleta, O. G., & Arizmendi, C. M. (2022). Mitigation of routing congestion on data networks: A quantum game theory approach. Quantum Reports, 4(2), 135-147.