EC 490 Week 3 lecture

1. We will first show how to model and solve sequential-move (perfect information) games in pure strategies. Wherever order of play matters to a game’s solution, it musr be shown in what is called extensive form – on a `game tree’. Contrary to what Dixit & Skeath say, a game tree is not a metaphor (or a diagram). It is a specifiable mathematical object, a directed graph. This is made clear by the fact that programmable algorithms can go back and forth between equations and game trees.

2. Even when order of play doesn’t matter in a game, you still can show it in extensive form – you just don’t have to. The first game we’ll show in extensive form is the one-shot 2-person Prisoner’s Dilemma.

3. It was said earlier that games of perfect information in pure strategies are the (logically) simplest sorts of games. This is so because in such games (as long as the games are finite, that is, terminate after a known number of actions) players and analysts can use a straightforward procedure for predicting outcomes. A rational player in such a game chooses her first action by considering each series of responses and counter-responses that will result from each action open to her. She then asks herself which of the available final outcomes brings her the highest utility, and chooses the action that starts the chain leading to this outcome. This process is called backward induction (because the reasoning works backwards from eventual outcomes to present decision problems).

4. Now we need definitions of some concepts that will be helpful in analyzing game trees:

Node: A point at which a player takes an action or receives a payoff.

Initial node: The point at which the first action in the game occurs.

Terminal node: Any node which, if reached, ends the game. Each terminal node corresponds to an outcome.

Branch: a connection between nodes, always leading in only one direction. Any number of branches may leave a node but only one branch may enter a node.

Subgame: Any set of nodes and branches descending uniquely from one node.

Payoff: an number from a player’s utility function assigned to that player at an outcome.

Outcome: an assignment of a set of payoffs, one to each player in the game.

Strategy: a program instructing a player which action to take at every node in the tree where she could possibly be called on to make a choice.

7. See <EC 490 trees>, Figure 1. This shows what a generic game tree, without assigned players and before specifying outcomes, looks like. Contrary to what Dixit & Skeath say, you should draw trees only from the top of the page to the bottom, or from left to right. In the first case, nodes at the top of the page are interpreted as coming earlier in the sequence of actions. In the case of a tree drawn from left to right, leftward nodes are prior in the sequence to rightward ones.

8. The point of representing games using trees can best be grasped by visualizing the use of them in supporting backward-induction reasoning. Just imagine the player (or analyst) beginning at the end of the tree, where outcomes are displayed, and then working backwards from these, looking for sets of strategies that describe paths leading to them. Since a player's utility function indicates which outcomes she prefers to which, we also know which paths she will prefer. Of course, not all paths will be possible because the other player has a role in selecting paths too, and won't take actions that lead to less preferred outcomes for him.

8. Our first step in modeling the PD as an extensive-form game is to represent it in terms of utility functions. In the PD, the two players’ utility functions are identical:

Go free ® 4

2 years ® 3

5 years ® 2

10 years ® 0

5. The numbers in the function above are now used to express the players’ payoffs in the various outcomes possible in the situation.

6. Let's suppose that the two players, being naïve about one-shot PDs, have formed an agreement to cooperate. Player I is to commit to refusal first, after which Player II will reciprocate. We will refer to a strategy of keeping the agreement as ‘cooperation’, and will denote it in the tree with ‘C’. We will refer to a strategy of breaking the agreement as ‘defection’, and will denote it on the tree with ‘D’. Now here is our tree: see <EC 490 trees>, Figure 2.

7. Look first at each of the terminal nodes (those along the bottom). These represent possible outcomes. Each is identified with a assignment of payoffs, with Player I's payoff appearing first in each set and Player II's appearing second. The Arabic numerals are just labels for the nodes so we can conveniently refer to them, and have no other significance. Each of the structures descending from the nodes 1, 2 and 3 respectively is a sub-game. We begin our backward-induction analysis—using a technique called Zermelo's algorithm —with the sub-games that arise last in the sequence of play. If the subgame descending from node 3 is played, then Player II will face a choice between a payoff of 4 and a payoff of 3. (Consult the second number, representing her payoff, in each set at a terminal node descending from node 3.) Player II earns her higher payoff by playing D. We may therefore replace the entire subgame with an assignment of the payoff (0,4) directly to node 3, since this is the outcome that will be realized if the game reaches that node. Now consider the subgame descending from node 2. Here, Player II faces a choice between a payoff of 2 and one of 0. She obtains her higher one, 2, by playing D. We may therefore assign the payoff (2,2) directly to node 2. Now we move to the subgame descending from node 1. (This subgame is, of course, identical to the whole game; all games are subgames of themselves.) Player I now faces a choice between outcomes (2,2) and (0,4). Consulting the first numbers in each of these sets, he sees that he gets his higher payoff—2—by playing D. D is, of course, the option of confessing. So Player I confesses, and then his partner also confesses, yielding the outcome (2, 2) at the leftmost terminal node.

8. Now we’ll practice with Zermelo’s algorithm by applying it to more games. Consult <EC 490 trees>, figures 4 and 5. These weren’t inspired so as to represent any particular situation – though no doubt there’s some circumstance or other out there in the world that each represents.

9. Now, a complication. As Dixit and Skeath say, if there’s an uncertain parametric factor that enters into the game, we can represent this by introducing a non-rational Player 0 called `Nature’ and give her a mixed strategy that represents the actual frequency distribution on the uncertain parameter in question. However, because Nature plays a mixed strategy, adding her to a game blocks use of Zermelo’s algorithm as a solution method. Dixit & Skeath get around this by averaging over the payoffs other players get on Nature’s various moves, and then inducting backward from these averages. But this is illegitimate because averaging is based on magnitudes of the numbers – and what we’re working with to this point are ordinal utility functions in which magnitudes are meaningless. So we’ll keep Nature out of the picture for now.

