Game Theory: An Introductory Sketch

Zero-Sum Games


 Roger McCain's Game Theory: A Nontechnical Introduction to the Analysis of Strategy (Revised Edition) is available in Asia now and will be available in USA, UK, Europe and the rest of the World in October. Should you require the title for fall term, special arrangements can be made so please do contact Ms Hooi-Yean Lee (mkt@wspc.com). If you are considering to use this title after fall and would like to receive an inspection copy, please send your request via World Scientific Publishing Company's website. You may also visit http://www.worldscibooks.com/economics/7517.html for sample chapters.

Meanwhile, at a more advanced level, give some thought to McCain's Game Theory and Public Policy, Elgar, 2010. Part 1, "A Historical and Critical Survey," assesses the literature of game theory particularly from the point of view of the pragmatic purposes of public policy, while Part 2 presents some proposals and research toward a game-theoretic foundation for political economy. 

By the time Tucker invented the Prisoners' Dilemma, Game Theory was already a going concern. But most of the earlier work had focused on a special class of games: zero-sum games.

In his earliest work, von Neumann made a striking discovery. He found that if poker players maximize their rewards, they do so by bluffing; and, more generally, that in many games it pays to be unpredictable. This was not qualitatively new, of course -- baseball pitchers were throwing change-up pitches before von Neumann wrote about mixed strategies. But von Neumann's discovery was a bit more than just that. He discovered a unique and unequivocal answer to the question "how can I maximize my rewards in this sort of game?" without any markets, prices, property rights, or other institutions in the picture. It was a very major extension of the concept of absolute rationality in neoclassical economics. But von Neumann had bought his discovery at a price. The price was a strong simplifying assumption: von Neumann's discovery applied only to zero-sum games.

For example, consider the children's game of "Matching Pennies." In this game, the two players agree that one will be "even" and the other will be "odd." Each one then shows a penny. The pennies are shown simultaneously, and each player may show either a head or a tail. If both show the same side, then "even" wins the penny from "odd;" or if they show different sides, "odd" wins the penny from "even". Here is the payoff table for the game.

Table 4-1

Odd

Head Tail
Even Head 1,-1 -1,1
Tail -1,1 1,-1

If we add up the payoffs in each cell, we find 1-1=0. This is a "zero-sum game."

DEFINITION: Zero-Sum game If we add up the wins and losses in a game, treating losses as negatives, and we find that the sum is zero for each set of strategies chosen, then the game is a "zero-sum game."

In less formal terms, a zero-sum game is a game in which one player's winnings equal the other player's losses. Do notice that the definition requires a zero sum for every set of strategies. If there is even one strategy set for which the sum differs from zero, then the game is not zero sum.

Another Example

Here is another example of a zero-sum game. It is a very simplified model of price competition. Like Augustin Cournot (writing in the 1840's) we will think of two companies that sell mineral water. Each company has a fixed cost of $5000 per period, regardless whether they sell anything or not. We will call the companies Perrier and Apollinaris, just to take two names at random.

The two companies are competing for the same market and each firm must choose a high price ($2 per bottle) or a low price ($1 per bottle). Here are the rules of the game:

1) At a price of $2, 5000 bottles can be sold for a total revenue of $10000.

2) At a price of $1, 10000 bottles can be sold for a total revenue of $10000.

3) If both companies charge the same price, they split the sales evenly between them.

4) If one company charges a higher price, the company with the lower price sells the whole amount and the company with the higher price sells nothing.

5) Payoffs are profits -- revenue minus the $5000 fixed cost.

Here is the payoff table for these two companies

Table 4-2

Perrier

Price=$1

Price=$2

Apollinaris

Price=$1

0,0

5000, -5000

Price=$2

-5000, 5000

0,0

(Verify for yourself that this is a zero-sum game.) For two-person zero-sum games, there is a clear concept of a solution. The solution to the game is the maximin criterion -- that is, each player chooses the strategy that maximizes her minimum payoff. In this game, Appolinaris' minimum payoff at a price of $1 is zero, and at a price of $2 it is -5000, so the $1 price maximizes the minimum payoff. The same reasoning applies to Perrier, so both will choose the $1 price. Here is the reasoning behind the maximin solution: Apollinaris knows that whatever she loses, Perrier gains; so whatever strategy she chooses, Perrier will choose the strategy that gives the minimum payoff for that row. Again, Perrier reasons conversely.

