Chapter 4

Larger Games and ­Refinements to Nash ­Equilibrium

In this chapter, we will expand our horizons by looking at some games with more than two choices for each player so that we can get a feel for how the ideas we have been discussing generalize. We will also look at some “refinements” to the Nash equilibrium and dominant strategy concepts that help them make more sense and more relevant in the real world.

4.1 Iterated Dominance and Dominated Strategies

Let’s have a look at the game in Table 4.1.

Using the same methods as before, our solution algorithm will look like Table 4.2.

In this case there is one Nash equilibrium. Note also that the Blue Army has a dominant strategy: Their best choice is to go north no matter what they think the Red Army is going to do. However, the Red Army prefers to go south when the Blue Army goes north and prefers to go north when the Blue Army goes south. What kind of prediction can we make in such a game? The fact that there is only one Nash equilibrium, even though both players do not have dominant strategies, points us in the direction of the Blue Army going north and the Red Army going south. However, we can take this one step further. Because the Blue Army never wants to go south, we call it a “dominated strategy.” Basically, this should remove this option from consideration in the game. As long as the payoffs are correct and the players are rational, the Blue Army will never go south. It allows us to cross out this row from the game (see Table 4.3).

Now that the Red Army knows what the Blue Army is going to do, it is rather simple for us to see that the Red Army will definitely go south. This technique is called finding an “iterated dominant strategy.” The technique allows us to remove choices that will never be made, to simplify the game, and perhaps find a dominant strategy that did not exist before.

While this concept is not revolutionary in the case of games where each player only has two choices, let us now expand our horizons by looking at a more complicated game. Keep in mind that all of the techniques that we have learned thus far can be used to analyze much larger games such as these. Don’t let its large size intimidate you.

4.2 Larger Games

In this larger game (see Table 4.4), we follow the same algorithm as before to find the Nash equilibria. Considering Player 1’s best responses to each of Player 2’s possible moves, we compare the 5, 0, 3, 2, and 1 when Player 2 chooses V and find that the 5 for playing “A” is a best response (so underline it). In the next column W, pick the largest bold number, and so on for each of Player 2’s choices. Then consider Player 2’s best responses to each of Player 1’s possible choices, beginning by assuming that Player 1 chooses A, Player 2’s payoffs could either be 0, 0, 0, 5, or 1 for playing V, W, X, Y, and Z respectively. Underline the 5 as it corresponds with Player 2’s best response when Player 1 chooses A. Do likewise to find Player 2’s best response for each of Player 1’s other possible choices. Once again this gives us one Nash equilibrium where Player 1 chooses B and Player 2 chooses Z. However, this is a somewhat weak prediction because neither Player has a dominant strategy. With a little more work, we can become much more certain that (B, Z) is the only logical outcome.

First, note that for Player 1 none of his numbers are underlined for choice D or E. That is, he always has something better to choose than D or E, so they are both “dominated.” Therefore we now know that Player 1 will never choose D or E, so we can cross them off (see Table 4.4.1).

Now we will demonstrate the “iterated” part of the “iterated dominant strategy” more clearly. Now that we have crossed D and E off the list, we can find some choices that Player 2 will never choose. We see that Player 2 uses X, Y, and Z as best responses to some of Player 1’s choices, but never V or W. So, now we see that V and W are dominated, and can cross them off. A more simplified game remains (see Table 4.4.2).

By continuing this to its logical conclusion, we can see now that A is dominated for Player 1, which leads us to see that Y is dominated for Player 2. Again, this is the matrix representing the choices that are left that make sense as possibilities (Table 4.4.3).

We now see that in the remnants of the game, Player 1 has one clear choice: an iterated dominant strategy. Player 1 will always choose B, and now C is dominated. Removing the bottom row leaves Player 2 with one clear choice: always choose Z. This iterated dominant strategy equilibrium is a more solid prediction than merely concluding that there is only one Nash equilibrium. Recall that a Nash equilibrium only means that each player made their best choice given the choice of the other player. By repeatedly removing strategies as “dominated,” or loosely speaking, illogical to choose, we arrive at only one pair of choices that makes sense (in this case).