10. As Dixit & Skeath suggest, one common kind of scenario in which backward induction can often be implied are games between people and their future selves, as in the `smoking game’ between present Carmen and 2 future Carmens – one of whom is a smoking addict and one of whom isn’t.

Dixit & Skeath have made a shocking error in their game tree on p. 52. What is it?

Here is the correct tree.

11. We’ll now take up Dixit & Skeath’s example of a 3-player finite game of perfect information in pure strategies. Each of the 3 players could contribute, or not, to a common garden. A nice garden can be maintained by 2 or more contributors. Each player prefers a free nice garden to one they pay for, and each prefers a nice to a sparse garden. Each player i has the following utility function:

Player i does not contribute, Players j, k do Õ 4

Player i contributes, either Player j or Player k contributes or both Õ 3

Player i does not contribute, one but not both of Players j or k contribute.

Player i contributes, neither Player j nor Player k contributes

Let Player I = Emily, Player II = Nina, Player III = Talia

Cont (3, 3, 3)

Talia 4

Cont Don’t (3, 3, 4)

Nina Cont (3, 4, 3)

Cont 2 Talia

Don’t 5 (1, 2, 2)

Emily 1 Don’t

Cont (4, 3, 3)

Don’t 6

3 Cont Talia

Nina Don’t (2, 1, 2)

Don’t 7Cont (2, 2, 1)

Talia

Don’t (2, 2, 2)

When we apply Zermelo’s algorithm to this tree, we get the equilibrium path of play – i.e., what happens in equilibrium – (don’t contribute, contribute, contribute). The equilibrium outcome is (4, 3, 3).

12. Now we’ll examine the players’ strategies. Recall that a strategy specifies what a player is to do at every node where she has a decision, including at nodes that are off the equilibrium path. Emily, having only one move (at node 1), has just two strategies: contribute or don’t. However, Nina has two nodes, 2 and 3. Therefore, her strategy must tell her what to do at both (i.e., tell her what to do for either of the possibilities open to Emily). At each of her nodes, Nina has two choices. Thus she has four possible strategies – one for each possible combinations of one move at node 2 and one move at node 3. So these are (CC) (contribute at node 2, contribute at node 3), (CD) (contribute at node 2, don’t at node 3), (DC) and (DD). Of these, what Dixit and Skeath call her `optimal strategy’, but which I instead want you to get used to calling her `equilibrium strategy’ is DC. You find this by solving the subgames descending from each of Nina’s nodes. Tania has 4 nodes, 4, 5, 6, and 7. At each node she has two choices. Thus she has 2⁴ = 16 possible strategies: CCCC (contribute at all four nodes), CCCD (contribute at each of nodes 4, 5, and 6, don’t at node 7), CCDC, CCDD, CDCC, CDCD, CDDC, CDDD, DCCC, DCCD, DCDC, DCDD, DDCC, DDCD, DDDC, and DDDD. By solving each of the four subgames descending from Tania’s nodes, we determine that her equilibrium strategy is DCCD.

13. We can now state the solution to the game – its equilibrium. This is (D, DC, DCCD).

14. Emily gets a higher-ranked item in her utility function than the other two because in this game there’s a first-mover advantage. This isn’t a general feature of games. In price-setting games, for example, there’s a second-mover advantage.

15. Trees can grow complex very quickly if players have many moves. In regular (three-by-three) tic-tac-toe, Player I has 72 nodes at her second move and Player II has 504 nodes at her second move. (Question: why does Player II have so many more?) But the fact that Zermelo’s algorithm can be used to solve this games shows that it has a unique solution. Furthermore, it’s a solution we can find. The tic-tac-toe tree, though big, can still be drawn and solved by hand. This confirms what you already knew using other words: if both players use their equilibrium strategies, the game has a guaranteed outcome (in this case, a tie). (Don’t infer that in zero-sum games with unique equilibria this is always a tie. It usually is not. Dixit & Skeath show that in two-by-two tic-tac-toe, if both players use their equilibrium strategies, the first mover must win.

16. Checkers and chess are both finite perfect-information games, so we know that both have unique equilibria. However, even our fast computers have not yet found this for checkers (though they will); and finding the equilibrium solution for chess would require more computational power than is available in the universe.

17. Dixit & Skeath say (p. 69) that “experiments with some games have yielded outcomes that appear to counter the predictions of the theory.” Nonsense. Game theory is a theory of mathematics; and mathematical theories don’t make any predictions about what people or any other physical systems will do. If we model people’s games a certain way and then the result differs from our analysis, this shows that our modelling was incorrect or inadequate. It does not show that there is something wrong with game theory. By analogy: if you count two piles of stones and then sum the result, but get a different number when you count all the stones, this shows that you miscounted on one or both attempts; it doesn’t refute the rules of addition.

18. This doesn’t mean that experiments with games aren’t interesting; quite the opposite. As Dixit & Skeath, describe, for example, experiments with so-called `ultimatum’ and `dictator’ games have shown that people prefer to trade off substantial amounts of money to avoid being treated unfairly, and to punish others who behave unfairly. Dixit & Skeath rightly say that this shows “not so much the failure of rollback as the theorist’s error in supposing that each player cares only about her money earnings.” The supposition that people care only about money isn’t a supposition of game theory. I’m not sure who they think made this supposition. The point remains, however, that the only way to find out what people prefer is to run economic experiments on them; we can’t determine this just by thinking about it and doing analytic exercises.

19. Another interesting game – both interesting in itself and interesting experimentally – is centipede. Here is its tree:

Pass Pass Pass Pass

I II I II (0,0)

Take Take Take Take

(10,0) (0,20) (30,0) (0,100)

If players here care only about money and solve the game by backward induction, then at equilibrium Player I should play `take’ at his first move and the game will end right away on this very inefficient outcome. However, in experimental plays of this game, people normally it for a few rounds. What should we say about this?

