Chapter 2

How to “Solve” a Game I

Simultaneous, One-Shot Games

Now we will introduce some tools for achieving the major objective of game theory: If we are thinking about a particular strategic situation, what would we predict the players will do? Sometimes we can pinpoint one prediction that is clear, but other times we are left without any clear guidance. However, as we will see, in these situations the guidance is to act randomly (but in a specific way), or to try to change the rules of the game when possible. In this and the next two chapters we will look at games where people make choices at the same time. Then in Chapter 5, we will discuss games where one player moves first, and then the second player makes their decision in response.

2.1 Simultaneous Games: Dominant and ­Dominated Strategies

We will begin by imagining a situation where players have to make their choices at the same time, or at least without knowing what the other players have done before making a choice. We call these ­simultaneous games, and we will start with a simple, nonsensical game to get ­accustomed to looking at a payoff matrix. In Table 2.1 we see two players, Row and ­Column, so named because Row’s choices are the top or bottom row, and Column’s choices are the left or right column. In these matrices we always list the Row player’s payoffs first, the Column player’s payoffs second after a comma. I also made Row’s numbers bold to make it easier to keep track. Suppose that Row chooses “top,” then his payoff depends on whether Column chooses Left, or Right. If Column chooses left, Row gets 4, and if Column chooses right, Row gets 8. More importantly, what should Column choose if he thought Row chose top? We must pay attention to Column’s payoffs, 7 for left and 6 for right. In this case, Column’s best response to Row’s top is to go left. As this is a simultaneous game, ­Column does not have the luxury of seeing Row’s choice before he must make his choice. How can we proceed?

Let us think about asking each player how they would respond if they saw the other player’s move, and keep a record of the responses.

Column: If Row chose top, you would choose left, because 7 is greater than 6.

Column: If Row chose bottom, you would choose left, because 9 is greater than 8.

It looks like Column should always choose left, regardless of whether Row goes top or bottom! Because this is the case, we say that for Column choosing left is 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 choices of the other players.

Dominated Strategy: A choice that is always worse than some other choice. When there are only two choices, if one is dominant, the other is dominated. In Chapter 4 we will explore dominated strategies further.

That is, “left” is a dominant strategy because it is his best move no matter what Row chooses to do. Now, let’s talk through Row’s best responses:

Row: If Column chose left, you would choose top, because 4 is greater than 3.

Row: If Column chose right, you would choose top, because 8 is greater than 7.

So, we can see that Row wants to choose top in this case, no ­matter whether Column chooses left or right. So, Row also has a dominant ­strategy, to always choose top, no matter what. Well, we should see clearly now what our prediction will be in such a game. Because both players have only one choice that makes sense for them, we will predict in this game that the outcome should be (top, left). We call this kind of outcome a Dominant Strategy Equilibrium.

Dominant Strategy Equilibrium: A predicted outcome where all players have a dominant strategy.

For games where there is a dominant strategy equilibrium we can have a very confident feeling that we know what will happen, assuming that the players are rational. However, it is not always the case that people have such clear-cut decisions.

2.2 Nash Equilibria

Take a look at Table 2.2 where the numbers have changed:

Let us again think about asking each player how they would respond if they saw the other player’s move, and keep a record of the responses.

Column: If Row chose top, you would choose left, because 6 is greater than 4.

Column: If Row chose bottom, you would choose right, because 8 is greater than 7.

Column now has a vested interest in Row’s choice, since Column has no dominant strategy!

Row: If Column chose left, you would choose top, because 6 is greater than 5.

Row: If Column chose right, you would choose bottom, because 10 is greater 7.

As with Column, Row does not have a dominant strategy, because sometimes he should go top, and sometimes bottom. How can we make a prediction about a reasonable outcome? Until John Nash’s idea of an equilibrium, no one could say. Thinking of an “equilibrium” as a ­balancing, or resting place, Nash said (paraphrasing, as his idea was actually a highly mathematical one):

Let’s call something an “Equilibrium,” or reasonable outcome, if we can find an outcome where neither player would want to change their decision after learning of the outcome. In other words, each player has made the best response to the other player’s choice.

Keeping in mind that this is a simultaneous game, we imagine that both players make a choice and then the pair of choices is revealed. Suppose the outcome of the game was top, right. Let’s see if either player would want to change their minds. Look at Table 2.2 again, and put yourself in Column’s shoes. He has just learned that Row chose top. Let us outline the top row to focus on Column’s Best Response in Table 2.3. As Row decided to put us in the top row of the table, Column could have chosen right for a payoff of 4, or left for a payoff of 6. Did he make the best response to Row’s choice of top?

