I thought that I would supplement the game theory portion of this class with some ideas that I learned in Econ 367. In this class, we have had a brief introduction to game theory. We have covered Nash equilibria in pure and mixed strategies in various games, such as the Prisoner’s Dilemma, Battle of the Sexes, and even in professional soccer. However, in each of these cases, we only considered the game being played once – the players choose their strategies, receive their payoffs, and then they walk away. What if the players play the game over a series of rounds? How would the players’ actions in the current round affect their actions in the next round? For instance, in the Prisoner’s Dilemma, would playing the game repeatedly somehow change the Nash equilibrium from (Don’t confess, Don’t confess) to something more socially optimal?

To answer this question, we need to make a distinction between finitely repeated games and infinitely repeated games. If a one-shot game is played for a finite number of rounds, then it turns out that the result in each round is the same as the result in the one-shot version. In other words, if two players play the Prisoner’s Dilemma for exactly N rounds, and they both know what N is, then they will each play (Don’t confess, Don’t confess). You may have hoped that the fact that the game is repeated allows one player to punish another in the next round for not playing Don’t confess. If this were the case, then the players would play (Don’t confess, Don’t confess) in each round, which would be socially optimal. To see why this plan breaks down, we use a technique called backwards induction. Consider round N. There are no future rounds, and so if player A plays Confess, then player B cannot punish him in the next round. Therefore, A will play Confess, since it is a best response. Knowing this, B will also play Confess in round N. Since each player knows that the other one will play Confess in round N, they will each play Confess in round N-1 as well. We continue backwards until we reach round 1, and we see that the players will have decided to play (Confess, Confess) in each round.

However, if the game is instead infinitely repeated, then the results can change drastically. Suppose that both players play a Trigger strategy, which means that each player will start off playing Don’t confess. If at any point he sees that the result of a previous game was not (Don’t confess, Don’t confess), then he will play Confess forever after. Otherwise, he continues to play Don’t confess. The joint strategy (Trigger, Trigger) then constitutes a Nash equilibrium. If both players cooperate and play Don’t confess each round, then they will each get a stream of high payoffs. If one of them deviates, then he will get a high payoff in that round, (since he plays Confess while the other player plays Don’t confess) but will get a low payoff in every round afterwards. The threat of punishment is quite severe – trying to cheat now will hurt you tremendously forever into the future. Therefore, if a game is played infinitely, then the players can achieve a socially optimal outcome.*

In the context of networks and graphs, it may be worth asking if the concept of infinitely repeated games can be applied to road networks. After all, a highway system, if formulated as a game, does not seem like it would be one-shot, since people travel on a fairly regular basis. One way to formulate an analogy could be as follows. We should all choose routes so that the total travel time for everyone is minimized. If you selfishly choose a route that decreases your travel time at the expense of others, then some other people will move over to the route that you have chosen, thus punishing you by increasing your travel time. Note that like in the infinitely repeated Prisoner’s Dilemma, this requires that the players be willing to suffer while punishing someone else. Realistically, I would not expect such a situation to arise. People punishing other people for violating social norms certainly does happen, although I would expect people on a highway to just honk their horns and shake their fists.

http://www.cs.cornell.edu/timr/papers/routing_full.ps

Here is a link to a paper about routing networks and selfish behavior, which was co-written by Prof. Eva Tardos. I have only written some of my own thoughts and speculation as to how infinitely repeated games could be applied to what we learned in class, and the paper is just extra reading for those who are interested and don’t mind some more mathematical material.

*Note: If one of the players does not value his future payoffs at all, then he will not be deterred from deviating and playing Confess.