Algorithmic game theory is an area that lies in the intersection of game theory and computer science, with the objective of under- standing 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 individual 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 before- hand to avoid this setback.
Chicken Game
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.
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.
What is Braess’ paradox?
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.
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 shoul- der 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 neces- sarily a good choice to make.
The same may happen in computer networks while load balancing or routing. Introduction of a new path changes the existing equilib- rium 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.
Effect Due to Technology
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 crises and emergencies as well as lower fuel consumption. But for this we need an algorithm which is efficient enough to coordinate the routing of automated vehicles. Autonomous vehicle traffic routing (AVTR) if achieved, would have a great impact, both on the 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 travelling from the same set of origin and destination, but also on the vehicles travelling between different sets of origin and destination. For faster and effective management oftraffic, we can develop an algorithm that assigns a vehicle a particular route from which it cannot profitably deviate.
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, 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 modelled as intelligence agents – which is not the case with human drivers.
Also read
Relationship Counselling : Job Prospects for Mending Broken Hearts
Entrepreneurship and Entrepreneurs: The Path Worth Paving
Understanding “Optimum”
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 which 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 situation, 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, complexity of finding equilibria, 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.