Let us look at another example that introduces a couple of new, interesting considerations (see Table 4.5). Suppose Player A chooses the last row, option J. What would Player B’s best response be? He could choose V for 2, W for 0, X for 7, or Y for 7. So, his best response would be either X or Y, so we should underline them both. Similarly with Player B, 9 is for V and Y when Player A chooses I.

In this game, there are two dominated strategies. Player B will never play W, because payoffs are always 0 and there is always a better choice. Player A will never choose H because it is never a best response.

After removing the choices H and W (see Table 4.5.1), we now see that choices G and J are dominated for Player A, and choice X is dominated for Player B.

In what remains of the game (see Table 4.5.2), there are two Nash equilibria, and if we weren’t thinking we could stop there and say “We can’t make a strong prediction in this game.” However, it would be more reasonable to say that F, V should be the prediction. Why?

Even though neither player has a dominant strategy, Player B does have what we call a “weakly dominant strategy.” Recall the definition of a dominant strategy:

Dominant Strategy: A player has a dominant strategy if one of his choices is always better than all others, for all possible strategies of the other players.

Weakly Dominant Strategy: A player has a weakly dominant strategy if one of his choices is always at least as good as all others, for all possible strategies of the other players. A weakly dominated strategy is one that is at most as good as another strategy, but sometimes worse.

In other words, Player B’s choice of V is never worse, and sometimes better than his other choice. Therefore, why should a reasonable person make any other choice? The reasoning is not quite as compelling as for dominant strategies, but it is strong. Player A should bet that Player B will choose V, and should optimally respond with F.

However, there is something else interesting about the outcome F, V that is obvious to all of us: The payoffs are huge. The top left cell with (90, 50) jumps off the page at the players (and us, the observers)! Using common sense, even though there are two Nash equilibria, we can be sure that the players’ decisions will gravitate toward the better one. This is one example of a “Focal Point.”

4.3 Focal Points

There are occasions where we can highlight some Nash equilibria as being much more “reasonable” or “likely” than others. Now that we are comfortable with analyzing games, let us look at two more whose predictions can use a little help from our common sense (see Table 4.6).

Take a moment to solve this game for yourself. You should find that:

1. neither player has a dominant strategy

2. there are two Nash equilibria, where Marge and Haley are at ­different places.

We can now tell a story about Marge and Haley from these numbers. These two people don’t seem to like each other because when they are in the same place, both would rather change their minds and leave! So, as long as they are in different places, we have a Nash equilibrium. Because there are two Nash equilibria and neither player has a dominant strategy, we can’t make a good prediction about the outcome (if we don’t use our common sense). Nash’s prediction would be for Haley and Marge to randomize their choices.1 However, we can tell more about this story: Apparently Haley loves skating and Marge loves football. The solution as to where Marge and Haley should go is obvious. We call such an obvious solution a “Focal Point,” where people gravitate toward one Nash equilibrium. These were introduced by Nobel Prize winner Thomas Schelling. In his book The Strategy of Conflict, he gives many examples similar to the following:

Suppose that you must meet someone tomorrow in Paris without being able to communicate where or when. If you meet, you win $1,000,000. If you don’t, you win nothing but must pay your travel expenses. Where and when do you meet?

Most people would say to meet at the Eiffel Tower. A large fraction of people would say to meet at noon. Out of the millions of possible Nash equilibria (all of the possible places and times that you could meet in Paris), one, or at least a very few, seem obvious. This is an example of a type of game called a “common entries contest,” where the goal is for people to choose the same thing without being able to talk about it. Another example would be if I gave people a list of colors and asked them all to write down the name of one color. If everyone writes down the same color, everyone wins $100. Here is the list of colors: red, black, beige, tan, and gray. Which color would you pick? Most people would choose red because it stands out from the other colors in some way; it is a focal point. What if everyone had to pick the same number out of all possible numbers? While this is less obvious, I would guess that “1” would be a good focal point. One can also imagine the opposite sort of game sometimes called a “rare entries contest,” where the goal is for everyone to pick something different. Could you pick a number different from everyone else in a room? How about the 1056th through the billionth digits of pi?

4.4 “Trembling Hands”

