100 Mark Project Game Theory

Game Theory

Introduction Game theory is concerned with the decision-making process in situations where outcomes depend upon choices made by one or more players. The word "game" is not used in the conventional sense but describes any situation involving positive or negative outcomes determined by the players' choices and, in some cases, chance. In order for game theory to apply, certain assumptions must be made. The first is that each player is rational, acting in his self-interest. In addition, the players' choices determine the outcome of the game, but each player has only partial control of the outcome. Game theory is the mathematical analysis of a conflict of interest to find optimal choices that will lead to desired outcome under given conditions. To put it simply, it's a study of ways to win in a situation given the conditions of the situation. While seemingly trivial in name, it is actually becoming a field of major interest in fields like economics, sociology, and political and military sciences, where game theory can be used to predict more important trends. Though the title of originator is given to mathematician John von Neumann, the first to explore this matter was a French mathematician named Borel. In the 1930s, Neumann published a set of papers that outlined the tenets of game theory and thus made way for the first simulations which considered mathematical probabilities. This was used by strategists during the Second World War, and since then has earned game theory a place in the context of Social Science. It may at first seem arcane to involve mathematics in something that seems purely based on skill and chance, but game theory is in actuality a complex part of many branches of mathematics including set theory, probability and statistics, and plain algebra. This results from the fact that games are dictated by a given set of rules that can be used to outline a set of possible moves which can be ranked by desirability and effectiveness, and with information available, such a set can also be constructed for the opponent, thus allowing predictions about the possible outcomes within a certain number of moves with a probabilistic accuracy.

1

Game Theory

Von Neumann and the development of Game Theory Emile Borel: The Forgotten Father of Game Theory? In 1921, Emile Borel, a French mathematician, published several papers on the theory of games. He used poker as an example and addressed the problem of bluffing and second-guessing the opponent in a game of imperfect information. Borel envisioned game theory as being used in economic and military applications. Borel's ultimate goal was to determine whether a "best" strategy for a given game exists and to find that strategy. While Borel could be arguably called as the first mathematician to envision an organized system for playing games, he did not develop his ideas very far. For that reason, most historians give the credit for developing and popularizing game theory to John Von Neumann, who published his first paper on game theory in 1928, seven years after Borel.

John Von Neumann Born in Budapest, Hungary, in 1903, Von Neumann distinguished himself from his peers in childhood for having a photographic memory, being able to memorize and recite back a page out of a phone book in a few minutes. Science, history, and psychology were among his many interests; he succeeded in every academic subject in school. He published his first mathematical paper in collaboration with his tutor at the age of eighteen, and resolved to study mathematics in college. He enrolled in the University of Budapest in 1921, and over the next few years attended the University of Berlin and the Swiss Federal Institute of Technology in Zurich as well. By 1926, he received his Ph.D. in mathematics with minors in physics and chemistry.

2