Now that Column learns that Row chose top, he regrets choosing right. He wishes that he could go back and change his mind to left. Let’s revisit the definition of the Nash equilibrium: “An outcome is a Nash equilibrium only if neither player would want to change their mind, that is, if neither player regrets their choice once they learn the other player’s choice.” Because the Column player did not choose his best response to Row’s choice of top, this outcome is not an equilibrium. Another way of saying this is that the outcome of top, right is not “stable” because someone wants to move. Thus, our goal is to determine if any of the four possible outcomes are Nash equilibria. Let me now teach you a shortcut method of finding Nash equilibria. Let us revisit the list of responses that the two players gave us about their past responses.

Column: If Row chose top, you would choose left, since 6 is greater than 4.

Column: If Row chose bottom, you would choose right, because 8 is greater than 7.

Row: If Column chose left, you would choose top, because 6 is greater than 5.

Row: If Column chose right, you would choose bottom, because 10 is greater than 7.

Notice that each of the numbers underlined above have been underlined in the payoff matrix below (Table 2.4). This shorthand notation will visually tell us the best response for each player. Note that top, left and bottom, right have both numbers underlined within the box. The first underlined number tells us that this choice is Row’s best response to Column’s choice. The second underlined number tells us that this choice is Column’s best response to Row’s choice.

Therefore, there are two Nash equilibria in this game: where the ­players have made their “mutual best response” to each other’s choices. In neither of these outcomes would either player desire to change their mind, given what the other player did, because they would obtain a lower payoff if they did so. However, since there are two such outcomes, we are not given quite as clear a prediction as in the case of dominant strategies, but it does offer some guidance.

At the risk of overcomplicating things, I have to also tell you that there is a third Nash equilibrium in this game. The kind of Nash equilibria we have been talking about so far are called “Pure Strategy” Nash equilibria. A pure strategy is when someone picks one choice. From time to time we will also talk about “Mixed Strategies,” that is, when it might be best to randomly pick your choices, but in a particular way.

For example, a pitcher in baseball might have a best strategy to throw a fast ball 32% of the time, a curveball 63% of the time, and a slider 5% of the time. He could program a computer to choose randomly according to these probabilities, or have a coach to do so and signal him. In response, a particular batter might optimally respond by swinging hard 55% of the time, going for a bunt 25% of the time, and letting the ball go by 20% of the time. If each player’s probabilities are “best responses” to the other player’s probabilities, then we call this a “Nash Equilibrium in Mixed Strategies.”

In John Nash’s discovery he also showed how players should randomize, that is, with which probabilities the pitcher and batter should choose each strategy. Although we will mention randomizing choices from time to time, the method of calculating the probabilities is an advanced topic beyond the scope of this book.

2.3 More Practice and a Simple Algorithm for Solution

Let’s look at two more games to practice this shortcut method, make it even easier, and make sure we understand how and why it works. Suppose that Joe and Jack are bar owners and they have never had “Happy Hours” before, but they have recently heard of them in other cities. Happy Hours are where bars have very cheap drinks and free food between, say, 5 and 6 p.m. on workdays. It is a way to attract customers after work. Even though you lose money on the drinks and food during the Happy Hour, some of the people attracted by this “loss leader” will stay until after 6 p.m. and provide extra profits. Their payoff matrix is represented in Table 2.5, where the numbers might represent profits per day in thousands of dollars.

When we query Joe and Jack about their best responses to the other player’s moves, the process can be simplified into the following simple procedure: Jack compares the two bold numbers, 2 and 1, and his best response is the larger one. This corresponds to saying: “If Joe chose to have a Happy Hour, Jack’s best response is to have a Happy Hour because 2 is greater than 1.” Underline the 2. Similarly, Jack compares the gray highlighted numbers, 11 and 8, and we can underline the 11 as his best response (to Joe not having a Happy Hour). When considering Joe’s best responses, we can compare the white 3 to the white 1 (underline the 3), and the 10 to the 9 (underline the 9). When all is said and done we will have two underlines in the box where both Jack and Joe will have Happy Hours. Therefore, in this game there is only one Nash equilibrium. However, we can also go further than this. Because both of Jack’s underlines are in the top row (for Happy Hour, under the 2 and 11), this tells us that Jack’s best choice is always to have a Happy Hour, no matter what Joe does; therefore, it is a dominant strategy for Jack to have a Happy Hour. Similarly, both of Joe’s underlined numbers (under the 3 and the 10) are in the left column where Joe chooses to have a Happy Hour, so we can also say that Joe has a dominant strategy to have a Happy Hour. So in this game our analysis would say that there is one Nash equilibrium, and it is also a dominant strategy equilibrium because both ­players have dominant strategies. In this case we can be fairly certain that both players will choose to have a Happy Hour, even though both players could make more money if they were somehow forced not to have Happy Hours (8 and 9). However, without some external force holding them to this agreement, Joe and Jack will not keep any agreement to refrain from Happy Hours, because they have such a strong incentive to cheat on any such agreement. Actually, in some states in the United States, bars have successfully lobbied their legislatures to outlaw Happy Hours in order to raise profits (North Carolina is one such example).