Two more Nobel Prize winners in economics, John Harsanyi and ­Reinhard Selten, discussed the idea that even though our opponent might be rational, maybe there is a chance that they might make some kind of mistake, or the other player could be making their choices according to probabilities instead of picking one choice that might appear ­optimal to us. They invented two refinements called “risk dominance” and the “trembling hand equilibrium” which are both somewhat complicated mathematical ideas that we won’t discuss in detail here. One of the things their work did was to strengthen the idea that people should never play weakly dominated strategies. However, I want to take their idea even further than they would have. Let’s look at a game to get a sense of what can happen if there is a reasonable chance of players making mistakes.

There are two Nash equilibria in this game, where you, the reader of this book and I, the author of this book both, choose A or where we both choose B. Now, both of us would rather be at B than A, because our payoffs are higher with each of us getting 3. Suppose, in addition, that we have a chance to talk to each other before the game is played and we agree that we will both choose B. However, there is one little wrinkle here: You have heard that game theorists sometimes do crazy things, or by not paying attention to what we are doing, could accidentally make the wrong choice. You believe that there is a small chance that the author could possibly forget and choose A. Now, for you choosing B does not look so appealing; there is that small chance that you will end up with –1000. Perhaps the safer bet is to agree to do something that avoids this unpleasant possibility, and agree that we will both choose A. In this case at best you wind up with 2 and at worst you will end up with 1. Taking into account the possibility of a variety of such mistakes tends to weed out some otherwise appealing equilibria.

Technically speaking, when a game theorist discusses a “Trembling Hand” he is considering only infinitesimally small chances of mistakes. This is somewhat different from the idea discussed earlier, where there may be a sizable chance that someone misunderstands, misremembers, or ­otherwise makes a mistake—which conforms to real life, in my ­experience.

4.5 Application: Rock, Paper, Scissors

Let us test our knowledge of Chapters 2, 3, and 4 by looking at the following game that will be familiar to many. The game is called Rock, Paper, Scissors, or called Rochambo by some. Think about what kind of game it is, and check for Nash equilibria, dominant strategies, and decide what advice you’d give the players.

This game is just a slightly larger version of a zero-sum game. It does not have any (pure strategy) Nash equilibria and there are no dominant strategies. However, as people who have actually played this game know, there are two ways to try to win, or at least survive this game. The first way is to try to think outside of the box and instead of making your move simultaneously as you are supposed to, to either throw a fake move before your opponent does (e.g., look like you are playing Scissors and at the last second change it to Paper), or to slightly delay making your choice until you see what the other player has played, and rapidly make a winning choice. This is normally considered cheating, however.

The real best way is to randomize your choices. We briefly mentioned in Section 2.3 that when there is no single outcome that we can divine from Nash equilibria or dominant strategies, that Nash also discussed “mixed strategies” where players randomize choices. In this case, the mixed strategies that are best are for each player to absolutely randomly pick Rock, Paper, or Scissors with a probability of 33.3% each. If each player randomizes in this way, then doing the same turns out to be a best response. That is, randomly picking is the best response to the other player randomly picking with equal probabilities. We could do this by rolling a die and if it comes up 1 or 2, play Rock; 3 or 4, play Paper; 5 or 6, play Scissors.

Just for a moment, let’s suppose that Player 2 does not randomize each of his choices one-third of the time. What would happen? Let’s discuss two possible ways he could “mess up” and how Player 1 could take advantage of it.

First, let’s assume that Player 2 has a habit of playing Rock more often than the other choices; that is, maybe the Rock is his favorite move. If you know that your opponent loves to play Rock a lot of the time, what should you do? Of course, you should play Paper a lot of time and ­Scissors much less often, and you will win more than half the time.

There is another interesting way that people might not randomize. Steven Scroggin2 discussed how people are unable to randomize inside their own heads. For example, suppose Player 2 has just played Rock. If Player 2 were truly randomizing, for example by rolling a die, then 33% of the time he should play Rock again. Suppose Player 2 has just played Rock twice in a row. Then once again, if you were truly randomizing then he should play Rock a third time in a row 33% of the time. What Dr. Scroggin found was that most people don’t randomize correctly, and that there are very few people who would ever play Rock three times in a row, because it just doesn’t “feel” random enough to most people.

Why is this important? If you are ever playing this game and someone plays the same thing twice in a row (say, rock) then you can be pretty sure that you will not see rock the next time. What that means is on the next play you should absolutely not play paper, because your opponent will likely not play rock. The lesson is that sometimes, when they try to become “unpredictable,” people actually become more predictable!