GAME THEORY
Thomas S. Ferguson
Part II. Two-Person Zero-Sum Games
1. The Strategic Form of a Game.
1.1 Strategic Form.
1.2 Example: Odd or Even.
1.3 Pure Strategies and Mixed Strategies.
1.4 The Minimax Theorem.
1.5 Exercises.
2. Matrix Games. Domination.
2.1 Saddle Points.
2.2 Solution of All 2 by 2 Matrix Games.
2.3 Removing Dominated Strategies.
2.4 Solving 2 × n and m × 2Games.
2.5 Latin Square Games.
2.6 Exercises.
3. The Principle of Indifference.
3.1 The Equilibrium Theorem.
3.2 Nonsingular Game Matrices.
3.3 Diagonal Games.
3.4 Triangular Games.
3.5 Symmetric Games.
3.6 Invariance.
3.7 Exercises.
4. Solving Finite Games.
II – 1
4.1 Best Responses.
4.2 Upper and Lower Values of a Game.
4.3 Invariance Under Change of Location and Scale.
4.4 Reduction to a Linear Programming Problem.
4.5 Description of the Pivot Method for Solving Games.
4.6 A Numerical Example.
4.7 Exercises.
5. The Extensive Form of a Game.
5.1 The Game Tree.
5.2 Basic Endgame in Poker.
5.3 The Kuhn Tree.
5.4 The Representation of a Strategic Form Game in Extensive Form.
5.5 Reduction of a Game in Extensive Form to Strategic Form.
5.6 Example.
5.7 Games of Perfect Information.
5.8 Behavioral Strategies.
5.9 Exercises.
6. Recursive and Stochastic Games.
6.1 Matrix Games with Games as Components.
6.2 Multistage Games.
6.3 Recursive Games. -Optimal Strategies.
6.4 Stochastic Movement Among Games.
6.5 Stochastic Games.
6.6 Approximating the Solution.
6.7 Exercises.
7. Continuous Poker Models.
7.1 La Relance.
7.2 The von Neumann Model.
7.3 Other Models.
7.4 Exercises.
References.
II – 2
Part II. Two-Person Zero-Sum Games
1. The Strategic Form of a Game.
The individual most closely associated with the creation of the theory of games is
John von Neumann, one of the greatest mathematicians of this century. Although others
preceded him in formulating a theory of games - notably
´
Emile Borel - it was von Neumann
who published in 1928 the paper that laid the foundation for the theory of two-person
zero-sum games. Von Neumann’s work culminated in a fundamental book on game theory
written in collaboration with Oskar Morgenstern entitled Theory of Games and Economic
Behavior, 1944. Other more current books on the theory of games may be found in the
text book, Game Theory by Guillermo Owen, 2nd edition, Academic Press, 1982, and
the expository book, Game Theory and Strategy by Philip D. Straffin, published by the
Mathematical Association of America, 1993.
The theory of von Neumann and Morgenstern is most complete for the class of games
called two-person zero-sum games, i.e. games with only two players in which one player
wins what the other player loses. In Part II, we restrict attention to such games. We will
refer to the players as Player I and Player II.
1.1 Strategic Form. The simplest mathematical description of a game is the strate-
gic form, mentioned in the introduction. For a two-person zero-sum game, the payoff
function of Player II is the negative of the payoff of Player I, so we may restrict attention
to the single payoff function of Player I, which we call here L.
Definition 1. The strategic form,ornormal form, of a two-person zero-sum game is given
by a triplet (X, Y, A), where
(1) X is a nonempty set, the set of strategies of Player I
(2) Y is a nonempty set, the set of strategies of Player II
(3) A is a real-valued function defined on X ×Y .(Thus,A(x, y)isarealnumberfor
every x ∈ X and every y ∈ Y .)
The interpretation is as follows. Simultaneously, Player I chooses x ∈ X and Player
II chooses y ∈ Y , each unaware of the choice of the other. Then their choices are made
known and I wins the amount A(x, y) from II. Depending on the monetary unit involved,
A(x, y) will be cents, dollars, pesos, beads, etc. If A is negative, I pays the absolute value
of this amount to II. Thus, A(x, y) represents the winnings of I and the losses of II.
This is a very simple definition of a game; yet it is broad enough to encompass the
finite combinatorial games and games such as tic-tac-toe and chess. This is done by being
sufficiently broadminded about the definition of a strategy. A strategy for a game of chess,
II – 3
for example, is a complete description of how to play the game, of what move to make in
every possible situation that could occur. It is rather time-consuming to write down even
one strategy, good or bad, for the game of chess. However, several different programs for
instructing a machine to play chess well have been written. Each program constitutes one
strategy. The program Deep Blue, that beat then world chess champion Gary Kasparov
in a match in 1997, represents one strategy. The set of all such strategies for Player I is
denoted by X. Naturally, in the game of chess it is physically impossible to describe all
possible strategies since there are too many; in fact, there are more strategies than there
are atoms in the known universe. On the other hand, the number of games of tic-tac-toe
is rather small, so that it is possible to study all strategies and find an optimal strategy
for each player. Later, when we study the extensive form of a game, we will see that many
other types of games may be modeled and described in strategic form.
To illustrate the notions involved in games, let us consider the simplest non-trivial
case when both X and Y consist of two elements. As an example, take the game called
Odd-or-Even.
1.2 Example: Odd or Even. Players I and II simultaneously call out one of the
numbers one or two. Player I’s name is Odd; he wins if the sum of the numbers if odd.
Player II’s name is Even; she wins if the sum of the numbers is even. The amount paid to
the winner by the loser is always the sum of the numbers in dollars. To put this game in
strategic form we must specify X, Y and A.HerewemaychooseX = {1, 2}, Y = {1, 2},
and A as given in the following table.
II (even) y
I (odd) x
12
1 −2+3
2+3−4
A(x, y) = I’s winnings = II’s losses.
It turns out that one of the players has a distinct advantage in this game. Can you
tell which one it is?
Let us analyze this game from Player I’s point of view. Suppose he calls ‘one’ 3/5ths
of the time and ‘two’ 2/5ths of the time at random. In this case,
1. If II calls ‘one’, I loses 2 dollars 3/5ths of the time and wins 3 dollars 2/5ths of the
time;ontheaverage,hewins−2(3/5) + 3(2/5) = 0 (he breaks even in the long run).
2. If II call ‘two’, I wins 3 dollars 3/5ths of the time and loses 4 dollars 2/5ths of the time;
on the average he wins 3(3/5) − 4(2/5) = 1/5.
That is, if I mixes his choices in the given way, the game is even every time II calls
‘one’, but I wins 20/c on the average every time II calls ‘two’. By employing this simple
strategy, I is assured of at least breaking even on the average no matter what II does. Can
Player I fix it so that he wins a positive amount no matter what II calls?
II – 4
Let p denote the proportion of times that Player I calls ‘one’. Let us try to choose p
so that Player I wins the same amount on the average whether II calls ‘one’ or ‘two’. Then
since I’s average winnings when II calls ‘one’ is −2p +3(1− p), and his average winnings
when II calls ‘two’ is 3p − 4(1 − p) Player I should choose p so that
−2p +3(1− p)=3p −4(1 − p)
3 − 5p =7p −4
12p =7
p =7/12.
Hence, I should call ‘one’ with probability 7/12, and ‘two’ with probability 5/12. On the
average, I wins −2(7/12) + 3(5/12) = 1/12, or 8
1
3
cents every time he plays the game, no
matter what II does. Such a strategy that produces the same average winnings no matter
what the opponent does is called an equalizing strategy.
Therefore, the game is clearly in I’s favor. Can he do better than 8
1
3
cents per game
on the average? The answer is: Not if II plays properly. In fact, II could use the same
procedure:
call ‘one’ with probability 7/12
call ‘two’ with probability 5/12.
If I calls ‘one’, II’s average loss is −2(7/12) + 3(5/12) = 1/12. If I calls ‘two’, II’s average
loss is 3(7/12) − 4(5/12) = 1/12.
Hence, I has a procedure that guarantees him at least 1/12 on the average, and II has
a procedure that keeps her average loss to at most 1/12. 1/12 is called the value of the
game, and the procedure each uses to insure this return is called an optimal strategy or
a minimax strategy.
If instead of playing the game, the players agree to call in an arbitrator to settle this
conflict, it seems reasonable that the arbitrator should require II to pay 8
1
3
cents to I. For
I could argue that he should receive at least 8
1
3
cents since his optimal strategy guarantees
him that much on the average no matter what II does. On the other hand II could argue
that he should not have to pay more than 8
1
3
cents since she has a strategy that keeps her
average loss to at most that amount no matter what I does.
1.3 Pure Strategies and Mixed Strategies. It is useful to make a distinction
between a pure strategy and a mixed strategy. We refer to elements of X or Y as pure
strategies. The more complex entity that chooses among the pure strategies at random in
various proportions is called a mixed strategy. Thus, I’s optimal strategy in the game of
Odd-or-Even is a mixed strategy; it mixes the pure strategies one and two with probabilities
7/12 and 5/12 respectively. Of course every pure strategy, x ∈ X, can be considered as
the mixed strategy that chooses the pure strategy x with probability 1.
In our analysis, we made a rather subtle assumption. We assumed that when a player
uses a mixed strategy, he is only interested in his average return. He does not care about his
II – 5
