Friday, May 14, 2010


An explanatory word to my readers. Each of the installments of this Formal Methods tutorial is not very long. There are two reasons for this. First, it is difficult stuff, and I do not want to scare away readers for whom this is all new.. Second, I am writing two blogs at the same time -- this one and my Memoirs -- and I am working flat out. Five typed pages or so of this formal material is all I can manage each time I post. So be patient.

We come now to the most elaborate, the technically most difficult, the most popular, and the most often misunderstood body of formal materials applied to philosophy, politics, law, military strategy, economics, and love: Game Theory. Quick check -- Google finds 600,000 sites for "Prisoner's Dilemma" and 1,900, 000 sites for "zero sum game." Not quite up there with Lady Gaga [83,700,000], but still, not chopped chicken liver either. This is going to take a long time, and there are going to be some seriously technical patches that will try both your patience and my skills at explication. Nevertheless, if, in the immortal words of W. S. Gilbert in Patience, you want to "get up all the germs/ of the transcendental terms," now is your chance to do it. By the way, if you are actually paying attention to the outline with which I started, you will notice that I moved Game Theory up ahead of Collective Choice Theory. Arrow's Theorem and Amartya Sen's extension of it are two of the loveliest bits of theoretical material around, fully deserving of the two Nobel Prizes they earned. But their application to the fields you folks come from is not as rich as the application or misapplication of Game Theory, so I figured I would get to the good stuff before you all drift away. Here we go.

I. Introductory Remarks

In the eighteenth and nineteenth centuries, the standard conception of the capitalist market was of a place inhabited by so many sellers and so many buyers that the actions of any one buyer or seller had a negligible effect on prices. One buyer, by shifting to a different supplier or choosing not to buy at all, could have no measurable impact on what came to be called aggregate demand, and the output of one factory or shop had as little impact on aggregate supply. The marketplace was, in this sense, opaque. One could not see through the hustle and bustle to the individual suppliers or buyers whose actions, intersecting with one another, were determining the structure of prices. The standard term for this situation is that everyone was a "price taker," and no one was a "price maker." This was always an idealization that did not quite fit the facts, of course. First of all, from the very beginning there had been producers who managed to control so large a part of the market for their goods that they could simply dictate the prices at which they sold. They were said to have a monopolistic position in the market. There were also buyers who exercised a monopoly -- Kings and Princes who by main force made themselves the sole buyers for certain luxury or military goods and so could dictate the prices at which they bought.

By the beginning of the twentieth century, economists were theorizing about situations that fell somewhere between monopoly and perfect competition, situations in which a small number of producers dominated a market -- three or four great steel producers, three auto manufacturers, and so forth. A sizeable literature grew up dealing with what was called Imperfect Competition. For example, in 1933, Joan Robinson, the doyenne of the Cambridge School, published The Economics of Imperfect Competition. The defining characteristic of imperfect competition is that it is a situation in which the opacity of the market lifts, and it becomes possible for the a producer to know about, be aware of the individual behavior of, and thereby adjust its own behavior to, that of the other producers.

Beginning in the 1920s, John von Neumann, one of the genuinely great minds of the last hundred years and more, developed a powerful mathematical analysis of the decision making that is possible in the precisely delineated structure of a game as well as in the situation of imperfect competition that economists had been examining. Joining forces with Oskar Morgenstern, an economist, von Neumann elaborated his theories in one of the great books of the twentieth century, The Theory of Games and Economic Behavior, published in 1943. If you are unfamiliar with von Neumann's career, it is worth your time to look him up. He had a unparalleled capacity to grasp the underlying formal structure of a wide variety of fields, and made contributions not only to mathematics and economics, but also to physics. He is also the person who came up with the idea of using a binary number system so that it could be modeled in an electrical circuit, thereby making possible the digital age. Suffice it to say that there are only two or three talents that I would give years off my life to possess, and that is one of them.

What makes games so interesting, from von Neumann's point of view, is that they are interactions in which the number of players, the outcomes or payoffs, and the permissible moves are all precisely defined by clearly stated rules. Games are thus, in a sense, models of economic transactions. In many games, each player knows who his or her fellow players are, how they value the outcomes, and what the moves are at any stage in the game that are available to each player.

II. The Definition of a Game - Extensive Form

