Traffic Lights and Nash Equilibrium

A post after a long while! I have been wanting to write a short blog post on how traffic lights relate to Nash equilibrium for a long time, so decided to finally do it today. This is an short but smart example on how traffic lights can be thought of as a medium to enforce certain special conditions among agents (people driving on the roads), and avoid conflicts in the process.

Imagine the scenario of two cars coming along different roads towards an intersection. As they approach the point where the two roads meet, they notice each other. Each one now has two choices: to either ‘Go‘ (i.e. continue driving) or ‘Stop‘ (i.e. hit the brakes). Lets draw the corresponding pay-off matrix (Calling the cars Player1 and Player2)

            Go              Stop

Go       -10, -10      4, -1

Stop     -1, 4           -3, -3

Assume Player1 corresponds to the rows, and Player2 corresponds to the columns. Of course it doesn’t really matter here, since the matrix is symmetrical. For each of the four tuples, the first number corresponds to the payoff to Player1, and the second one to Player2. Lets look at the payoffs in each of the four scenarios. If both players Go, it will cause an accident- hence the high negative payoffs for both. If one Goes and the other Stops, the stopping one gets a small negative payoff (-1), while the one who continues driving gets the best possible payoff (4). The weirdest case would be if both Stop, causing something of an infinite wait (technically) – yielding negative payoffs for both (Though not as negative as an accident, since being bored waiting is better than being dead any day). So how do we determine who does what? For that, we will analyze the best responses.

Consider Player1. If Player2 decides to Go, Player1’s better payoff comes from doing Stop (-1 > -10). On the other hand, if Player2 decides to Stop, Player1 should Go (4 > -3). Now since this is a symmetrical scenario, the same applies the other way round too. So lets mark these ‘best responses’ on the payoff matrix.

             Go              Stop

    Go       -10, -10      4*, -1*

    Stop     -1*, 4*           -3, -3

Remember: In a pure-strategy payoff matrix, whenever a cell corresponds to the best response for all players involved, it indicates a Nash equilibrium. In simple terms, a Nash equilibrium is a scenario where NO player benefits from changing his/her strategy, given the strategies of all the others. Look at the cell (Stop, Go) for example. Player1 has decided to halt and Player2 is continuing to drive. Would either be better off doing the opposite, given the other continues with what he is doing? Not really, cause it will either lead to an accident (Go, Stop) or an infinite wait (Stop, Stop).

So we have two different Nash Equilibria, essentially at the scenarios where one player goes and other stops. But we must realize that each player will prefer one of these two scenarios. Player1 prefers (Go, Stop) – where he gets to continue on and the other stops, while Player2 prefers (Stop, Go). If both decide to do what they prefer, its obviously an accident.

Now this is where traffic lights come in. Based on the time instant when the two cars arrive at the intersection, the traffic lights will tell one Player to stop, while the other to Go – thus forcing the whole ‘Game’ into one of its Nash equilibria. The main thing to remember is that it does so randomly, or atleast fairly (Sometimes, a light may go green for a little longer for roads that are known to have high traffic at certain times of the day). Because of this, no agent (i.e. driver) has any incentive to gain from deviating from what the traffic lights tell him/her to do. Obviously (like all Game theory simulations really), this is a simplified version of what really happens, but you get the basic idea: traffic lights randomly push the game towards one of its Nash equilibria.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s