Algorithmic Game Theory

Analyzing the Braess’ Paradox

What does one mean by “correct behaviour”?

Published in

Intellectually Yours

5 min readOct 24, 2020

Algorithmic game theory is an area that lies in the intersection of game theory and computer science, with the objective of understanding and designing algorithms in a strategic environment. In 1999, Noam Nisan and Amir Ronen in their seminal paper ‘Algorithmic Mechanism Design’ claimed that algorithms are considered in a distributed setting where it is assumed that the participants (“agents”) follow their self-interest rather than the algorithms. The agents are capable of manipulating the algorithms and thus it is more reasonable to believe that an algorithm will be exploited for the owner’s benefit rather than acting as instructed. Integrating game-theoretical tools takes into account the possible strategic interactions in the situation with a given set of rules and outcomes beforehand to avoid this setback.

Clashing self-interests (literally)

One might be familiar with the dramatic chicken game, also known as the hawk-dove or snowdrift game. In this game, two drivers drive towards each other on a collision course and the one who swerves, loses. If not, they both may die in the crash.

*(https://economics.fandom.com/wiki/Chicken_game)*

The one who swerved will be called a “chicken”- a coward and the other “brave” player - the winner. Through this example, we see that more often than not the self-interests of the players clash and why then it becomes imperative for the algorithm designer to keep in mind that the “correct” behavior for the players also serves their own self-interest — to prevent the losses for the entire system.

The Braess’ Paradox

The Braess’ paradox is a counterintuitive observation that says adding one or more roads to a network slows down overall traffic flow through it. This happens because if a person wants to reduce travel time, it is likely that they will choose a shortcut which is in their self-interest. That is the case with all the drivers on that road network, thus leading to congestion. In Seoul, South Korea, traffic sped up only when a motorway was removed. In Stuttgart, Germany, even after much investment, the traffic situation did not improve until a section of the newly built road was closed.

*https://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Braess_paradox_road_example.svg/500px-Braess_paradox_road_example.svg.png*

One can visualize the Braess’ Paradox easily from an iconic scene from the movie “A Beautiful Mind” which is a biopic of John Nash. In this scene, John and his friends went to a club where they saw some girls, one being perceived as the most beautiful. John devised a way in which all his friends could each dance with a girl. He said that if all of them approached the most beautiful one, they would end up blocking each other and no one would end up with her. Rejected, they would go for her friends next. They were bound to get a cold shoulder from the girls as no one likes to be a second choice. But what if no one went for the most attractive but directly for her friends? They would increase their chances as they were neither insulting any of the girls (except the one) nor were they coming in each other’s way.

This directly challenged Adam Smith’s “Individual ambition serves the Common Good” with “Collective Good comes by each Individual doing Good for themselves — and the Group” and illustrates Braess’ paradox which points out that the addition of options is not necessarily a good choice to make.

The same may happen in computer networks while load balancing or routing. The introduction of a new path changes the existing equilibrium and adds complexity to the dynamics of the situation. A game-theoretical algorithm thus designed will compute the equilibrium at each step of the algorithm. It will check whether some driver on a network has a better response to the strategies of all other drivers and switch to that response. Consider the following pseudocode for Best Response Dynamics:

Let P be some traffic pattern.while P is not at equilibrium:    compute the potential energy e of P    for each driver d in P:        for each alternate path p available to d:            compute the potential energy n of the pattern when d takes path p            if n < e:                modify P so that d takes path pcontinue the topmost while

With the rapid advancement of technology, it does not seem impossible to have a system where all the vehicles are interconnected through an algorithm which will help in reducing congestion. This can be incredibly useful in times of crisis and emergencies as well as lower fuel consumption. But for this, we need an algorithm that is efficient enough to coordinate the routing of automated vehicles. Autonomous vehicle traffic routing (AVTR) if achieved, would have a great impact, both on society as well as in the field of computer science. The congestion on a particular road or travel time depends not only on the vehicles traveling from the same set of origin and destination but also on the vehicles traveling between different sets of origin and destination. For faster and effective management of traffic, we can develop an algorithm that assigns a vehicle a particular route from which it cannot profitably deviate.

*https://fpf.org/wp-content/uploads/2017/03/privacy-adn-connected-vehicle.jpg*

We see drivers deciding to travel on a particular route based on information like real-time delays and congestion on the route suggested by apps like Google Maps and Waze. When we have autonomous vehicles on the roads in place of human drivers, the problem of decision making would still exist. Nevertheless, autonomous vehicles can be better modeled as intelligence agents — which is not the case with human drivers.

A System that can adapt

For many years, game theorists were focused on stability - finding and understanding the Nash equilibrium. But life isn’t that stable, so rather than figuring a system that is stable, we should work on a system that can adapt. Game theory studies equilibrium, generally a state where no player has an incentive to change their strategy. The Braess’ Paradox is all about understanding the difference between “equilibrium” and “optimum.” If we say that an equilibrium exists in some situations, then how can it be found? This leads us to the analysis of algorithms for finding equilibria. We have several areas of research in algorithmic game theory such as algorithmic mechanism design, the complexity of finding equilibria, the inefficiency of equilibria, etc. The astonishing and incredible rate of progress in algorithmic game theory having connections with areas of computer science has led us to conclude that it will continue to flourish for many years to come and can be relied upon to furnish the solutions to modern-day as well as age-old problems.