Repeated Games and Cooperation
In the Prisoner’s Dilemma-type game we saw the clear idea that even though by cooperating the outcome could be much better for the players, when the players make the choice in their rational self-interest we end up at a “Bad” equilibrium. Additionally, we saw that these players have a strong incentive to always confess because it is their dominant strategy.
However, in the real world, we do see people cooperate in such situations. It has been found that one of the strongest cooperation mechanisms is repeated interaction. We are much more willing to cooperate with people that we see every day, and to do a little bit of give-and-take when we know that we will see these people again tomorrow. Building up “trust” can be important and can make life better for everyone. In this chapter, we will outline some of the important conditions necessary in repeated games to make cooperation and commitments possible.
6.1 First: What Won’t Work
First let’s discuss a few situations that will not work to encourage cooperation in a Prisoner’s Dilemma-type game. Suppose we repeated the simultaneous game twice. In order to understand the actions and reactions of the players, let’s suppose that in the first round, both players cooperated and stayed quiet (Deny).
|
|
Clyde |
||
|
Bonnie |
|
Rat |
Deny |
|
Rat |
–10,–10 |
0,–20 |
|
|
Deny |
–20,0 |
–1,–1 |
|
Now we are in the last play of the game: Bonnie and Clyde have been arrested again and for some reason they know that they will never see each other again after this round of the game. Doesn’t this sound exactly like the assumptions of a one-shot game? Of course it does, and so we would predict that because both players have a dominant strategy to Rat, in this last round of the game they will both rat each other out.
So, we have clearly established that in the last round of the repeated game, they will both rat each other out. So let’s go back to the first round of the game. Because I know that in the next round of the game we will both rat each other out, what would keep me from playing my dominant strategy of ratting in the first round? The answer is, “nothing.” We could use a similar logic even if the Prisoner’s Dilemma were to be repeated 5 times, or 10 times, or 1000 times. If there is a definite ending point, the one-shot game at the end ruins the entire series.
6.2 Infinitely Repeated Games… No End in Sight
One key to cooperation is to not have a “last” play of the game. “But that’s impossible!” you say. While that may or may not be true, let’s put it in a different way: The key to cooperation is not knowing exactly when (or if) the game will ever end. For example, it is possible to achieve cooperation if there is perhaps a 10% chance that the game will end after each repetition. Thus, in theory, the game could go on forever, though it is infinitely unlikely. However, it is 90% likely that each repetition is not the last one.
How can this make such a difference? The entire chain of logic is somewhat complicated, so let’s take it step by step. First, if we don’t know with certainty when the game will end, we get rid of that “I know for sure that the other player is going to rat on me next time” dilemma, and the associated “well I can benefit by ratting on him, because I’ll never see him again” dilemma. That is one key to the answer.
Another key is to understand that strategies in repeated games can be extremely complicated. A strategy in a repeated game really has to tell you what you should do in each repetition of the game, depending on what the other player has done previously, depending on what you think he might do in the future, and depending on what you’ve done in the past and might do in the future. And, in a potentially infinite game, that is a potentially infinite number of “dependings!”
These strategies can be extremely complicated, potentially describing what to do for every repetition for every possible sequence of moves by each player. Therefore, let us have a look at a couple of simple ones. A strategy that has been shown to ensure cooperation is called the “Grim Trigger” strategy. It is a Nash equilibrium for both players to cooperate forever if their strategies for the game are both as follows:
I will cooperate and choose “Deny” in the first round. If at any point the other player (or me) chooses “Rat” then from then on I will only choose “Rat.”
This kind of strategy is called a “Grim Trigger” because it is merciless in its punishment for a single (possibly accidental) lack of cooperation on the part of the other player, and the outcome for the rest of the game is quite grim. This kind of strategy is a Nash equilibrium because if both players use it, neither player has an incentive to deviate from it, because the small gain from Ratting in this repetition is swamped by the losses forever into the future of being stuck in the (Rat, Rat) outcome.
However, there are other Nash equilibrium strategies as well, in fact there are an infinite number. In an infinitely repeated Prisoner’s Dilemma game (or one where the probability of the game ending is extremely small), literally anything could happen. This result is called the “Folk Theorem,” because like a folk tale no one knows exactly who the first person was to prove it. Without delving into the mathematical nuances, the Folk Theorem tells us that “any sequence of choices in an infinitely repeated game (such as the Prisoner’s Dilemma) are consistent with some set of rational strategies.” So, as unsatisfying as it is, we can’t rule out a scenario where both players confess five times in a row and then cooperate forever, as being irrational. Let us look at one additional example to be more concrete. We demonstrated that cooperating forever is a rational equilibrium strategy. However, so is playing “Rat” forever in this situation! It is a Nash equilibrium for both players to Rat forever if their strategies for the game are both as follows:
I will Rat forever, no matter what.
Simply put, my Ratting forever is a best response to the other player Ratting forever—to deny when the other player is always ratting senselessly harms the player who chooses to deny. So with repeated games, it is possible to get stuck in a long-run “Good” pattern with other players, or a long-run “Bad” sequence.
6.3 The Importance of Patience
The last formal lesson about repeated games that we will discuss is the importance of patience in having a chance to build a long-run relationship that stays in the “Good” outcome state. Let’s formally discuss what we mean by “patience.” Let me give you a choice between two amounts of money: I will either give you $100 today, or I can give you $111 one year from today. Which do you prefer? There is actually no “right” answer to this question, it all depends on how patient you are. Economists normally measure the patience of a person by what we call their “rate of time preference” or “discount factor.” Suppose we found a person who answered the following three questions this way:
$100 now or $110 in one year? $100 now.
$100 now or $111 in one year? I am indifferent between these two.
$100 now or $112 in one year? $112 in one year.
What we now know about this person is that their “rate of time preference” is 11%. That is, they are willing to wait on the money if we pay them at least an 11% return to wait, but they want the money now if we will pay them less than a 11% “fee” for waiting. This rate of time preference is analogous to an interest rate, and is a convenient way to measure levels of patience. A discount factor is the reciprocal of one plus the rate of time preference (r). That is, if r = 11% or 0.11, then the discount factor = 1 / (1.11) = 0.9009…. What this means is that people value $1 next year only 90.09% as much as they value $1 today.
People who have a high rate of time preference, or discount the future heavily are impatient. They have a strong preference for having things now rather than for having them later. This kind of person is less likely to get a college education because getting a college education requires that you delay gratification while you are earning a degree. This kind of person is also likely to borrow money to have now, under the assumption that they will have to pay it back later (but may never actually decide to pay it off). The impatient person is much more concerned about the “now” and not so much about the “later.”
This concept is extremely important when it comes to the prospect of finding a “Good” long-run relationship in a game. To demonstrate this for our discussion, suppose you give an employee $1000 to take to the bank. If the employee does this, they will be rewarded $1,110 over the course of the next year as the company thrives. However, the employee may just decide to take the money. If the employee is impatient, enjoying the $1000 today may sound better to them than future rewards, and such a person will discount future punishments as well.
This is part of the logic behind checking the credit reports of potential employees, and is also an argument for why education has value to employers—people who show that they are patient are simply more trustworthy!
What does this have to do with game theory? In a sequential game or in a repeated game, estimating how patient other players are is an important element. If cooperation means a lower payoff today in the hope of future gains, an impatient opponent is much more likely to take the short-run gain instead.
6.4 Some Surprising Examples of Repeated Games: The Evolution of Cooperation
Repeated games are important because they can foster cooperation. One of the best treatises on repeated games and cooperation is Robert Axelrod’s The Evolution of Cooperation.1 In the book he describes two types of things: a computer tournament and real World examples of cooperation.
In 1979, Axelrod hosted a competition where he invited people worldwide to design strategies for a repeated Prisoner’s Dilemma competition. The idea was that people would design strategies that could be fed into a computer, and then Axelrod had each strategy play against all of the others to see which performed best. The results were very enlightening. The strategy that “won,” or performed best on average against all of the other strategies was a “Tit for Tat” strategy. This strategy was to start out cooperating (Deny) and if the other player cheats (Rat) then you punish him by cheating once. From then on, always play what your opponent played in the last round: If he cheats, then cheat back. If he cooperates, then do the same in the next round. He learned that this strategy does well because while it punishes cheaters quickly, it is more forgiving than the “Grim Trigger” strategy, and allows players to get back to a “Good” equilibrium if the other player starts cooperating.
What’s more, Axelrod found that all of the top performing strategies were “nice”—meaning, that while the best strategies were willing to cheat in response to cheating, they were never the first ones to cheat. This gives some credence to the idea that “nice” guys don’t have to finish last, but quite the opposite. The lesson is, start by putting yourself out there, and reciprocity is key: Return kindness with kindness, don’t let a transgression pass without punishment, but be willing to forgive in the long run. Quite sage advice!
In the remainder of Axelrod’s book he describes many surprising tales where cooperation emerges out of chaos. I highly recommend this book to the interested reader, but I will summarize one of his stories here. Much of World War I was dominated by trench warfare. Of course, the very nature of war is to try to kill your opponent. It is hard to think of a situation where cooperation is less likely. However, after being lined up in trenches across from your enemy for a while, a repeated game sets in. To borrow two quotes that Axelrod used in his book:
… the quartermaster used to bring their rations up... each night after dark; they were laid out and parties used to come from the front line to fetch them. I suppose the enemy were occupied in the same way; so things were quiet at that hour for a couple of nights, and the ration parties became careless because of it, and laughed and talked on their way back to their companies.2
In one section the hour of 8 to 9 a.m. was regarded as consecrated to “private business,” in certain places indicated by a flag were regarded as an out of bounds by the snipers on both sides.3
Axelrod describes this as a “live and let live” policy that can spontaneously develop between opposing forces on the ground. If cooperation can evolve between opposing soldiers, then cooperation should be achievable in other very difficult situations as well.
These lessons show why it is important to study game theory by doing more than merely scratching the surface. Often people who only have one or two lectures on game theory in college, take away “be selfish” as the lesson. Sometimes, this is our advice, but for the more important cases of long-run relationships, the advice is quite different.
6.5 Game Changers: Kidnapping and Blackmail
One additional bit of advice about cooperation and repeated games: If you are ever faced with a one-shot game that has a large probability of a lack of cooperation, then try to restructure the game into a sequence of smaller games. As we have learned that cooperation is more likely in repeated games, this can often create a “better game to be playing.”
If you are ever blackmailed, you should realize from the beginning that making a large payment to the blackmailer will not work. Why not? Well because after you make the payment, you’re in exactly the same position as you were before you made the payment (except a bit poorer). The blackmailer is still unscrupulous, still knows a secret about you, and there is nothing keeping the blackmailer from coming back a second or third or fourth time to extract more money from you, or from telling the secret anyway. So, rather than settling on one payment, instead offer the blackmailer a small payment every month as long as you’re alive. That way the blackmailer is guaranteed to keep quiet and cooperation is likely to last because this is now a game with no foreseeable end.
In a similar vein, would you rather be kidnapped by an “amateur,” or by a hard-core, murderous, serial kidnapper? The serial kidnapper, of course! The serial kidnapper has a reputation to protect and must let you go when ransom is paid, because if a “paying customer” is harmed, then no one will ever make a payment to this kidnapper again. However, someone who is simply doing a one-time kidnapping in order to get some money has nothing to lose by taking the ransom and killing the hostage as well. Indeed, there is actually a benefit to killing the hostage because that is one less witness to worry about, which decreases the probability of being caught.