Game Theory By his mid-twenties, von Neumann was known as a young mathematical genius and his fame had spread worldwide in the academic community. In 1929, he was offered a job at Princeton. Upon marrying his fiancee, Mariette, Neumann moved to the U.S. (Agnostic most of his life, Von Neumann accepted his wife's Catholic faith for the marriage, though not taking it very seriously.) In 1937, Mariette left Von Neumann for J. B. Kuper, a physicist. Within a year of his divorce, Von Neumann began an affair with Klara Dan, his childhood sweetheart, who was willing to leave her husband for him. Von Neumann is commonly described as a practical joker and always the life of the party. John and Klara held a party every week or so, creating a kind of salon at their house. Von Neumann used his phenomenal memory to compile an immense library of jokes which he used to liven up a conversation. Von Neumann loved games and toys, which probably contributed in great part to his work in Game Theory. Beginning in 1927, Von Neumann applied new mathematical methods to quantum theory. His work was instrumental in subsequent "philosophical" interpretations of the theory. For Von Neumann, the inspiration for game theory was poker, a game he played occasionally and not terribly well. Von Neumann realized that poker was not guided by probability theory alone, as an unfortunate player who would use only probability theory would find out. Von Neumann wanted to formalize the idea of "bluffing," a strategy that is meant to deceive the other players and hide information from them. In his 1928 article, "Theory of Parlor Games," Von Neumann first approached the discussion of game theory, and proved the famous Minimax theorem. From the outset, Von Neumann knew that game theory would prove invaluable to economists. He teamed up with Oskar Morgenstern, an Austrian economist at Princeton, to develop his theory. Their book, Theory of Games and Economic Behavior, revolutionized the field of economics. Although the work itself was intended solely for economists, its applications to psychology, sociology, politics, warfare, recreational games, and many other fields soon became apparent. 3

Game Theory Although Von Neumann appreciated Game Theory's applications to economics, he was most interested in applying his methods to politics and warfare, perhaps stemming from his favorite childhood game, Kriegspiel, a chess-like military simulation. He used his methods to model the Cold War interaction between the U.S. and the USSR, viewing them as two players in a zero-sum game. From the very beginning of World War II, Von Neumann was confident of the Allies' victory. He sketched out a mathematical model of the conflict from which he deduced that the Allies would win, applying some of the methods of game theory to his predictions. In 1943, Von Neumann was invited to work on the Manhattan Project. Von Neumann did crucial calculations on the implosion design of the atomic bomb, allowing for a more efficient, and more deadly, weapon. Von Neumann's mathematical models were also used to plan out the path the bombers carrying the bombs would take to minimize their chances of being shot down. The mathematician helped select the location in Japan to bomb. Among the potential targets he examined was Kyoto, Yokohama, and Kokura. "Of all of Von Neumann's postwar work, his development of the digital computer looms the largest today." After examining the Army's ENIAC during the war, Von Neumann came up with ideas for a better computer, using his mathematical abilities to improve the computer's logic design. Once the war had ended, the U.S. Navy and other sources provided funds for Von Neumann's machine, which he claimed would be able to accurately predict weather patterns. Capable of 2,000 operations a second, the computer did not predict weather very well, but became quite useful doing a set of calculations necessary for the design of the hydrogen bomb. Von Neumann is also credited with coming up with the idea of basing computer calculations on binary numbers, having programs stored in computer's memory in coded form as opposed to punchcards, and several other crucial developments. Von Neumann's wife, Klara, became one of the first computer programmers. Von Neumann later helped design the SAGE computer system designed to detect a Soviet nuclear attack In 1948, Von Neumann became a consultant for the RAND Corporation. RAND (Research ANd Development) was founded by defense contractors and the Air Force as a 4

Game Theory "think tank" to "think about the unthinkable." Their main focus was exploring the possibilities of nuclear war and the possible strategies for such a possibility. Von Neumann was, at the time, a strong supporter of "preventive war." Confident even during World War II that the Russian spy network had obtained many of the details of the atom bomb design, Von Neumann knew that it was only a matter of time before the Soviet Union became a nuclear power. He predicted that were Russia allowed to build a nuclear arsenal, a war against the U.S. would be inevitable. He therefore recommended that the U.S. launch a nuclear strike at Moscow, destroying its enemy and becoming a dominant world power, so as to avoid a more destructive nuclear war later on. "With the Russians it is not a question of whether but of when," he would say. An oft-quoted remark of his is, "If you say why not bomb them tomorrow, I say why not today? If you say today at 5 o'clock, I say why not one o'clock?" Just a few years after "preventive war" was first advocated, it became an impossibility. By 1953, the Soviets had 300-400 warheads, meaning that any nuclear strike would be effectively retaliated. In 1954, Von Neumann was appointed to the Atomic Energy Commission. A year later, he was diagnosed with bone cancer. The disease resulted from the radiation Von Neumann received as a witness to the atomic tests on Bikini atoll. Von Neumann maintained a busy schedule throughout his sickness, even when he became confined to a wheelchair. It has been claimed by some that the wheelchair-bound mathematician was the inspiration for the character of Dr. Strangelove in the 1963 film Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb. Von Neumann's last public appearance was in February 1956, when President Eisenhower presented him with the Medal of Freedom at the White House. In April, Von Neumann checked into Walter Reed Hospital. He set up office in his room, and constantly received visitors from the Air Force and the Secretary of Defense office, still performing his duties as a consultant to many top political figures. John von Neumann died on February 8, 1957. His wife, Klara von Neumann, committed suicide six years later. 5

Game Theory Dr. Marina von Neumann Whitman, John's daughter from his first marriage, was invited by President Nixon to become the first woman to serve on the council of economic advisers.

Concepts in Game Theory Game A conflict in interest among n individuals or groups (players). There exists a set of rules that define the terms of exchange of information and pieces, the conditions under which the game begins, and the possible legal exchanges in particular conditions. The entirety of the game is defined by all the moves to that point, leading to an outcome.

Move The way in which the game progresses between states through exchange of information and pieces. Moves are defined by the rules of the game and can be made in either alternating fashion, occur simultaneously for all players, or continuously for a single player until he reaches a certain state or declines to move further. Moves may be choice or by chance. For example, choosing a card from a deck or rolling a die is a chance move with known probabilities. On the other hand, asking for cards in blackjack is a choice move.

Information A state of perfect information is when all moves are known to all players in a game. Games without chance elements like chess are games of perfect information, while games with chance involved like blackjack are games of imperfect information.

Strategy A strategy is the set of best choices for a player for an entire game. It is an overlying plan that cannot be upset by occurrences in the game itself.

Payoff 6

Game Theory The payoff or outcome is the state of the game at it's conclusion. In games such as chess, payoff is defined as win or a loss. In other situations the payoff may be material (i.e. money) or a ranking as in a game with many players.

Extensive and Normal Form Games can be characterized as extensive or normal. A in extensive form game is characterized by a rules that dictate all possible moves in a state. It may indicate which player can move at which times, the payoffs of each chance determination, and the conditions of the final payoffs of the game to each player. Each player can be said to have a set of preferred moves based on eventual goals and the attempt to gain the maximum payoff, and the extensive form of a game lists all such preference patterns for all players. Games involving some level of determination are examples of extensive form games. The normal form of a game is a game where computations can be carried out completely. This stems from the fact that even the simplest extensive form game has an enormous number of strategies, making preference lists are difficult to compute. More complicated games such as chess have more possible strategies that there are molecules in the universe. A normal form game already has a complete list of all possible combinations of strategies and payoffs, thus removing the element of player choices. In short, in a normal form game, the best move is always known.

7

Game Theory

Types of Games One-Person Games A one-person games has no real conflict of interest. Only the interest of the player in achieving a particular state of the game exists. Single-person games are not interesting from a game-theory perspective because there is no adversary making conscious choices that the player must deal with. However, they can be interesting from a probabilistic point of view in terms of their internal complexity.

Zero-Sum Games In a zero-sum game the sum of the total possible payoffs at the end is zero since the amounts won or lost are equal. Von Neumann and Oskar Morgenstern demonstrated mathematically that n-person non-zero-sum game can be reduced to an n + 1 zero-sum game, and that such n + 1 person games can be generalized from the special case of the two-person zero-sum game. Another important theorem by Von Neumann, the minimax theorem, states certain aspects of the maximal and minimal strategies of are part of all two-person zero-sum games. Thanks to these discoveries, such games are a major part of game theory.

Two-Person Games Two-person games are the largest category of familiar games. A more complicated game derived from 2-person games is the n-person game. These games are extensively analyzed by game theorists. However, in extending these theories to n-person games a difficulty arises in predicting the interaction possible among players since opportunities arise for cooperation and collusion.

8

Game Theory

Zero-Sum Games A zero-sum game is one in which no wealth is created or destroyed. So, in a two-player zero-sum game, whatever one player wins, the other loses. Therefore, the players share no common interests. There are two general types of zero-sum games: those with perfect information and those without. In a game with perfect information, every player knows the results of all previous moves. Such games include chess, tic-tac-toe, and Nim. In games of perfect information, there is at least one "best" way to play for each player. This best strategy does not necessarily allow him to win but will minimize his losses. For instance, in tic-tac-toe, there is a strategy that will allow you to never lose, but there is no strategy that will allow you to always win. Even though there is an optimal strategy, it is not always possible for players to find it. For instance, chess is a zero-sum game with perfect information, but the number of possible strategies is so large that it is not possible for our computers to determine the best strategy. In games with imperfect information, the players do not know all of the previous moves. Often, this occurs because the players play simulataneously. Here are some examples of such games:

Game 1 Suppose two people are playing a simple game with nickels and quarters. At the same time, they each put out either a nickel or a quarter. If at least one player plays a nickel, player 1 gets both coins. Otherwise, player 2 gets both. Naturally, both players wish to gain as much money as possible. How should they play in order to do this?

Game 2 Suppose two people are playing a similar game with nickels and quarters. Now, if player 1 plays a nickel, player 2 gives him 5 cents. If player 2 plays a nickel and player 1 plays a quarter, player 1 gets 25 cents. If both players play quarters, player 2 gets 25 cents.

Game 3 9

Game Theory We still have two people playing a game with nickels and quarters. Now, if both players play the same coin, player 2 gives player 1 the average value of the coins; otherwise, player 1 gives player 2 the average value of the coins.

Although the three games seem similar, the methods used to find the best strategies in each are very different. Game 1 is solved by eliminating dominant strategies, game 2's solution is known as a saddle point, and game 3 requires a mixed strategy.

Game 1 – Dominant Strategies Suppose two people are playing a simple game with nickels and quarters. At the same time, they each put out either a nickel or a quarter. If at least one player plays a nickel, player 1 gets both coins. Otherwise, player 2 gets both. Naturally, both players wish to gain as much money as possible. How should they play in order to do this? We can assign payoff matrices to such games that define the payoffs that players will get based on the strategies they use. In this example, each player has only two strategies--put out a nickel or put out a quarter. Here is a payoff matrix for player 1:

Player 1

Nickel Quarter

Player 2 Nickel Quarter 5 25 5 -25

The rows represent player 1's possible strategies, and the columns represent player 2's possible strategies. If player 1 and player 2 both play nickels (the top left entry), player 1 wins player 2's nickel so gains 5 cents. On the other hand, if both play quarters (the bottom right entry), player 2 wins player 1's quarter, so player 1 loses 25 cents. Notice that every entry in the first row is greater than all of the entries in that column. In other words, playing a nickel is always at least as good as playing a quarter for player 1. So, playing a nickel is called a dominant strategy, and it dominates the strategy of playing a quarter. It is never advantageous to play a dominated strategy, so we can reduce our payoff matrix to reflect this:

10

Game Theory Player 2 Nickel Quarter 5 25

Nickel

Player 1

Now, the nickel strategy for player 2 also dominates. So, playing nickels is the best strategy for both players. Notice that, if either plays quarters, he will not gain more money than if he had just played nickels.

Game 2 – Saddle Points This game differs from game 1 in that it has no dominant strategies. The rules are as follows: If player 1 plays a nickel, player 2 gives him 5 cents. If player 2 plays a nickel and player 1 plays a quarter, player 1 gets 25 cents. If both players play quarters, player 2 gets 25 cents. We get a payoff matrix for this game:

Player 1

Nickel Quarter

Player 2 Nickel Quarter 5 25 25 -25

Notice that there are no longer any dominant strategies. To solve this game, we need a more sophisticated approach. First, we can define lower and upper values of a game. These specify the least and most (on average) that a player can expect to win in the game if both player play rationally. To find the lower value of the game, first look at the minimum of the entries in each row. In our example, the first row has minimum value 5 and the second has minimum -25. The lower value of the game is the maximum of these numbers, or 5. In other words, player 1 expects to win at least an average of 5 cents per game. To find the upper value of the game, do the opposite. Look at the maximum of every column. In this case, these values are 25 and 5. The upper value of the game is the minimum of these numbers, or 5. So, on average, player 1 should win at most 5 cents per game.

Nickel

Nickel 5 11

Quarter 5

Min 5

Game Theory Quarter Max

25 25

-25 5

-25

Notice that, in our example, the upper and lower values of the game are the same. This is not always true; however, when it is, we just call this number the pure value of the game. The row with value 5 and the column with value 5 intersect in the top right entry of the payoff matrix. This entry is called the saddle point or minimax of the game and is both the smallest in its row and the largest in its column. The row and column that the saddle point belongs to are the best strategies for the players. So, in this example, player 1 should always play a nickel while player 2 should always play a quarter.

Game 3 – Mixed Strategies The rules of game 3 were as follows: two players have nickels and quarters. At the same time, they each play one coin. If both players play the same coin, player 2 gives player 1 the average value of the coins; otherwise, player 1 gives player 2 the average value of the coins. Here is the payoff matrix for this game:

Player 1

Nickel Quarter

Player 2 Nickel Quarter 5 -15 -15 25

The lower value of this game is -15 while the upper value is 5. Can we find a pure value for the game? According to the Minimax Theorem, one of the most important results in game theory, we can. The Minimax Theorem states that every finite, two-person, zerosum game has a value V that is the average amount that one player can expect to win if both players act sensibly. Suppose player 2 knows which coin player 1 will play on each turn. Then it will be easy for player 2 to play a coin that makes player 2 lose money. Therefore, player 1 can't play with a pattern. Instead, he must use a mixed strategy, in which he randomly chooses to play a nickel or quarter on each turn. However, it is not necessarily true that he should play each strategy half the time. He may want to weight the strategies differently, playing one with probability p and the other with probability 1 - p. How do we figure out p? It turns out that one property of the value of a game is that, if player 1 plays his optimal strategy, he will achieve exactly the value of the game no matter what the other player 12

Game Theory does (as long as the other player has no dominant strategies). In particular, the yield when player 1 plays agains player 2's two different pure strategies should be the same. In other words, if player 1 uses his optimal strategy, he will get the same amount of money whether player 2 always plays nickels or always plays quarters. Let's suppose that player 2 always plays nickels. Player 1 plays nickels p of the time so gains 5 cents p of the time. The other 1 - p of the time, he loses 15 cents. Overall, he wins 5p - 15(1 - p) = 20p - 15. Now, suppose player 2 always plays quarters. Player 1 plays nickels p of the time so loses 15 cents p of the time. The rest of the time, he wins 25 cents. Overall, he wins -15p + 25(1 - p) = 25 - 40p. Because he should win the same in both situations, the two winnings are the same. So, 20p - 15 = 25 - 40p. Solving for p, we find that it is 2/3. To find the amount that player 1 expects to win, we just plug this back into either of the equations and find that he should win an average of -5/3 per game. Even if player 2 figures out this strategy, he cannot do anything to change it. Similarly, we can look at the payoff matrix from player 2's point of view and find a mixed strategy for player 2. If we do so, we find that player 2 should play nickels 2/3 of the time and quarters 1/3 of the time. If he does so, he should win an average of 5/3 cents per game.

13

Game Theory

Strategies of Play The Minimax algorithm is the most well-known strategy of play of two-player, zero-sum games. The minimax theorem was proven by John von Neumann in 1928. Minimax is a strategy of always minimizing the maximum possible loss which can result from a choice that a player makes. Before we examine minimax, though, let's look at some of the other possible algorithms.

Maximax Maximax principle counsels the player to choose the strategy that yields the best of the best possible outcomes. For example, let's consider a zero-sum game where two players simultaneously put either a blue or a red card on the table. If player 1 puts a red card down on the table, whichever card player 2 puts down, no one wins anything. If player 1 puts a blue card on the table and player 2 puts a red card, then player 2 wins $1,000 from player 1. Finally, if player 1 puts a blue card on the table and player 2 puts a blue card down, then player 1 wins $1,000 from player 2. The payoff matrix for player 1 is shown in this table:

Player 1

Blue Red

Player 2 Blue Red 1,000 -1,000 0 0

Going by maximax principle, player 1 will always play the blue card, since it has the maximum possible payoff of 1,000. But as can be clearly seen from the table, assuming player 2 is rational, he will never play the blue card, since the red card gives him the dominant strategy. In such a case, if player 1 plays by the maximax rule, he will always lose. The maximax principle is inherently irrational, as it does not take into account the other player's possible choices. Maximax is often adopted by naive decision-makers such as young children.

14

Game Theory Maximin Maximin is solely a one-person game strategy, i.e. a principle which may be used when a person's "competition" is nature, or chance. Whereas the maximax principle is ultraoptimistic, expecting the best possible payoff, the maximin is ultra-pessimistic, expecting the worst possible payoff. It involves choosing the best of the worst possible outcomes. A simple example of a slot machine game may be used. A player has only two choices to make -- to gamble or not to gamble. If he gambles, he risks losing his bet (say, $1), but also has a chance to win the maximum payoff (say, $10,000). If he does not gamble, he can neither win nor lose. The payoff matrix looks like this:

Player

Gamble Not Gamble

Chance Win Lose 1000 -1 0 0 0

According to the maximin principle, the player should never gamble, because he faces a risk of losing $1. It is clear that the maximin principle is quite inefficient, since it discourages taking any risks, no matter how high the reward may be.

Minimax for One-Person Games The Minimax Regret Principle is based on the Minimax Theorem advanced by John von Neumann, but is geared only towards one-person games. It relies on the concept of regret matrices. To demonstrate, consider an example of a company trying to decide whether or not it should support a research project. Let's assume that the research project costs c units. If it succeeds, it will bring in a return of r units. If it fails, it will obviously not bring in anything.

The payoff matrix for the company looks like this:

15

Game Theory

Company

Supports Research Neglect Research

Research Succeeds Fails R-C -C 0 0

By the maximax principle, a company should always support research if the expected return on it is greater than its cost. By maximin, the company should never support research, since it is risking the cost of the research. Minimax is slightly more complicated. We need to come up with a matrix that shows the "opportunity cost," or regret, of the player, depending on each possible decision. For example, if the company supports the research and it fails, the company's regret will be c, the price of research. If the company supports the research and it succeeds, the company will have no regrets. If the company neglects research and it would have succeeded, its regret value is r-c, the return on the research. So, the minimax regret matrix will look like this:

Company

Supports Research Neglect Research

Research Succeeds Fails 0 C R-C 0

The object is to minimize the maximum possible regret. It is not obvious from the above matrix what the maximum value is. That is, is c greater than r-c? If (r-c) > c, the company should support research. If (r-c) < c, the company should not. In other words, the company should support research if c < r/2, or, if the expected return on research is more than twice its cost.

Minimax for Two-Person Games In a two-person, zero-sum game, a person can win only if the other player loses. No cooperation is possible. Andrew Colman's Game Theory and Experimental Games shows the following historical example: 16

Game Theory

In 1943, the Allied forces received reports that a Japanese convoy would be heading by sea to reinforce their troops. The convoy could take on of two routes – the Northern or the Southern route. The Allies had to decide where to disperse their reconnaissance aircraft - in the north or the south - in order to spot the convoy as early as possible. The following payoff matrix shows the possible decisions made by the Japanese and the Allies, with the outcomes expressed in the number of days of bombing the Allies could achieve with each possibility:

Allies Reconnaissance

North South

Japanese Route North South 2 2 1 3

By this matrix, if the Japanese chose to take the southern route while the Allies decided to focus their recon planes in the north, the convoy would be bombed for 2 days. The best outcome for the Allies would be if they placed their airplanes in the south and the Japanese took the southern route. The best outcome for the Japanese would be to take the northern route, provided the Allies were looking for them in the south. To minimize the worst possible outcome, the Allies would have to choose the north as the focus of their reconnaisance efforts. This ensures them 2 days of bombing, whereas they risk only 1 day of bombing if they focus on the south. Therefore, by minimax, the best strategy for them would be to focus on the north. The Japanese can use the same strategy. The worst possible outcome for them is the 3 days of bombing which might occur if they took the southern route. Therefore, the Japanese would take the northern route. It is, in fact, what had occurred: both the Allies and the Japanese chose the north, and the Japanese convoy was bombed for 2 days. The previous matrix had a saddle point, meaning that both the Japanese and the Allies settled on the (North, North) square as the best outcome for both of them. Neither could do any better if the opponent was rational. In this case, the maximin and the minimax 17

Game Theory strategies produce the same result. Notice that if the Allies were following maximax, they would choose the South, and surely forfeit one day of bombing.

Mixed Strategies and Randomization In some cases, there is no saddle point, and the players have to choose their strategies with a degree of randomness, as in the following simple game, called "Matching Pennies." Two players simultaneously place a penny on a table, either heads up or tails up. If the pennies are facing the same way, player 1 gets to keep both pennies. Otherwise, player 2 gets to keep both. The payoff matrix for player 1 looks like this:

Player 1

Heads Tails

Player 2 Heads Tails 1 -1 -1 1

There is no clearly defined strategy for each player. The best way to play is to choose the position of the coin randomly. If either player follows this strategy, then in the long run, the payoffs for each will be 0. Notice that if, say, player 1 uses a 50/50 strategy, while player 2 plays heads 75% of the time, in the long run, both players will still have payoffs of 0. But if player 2 follows the 75/25 strategy, then player 1 can easily take advantage of it by playing heads more frequently, and therefore winning more frequently. So, it is important for each player to not only maintain a random strategy, but to also analyze the strategy of the other player.

Applications to Computing In computer simulations for cases such as this, it is important not to program the computer with a specific strategy in advance, but let it decide it at run-time. If the computer does not maintain unpredictability, then the opposing player may use this knowledge to his advantage. Many computer games suffer because although the

18

Game Theory computer is programmed with a strong strategy, it becomes predictable and easy to take advantage of. On the other hand, the computer might very well benefit if it recognizes a predictable strategy on the part of an opponent. Even in such a simple game as "Matching Pennies," where a 50/50 is called for, while the computer may follow a 50% algorithm for deciding whether to play heads or tails, a human cannot come up with completely random numbers. In fact, it has been observed that humans tend to play heads slightly more often. If a computer recognizes that the probability of its opponent of picking heads is slightly higher, it may adjust its own strategy to have an advantage.

19

Game Theory

Non-Zero-Sum Games The theory of zero-sum games is vastly different from that of non-zero-sum games because an optimal solution can always be found. However, this hardly represents the conflicts faced in the everyday world. Problems in the real world do not usually have straightforward results. The branch of Game Theory that better represents the dynamics of the world we live in is called the theory of non-zero-sum games. Non-zero-sum games differ from zero-sum games in that there is no universally accepted solution. That is, there is no single optimal strategy that is preferable to all others, nor is there a predictable outcome. Non-zero-sum games are also non-strictly competitive, as opposed to the completely competitive zero-sum games, because such games generally have both competitive and cooperative elements. Players engaged in a non-zero sum conflict have some complementary interests and some interests that are completely opposed.

A Typical Example The Battle of the Sexes is a simple example of a typical non-zero-sum game. In this example a man and his wife want to go out for the evening. They have decided to go either to a ballet or to a boxing match. Both prefer to go together rather than going alone. While the man prefers to go to the boxing match, he would prefer to go with his wife to the ballet rather than go to the fight alone. Similarly, the wife would prefer to go to the ballet, but she too would rather go to the fight with her husband than go to the ballet alone. The matrix representing the game is given below:

Wife

Husband Boxing Match Ballet 2, 3 1, 1 1, 1 3, 2

Boxing Match Ballet

The wife's payoff matrix is represented by the first element of the ordered pair while the husband's payoff matrix is represented by the second of the ordered pair. From the matrix above, it can be seen that the situation represents a non-zero-sum, nonstrictly competitive conflict. The common interest between the husband and wife is that they would both prefer to be together than to go to the events separately. However, the 20

Game Theory opposing interests is that the wife prefers to go to the ballet while her husband prefers to go to the boxing match.

Analyzing a Non-Zero-Sum Game 

Communication

It is conventional belief that the ability to communicate could never work to a player's disadvantage since a player can always refuse to exercise his right to communicate. However, refusing to communicate is different from an inability to communicate. The inability to communicate may work to a player's advantage in many cases. An experiment performed by Luce and Raiffa compares what happens when player can communicate and when players cannot communicate. Luce and Raiffa devised the following game: A B

A 1, 2 0, -200

B 3,1 2, -300

If Susan and Bob cannot communicate, then there is no possibility of threats being made. So, Susan can do no better than to play strategy A and Bob can do no better than to play strategy a. Susan, therefore gains 1 and Bob gains 2. However, when communication is allowed, the situation is complicated. Susan can threaten Bob by saying that she will play strategy B unless Bob commits himself to playing strategy b. If Bob submits, Susan will gain 2 and Bob will lose 1 (as opposed to Susan gaining 1 and Bob gaining 2 when communication is not allowed).



Restricting Alternatives

The Battle of the Sexes example given above seems to be an unsolvable dilemma. However, this problem can be solved it either the husband or the wife resticts the others' alternatives. For example, if the wife buys two tickets for the ballet, indicating that she is definitely not going to the boxing match, the husband would have to go to the ballet along with his wife in order to maximize his self-interest. Because the wife bought the two tickets, the husbands optimal payoff, now, would be to go along with his wife. If he were to go to the boxing match alone, he would not be maximizing his self-interest.

21

Game Theory 

The Number of Times the Game is "Played"

If the game is played only once, players do not have to fear retaliation from their opponents, so they may play differently than they would in a game played repeatedly.

Typical Non-Zero-Sum Games: •

Prisoner's Dilemma

•

Chicken and Volunteer's Dilemma

•

Deadlock and Stag Hunt

The Prisoner’s Dilemma The Prisoner's Dilemma game was first proposed by Merrill Flood in 1951. It was formalized and defined by Albert W. Tucker. The name refers to the following hypothetical situation: Two criminals are captured by the police. The police suspect that they are responsible for a murder, but do not have enough evidence to prove it in court, though they are able to convict them of a lesser charge (carrying a concealed weapon, for example). The prisoners are put in separate cells with no way to communicate with one another and each is offered to confess. If neither prisoner confesses, both will be convicted of the lesser offense and sentenced to a year in prison. If both confess to murder, both will be sentenced to 5 years. If, however, one prisoner confesses while the other does not, then the prisoner who confessed will be granted immunity while the prisoner who did not confess will go to jail for 20 years. What should each prisoner do?

Discussion of Prisoners Dilemma 22

Game Theory To help us determine the answer, let's come up with a payoff matrix for each prisoner. The value in each cell is the time spent in prison, so the prisoners will try to end up in the matrix cell with the lowest number. The first number of each pair refers to the prison time of prisoner 1, and the second number to prisoner 2.

Prisoner 1

Confess Not Confess

Prisoner 2 Confess Not Confess 5, 5 0, 20 20, 0 1, 1

Let's assume the role of prisoner 1. We're looking to minimize our prison time. Since we have no way of knowing whether our partner in crime has confessed, let's first assume that he has not. If Prisoner 1 doesn't confess either, both will go to prison for 1 year. Not bad. But, if Prisoner 1 confesses, he will go free, while his partner rots away in jail. We'll assume that there is no "honor among thieves" and each prisoner only cares about minimizing his jail time. From the above discussion, it is obvious that if Prisoner 2 does not confess, Prisoner 1 is definitely better off confessing. Now let's look at the other possibility. Say prisoner 2 confesses. If Prisoner 1 does not confess, he will go to jail for 20 years. But if he does confess, he will get only 5 years in prison. It is clearly better to confess in this case as well. So is that it? Is the problem solved? Is each prisoner better off confessing? Well, it may seem so from the above discussion, but if we look at the payoff matrix, it is clear that the best payoff for both prisoners is when neither confesses! But game theory advocates that both confess. This "game" can be generalized to any situation when two players are in a noncooperative situation where the best all-around situation is for both to cooperate, but the worst individual outcome is to be cooperating player while the other player defects. On the one hand, it is tempting to defect, or confess. Since you have no way of influencing the other player's decision, no matter what he does, you're better off confessing. But on the other hand, you're both in the same boat. Both of you should be sensible enough to realize that cheating undermines the common good. 23

Game Theory

There is no single "right" solution to the Prisoner's Dilemma (that's why it's a dilemma). Its implications carry into psychology, economics, and many other fields.

The Flood Dresher Experiment Many experiments have been done on the Prisoner's Dilemma, to try to gauge the normal human behavior in a prisoner's dilemma-type situation. The Flood-Dresher Experiment was a prisoner's dilemma game run 100 times between 2 players. In this case, the game was unfair - one of the players had an inherent advantage over the other player, but the payoff matrix layout was still a prisoner's dilemma. The following is the table used in the experiment. (In this case, the payoffs are positive, that is, each rational player seeks to maximize the value in the matrix cell he ends up in.)

Prisoner 1

Prisoner 2 Defect Cooperate -1, 2 0.5, 1 0, 0.5 1, -1

Cooperate Defect

As in the Prisoner's Dilemma, both players are better off defecting. But when both defect, they do relatively poorly. On the other hand, if both choose their "worse" strategy consistently, they should both gain. In the 100 trials, Player 1 chose to cooperate 68 times, and Player 2 78 times. Player 1 began the game expecting both players to defect. Player 2 realized the value of cooperation and started cooperating. Both players started cooperating after the first 10 or so moves, though Player 1 would defect on a regular basis, unhappy that his payoff wasn't as big as Player 2's. This in turn brought retaliation from Player 2, who would defect on the next move. Each player kept a log of comments for each move. Some of those comments are quite amusing. "The stinker," writes Player 2 after Player 1's defection. "He's a shady character... A shiftless individual--opportunist, knave... He can't stand success."

24

Game Theory The players' comments reflect their concern about the final few moves. Both seem to realize that it would make sense for both to defect on move 100, since no retaliation from the other player is possible. Player 1 worries about starting to defect earlier than Player 2 so that he has the advantage. As the game was played, both players cooperated on moves 83 through 98. On move 99, Player 1 defected, and on move 100, both defected. It is clear that the long-term prospect of the game encouraged cooperation. Since the game was played multiple times, it became beneficial for both players to cooperate. On move 100, however, the game suddenly becomes a regular prisoner's dilemma, and both players defect, as game theory advocates they should (although if they both cooperated they would ensure themselves a gain of 0.5 points). This reasoning is troubling though. Since both players must realize that they will both defect on move 100, move 100 does not have to figure into the game. It can then be thought that move 99 is really the last move in the game, since both players are obviously going to defect on move 100. But if move 99 is the last move, both players should defect, since no retaliation is possible (both players will defect anyway on move 100, no matter what the other player did on move 99). So both players should defect on move 99 as well. Then, move 98 can be thought of as the last move in the game. This line of reasoning can be extended indefinitely until move 1. So should both players always defect? Clearly not, since if they both cooperate, they will gain more than if both defect. This paradox is still unresolved. William Poundstone, in Prisoner's Dilemma, says that "Both Flood and Dresher say they initially hoped that someone would 'resolve' the prisoner's dilemma. They expected someone to come up with a new and better theory of non-zero-sum games. The solution never came. The prisoner's dilemma remains a negative result - A demonstration of what's wrong with theory, and indeed, the world."

Axelrod’s Tournament In 1980, Robert Axelrod, professor of political science at the University of Michigan, held a tournament of various strategies for the prisoner's dilemma. He invited a number 25

Game Theory of well-known game theorists to submit strategies to be run by computers. In the tournament, programs played games against each other and themselves repeatedly. Each strategy specified whether to cooperate or defect based on the previous moves of both the strategy and its opponent. Some of the strategies submitted were: 

Always defect: This strategy defects on every turn. This is what game theory advocates. It is the safest strategy since it cannot be taken advantage of. However, it misses the chance to gain larger payoffs by cooperating with an opponent who is ready to cooperate.



Always cooperate: This strategy does very well when matched against itself. However, if the opponent chooses to defect, then this strategy will do badly.



Random: The strategy cooperates 50% of the time.

All of these strategies are prescribed in advance. Therefore, they cannot take advantage of knowing the opponent's previous moves and figuring out its strategy. The winner of Axelrod's tournament was the TIT FOR TAT strategy. The strategy cooperates on the first move, and then does whatever its opponent has done on the previous move. Thus, when matched against the all-defect strategy, TIT FOR TAT strategy always defects after the first move. When matched against the all-cooperate strategy, TIT FOR TAT always cooperates. This strategy has the benefit of both cooperating with a friendly opponent, getting the full benefits of cooperation, and of defecting when matched against an opponent who defects. When matched against itself, the TIT FOR TAT strategy always cooperates. Several variations to TIT FOR TAT have been proposed. TIT FOR TWO TATS is a forgiving strategy that defects only when the opponent has defected twice in a row. TWO TITS FOR TAT, on the other hand, is a strategy that punishes every defection with two of its own.

26

Game Theory TIT FOR TAT relies on the assumption that its opponent is trying to maximize his score. When paired with a mindless strategy like RANDOM, TIT FOR TAT sinks to its opponent's level. For that reason, TIT FOR TAT cannot be called a "best" strategy. It must be realized that there really is no "best" strategy for prisoner's dilemma. Each individual strategy will work best when matched against a "worse" strategy. In order to win, a player must figure out his opponent's strategy and then pick a strategy that is best suited for the situation.

Multi-Person Prisoner’s Dilemma The n-person prisoner's dilemma (NPD) is basically the Prisoner's Dilemma with more than two players. The NPD emerged during the early 1970's and quickly became popular among social theorists and economists. The sudden interest in NPD occurred mainly because of the economic and social developments during the late 60s and early 70s. At this time, problems such as inflation, voluntary wage restraint, the energy crisis, and environmental pollution were pressing issues. This era of history, however, is better known for the increasing international tension between the U.S. and the Soviet Union. Both superpowers were engaged in mass production of nuclear weapons, creating a very real threat to the existence of the entire world. With the proliferation of nuclear weapons came the issue of multilateral disarmament. The various social, political, and economic tensions of the 70's can all be modeled by the NPD, indicating the remarkable range of real-world problems that NPDs can simulate. Many real-world problems, be they social, political, or economic, can be modeled as an NPD. In economics, an interesting example concerns the "invisible hand theory" and how it applies to the labor market. In 1776, economist Adam Smith introduced the theory of the "invisible hand" which still remains the cornerstone of traditional economics. The "invisible hand", in short, is what dictates the motion of the economy. It is not a single individual or government that controls its motion, but is instead motivated by every person who participates in the economy.

27

Game Theory In the labor market, companies hiring workers are consumers and those looking for jobs are the producers. That is, job seekers have a product to sell, namely their skills and the companies want to buy their labor. The "invisible hand" which dictates the labor market decides the wages that companies will pay. An example of how and NPD can be used to model the labor market is as follows: Every trade union's individual self-interest is to negotiate wages that exceed the rate of inflation in the economy as a whole. However, if all trade unions negotiated wages to benefit their own self-interest, the prices of goods and services go up and everyone is worse off than if they had all exercised restraint. In order to solve this problem, the British Labour Party issued a Manifesto (1974) which contained an outline of a "social contract" whose aim was to encourage trade unions to exercise voluntary wage restraint in order to decrease the rate of inflation. The "social contract" was designed to encourage collective rationality in wage bargaining over individual rationality. However, this solution was unsuccessful because it did not change the underlying strategic structure of the wage bargaining game. Another type of NPD that is readily evident in the real world is that which simulates situations where resources are scarce. For example, when there is a shortage of any resource, such as water or energy, there is usually a call for conservation. However, and individual only benefits from restraint if everyone else restrains as well. However, restraint of an individual is unnecessary. That is, if everyone else restrains then it would make much of a difference if you didn't restrain. On the other-hand, if you restrain and no one else does, then your attempt at conservation is futile. Therefore, it is everyone's individual self-interest to NOT conserve. However, if everyone acts individualistically, all are worse off. One last interesting example of an NPD is called the ‘tragedy of the commons’. Suppose there are six farmers who each owns one cow that weighs 1000 lbs. These six farmers share one plot of grazing land, a plot that can maximally sustain six cows without deterioration from overgrazing. For every additional cow that is added, the weight of every animal decreases by 100 lbs. Suppose every farmer had the opportunity to add one 28

Game Theory cow. If one farmer decides to add one cow, then his wealth increases since he will now have two cows that weigh 900 lbs each instead of just one cow that weighs 1000 lbs. Each of the six farmers, if they act in their own self-interest, will also add another cow. However, if all six farmers do add another cow, then each farmer ends up worse off. That is, each farmer will have two cows that weighs 400 lbs each instead of one cow that weighs 1000 lbs. Small farmers in England during the period of the enclosures in the eighteenth century became impoverished because of this NPD situation. All multi-person prisoner's dilemmas share a common underlying strategic structure. Therefore, any game that satisfies the following criteria is an NPD by definition:



each player has two options: cooperate or defect



defecting is the dominant strategy for each player (i.e. each player is better off choosing to defect than to cooperate no matter how many other players choose to cooperate)



the dominant strategies (to defect) intersect at a deficient equilibrium point (if all players choose to defect, the outcome is worse than if each player had chosen non-dominant strategies (to cooperate))

Chicken There is a game called Chicken, in which two people drive two very fast cars towards each other from opposite ends of a long straight road. If one of them swerves before the other, he is called a chicken. Of course, if neither swerves, they will crash. The worst possible payoff is to crash into each other, so we assign this a value 0. The best payoff is to have your opponent be the chicken, so we assign this a value 3. The next to worst possibility is to be the chicken, so we assign this a value 1. The last possibility is that both drivers swerve. Then, neither has less honor than the other, so this is preferable to being the chicken. However, it is not quite as good as being the victor, so we assign it a value 2. We could assign a payoff matrix to this:

Swerve

Swerve 2, 2 29

Drive Straight 1, 3

Game Theory Drive Straight

3, 1

0, 0

Unlike the prisoner's dilemma, mutual defection is the worst outcome in chicken. Both players want to do the opposite of what the other player does.

Volunteers’ Dilemma The version of chicken with more than two players is known as the volunteer's dilemma. In a volunteer's dilemma, one player needs to take an action that will benefit all of the players. For instance, suppose James Bond, Paris Carver, and Wai Lin are locked in three sound-proof cells by Elliot Carver. In one hour, Elliott will release poison gas into their cells unless at least one of the three pushes a button. Whoever pushes the button will be immediately killed, but the other two will be released immediately. The three cannot communicate or coordinate their efforts. If any of the three are to survive, one of them must sacrifice himself or herself. The least disturbing case is when all three reach the same conclusion about who should be sacrificed. In this case, the martyr will push the button, and the others will be spared. A second possibility is that all players decide to save each other. Then there will be a race to push the button first. The most disturbing case is when each player decides that he or she should be saved. When this happens, none push the button and the clock ticks away. Suppose that you are Bond, and Paris and Wai Lin have not pushed the button by the end of 59 minutes. It seems that they have decided that you should sacrifice yourself, but you don't want to do that. There is no point in vowing to never push the button because then all three of you will die. Ideally, you want to push the button in the last possible second. However, there is no way to determine exactly when this is, so the resolution of the conflict rides on chance and reflexes.

Other Dilemmas These dilemmas are examples of games in which both players share the same preferences. These games are known as symmetric games. In these games, neither player has a privileged position. In this sense, they can often model the real world. 30

Game Theory

Deadlock The payoff matrix for deadlock looks something like this: Cooperate Defect

Cooperate 1, 1 3, 0

Defect 0, 3 2, 2

Each player does better defecting no matter what his partner does. Unlike the prisoner's dilemma though, it is better for them to both defect than to both cooperate. This is called deadlock because the two players will decide not to cooperate. This situation sometimes arises when two countries do not want to disarm so fail to reach arms control agreements.

Stag Hunt The philosopher Jean-Jacques Rousseau imagined a situation like this: In early societies, people formed alliances to hunt deer. If even one person in the group did not help with the hunt, the deer would be lost. The hunters were sometimes tempted to leave the hunt by seeing rabbits, but they preferred deer to rabbit. However, only one person was needed to catch a rabbit. From a game theory perspective, the best strategy is to hunt the deer, but people may decide to hunt the rabbit because they believe others may defect from the hunt also. Countries face the same dilemma in situations involving nuclear weapons. Each country generally believes that the world would be better if no countries possessed nuclear weapons. However, the temptation to build up a nuclear arsenal arises because each country is afraid that other countries may stash nuclear warheads and undermine international security.

31

Game Theory

Applications of Game Theory Though at first glance the idea of game theory sounds trivial, applications of game theory are extensive. Von Neumann and Morgenstern originally applied their models of games to economic analysis. Each factor in the market, such as seasonal preferences, buyer choice, changes in supply and material costs, and other such market factors can be used to describe strategies to maximize the outcome and thus the profit. However, game theory can be also used to simply study economics of the past and interactions of different factors in a matter. It can also be used to investigate matters such as monetary distributions and their effects on other outcomes. Military strategists have turned to game theory to play "war games." Usually, such games are not zero-sum games, for loses to one side are not won by the other, and they have been criticized as potentially dangerous oversimplification of necessarily factors. Economic situations are also more complicated than zero-sum games, but those factors only require readjustments to the strategy over time. Sociologists have taken an interest in game theory, and have developed an entire branch dedicated to group decision making. Immunization procedures and vaccine or other medication tests are analyzed by epidemiologists using game theory. The properties of n-person non-zero-sum games can be used to study different aspects of social sciences as well. Matters such as distribution of power, interactions between nations, the distribution of classes and their effects of government, and many other matters can be easily investigated by breaking the problem down into smaller games, each of whose outcomes affect the final result of a larger game.

32

Game Theory Philosophy Philosophers are increasingly becoming interested in Game Theory because it provides a way of elucidating the logical difficulty of philosophers such as Hobbes, Rousseau, Kant and other social and political theorists.

 Rationality and the pursuit of self-interest: According to Bertrand Russell “‘Reason’ has a perfectly clear and precise meaning. It signifies the choice of the right means to an end that you wish to achieve". This is the interpretation of 'reason' that most contemporary philosophers favor. However, many philosophers have pointed out situations where the concept of rationality seems to break down. The situations are those who strategic structures resemble that of the Prisoner's Dilemma. An example of a multiple person Prisoner's Dilemma is as follows: Suppose that during a drought, a person must decide whether he should act in his own self-interest and water the garden or whether he should exercise restraint and conserve water. No matter what the other community members do, a person is always better off watering his garden because this is the right means to the end that he desires. The reasoning for this is that it is unnecessary for one person to exercise restraint if the most other community members are restraining as well. Even if the rest of the community doesn't exercise restraint, it is futile for just one person to do so since one person does not have that big of an impact on the whole water supply. The paradox is that if the entire community reasons this way, the water supply will dry up completely but if each community member cooperates and exercises restraint (acts irrationally) the water supply will be spared. Moral philosopher, Derek Parfit, believes that cooperation, instead of being the irrational choice, can be a rational course of action. Parfit has proposed several solutions to the Prisoner's dilemma so that cooperation becomes the reasonable choice. One solution involves changing the entire structure of the game so that it is no longer a Prisoner's Dilemma. To do this, the payoff functions of each player should be changed in order to make it unprofitable for anyone to defect. In the case of the example given above, the payoff functions of each individual would change if there were a fine for watering the garden during a drought. Such a solution is

33

Game Theory considered a "political" solution and oftentimes these sorts of solutions cannot be implemented. Parfit argues that an even better solution would be to find ways to make people cooperate for purely moral reasons. Parfit proposes that the way to achieve such a "moral" solution would be to educate society about the Prisoner's Dilemma and it's most desirable, though irrational solution.

 Kant's Categorical Imperative Immanuel Kant's categorical imperative, which is intended to be a fundamental principle of morality, states: "Act only on such a maxim through which you can at the same time will that it should become a universal law." A maxim is just a personal rule of conduct while the universal law is the conduct of all people. Kant's categorical imperative is continually debated among moral philosophers because of its obscurity. Through the use of Game Theory, Kant's views can be clarified. Kant's beliefs, when understood, offers a moral solution to the Prisoner's Dilemma. One of Kant's examples of categorical imperative is illustrated in the following maxim: "Always borrow money when in need and promise to pay it back without any intention of keeping the promise." This maxim cannot possibly made into a universal law because it cannot be made universal without creating a contradiction. That is, if this maxim was made universal, then everyone would break promises and a promise would have no meaning and therefore promises would cease to exist. Therefore, if this maxim were made universal, a logical contradiction would follow. In terms of Game Theory, Kant's categorical imperative can be restated as follows: "Choose only a strategy which, if you could will it to be chosen by all the players, would yield a better outcome from you point of view than any other". This statement, then, becomes a solution to the Prisoner's Dilemma. That is, according to Kant's categorical imperative, only a cooperative choice can result. This is because the personal choice of defecting, if made universal, is in contradiction to one's personal interest (similar to the above example).

34

Game Theory

 Hobbes's and Rousseau's Social Contract Through the use of Game Theory, Hobbes' argument, later made popular by Jean-Jacques Rousseau, for absolute monarchy can be reconstructed. Hobbes argued that, without some form of external constraint on people's behaviors, anarchy would ensue. Cooperation among people would be impossible since people act only to maximize individual welfare and not the welfare of society as a whole. Granted, there will exists altruists (maybe even many of them) who constrain their self-interests for the good of others. However, if even one self-interested person exists, he/she will exploit the altruists' constraints, profiting from both his/her absence of constraint and the altruist's unselfish behavior. As a result, Hobbes believes that it is psychologically unnatural for altruists to exist. If just one narrowly self-interested person exists no altruist can survive unless he/she becomes narrowly self-interested too. In such an environment, known as a State of Nature, Hobbes argues that a person must always be suspicious that another will attack in order to maximize his/her own self-interest. Therefore, in order for a person to maximize his best interest, he must attack the other person before that other person can attack. Each such conflict between two people in a state of nature has been termed as the "Hobbesian Dilemma." However, in the field of Game Theory, the Hobbesian Dilemma has the same structure as a "Prisoner's Dilemma." Hobbes believed that the "Hobbesian Dilemma" results in a State of Nature because morality is an unstable enforcer of social cooperation. According to Hobbes, a stable enforcer can only exist if not one person can deviate from the established rule by which the rest adhere to. Since cooperation among people is biologically necessary, a stable enforcer must exist. Hobbes believes that the best form of social enforcement is the existence of an all-powerful sovereign.

Resource Allocation and Networking Computer network bandwidth can be viewed as a limited resource. The users on the network compete for that resource. Their competition can be simulated using game theory models. No centralized regulation of network usage is possible because of the diverse ownership of network resources.

35

Game Theory The problem is of ensuring the fair sharing of network resources. For example, ten Stanford students on the same local network need access to the Internet. Each person, by using their network connection, diminishes the quality of the connection for the other users. This particular case is that of a volunteer's dilemma. That is, if one person abstains from using the network, the other people will be better off, but that person will be worse off. If a centralized system could be developed which would govern the use of the shared resources, each person would get an assigned network usage time or bandwidth, thereby limiting each person's usage of network resources to his or her fair share. As of yet, however, such a system remains an impossibility, making the situation of sharing network resources a competitive game between the users of the network and decreasing everyone's utility.

Biology Although the natural world is often thought of as brutal, dog-eat-dog type, cooperation exists between many different species. The reason behind this coexistence can be modeled using game theory. For example, birds called ziczacs enter crocodiles' mouths to eat parasites. This symbiosis allows crocodiles to achieve good oral hygiene and allows the ziczacs to get a decent meal. But any crocodile can easily eat a ziczac (defect). So why don't they? Apparently, over the eons of evolutionary action, the crocodiles and the ziczacs have learned the benefits of cooperation, the "equilibrium point." Of course, chances are that neither the crocodiles nor the ziczacs rationalize their behavior with game theory. But their behavior can still be modeled using game theory principles.

Artificial Intelligence One of the marks that differentiate a human from a machine is the human's ability to make independent decisions based on environmental stimuli. Most computer programs that are required to make any sort of a decision are currently pre-programmed with the lists of decisions based on a number of conditions. However, if those conditions are not

36

Game Theory met in some way or are altered, computers have no way of making decisions they were not programmed to make. In the future, AI programs may be endowed with the ability to make new decisions unplanned for by their creators. This would require the programs to be able to generate new payoff matrices based on the observed stimuli and experience. A program that is able to do that would be capable of learning and would, in a lot of ways, resemble the human decision-making process.

Economics Many of the interactions in the business world may be modeled using game theory methodology. A famous example is that of the similarity of the price-setting of oligopolies to the Prisoner's Dilemma. If an oligopoly situation exists, the companies are able to set prices if they choose to cooperate with each other. If they cooperate, both are able to set higher prices, leading to higher profits. However, if one company decides to defect by lowering its price, it will get higher sales, and, consequently, bigger profits than its competitor(s), who will receive lower profits. If both companies decide to defect, i.e. lower prices, a price war will ensue, in which case neither company will profit, since it will retain its market share and experience lower revenues at the same time.

Similar arguments can be extended to many cases like: 

advertising for a company’s products



international trade between nations and Trade Barriers



expenditure on National Defense for two neighbouring nations

This can better be explained with the help of the following example: Suppose PepsiCo & Coca-Cola enter a new market and decide to form a cartel and fix prices. Assuming that if they honour the cartel agreement, they both would land up with revenues of $6 million each. But in case one of them cheats and the other does not, the difference in revenues could be huge ($6 million in this case; between the companies).

37

Game Theory The temptation to cheat is very high in this case and if both the companies cheat on the agreement, then it’s a loss to both as can be very well seen from the following table.

PepsiCo

Cheat on

Cheat on Cartel

Don’t Cheat

(Charge Low Price)

(Charge Monopoly Price)

$3 million each

Coca-

Cartel

Cola

Don’t

Coke earns $2 million

Cheat

Pepsi earns $8 million

Coke earns $8 million Pepsi earns $2 million $6 million each

Prisoner's dilemma is not the only game theory model which can be used to model economic situations. Other models can be applied to different situations and, in many cases, can suggest the best outcome for all parties concerned.

38

Game Theory

Case Study: Limitations of ‘Game Theory’ & the ‘Theory of Moves’ Theory of Moves "We're eyeball to eyeball, and I think the other fellow just blinked" were the eerie words of Secretary of State Dean Rusk at the height of the Cuban missile crisis in October 1962. He was referring to signals by the Soviet Union that it desired to defuse the most dangerous nuclear confrontation ever to occur between the superpowers, which many analysts have interpreted as a classic instance of nuclear "Chicken". Chicken is the usual game used to model conflicts in which the players are on a collision course. The players may be drivers approaching each other on a narrow road, in which each has the choice of swerving to avoid a collision or not swerving. In the novel Rebel without a Cause, which was later made into a movie starring James Dean, the drivers were two teenagers, but instead of bearing down on each other they both raced toward a cliff, with the object being not to be the first driver to slam on his brakes and thereby "chicken out", while, at the same time, not plunging over the cliff. While ostensibly a game of Chicken, the Cuban missile crisis is in fact not well modelled by this game. Another game more accurately represents the preferences of American and Soviet leaders, but even for this game standard game theory does not explain their choices. On the other hand, the "theory of moves," which is founded on game theory but radically changes its standard rules of play, does retrodict, or make past predictions of, the leaders' choices. More important, the theory explicates the dynamics of play, based on the assumption that players think not just about the immediate consequences of their actions but their repercussions for future play as well.

39

Game Theory I will use the Cuban missile crisis to illustrate parts of the theory, which is not just an abstract mathematical model but one that mirrors the real-life choices, and underlying thinking, of flesh-and-blood decision makers. Indeed, Theodore Sorensen, special counsel to President John Kennedy, used the language of "moves" to describe the deliberations of Excom, the Executive Committee of key advisors to Kennedy during the Cuban missile crisis: "We discussed what the Soviet reaction would be to any possible move by the United States, what our reaction with them would have to be to that Soviet action, and so on, trying to follow each of those roads to their ultimate conclusion."

Classical Game Theory and the Missile Crisis Game theory is a branch of mathematics concerned with decision-making in social interactions. It applies to situations (games) where there are two or more people (called players) each attempting to choose between two more more ways of acting (called strategies). The possible outcomes of a game depend on the choices made by all players, and can be ranked in order of preference by each player. In some two-person, two-strategy games, there are combinations of strategies for the players that are in a certain sense "stable". This will be true when neither player, by departing from its strategy, can do better. Two such strategies are together known as ‘Nash equilibrium’, named after John Nash, a mathematician who received the Nobel prize in economics in 1994 for his work on game theory. Nash equilibria do not necessarily lead to the best outcomes for one, or even both, players. Moreover, for the games that will be analyzed - in which players can only rank outcomes ("ordinal games") but not attach numerical values to them ("cardinal games") they may not always exist. (While they always exist, as Nash showed, in cardinal games, Nash equilibria in such games may involve "mixed strategies," which will be described later.) The Cuban missile crisis was precipitated by a Soviet attempt in October 1962 to install medium-range and intermediate-range nuclear-armed ballistic missiles in Cuba that were 40

Game Theory capable of hitting a large portion of the United States. The goal of the United States was immediate removal of the Soviet missiles, and U.S. policy makers seriously considered two strategies to achieve this end [see Figure 1 below]: 1. A naval blockade (B), or "quarantine" as it was euphemistically called, to prevent shipment of more missiles, possibly followed by stronger action to induce the Soviet Union to withdraw the missiles already installed. 2. A "surgical" air strike (A) to wipe out the missiles already installed, insofar as possible, perhaps followed by an invasion of the island. The alternatives open to Soviet policy makers were: 1. Withdrawal (W) of their missiles. 2. Maintenance (M) of their missiles.

Blockade United

(B)

States (U.S.)

Air strike (A)

Soviet Union (S.U.) Withdrawal (W) Maintenance (M) Soviet victory, Compromise U.S. defeat (3,3) (2,4) U.S. victory, Nuclear war Soviet defeat (1,1) (4,2)

Figure 1: Cuban missile crisis as Chicken Key: (x, y) = (payoff to U.S., payoff to S.U.) 4=best; 3=next best; 2=next worst; 1=worst Nash equilibria underscored These strategies can be thought of as alternative courses of action that the two sides, or "players" in the parlance of game theory, can choose. They lead to four possible outcomes, which the players are assumed to rank as follows: 4=best; 3=next best; 2=next worst; and l=worst. Thus, the higher the number, the greater the payoff; but the payoffs are only ordinal, that is, they indicate an ordering of outcomes from best to worst, not the degree to which a player prefers one outcome over another. The first number in the

41

Game Theory ordered pairs for each outcome is the payoff to the row player (United States), the second number the payoff to the column player (Soviet Union). Needless to say, the strategy choices, probable outcomes, and associated payoffs shown in Figure 1 provide only a skeletal picture of the crisis as it developed over a period of thirteen days. Both sides considered more than the two alternatives listed, as well as several variations on each. The Soviets, for example, demanded withdrawal of American missiles from Turkey as a quid pro quo for withdrawal of their own missiles from Cuba, a demand publicly ignored by the United States. Nevertheless, most observers of this crisis believe that the two superpowers were on a collision course, which is actually the title of one book describing this nuclear confrontation. They also agree that neither side was eager to take any irreversible step, such as one of the drivers in Chicken might do by defiantly ripping off the steering wheel in full view of the other driver, thereby foreclosing the option of swerving. Although in one sense the United States "won" by getting the Soviets to withdraw their missiles, Premier Nikita Khrushchev of the Soviet Union at the same time extracted from President Kennedy a promise not to invade Cuba, which seems to indicate that the eventual outcome was a compromise of sorts. But this is not game theory's prediction for Chicken, because the strategies associated with compromise do not constitute a Nash equilibrium. To see this, assume play is at the compromise position (3,3), that is, the U.S. blockades Cuba and the S.U. withdraws its missiles. This strategy is not stable, because both players would have an incentive to defect to their more belligerent strategy. If the U.S. were to defect by changing its strategy to airstrike, play would move to (4,2), improving the payoff the U.S. received; if the S.U. were to defect by changing its strategy to maintenance, play would move to (2,4), giving the S.U. a payoff of 4. (This classic game theory setup gives us no information about which outcome would be chosen, because the table of payoffs is symmetric for the two players. This is a frequent problem in interpreting the results of a game theoretic analysis, where more than one equilibrium position can arise.) Finally, should the players be at the mutually worst outcome of (1,1), that is, nuclear war, both would obviously desire to move away from it, making the strategies associated with it, like those with (3,3), unstable. 42

Game Theory

Theory of Moves and the Missile Crisis Using Chicken to model a situation such as the Cuban missile crisis is problematic not only because the (3,3) compromise outcome is unstable but also because, in real life, the two sides did not choose their strategies simultaneously, or independently of each other, as assumed in the game of Chicken described above. The Soviets responded specifically to the blockade after it was imposed by the United States. Moreover, the fact that the United States held out the possibility of escalating the conflict to at least an air strike indicates that the initial blockade decision was not considered final - that is, the United States considered its strategy choices still open after imposing the blockade. As a consequence, this game is better modelled as one of sequential bargaining, in which neither side made an all-or-nothing choice but rather both considered alternatives, especially should the other side fail to respond in a manner deemed appropriate. In the most serious breakdown in the nuclear deterrence relationship between the superpowers that had persisted from World War II until that point, each side was gingerly feeling its way, step by ominous step. Before the crisis, the Soviets, fearing an invasion of Cuba by the United States and also the need to bolster their international strategic position, concluded that installing the missiles was worth the risk. They thought that the United States, confronted by a fait accompli, would be deterred from invading Cuba and would not attempt any other severe reprisals. Even if the installation of the missiles precipitated a crisis, the Soviets did not reckon the probability of war to be high (President Kennedy estimated the chances of war to be between 1/3 and 1/2 during the crisis), thereby making it rational for them to risk provoking the United States. There are good reasons to believe that U.S. policymakers did not view the confrontation to be Chicken-like, at least as far as they interpreted and ranked the possible outcomes. I offer an alternative representation of the Cuban missile crisis in the form of a game I will call Alternative, retaining the same strategies for both players as given in Chicken but presuming a different ranking and interpretation of outcomes by the United States [see Figure 2]. These rankings and interpretations fit the historical record better than those of "Chicken", as far as can be told by examining the statements made at the time by 43

Game Theory President Kennedy and the U.S. Air Force, and the type and number of nuclear weapons maintained by the S.U. (more on this below). BW: The choice of blockade by the United States and withdrawal by the Soviet Union remains the compromise for both players - (3,3). BM: In the face of a U.S. blockade, Soviet maintenance of their missiles leads to a Soviet victory (its best outcome) and U.S. capitulation (its worst outcome) - (1,4). AM: An air strike that destroys the missiles maintained by Soviets is an "honourable" U.S. action (its best outcome) and thwarts the Soviets (their worst outcome) - (4,1). AW: An air strike that destroys the missiles that the Soviets were withdrawing is a "dishonorable" U.S. action (its next-worst outcome) and thwarts the Soviets (their nextworst outcome) - (2,2).

Blockade (B) United

↓

States (US)

Soviet Union (S.U.) Withdrawal (W) Maintenance (M) Soviet victory, Compromise U.S. capitulation → (3,3) (1,4) "Dishonourable" U.S.

Air strike

action,

(A)

Soviets thwarted

"Honourable" U.S. ←

action, Soviets thwarted

(2,2) (4,1) Figure 2: Cuban missile crisis as Alternative Key: (x, y) = (payoff to U.S., payoff to S.U.) 4=best; 3=next best; 2=next worst; 1=worst Nonmyopic equilibria in bold Arrows indicate direction of cycling Even though an air strike thwarts the Soviets at both outcomes (2,2) and (4,1), I interpret (2,2) to be less damaging for the Soviet Union. This is because world opinion, it may be surmised, would severely condemn the air strike as a flagrant overreaction - and hence a "dishonourable" action of the United States - if there were clear evidence that the Soviets were in the process of withdrawing their missiles anyway. On the other hand, given no 44

Game Theory such evidence, a U.S. air strike, perhaps followed by an invasion, would action to dislodge the Soviet missiles. The statements of U.S. policy makers support Alternative. In responding to a letter from Khrushchev, Kennedy said, "If you would agree to remove these weapons systems from Cuba . . . we, on our part, would agree . . . (a) to remove promptly the quarantine measures now in effect and (b) to give assurances against an invasion of Cuba," which is consistent with Alternative since (3,3) is preferred to (2,2) by the United States, whereas (4,2) is not preferred to (3,3) in Chicken. If the Soviets maintained their missiles, the United States preferred an air strike to the blockade. As Robert Kennedy, a close adviser to his brother during the crisis, said, "If they did not remove those bases, we would remove them," which is consistent with Alternative, since the United States prefers (4,1) to (1,4) but not (1,1) to (2,4) in Chicken. Finally, it is well known that several of President Kennedy's advisers felt very reluctant about initiating an attack against Cuba without exhausting less belligerent courses of action that might bring about the removal of the missiles with less risk and greater sensitivity to American ideals and values. Pointedly, Robert Kennedy claimed that an immediate attack would be looked upon as "a Pearl Harbor in reverse, and it would blacken the name of the United States in the pages of history," which is again consistent with the Alternative since the United States ranks AW next worst (2) - a "dishonourable" U.S. action - rather than best (4) - a U.S. victory - in Chicken. If Alternative provides a more realistic representation of the participants' perceptions than Chicken does, standard game theory offers little help in explaining how the (3,3) compromise was achieved and rendered stable. As in Chicken, the strategies associated 45

Game Theory with this outcome are not a Nash equilibrium, because the Soviets have an immediate incentive to move from (3,3) to (1,4). However, unlike Chicken, Alternative has no outcome at all that is a Nash equilibrium, except in "mixed strategies". These are strategies in which players randomize their choices, choosing each of their two so-called pure strategies with specified probabilities. But mixed strategies cannot be used to analyse Alternative, because to carry out such an analysis, there would need to be numerical payoffs assigned to each of the outcomes, not the rankings I have assumed. The instability of outcomes in Alternative can most easily be seen by examining the cycle of preferences, indicated by the arrows going in a clockwise direction in this game. Following these arrows shows that this game is cyclic, with one player always having an immediate incentive to depart from every state: the Soviets from (3,3) to (1,4); the United States from (1,4) to (4,1); the Soviets from (4,1) to (2,2); and the United States from (2,2) to (3,3). Again we have indeterminacy, but not because of multiple Nash equilibria, as in Chicken, but rather because there are no equilibria in pure strategies in Alternative.

Rules of Play in Theory of Moves How, then, can we explain the choice of (3,3) in Alternative, or Chicken for that matter, given its nonequilibrium status according to standard game theory? It turns out that (3,3) is a "nonmyopic equilibrium" in both games, and uniquely so in Alternative, according to the theory of moves (TOM). By postulating that players think ahead not just to the immediate consequences of making moves, but also to the consequences of countermoves to these moves, counter-countermoves, and so on, TOM extends the strategic analysis of conflict into the more distant future. To be sure, game theory allows for this kind of thinking through the analysis of "game trees," where the sequential choices of players over time are described. But the game tree 46

Game Theory continually changed with each development in the crisis. By contrast, what remained more or less constant was the configuration of payoffs of Alternative, though where the players were in the matrix changed. In effect, TOM, by describing the payoffs in a single game but allowing players to make successive calculations of moves to different positions within it, adds nonmyopic thinking to the economy of description offered by classical game theory. The founders of game theory, John von Neumann and Oskar Morgenstern, defined a game to be "the totality of rules of play which describe it." While the rules of TOM apply to all games between two players, here I will assume that the players each have just two strategies. The four rules of play of TOM describe the possible choices of the players at each stage of play:

Rules of Play 1. Play starts at an initial state, given at the intersection of the row and column of a payoff matrix. 2. Either player can unilaterally switch its strategy, or make a move, and thereby change the initial state into a new state, in the same row or column as the initial state. The player who switches is called player l (P1). 3. Player 2 (P2) can respond by unilaterally switching its strategy, thereby moving the game to a new state. 4. The alternating responses continue until the player (P1 or P2) whose turn it is to move next chooses not to switch its strategy. When this happens, the game terminates in a final state, which is the outcome of the game.

Termination Rule 5. A player will not move from an initial state if this moves (i) leads to a less preferred outcome, or (ii) returns play to the initial state, making this state the outcome.

Precedence Rule 47

Game Theory 6. If it is rational for one player to move and the other player not to move from the initial state, the move takes precedence: it overrides staying, so the outcome will be induced by the player that moves. Note that the sequence of moves and countermoves is strictly alternating: first, say, the row player moves, then the column player, and so on, until one player stops, at which point the state reached is final and, therefore, the outcome of the game. I assume that no payoffs accrue to players from being in a state unless it becomes the outcome (which could be the initial state if the players choose not to move from it). To assume otherwise would require that payoffs be numerical, rather than ordinal ranks, which players can accumulate as they pass through states. But in many real-life games, payoffs cannot easily be quantified and summed across the states visited. Moreover, the big reward in many games depends overwhelmingly on the final state reached, not on how it was reached. In politics, for example, the payoff for most politicians is not in campaigning, which is arduous and costly, but in winning. Rule 1 differs drastically from the corresponding rule of play in standard game theory, in which players simultaneously choose strategies in a matrix game that determines its outcome. Instead of starting with strategy choices, TOM assumes that players are already in some state at the start of play and receive payoffs from this state only if they stay. Based on these payoffs, they must decide, individually, whether or not to change this state in order to try to do better. Of course, some decisions are made collectively by players, in which case it is reasonable to say that they choose strategies from scratch, either simultaneously or by coordinating their choices. But if, say, two countries are coordinating their choices, as when they agree to sign a treaty, the important strategic question is what individualistic calculations led them to this point. The formality of jointly signing the treaty is the culmination of their negotiations and does not reveal the move-countermove process that preceded the signing. It is precisely these negotiations, and the calculations underlying them, that TOM is designed to uncover.

48

Game Theory To continue this example, the parties that sign the treaty were in some prior state from which both desired to move - or, perhaps, only one desired to move and the other could not prevent this move from happening (rule 6). Eventually they may arrive at a new state, after, say, treaty negotiations, in which it is rational for both countries to sign the treaty that was previously negotiated. As with a treaty signing, almost all outcomes of games that we observe have a history. TOM seeks to explain strategically the progression of (temporary) states that lead to a (more permanent) outcome. Consequently, play of a game starts in an initial state, at which players collect payoffs only if they remain in that state so that it becomes the final state, or outcome, of the game. If they do not remain, they still know what payoffs they would have collected had they stayed; hence, they can make a rational calculation of the advantages of staying or moving. They move precisely because they calculate that they can do better by switching strategies, anticipating a better outcome when the move-countermove process finally comes to rest. The game is different, but not the configuration of payoffs, when play starts in a different state. Rules 1 - 4 (rules of play) say nothing about what causes a game to end, only when: termination occurs when a "player whose turn it is to move next chooses not to switch its strategy" (rule 4). But when is it rational not to continue moving, or not to move at all from the initial state? Rule 5 (termination rule) says when a player will not move from an initial state. While condition (i) of this rule needs no defence, condition (ii) requires justification. It says that if it is rational, after P1 moves, for play of the game to cycle back to the initial state, P1 will not move in the first place. After all, what is the point of initiating the movecountermove process if play simply returns to "square one," given that the players receive no payoffs along the way to the outcome?

Backward Induction To determine where play will end up when at least one player wants to move from the initial state, I assume the players use backward induction. This is a reasoning process by 49

Game Theory which the players, working backward from the last possible move in a game, anticipate each other's rational choices. For this purpose, I assume that each has complete information about the other's preferences, so each can calculate the other player's rational choices, as well as its own, in deciding whether to move from the initial state or any subsequent state. To illustrate backward induction, consider again the game Alternative in Figure 2. After the missiles were detected and the United States imposed a blockade on Cuba, the game was in state BM, which is worst for the United States (1) and best for the Soviet Union (4). Now consider the clockwise progression of moves that the United States can initiate by moving to AM, the Soviet Union to AW, and so on, assuming the players look ahead to the possibility that the game makes one complete cycle and returns to the initial state (state 1):

U.S. starts Survivor

State 1 U.S. (1,4) (2,2)

→

State 2 S.U. (4,1) (2,2)

→

State 3 U.S. (2,2) (2,2)

→

|

State 4 S.U. (3,3) (1,4)

State 1 →

(1,4)

This is a game tree, though drawn horizontally rather than vertically. The survivor is a state selected at each stage as the result of backward induction. It is determined by working backward from where play, theoretically, can end up (state 1, at the completion of the cycle).

Assume the players' alternating moves have taken them clockwise in Alternative from (1,4) to (4,1) to (2,2) to (3, 3), at which point S.U. in state 4 must decide whether to stop at (3,3) or complete the cycle by returning to (1,4). Clearly, S.U. prefers (1,4) to (3,3), so (1,4) is listed as the survivor below (3,3): because S.U. would move the process back to (1,4) should it reach (3,3), the players know that if the move-countermove process reaches this state, the outcome will be (1,4). Knowing this, would U.S. at the prior state, (2,2), move to (3,3)? Because U.S. prefers (2,2) to the survivor at (3,3) - namely, (1,4) - the answer is no. Hence, (2,2) becomes the 50

Game Theory survivor when U.S. must choose between stopping at (2,2) and moving to (3,3) - which, as I just showed, would become (1,4) once (3,3) is reached. At the prior state, (4,1), S.U. would prefer moving to (2,2) than stopping at (4,1), so (2,2) again is the survivor if the process reaches (4,1). Similarly, at the initial state, (1,4), because U.S. prefers the previous survivor, (2,2), to (1,4), (2,2) is the survivor at this state as well. The fact that (2,2) is the survivor at the initial state, (1,4), means that it is rational for U.S. to move to (4,1), and S.U. subsequently to (2,2), where the process will stop, making (2,2) the rational choice if U.S. moves first from the initial state, (1,4). That is, after working backwards from S.U.'s choice of completing the cycle or not from (3,3), the players can reverse the process and, looking forward, determine what is rational for each to do. I indicate that it is rational for the process to stop at (2,2) by the vertical line blocking the arrow emanating from (2,2), and underscoring (2,2) at this point. Observe that (2,2) at state AM is worse for both players than (3,3) at state BW. Can S.U., instead of letting U.S. initiate the move-countermove process at (1,4), do better by seizing the initiative and moving, counterclockwise, from its best state of (1,4)? Not only is the answer yes, but it is also in the interest of U.S. to allow S.U. to start the process, as seen in the following counterclockwise progression of moves from (1,4):

S.U. starts Survivor

State 1 S.U. (1,4) (3,3)

→

State 2 U.S. (3,3) (3,3)

→

|

State 3 S.U. (2,2) (2,2)

→

State 4 U.S. (4,1) (4,1)

State 1 →

(1,4)

S.U., by acting "magnanimously" in moving from victory (4) at BM to compromise (3) at BW, makes it rational for U.S. to terminate play at (3,3), as seen by the blocked arrow emanating from state 2. This, of course, is exactly what happened in the crisis, with the threat of further escalation by the United States, including the forced surfacing of Soviet submarines as well as an air strike (the U.S. Air Force estimated it had a 90 percent 51

Game Theory chance of eliminating all the missiles), being the incentive for the Soviets to withdraw their missiles.

Applying TOM Like any scientific theory, TOM's calculations may not take into account the empirical realities of a situation. In the second backward-induction calculation, for example, it is hard to imagine a move by the Soviet Union from state 3 to state 4, involving maintenance (via reinstallation?) of their missiles after their withdrawal and an air strike. However, if a move to state 4, and later back to state 1, were ruled out as infeasible, the result would be the same: commencing the backward induction at state 3, it would be rational for the Soviet Union to move initially to state 2 (compromise), where play would stop. Compromise would also be rational in the first backward-induction calculation if the same move (a return to maintenance), which in this progression is from state 4 back to state 1, were believed infeasible: commencing the backward induction at state 4, it would be rational for the United States to escalate to air strike to induce moves that carry the players to compromise at state 4. Because it is less costly for both sides if the Soviet Union is the initiator of compromise - eliminating the need for an air strike - it is not surprising that this is what happened. To sum up, the Theory of Moves renders game theory a more dynamic theory. By postulating that players think ahead not just to the immediate consequences of making moves, but also to the consequences of countermoves to those moves, countercountermoves, and so on, it extends the strategic analysis of conflicts into the more distant future. TOM has also been used to elucidate the role that different kinds of power - moving, order and threat - may have on conflict outcomes, and to show how misinformation can affect player choices. These concepts and the analysis have been illustrated by numerous cases, ranging from conflicts in the Bible to disputes and struggles today.

52

Game Theory

Conclusion "Managers have much to learn from game theory - provided they use it to clarify their thinking, not as a substitute for business experience" FOR old-fashioned managers, business was a branch of warfare - a way of 'capturing markets' and 'making a killing'. Today, however, the language is all about working with suppliers, building alliances, and thriving on trust and loyalty. Management theorists like to point out that there is such a thing as 'win-win', and that business feuds can end up hurting both parties. But this can be taken too far. Microsoft's success has helped Intel, but it has been hell for Apple Computer. Instead, business needs a new way of thinking that makes room for collaboration as well as competition, for mutual benefits as well as trade-offs. Enter game theory. Stripped to its essentials, game theory is a tool for understanding how decisions affect each other. Until the theory came along, economists assumed that firms could ignore the effects of their behaviour on the actions of rivals, which was fine when competition was perfect or a monopolist held sway, but was otherwise misleading. Game theorists argue that firms can learn from game players: no card player plans his strategy without thinking about how other players are planning theirs. Economists have long used game theory to illuminate practical problems, such as what to do about global warming or about fetuses with Down's syndrome. Now business people have started to wake up to the theory's possibilities. McKinsey, a consultancy, is setting up a practice in game theory. Firms as diverse as Xerox, an office-equipment maker, Bear Stearns, an investment bank, and PepsiCo, a soft-drinks giant, are all interested. They will no doubt seize on 'Co-opetition' (Doubleday, $ 24.95), because it is written by two of the leading names in the field, Adam Brandenburger, of Harvard Business School, and Barry Nalebuff, of the Yale School of Management. It also helps by using readable case studies rather than complex mathematics.

53

Game Theory

The main practical use of game theory, say the authors, is to help a firm decide when to compete and when to co-operate. Broadly speaking, the time to co-operate is when you are increasing the size of the pie, and the time to compete is when you are dividing it up. The authors also argue that, to get a full picture of their business, managers need to think about a new category of firms, 'complementers', which lead your customers to value your products more highly than if they had only your product. Hot-dog makers and Colman's mustard are complementers: buy one and you are more likely to buy the other. So are Intel and Microsoft. The most important thing to know about a game is who the players are. A small change in the number of players can have unexpected consequences. The Holland Sweetener Company, a Dutch-Japanese joint venture, discovered this to its cost in the late 1980s when it tried to break NutraSweet's monopoly of the American artificial-sweetener market. NutraSweet managed to keep the predator out, but only after Coca-Cola and Pepsi used the threat of competition to force NutraSweet to lower its prices. When competition between two players benefits third parties in this way, there is scope for the beneficiary to split its gains. Holland Sweetener in effect gave up its share of the gains that it had helped Coke and Pepsi to win. BellSouth, a telephone company, was wiser: it insisted on being paid to play. The firm said that it would bid against Craig McCaw for control of LIN Broadcasting Corporation only if LIN paid it $ 54m for entering the fray and a further $ 15m in expenses if it lost the bid. One way for a player to do well in a game is to make itself indispensable. Nintendo built its video-games business in the late 1980s by restricting software developers to making five games each, keeping retailers on short rations, and doing much of the development in-house. Nobody else had any bargaining power. By contrast, IBM stored up trouble for itself in personal computers by allowing Microsoft and Intel to establish a lock on the two most valuable bits of the business. A second technique is to tempt lots of competing players into the game - for instance by increasing the prize. That is what American Express did in 1994 when it organised a coalition with other big companies to purchase health care. The potential contract was so large that a host of health-care providers got into a bidding war. A third technique is to 54

Game Theory make intelligent use of a resource which is worth more to your customer than to you. In 1993 TWA lifted itself off the bottom of the airline league by tearing out several rows of seats that were usually empty because the carrier was so unpopular, giving passengers more leg-room - and making the airline popular once more.

When to stop playing Game theory seems a fine way to analyse decisions retrospectively. But is it much help in the heat of battle? The track record of grand ideas imported from other disciplines, notably chaos theory, is not impressive. However, the game theorists have already notched up some significant practical successes. The Federal Communications Commission used the theory to help design its $ 7 billion auction of radio spectrum for mobile phones - and hundreds of mobile-phone companies also used the theory to formulate their bids.

But, as Peter Scott-Morgan, a consultant with Arthur D. Little, points out, game theorists are worryingly silent about the links between a company's strategy and its internal capabilities. Today's most successful managers craft their strategies on the basis of knowledge of their own companies, and devote at least as much thought to the question of how blueprints will be translated into practice. At their worst, game theorists represent a throwback to the days of such whiz-kids as Robert McNamara, chairman of Ford in 1960 and later defence secretary, who thought that rigorous analytical skills were the key to success.

Yet nothing can ever substitute for deep first-hand knowledge and experience. So, however sophisticated the games that managers play may be, they will still need to get their hands dirty.

55