Solving Games

Monday, 12/03/01

The amount of material presented in lectures on game theory are a very small slice of what all of game theory is about. Game theory has been extended to all kinds of strategic situations, and most of what you see in computer games, political negotiations and elections, and military conflict can be modeled as a game in our game theoretic sense. In fact, the guys at RAND Corporation (a government-military think tank) did much of the breakthrough research in game theory in the 1950s as part of figuring out how to play the Cold War against the Soviets. The game was intimidating each other into not actually firing nuclear weapons. Can you see how this could be diagrammed as a prisoners' dilemma game?

What you need to know to Set Up a Game

Anyway, we have only presented two types of simple games with basic structures. Whenever you need to figure out a game, the things you need to know are:

1. Who is playing?
2. What strategies can each player pick?
3. What order do the players pick their strategies in?
4. For every possible outcome, what is the payoff to each player?

The problem will always give you these pieces of information. If you do not have any of the four pieces, you cannot even set up the game, much less solve it.

Solving the Game

Now then, suppose we have all the pieces of information necessary. How do we go about solving a game?

1. The first thing to ask is if this is a sequential or a simultaneous move game. Identify who the players are, and then figure out if there is an order to the game. If everybody picks at the same time, then you want to solve the game by using a diagram like prisoners' dilemma. If it is a sequential game where one guy moves and then the other guy moves after him, you want to set it up as a tree.

2. Now that you know if you want a tree or a box diagram, put the players at the appropriate places. Now fill in the strategies they can pick and the payoffs. If you do not know how to do this, you definitely should come in for help.

3. This is where we start to figure out best moves.
   • If this is a box diagram, you want to find out what everyone's best moves are.
     • First assume the Column guy picks Left. What is the Row guy's best move? Compare the Row guy's payoffs in the (Top, Left) and (Bottom, Left) cells. Underline the better of the two Row guy payoffs.
     • Now assume that the Column guy picks Right. What is the Row guy's best move? Compare the Row guy's payoffs in the (Top, Right) and (Bottom, Right) cells. Underline the better of the two Row guy payoffs.
     • Then we need to solve for the Column guy's best moves. Suppose the Row guy picks Top. What is the Column guy's best move? Compare the Column guy's payoffs in the (Top, Left) and (Top, Right) cells. Underline the better of the two Column guy payoffs.
     • Lastly, suppose the Row guy picks Bottom. What is the Column guy's best move? Compare the Column guy's payoffs in the (Bottom, Right) and (Bottom, Left) cells. Underline the better of the two Column guy payoffs.

   • If this is a tree, we are dealing with a sequential game and solve it by working backwards from the end of the game.
     • Suppose we are on the top branch. What will the second mover pick? Compare his two options on the top branch and underline the better of the two second mover payoffs.
     • Suppose we are on the bottom branch. What will the second mover pick? Compare his two options on the bottom branch and underline the better of the two second mover payoffs.
     • The first mover is clever and knows what the second mover will do in either case. The first mover picks which branch to go to, so he will consider the outcome the second mover forces on each branch. He thinks: "If I go to the top branch, I know which outcome the second mover will choose to happen. If I go to the bottom branch, I know which outcome the second mover will choose to happen. Of those two, which is better for me?" The first mover will compare only those two outcomes and disregard the ones the second mover will not pick. Underline the better first mover payoffs when you compare those two.

   • Note that if some player always does the same thing in either game diagram type, then that guy has a dominant strategy. After you do all your underlinings, check for dominant strategies - if you don't know how to do this, ask!

4. Now check for dominant strategy equilibria. There can only be a dominant strategy equilibrium if every player has a dominant strategy. If this is not the case, move on to the next step.

5. Lastly, look for Nash equilibria. Any cell or tree outcome that has underlines for both players will be Nash. This is always true. If you need convincing of it, come talk to me.

Dominant vs. Nash

We have two solution concepts: Dominant Strategy Equilibrium and Nash Equilibrium. How do we distinguish the two?

Quick answer: All dominant strategy are Nash, but not all Nash are dominant strategy.

First, what's the definition of a dominant strategy? If you have a dominant strategy, it means you don't care what the other guy does. That dominant strategy is so awesome, that you're gonna pick it no matter what.

The second thing we want to know is what an outcome means. When we talk about an outcome, we are talking about the strategies that every player plays. In order to have a well specified outcome, you need to say what strategy every player picks. If you forget to tell me what one of the players does, then you have not given me a complete outcome. The payoffs from the outcome of the game are different from the outcome itself.

So what is a Nash equilibrium? An outcome is Nash if nobody wants to change their mind. Payoffs are not Nash! Recall what an outcome is - a set of assigned strategies that everybody will pick. If you take one guy and tell him, "Look, I can force everybody else to continue to pick what we told them to pick in the Nash equilibrium. I will cut you a special deal and let you change your mind if you like. Do you want to pick something other than what we've told you to pick?" If the outcome is truly Nash, the guy will say no. Just try looking at a cell in a game that is claimed to be Nash. Force everyone to stay with their assigned strategy except one guy. Compare his alternatives - they will be worse than if he sticks with his assigned strategy.

Remember what a dominant strategy was - if you have a dominant strategy you never want to pick anything else. Guess what, that means that in a dominant strategy equilibrium, nobody wants to change their mind. That sounds like it's Nash. But can you have Nash equilibria without dominant strategies? Indeed you can, and we gave an example on problem set 5, problem 5. Neither player has a dominant strategy (hence there cannot be any dominant strategy equilibria), but there are two Nash equilibria.