I am going to start by analyzing a very simple game. This will give me a chance to define the key concepts we are going to be working with. Here is a game I invented for these purposes, called Take Away Matchsticks. There are two players, and a pile of four matchsticks lying on a table. Players take turns moving. Each move consists of taking away either one or two matchsticks. The last player to take away a matchstick loses. The loser has to give the winner a penny. The rules say that if it is your turn, you have to move. That's the whole game. Obviously, the first person to move loses every time, because either she takes away one matchstick or two. If she takes away one, that leaves three, and the other player takes two, forcing her to take the last one and lose. If the first player starts by taking away two, then the second player takes one, forcing the first player to take the last matchstick and lose. Everybody got it? Trust me, for present purposes, you don't want me to choose a more complicated game.

A game consist of a number of moves. The rules define the starting point, the number of players, whose move it is at each step in the game, what the available choices are for each player at each step, when the game ends, and what the result is for each player at each ending point. We are going to limit ourselves to games whose rules define a finite number of players and guarantee a finite number of moves. So, for example, if we are analyzing chess, we will include the rule that says that if a position is repeated three times, or if fifty moves are made by each player without a piece being taken or a pawn being advanced to the eighth rank, then the game is declared a draw.

In Taking Away Matchsticks, there are two players, whom we will call A and B. The starting point is the pile of four matchsticks. The player labeled A goes first [tough luck]. A move consists of taking away one matchstick or two. The rules of the game ensure that it can last at most four moves [if each player takes one matchstick each time -- stupid, but legal]. There are two possible outcomes: either A pays B one cent, or B pays A one cent. There cannot be any draws.

Just as Economics doesn't care how anything is actually produced or consumed, so Game Theory doesn't really whether a game is played with matchsticks or chess pieces or a pile of chips and a deck or a bat and a ball. It only cares about moves and players and outcomes and such. So our entire little game can be fully represented by the following diagram, which for obvious reasons is called a Game Tree:

Each of the black circles is a node. It is a point at which a player has a move. The nodes are labeled, showing whose move it is. Each branch coming out of a node represents one of the moves that the rules allow that player to make at that point in the game. A square box indicates that the game is over. A white box indicates that Player A has won. A black box indicates that Player B has won. For purposes of Game Theory, two games with identical game trees are
indistinguishable, even if one involves guns and swords and the other involves cards and chips.

If I had created a game in which a coin toss decides which player goes first [a little bit fairer for Player A], then there would be three players in the game. The third player would be Lady Luck, and she would have the first move.

I want each of you to take a moment to look carefully at the Game Tree and follow out in your mind the sequence of moves I described earlier leading to one player or the other winning. There are five different sequences of moves that can occur in the game, each one leading to a different square box. Notice that there are no loops in the tree -- no way that two different sequences of plays can lead to the same node up the tree a ways. For example: A takes the right hand branch; B then takes the right hand branch; then A takes the left hand branch. Game over, B wins. Or, A takes the left hand branch, B takes the right hand branch, A takes the only branch offered. Game over, B wins. And so forth. A game represented in this form is said to be in the Extensive Form. The Game Tree is said to be the Extensive Form of the Game.


  1. Is it possible that the game tree as you have drawn it applies to a game with more than four match sticks, or are there too many branches? Or I may not understand it....the more likely case, I'm afraid.

  2. No, it is the game tree of the game I described. Look at the farthest right branch. That is a series of four moves, each of which consists of taking away one matchstick. That is the longest play possible with that game. The other paths all involve at least one move of taking two. Each path is a different possible combination of moves by A and B leading to the last stick being taken.

  3. Now I feel REALLY silly. Am I to assume that we are to read the tree from the bottom up? Starting with the single point at the bottom, A? Then it seems that there are at least two paths by which A (clearly the underdog) can win, no?

    Thanks very much for clarification!

  4. Yes, that is right, but unfortunately for A, B can block both of those paths. It is, as they say in Chess, a forced win for B. But hey, who said life is fair? The point is simply to introduce the idea of a game tree with a very simple example.

  5. Are we assuming that B has foresight? That is, that B has analyzed the entire game (using such a lovely tree) and will choose accordingly? Is there any way to highlight the paths that each would prefer? Or a symbol for B "blocking" A?

    Now I can see how programmers and simulators would love this!

  6. Of course A and B know the entire game tree. Otherwise they could not formulate strategies! This is what is meant by choice under uncertainty -- each knows everything except what the other will choose to do. Then they attempt to reason out what the other will do on the basis both of the game tree and of each player's preference order, which they know. That is what Game Theory is about.