Read an Excerpt
Game Theory
A Nontechnical Introduction
By Morton D. Davis Dover Publications, Inc.
Copyright © 1983 Morton D. Davis
All rights reserved.
ISBN: 978-0-486-13515-1
CHAPTER 1
An Overview
The theory of games is a theory of decision making. It considers how one should make decisions and, to a lesser extent, how one does make them. You make a number of decisions every day. Some involve deep thought, while others are almost automatic. Your decisions are linked to your goals—if you know the consequences of each of your options, the solution is easy. Decide where you want to be and choose the path that takes you there. When you enter an elevator with a particular floor in mind (your goal), you push the button (one of your choices) that corresponds to your floor. Building a bridge involves more complex decisions but, to a competent engineer, is no different in principle. The engineer calculates the greatest load the bridge is expected to bear and designs a bridge to withstand it.
When chance plays a role, however, decisions are harder to make. A travel agency may want to give its customers prompt service and yet avoid excessive telephone bills. But since the agency doesn't know what future demands will be, it doesn't know how many phones to install. By using past experience and applying the laws of probability, a balance can be struck between losses from excessive phone bills and defecting customers.
Game theory was designed as a decision-making tool to be used in more complex situations, situations in which chance and your choice are not the only factors operating. These are the situations that will concern us from now on. Let's look at a few such examples to clarify what I am saying and postpone our analysis of these kinds of problems to the later chapters.
Companies A and B intend to buy 30 and 24 typewriters, respectively. Salesman P represents the company that currently supplies them both; Q represents a competitor. Each has time to give one sales talk at either company A or B. If they visit the same company, they divide the sales at that company equally but P makes all the sales to the other company. If they visit different companies, each makes all the sales at the company visited. In figure 1.1 the alternatives for salesman Q are represented by columns and the alternatives for P are represented by rows. The entry corresponding to each pair of alternatives represents P's total sales (since there are 54 typewriter sales in all, Q's total sales can be deduced from P's sales).
If Q and P both visit A, for example, we find the entry where column "Visit A" meets the row "Visit A" is 39. P gets half the sales at A and all the sales at B, which is 15 + 24 = 39. It is understood that, Q had 15 sales since the total number of sales is 54.
Generals P and Q each want control of oil deposits that P now controls. Thirty acres are located at A and 24 are located at B. Q has enough strength to invade only one location and P has enough strength to defend only one. Both forces are equally matched, so if P and Q go to the same place there will be a standoff; each gets half the acreage there while P retains control of the other location. If P and Q choose different locations, each army will control all the acreage at its own location.
Figure 1.2 indicates the total acreage that P will control.
On the last day of a political convention, aspiring candidates P and Q will meet delegates from either states A or B. P is the current favorite, so if both candidates visit the same state, each will get half the delegates of that state and P will get all the delegates of the other one; if they visit different states, each will get the delegates of the state visited. If A and B have 30 and 24 delegates, respectively, the possible outcomes are reflected in figure 1.3.
Although these three situations differ—one involves business competition, another military conflict, and the third a political campaign—they all reduce to a single problem involving the theory of games. They differ from the problems described earlier—building a bridge and installing telephones—in one essential respect: While decision makers are trying to manipulate their environment, their environment is trying to manipulate them. A store owner who lowers her price to gain a larger share of the market must know that her competitors will react in kind. A thief who robs banks rather than newsstands (because that's where the money is) must be aware that the police will be asking themselves "Where would I go if I were a thief?" and act accordingly. The bridge under construction, on the other hand, has no feelings about its own safety, and the travel agency's customers were not trying to embarrass it by calling too frequently or not calling it frequently enough.
A player involved in a game with other decision-making players is in the same position as the scientist who wanted to study a monkey's behavior. After he placed the monkey in a room and gave it time to get acclimated, he looked through the observation slot—and saw the monkey's eyeball looking back at him.
In the rest of this book I will talk about certain situations that I will call games. In a game there will be players (at least two), and each will pick a strategy (make a decision). As a result of this joint choice—and possibly chance, a disinterested player—the result will be a reward or punishment for each player: the payoff. Because everyone's strategy affects the outcome, a player must worry about what everyone else does and knows that everyone else is worrying about him or her.
The words "strategy," "player," and "payoff" have roughly the same meaning here as they do in everyday language. A player, a participant in the game, need not be a single person. If each member of a group has exactly the same feelings about how the game should turn out, the members may be considered a single player. So a "player" may be a corporation, a county, or a football team.
A strategy in game theory is a complete plan of action that describes what a player will do under all possible circumstances. In ordinary usage a strategy is considered to be something clever, but nothing like that is intended here. There are poor strategies, just as there are good strategies. In the three examples depicted in figures 1.1 to 1.3, each player had two simple strategies—A and B—but in real games strategies may be so complex that they can't be written out explicitly. Also, in some real games it might seem convenient to think of a player as using several different strategies. Competing automobile companies that fix their prices every year and chess players who rethink their position after each move are two examples. But in principle you can imagine that all these decisions are merged into one to form a single strategy, and from the point of view of the theorist this is more convenient.
A complete strategy in chess, then, would start something like this: "On my first move I will move to position A. If he then moves to B, then I'll move to B'; if he then moves to C, I'll move to C'; if he ... If after I move to A, he moves to B, I move to B'. If he then moves to Q, I'll move to Q'..." It is almost impossible to describe a complete strategy in detail in any real game one actually plays, and even in such a simple game as tick-tack-toe, which is played by very young children, the task is formidable. But the practical problem of writing out an entire strategy in detail shouldn't stop us from making use of the concept any more than our inability to multiply all the numbers from I to 1,000 shouldn't stop us from writing a formula in which this product appears.
This distinction between theory and practice is very important; the difference becomes clear if you compare a chess player's attitude toward the game of chess with that of the game theorist. Chess has been around for many centuries, and no human being or computer has come close to mastering it. In films and cartoons the bearded chess player is often used to symbolize profound thought, and, in fact, the chess player finds the game profound and subtle. To the game theorist, however, the game is trivial. This seems an absurd position, since game theorists are not even particularly good chess players.
The apparent paradox is easily resolved, however; chess, complex as it is, is finite, so, in principle, every position on the board is either (a) a win for white, (b) a draw, or (c) a win for black. Given enough time, you could start from the end of the game and work forward labeling every position that can possibly arise in the game as a win, loss, or draw and finally determine whether the game itself is a win, loss, or draw. (This technique would also indicate how to enforce the win or draw.) In practice the task is hopeless, of course, so from the chess player's point of view the game is as deep as he or she believes it to be.
There is also a difference in the way we will be analyzing our "games" and the way experts analyze parlor games. If a player in a game like chess has a winning strategy, we assume he will use it; if a player is in great difficulty and needs to adopt a very subtle defense to draw, we assume she will find it. In short, we assume players always do their best.
In real life, it may make an enormous difference how you play even if you are backing a lost cause. Against an ideal player you may be defeated, but against a real person it is well known that certain strategies induce errors. Emanuel Lasker, world chess champion for many years, felt that psychology plays a very important role in the game. He often adopted a slightly inferior opening, which initially gave him a slight disadvantage, in order to disconcert his opponent. And a Russian handbook on championship chess suggests that a player should try to force an opponent into an early commitment, even if by doing so the first player obtains a slightly inferior position. In the children's game of ticktack-toe, the outcome will always be a draw if there is correct play on both sides, but there is a pragmatic argument for making the first move in the corner: there is only one answer to the corner move that preserves the draw, and that is a move in the center. Any other first move allows at least four adequate replies. So, in a sense, the corner move is strongest, but it is a sense that the game theorist does not recognize. Game theorists do not speak of "slightly unfavorable positions" or "commitments" or "attacks," premature or otherwise. They are incompetent to deal with the game on these terms, and these terms are superfluous to their theory. In short, game theorists, do not attempt to exploit their opponent's folly.
Since it takes no great insight to recognize the existence of folly in this world, and since the game theorist purports to be influenced by the world, why this puristic attitude? The answer is simply this: it is much easier to recognize the existence of error than to fashion a general, systematic theory that will allow you to exploit it. So the study of tricks is left to the experts in each particular game; game theorists make the pessimistic, and often imperfect, assumption that their opponents will play flawlessly.
Games like chess, checkers, tick-tack-toe, and the Japanese game of Go are called games of perfect information because everyone knows exactly what is going on at all times. These games offer few conceptual problems, and they won't be discussed here. In games like poker and bridge the players are, to some extent, kept in the dark, and in this sense the games are more complex. Even as trivial a game as matching pennies in which each player must choose a strategy without knowing what an adversary is doing has this added dimension of complexity.
One of the engaging properties of game theory is that many problems can be understood immediately without any special technical background. Terms such as "zero-sum" and "prisoner's dilemma" have become part of the vocabulary of economics and the social sciences. Particularly seductive are the problems growing out of chapters 5 and 6, both for the sophisticate and beginner. Since much of the material is accessible to the reader, a number of problems have been listed at the beginning of each chapter instead of the end. Read them and think about them before your ideas are shaped by the text. They generally don't require any great quantitative skill, but they do require thought. This forethought will make the book much more challenging.
CHAPTER 2
The Two-Person, Zero-Sum Game with Equilibrium Points
Introductory Problems
Several variations of a certain type of game are shown in figures 2.1 to 2.4. Take a moment to see what you do in each case and guess what the likely outcome will be. The material in the chapter will be much more interesting if you think about the ideas involved first.
Each of the matrices shown below represents a game. I will describe how game 1 is played in some detail; the other games are played in much the same way.
You pick a row (A, B, or C) and your opponent picks a column (I, II, or III) at the same time so neither knows when choosing what the other has picked. The number where the row and column intersect is the amount your opponent pays you in dollars. So if you pick row A and your opponent picks column III, you will receive a dollar from her. (If your opponent chose II you would pay two dollars to her, since the number is negative.) You may assume here and throughout the book that your opponent knows the rules of the game and is as intelligent as you are. Remember that you must take your opponent's thinking into account—if you play C you have a chance at your greatest possible gain, 7, but will your opponent cooperate by choosing column II? So once again: What do you do, why, and what should the outcome of this game be?
In each of the first four games, imagine what you would do if you knew in advance your opponent's strategy (take each of his or her strategies in turn). If your choice depends on your opponent's choice, how do you play when you don't know what he or she will do?
Figure 2.5 depicts a similar type of game but some of the payoffs (matrix entries) have been omitted. Can you still predict what will happen even though you don't know the missing payoffs?
IN FEBRUARY 1943 General George Churchill Kenney, Commander of the Allied Air Forces in the Southwest Pacific, was faced with a problem. The Japanese were about to reinforce their army in New Guinea and had a choice of two alternative routes. They could sail either north of New Britain, where the weather was rainy, or south of New Britain, where the weather was generally fair. In any case, the journey would take three days. General Kenney had to decide where to concentrate the bulk of his reconnaissance aircraft. The Japanese wanted their ships to have the least possible exposure to enemy bombers, and, of course, General Kenney wanted the reverse. The matrix entries in figure 2.6 represent the expected number of days of bombing exposure.
It is more difficult to make decisions in this kind of a game than in the games mentioned in chapter 1. The critical difference between this game and the game of chess is that here the players lack information. Both players must decide simultaneously, so neither knows the other's strategy when choosing his or her own. The analysis of this particular game is simple enough, however. At first it seems the Allies have a problem: it would be best for them to take the same route as the Japanese, but when they make their decision they don't know what that route will be. But the problem is quickly solved when you take the Japanese view. For them, the northern route minimizes their exposure whatever the Allies do, so their action is clear. After working this out, the Allies' decision also becomes clear: go north.
This last is an example of a two-person, zero-sum game with equilibrium points. The term "zero-sum" (or equivalently, "constant sum") means the players have diametrically opposed interests. The term comes from parlor games like poker where there is a fixed amount of money around the table. If you want to win some money, others have to lose an equivalent amount. Two nations trading make up a non-zero-sum game since both may simultaneously gain. An equilibrium point is a stable outcome of a game associated with a pair of strategies. It is considered stable because a player unilaterally picking a new strategy is hurt by the change.
A Political Example
It is an election year and the two major political parties are in the process of writing their platforms. There is a dispute between state X and state Y concerning certain water rights. Each party must decide whether it will favor X or favor Y or evade the issue. The parties, after holding their conventions privately, will announce their decisions simultaneously.
(Continues...)
Excerpted from Game Theory by Morton D. Davis. Copyright © 1983 Morton D. Davis. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