SOLUTION: Maximin criterion For a two-person, zero sum game it is rational for each player to choose the strategy that maximizes the minimum payoff, and the pair of strategies and payoffs such that each player maximizes her minimum payoff is the "solution to the game."

Mixed Strategies

Now let'slook back at the game of matching pennies. It appears that this game does not have a unique solution. The minimum payoff for each of the two strategies is the same: -1. But this is not the whole story. This game can have more than two strategies. In addition to the two obvious strategies, head and tail, a player can "randomize" her strategy by offering either a head or a tail, at random, with specific probabilities. Such a randomized strategy is called a "mixed strategy." The obvious two strategies, heads and tails, are called "pure strategies." There are infinitely many mixed strategies corresponding to the infinitely many ways probabilities can be assigned to the two pure strategies.

DEFINITION Mixed strategy If a player in a game chooses among two or more strategies at random according to specific probabilities, this choice is called a "mixed strategy."

The game of matching pennies has a solution in mixed strategies, and it is to offer heads or tails at random with probabilities 0.5 each way. Here is the reasoning: if odd offers heads with any probability greater than 0.5, then even can have better than even odds of winning by offering heads with probability 1. On the other hand, if odd offers heads with any probability less than 0.5, then even can have better than even odds of winning by offering tails with probability 1. The only way odd can get even odds of winning is to choose a randomized strategy with probability 0.5, and there is no way odd can get better than even odds. The 0.5 probability maximizes the minimum payoff over all pure or mixed strategies. And even can reason the same way (reversing heads and tails) and come to the same conclusion, so both players choose 0.5.

Von Neumann's Discovery

We can now say more exactly what von Neumann's discovery was. Von Neumann showed that every two-person zero sum game had a maximin solution, in mixed if not in pure strategies. This was an important insight, but it probably seemed more important at the time than it does now. In limiting his analysis to two-person zero sum games, von Neumann had made a strong simplifying assumption. Von Neumann was a mathematician, and he had used the mathematician's approach: take a simple example, solve it, and then try to extend the solution to the more complex cases. But the mathematician's approach did not work as well in game theory as it does in some other cases. Von Neumann's solution applies unequivocally only to "games" that share this zero-sum property. Because of this assumption, von Neumann's brilliant solution was and is only applicable to a small proportion of all "games," serious and nonserious. Arms races, for example, are not zero-sum games. Both participants can and often do lose. The Prisoners' Dilemma, as we have already noticed, is not a zero-sum game, and that is the source of a major part of its interest. Economic competition is not a zero-sum game. It is often possible for most players to win, and in principle, economics is a win-win game. Environmental pollution and the overexploitation of resources, again, tend to be lose-lose games: it is hard to find a winner in the destruction of most of the world's ocean fisheries in the past generation. Thus, von Neumann's solution does not -- without further work -- apply to these serious interactions.

The serious interactions are instances of "nonconstant sum games," since the winnings and losses may add up differently depending on the strategies the participants choose. It is possible, for example, for rival nations to choose mutual disarmament, save the cost of weapons, and both be better off as a result -- so the sum of the winnings is greater in that case. In economic competition, increasing division of labor, specialization, investment, and improved coordination can increase "the size of the pie," leading to "that universal opulence which extends itself to the lowest ranks of the people," in the words of Adam Smith. In cases of environmental pollution, the benefits to each individual from the polluting activity is so swamped by others' losses from polluting activity that all can lose -- as we have often observed.

Poker and baseball are zero-sum games. It begins to seem that the only zero-sum games are literal games that human beings have invented -- and made them zero-sum -- for our own amusement. "Games" that are in some sense natural are non-constant sum games. And even poker and baseball are somewhat unclear cases. A "friendly" poker game is zero-sum, but in a casino game, the house takes a proportion of the pot, so the sum of the winnings is less the more the players bet. And even in the friendly game, we are considering only the money payoffs -- not the thrill of gambling and the pleasure of the social event, without which presumably the players would not play. When we take those rewards into account, even gambling games are not really zero-sum.

Von Neumann and Morgenstern hoped to extend their analysis to non-constant sum games with many participants, and they proposed an analysis of these games. However, the problem was much more difficult, and while a number of solutions have been proposed, there is no one generally accepted mathematical solution of nonconstant sum games. To put it a little differently, there seems to be no clear answer to the question, "Just what is rational in a non-constant sum game?" The well-defined rational policy in neoclassical economics -- maximization of reward -- is extended to zero-sum games but not to the more realistic category of non-constant sum games.

Table of Contents

Next file:

Roger A. McCain signature chop