The unique equilibrium of centipede really is (take at every move, take at every move). So what we must conclude from the experimental evidence is that you can’t get people to play centipede for money prizes alone; they insist on playing some other game, with other things they care about at stake. It would be a very tricky exercise to try to design a game in which what lies in the temptation basket is a proxy for what the players really care about – including their reputations with others and with themselves. Centipede might be a case of a logically interesting game that just can’t arise in the empirical world, even if you deliberately try to set it up.

20. The survivor game analyzed at the end is very interesting. Note that Dixit & Skeath use Zermelo’s algorithm here even though the game contains moves by Nature (i.e., uncertain parameters relating to players’ levels of stamina, and the choices that the jury makes). To do this they must average over payoffs. As explained earlier, in doing this they’re implicitly treating the utility numbers as cardinal – before showing you how to make sense of cardinal utility. I’d prefer that they hadn’t done this. However, in this case their averaging is relatively innocent for the special reason that we assume all players have the same utility function over what’s at stake in the game: they care overwhelmingly about the million dollars. (But see below.) One can often make the same assumption in games amongst businesses, which are supposed to care only about monetary profits for their shareholders. (However: in many cases CEOs pursue their own private agendas instead; and recently environmental and other activists have pressed for businesses to take ecological and social benefits into account in addition to profits – thus, it seems, expressing the view that shareholders in companies, for some reason, should pay higher taxes than everyone else.)

21. Unfortunately: Dixit and Skeath say in their analysis that “We can safely assume that Rich and Kelly want to maximize the probability of his or her emerging as the ultimate winner of the $1 million. Rudy similarly wants to get the prize, but keeping his word to Rich is paramount.” Stop right there! If this is true then it must appear in Rudy’s utility function.

22. In fact, Dixit & Skeath provide no payoff numbers on their tree: terminal nodes aren’t associated with utility functions. Never follow this example in this course. The situation they describe is indeed an interesting game. But it’s much too difficult for use at this point in your knowledge of game theory so I don’t know what it’s doing in this chapter. Their attempt to discuss it here leads them to provide a partial approximation of a real game tree with unspecified payoffs. Again, please treat this as an example of what you should never do: draw only game trees that contain no missing elements.