Game Theory

How Adding a New Expressway Might Lead To More Traffic?

756

Game Theory

Mathematics

Generally, new roads and highways are built to reduce the travel time and traffic between two points. But on the contrary, the opposite can happen. These new roads might result in more traffic and increased travel time. This is generally called <b>Braess paradox</b>. Here we will discuss why this happens and what can be done to avoid this. But before that, we will need to understand some Game Theory. <b><h2><center>A Small Introduction to Game Theory</b></h2></center> Game Theory is a branch of mathematics concerned with the <b>analysis of strategies</b> for dealing with competitive situations where the outcome of a participant's choice of action depends critically on the actions of other participants. The player aims to make a choice such that whatever the other player(s) choose, their payoff is the least. One classic and simple example to understand the concept of Game Theory is <b>Prisoner's Dilemma</b>. Let's say there are two thieves. They are being interrogated in separate rooms, and they can't communicate with each other. Police give both of them a deal. The deal is that if one thief agrees to the crime while the other doesn't, the one agreed will receive jail time for one year, and the other guy will be imprisoned for six years. If both of them agree to the crime, they will receive jail time of 4 years. If they both deny that they committed the crime, they will be imprisoned for 2.5 years. As thieves can't communicate, they can't tell which option the other one will go for. So what choice should the thief one should go with? <img src="https://i.ibb.co/ZSWgxHF/thief-gt.jpg" alt="thief-gt" border="0"> The above table (called the <b>payoff matrix</b>) shows all the possible scenarios for both thieves. Now the "best" option for both the thieves will be to deny the crime. But that's not the safest option to go with for thief 1. Let's say thief 1 and thief 2 deny the crime; they both will receive 2.5 years of jail time. But thief 2 can also accept the offense, thinking that if thief 1 denies the crime, they will receive only one year of jail time. In such a case, thief 1 should see the possible options for thief 2 and try to reduce their payoff. So let's consider the case in which thief 2 accepts the crime. In that case, thief 1 will receive four years of jail time for accepting the crime and six years for denying it, so the best option for thief 1, in this case, is to accept the crime. On the other hand, let's say thief 2 denies the crime. In this case, thief 1 will receive jail time of 1 year for accepting the crime and jail time of 2.5 years for denying it. Again, in this case, the best possible option for thief 1 is to accept the crime. Hence using game theory, thief 1's safest bet is to accept the crime no matter what option thief 2 goes for. Similarly, thief 2 should also go for accepting the crime to minimize the payoff. This configuration (of both thieves accepting the crime) is <b><a href="https://en.wikipedia.org/wiki/Nash_equilibrium">Nash equilibrium</a></b> for this case. <b><h2><center>The Traffic Problem</b></h2></center> Now let's understand the setup for highway-traffic problems and how game theory is involved in this. We have to go from place A to place B. There are two different ways to go from place A to B. One road goes from A to B through another point, C. In contrast, another road goes through point A to B through point D. The time it takes to go from point A to C is proportional to the number of cars on the road [time = k.x where x is the number of vehicles and k is a constant] but the time taken to go from C to B is always 45 minutes. Similarly, the time taken from point A to D is always 45 minutes. On the other hand, the time taken to go from D to B is proportional to the number of cars on the road. This whole setup is shown below. <img src="https://i.ibb.co/3FGRPzK/road-setup-1.jpg" alt="road-setup-1" border="0"> In the above setup, the travel time from A to C is proportional to the number of cars, where x is the number of vehicles on the road. Similar is the case of route D to B, where y is the number of vehicles on the road. Now, if you think <strong><i>people are always playing a game while driving</strong></i>. If they have two options to reach a place, they will start thinking about which way will help them get faster to their destination. This is another example of game theory, but hundreds and thousands of people are playing the game simultaneously. Now let's consider that in the above setup, 4000 people are driving a car together and have a choice on which road to take. What would be the best configuration of the vehicles on each route? It would be challenging to make a payoff matrix for 4000 people. So here, we will use another concept of game theory called <b>Potential function</b>. The potential function is the sum of the payoffs of all the players playing the game. This function is also called the <b>Potential energy of the game</b>. We will try to minimize the potential function to find the configuration of cars in equilibrium. In our example, if 'n' cars are running on the road AC then the potential function for road AC will be given by &sum;<sub>x=1</sub><sup>N</sup> x/100. Similarly, the potential for road CB will be n*45. The total potential of the whole system is: <b><center>P(n) = &sum;<sub>x=1</sub><sup>N</sup> (x/100) + n*45 + &sum;<sub>y=1</sub><sup>4000-N</sup> (y/100) + (4000 - n)*45</b></center> To minimize the potential, we will use some basic calculus and differentiate P(n) with respect to n and equate it to 0. After we minimize the potential, we will get that 2000 cars should run on each road. Incidentally, that is the optimal case as well. It must be noted that <i>game theory doesn't provide the optimal solution; instead, it provides the solution where the risk of a higher payoff is the least.</i> <b><h2><center>Braess Paradox</b></h2></center> Until now, we haven't discussed the original problem of how adding a new highway or expressway increases traffic or travel time. Everything we have seen till now was a setup for this problem. In the above example, let's say the government decides to add a new expressway from point C to D which is a one-way expressway. The travel time on this expressway is almost 0 compared to roads like AC and CB. Our new diagram looks like this: <img src="https://i.ibb.co/7SGTkgC/road-setup-2.jpg" alt="road-setup-2" border="0"> Before the expressway was built, our Nash equilibrium was 2000 cars on either road. Now, at point C, n1 cars decide to go from C to B and n-n1 cars decide to go from C to D. What will be the new nash equilibrium? The potential for this system will be given by: <b><center>P(n) = &sum;<sub>x=1</sub><sup>N</sup> (x/100) + n<sub>1</sub>*45 + &sum;<sub>y=1</sub><sup>4000-N<sub>1</sub></sup> (y/100) + (4000 - n)*45</b></center> We cannot use differentiation to find n and n1 values where the potential function maps to its lowest value because the function is decreasing linearly in the domain. Hence, it will be the lowest at n (= 4000) and n1 = 0. These values mean all the cars follow route A->C->D->B to achieve nash equilibrium. The total travel time for one car, in this case, is 80 minutes but you may notice this is not the optimal travel time. The optimal travel time would be when half of the car use route A->C->B and the other half use route A->D->B when the travel time will be 55 minutes for all the cars. The new expressway was built to decrease the traffic but in turn, it led to more traffic on some specific routes. This is what we call the <b><a href="https://en.wikipedia.org/wiki/Braess%27s_paradox">Braess Paradox</a></b>. <b><h2><center>How Can This Be Solved?</b></h2></center> Now let's say the government has already built the expressway and realized that it is leading to more traffic. What can they do to prevent this? One simple solution is to <b>increase toll tax on route AC and decrease toll tax on route AD</b>. Increasing and decreasing toll tax will form another game theory setup. Another way would be to just <b>remove the expressway</b> but that would be a waste of money spent on building the highway. The <a href="https://can.org.nz/article/huh-4-cases-of-how-tearing-down-a-highway-can-relieve-traffic-jams-and-save-your-city">real-life example of the Braess paradox</a> could be seen in the Jung Gu district of South Korea, the Seoul Metropolitan Government decided to dismantle the 10-lane roadway and the 4-lane elevated highway that carried over 170,000 vehicles daily along the Cheonggyecheon stream. This led to a decrease in traffic. Another example comes from the state of Haryana in India where the state government decided to scrap a flyover project after models predicted it would lead to higher traffic.

- Ojas Srivastava, 11:13 PM, 14 May, 2022

Braess Paradox