Here is one final game (see Table 2.6). Practice the method described so far to determine if there are any Nash equilibria or if either player has a dominant strategy.

For Sarah we underline the 10 and the 8 and for Paul we underline the 11 and the 13. Are there any Nash equilibria? No, in this game there is not, because there is no outcome where both players have made a mutual best response. We can see this because there is no outcome where both players’ numbers are underlined. What is going on in this game?

Suppose that both players showed up at the skating rink. Paul is content with this outcome and would not want to change his mind. However, Sarah’s best response to Paul showing up at the skating rink is to be at the football game. Therefore, it is not a Nash equilibrium. What about the outcome in the bottom left corner where Paul is at the skating rink but Sarah is at the football game. We see that Sarah is content with this because when Paul is at the skating rink Sarah’s best response is to be at the football game. However, this is not a Nash equilibrium (think: stable point) because when Sarah is at the football game Paul’s best response is to be at the football game also because he gets 13 in that case instead of 5. When they are both at the football game, this is not a Nash equilibrium because when Paul is at the football game Sarah’s best response is to be at the skating rink. And finally, when Sarah is at the skating rink and Paul is at the football game, this is not a Nash equilibrium because when Sarah is at the skating rink Paul’s best response is to also be at the skating rink. Can you now summarize what’s going on in this game in a few words? It appears that Paul is only happy when he is with Sarah. However, Sarah does not want to be in the same place as Paul. In this kind of situation, there is no outcome where both players are content. But, let’s be a little more precise in our language because a Nash equilibrium is not really about being “content” or not; it is about whether there is an outcome where neither player regrets their choice, given the choice of the other player. In this case, in each outcome there is one player who regrets their choice after learning the outcome of the game; it is unavoidable.

Also note that neither player has a dominant strategy. Paul’s best choice depends on Sarah’s choice, and vice versa. In this type of game, we can’t make any solid prediction about what might happen, except to say that players in this game should randomize their choices. So, we see here a case where the only Nash equilibrium is in mixed strategies, or probabilities.

2.4 It Is All About the Payoffs

Hopefully by now you are thinking: “How can I actually use this?” The answer is, “By carefully writing down the choices and the payoffs for each player in the game.” In Chapter 4, we will look at larger games with more than two choices for each player, and it is possible to analyze choices for more than two players as well. So you really can apply this to the real world. In this section we give some words of caution, however.

When people have different notions about the payoffs for other ­players, we end up with bad outcomes. Here is a classic “Marriage Game” illustrated by a common difficulty discussed in “Men are from Mars, Women are from Venus.” The woman (Steph) comes home from work upset. She sees her husband (Sam) and they have to decide how to interact. Now, in this game, the husband’s payoffs are the same as the wife’s, because sometimes the husband is only going to be as happy as the wife is! Sam thinks the game looks like Table 2.7.

Sam thinks that he has a dominant strategy for talking a lot and trying to “fix” whatever the problem is, and also seems to think that women always want to talk about their problems. His expectation is that she will talk, and he should talk about it with her as well. The “real” game might be (see Table 2.8)

Here we see the real dominant strategy for Sam: Listen, and don’t try to help or interrupt. If you insist on talking, then her best response is not to talk to you!

Similar situations can arise in the business or government world, as well. You may not understand why a company or a country is making “irrational” decisions; it may be that they are rational, but you simply misunderstand their payoffs. This points out the now obvious fact that sometimes it is important to clearly let other players know what your payoffs or preferences are. However, sometimes, one can obtain a higher payoff by deceiving the other players about your payoffs.

In the next chapter, we will discuss several common types of games. Once you learn to recognize them, they give a shorthand way to classify strategic situations so that you can easily foresee the types of outcomes that are likely.