37 Games

Chapter 37 out of 37 from Discrete Mathematics for Neophytes: Number Theory, Probability, Algorithms, and Other Stuff by J. M.
Cargal
37
Game Theory
Game theory is one of the most interesting topics of discrete mathematics. The principal
theorem of game theory is sublime and wonderful. We will merely assume this theorem and use
it to achieve some of our early insights. To appreciate the theorem it is not necessary to know
the proof. Do not let any math pedant tell you otherwise.1 By a game mathematics refers to a
conflict between individuals (or entities) with conflicting goals. The element of fun is not
addressed in the mathematical view of games. To mathematicians nuclear war is a game and it
has been studied as such.
Bebe
b1 b2 b3
a1 3 1 -2
Abe a2 1 2 4
a3 -3 1 5
Game 1 A Two-Person Zero-Sum Game
An example of a game is given in the box at right, Game 1 . All of the games we study
will be two-person games. In this example, the two players are Abe and Bebe. Abe has three
possible moves: a1, a2, a3; and Bebe's possible moves are b1, b2, and b3. Since each player has
3 moves, this game is said to be 3-by-3 game. The pay-off of a move is the corresponding table
1
Here I repeat remarks in the note preceding Chapter 15. That note also tells you where
to find proofs.
1
Chapter 37 out of 37 from Discrete Mathematics for Neophytes: Number Theory, Probability, Algorithms, and Other Stuff by J. M. Cargal
entry (the table is sometimes referred to as the pay-off matrix of the game). For example, if Abe
were to make move a1 and Bebe were to make move b3, then the pay-off to Abe would be the
amount in the a1-b3 entry of the table, -2. This would be a 2 point loss for Abe and a 2 point
gain for Bebe. This last property is why the game is called a zero-sum game: Abe's loss is
Bebe's gain and vice versa. It follows that if the game is not to be trivial then each player should
make his or her move without knowledge of the other player's move. For example, in this in-
stance, if Abe knows that Bebe will do move b3, then he will make move a3. If he knows that
Bebe will make move b2, then he will make move a2. Similarly, if Abe knows that Bebe will
make move b1, in this instance, he will make move a1. Clearly Game 1 is written from Abe's
point of view. Another convention in this book is to add the same constant to each entry of the
game so that there are no negative values. This is simply done for convenience. It has no effect
whatsoever on the strategies. Its effect on the game is to add the same constant to the value of
the game (the meaning of which will be explained later). For example, Game 2 is precisely the
same as Game 1 except that each entry of the pay-off matrix has been increased by 3 points.
Since the value of Game 1 is 1.66, the value of Game 2 is 4.66.
Bebe
b1 b2 b3
a1 6 4 1
Abe a2 4 5 7
a3 0 4 8
Game 2 The Previous Game Plus 3 Points
2
Strategies
In Game 2 , a strategy for Abe means a probability vector P = (p1, p2, p3). Since P is a
probability vector, this means (just to remind you) that each pi $ 0 and p1 + p2 + p3 = 1. p1 is the
probability that Abe will play strategy a1; p2 is the probability that Abe will play strategy a2;
p3 is the probability that Abe will play strategy a3. If Abe has the strategy P = (0, 1, 0), he will
always play move a2. Such a strategy is called a pure strategy. By contrast, the strategy
P = (¼, ½, ¼) is called a mixed strategy and must be randomized. This means that at any given
move, Abe has probability ½ of playing move a2 regardless of his last move. Note that when
we examine Game 2 , I have not specified
whether the game is a one-time game, or a game
that will be played many times in sequence. The
analysis done here seems to imply the latter
case. However, there is no such intention. It
can be argued that analysis is predicated on the
assumption of a sequential series of games and
that this analysis does not apply to a one time
game. This is an interesting philosophical
argument and the reader is encouraged to think
about it. One argument goes that even if a
particular game is to be played once, perhaps
there will be other occasions where "equivalent"
games will be played, and therefore the best
approach is to play each game as if it is part of
a sequence. I do not suggest that you must
accept this argument.
Figure 1 The Game Tree for Game 2
3
We can associate a game tree with a game such as Game 2 . This game tree is shown in Figure
1. Here Abe's strategy is P = (p1, p2, p3) and Bebe's strategy is Q = (q1, q2, q3). The numbers on
the leaves of the tree are the outcomes. It follows that the expected outcome of the game is:1
The Fundamental Theorem of Game Theory
Again, we are studying two-person zero-sum games. In this environment, there is

a remarkable theorem: Each game has a definite value. There is a value such that either
player can guarantee averaging that well. For instance if the value of the game is, say 4,
then Abe has a strategy such that the average outcome will be at least 4. Bebe will have a
strategy such that the average outcome will be at most 4. These strategies are called optimal
strategies. It follows that if each player uses his optimal strategy then the average outcome
will be fixed at the value of the game.
Let us reconsider Game 2 . Without knowing anything about how to find the value
of the game we can find a lower and higher bound for it. We do this by consider pessimistic
strategies for each player. We ask: What is the worst that can happen for a given pure
strategy? From Abe's point of view if he plays strategy a1 the worst that can happen is that
Bebe plays strategy b3 and the outcome is 1. If he plays strategy a2 the worst outcome is
1
The same expression for the expected outcome value of the game can be more
economically expressed using matrix notation as follows: . This is
an excellent example of the utility of matrices.
4
4 points and if he plays a3 the worst outcome is 0 points. The best of these is playing
strategy a2 which guarantees that he achieves at least 4 points. This is the maxi-min strategy
(it maximizes the minimum of the rows). The maxi-min strategy for Abe is to play a2 and
assure himself of at least 4 points. For Bebe, she must look at things from the opposite per-
spective. She wants the minimum number of points since Abe's win is her loss. By making
all of the scores positive we have Bebe losing from 0 to 8 points depending on the strategies
played, but that is unimportant. The important consideration is that Bebe wants to minimize
the payoff (outcome) to Abe. Looking at the game from a pessimistic point of view, if she
plays strategy b1, then the worst that can happen to her is that Abe plays a1 and wins 6
points. The worst that can happen
if she plays b2 is that Abe plays a2
Bebe
and wins 5 points. The worst that
b1 b2 b3
can happen if she plays b3 is that
Abe plays a3 and wins 8 points. a1 6 4 1
The best of these outcomes from Abe a2 4 5 7

her point of view is when she plays
a3 0 4 8
b2 and Abe makes at most 5 points.
By playing b2 she assures herself
Game 3 Same Game With Pessimistic Strategies
of losing no more than 5 points. as Indicated
Her pessimistic strategy is to
minimize the maximum outcome of the columns. She plays a mini-max strategy. In fact the
custom is frequently to describe both strategies as mini-max strategies. In principle both
players are using the same approach: pick the pure strategy that minimizes the worst that
can happen.
5
Saddlepoints
In the above analysis Abe's mini-max strategy assures him of at least 4 points and
Bebe's strategy assures her of losing no more than 5 points. Hence the optimal value, the
value of the game, is between 4 and 5 points inclusive, and the optimal strategies for both
players is a mixed strategy. Note that when both Abe and Bebe play the mini-max strategies
the outcome is 5 points and Abe may well be satisfied.
Only when the mini-max strategies assure the same value are they optimal. In this case the
optimal outcome is a minimal value on its row and a maximum value of its column. It is
called a saddlepoint and is the optimal value of the game. The optimal strategies for both
sides are to play for the saddlepoint. That is each player has an optimal pure strategy. A
saddlepoint is not necessarily unique, but its value is unique.
In Game 2 Abe's mini-max strategy assures him of at least 4 points; Bebe's mini-
max assures her of losing no more than 5 points. Since these numbers are not the same, this
game does not have a saddlepoint and the optimal strategies for both players are mixed and
the value of the game is between 4 and 5 points.
It so happens that the value of that game is 4.66. Bebe can assure herself of doing
no worse than losing (on average) 4.66 points a game if she plays the strategy
Q = (1/3, 2/3, 0). In that case if Abe plays any mixture at all of his first two strategies, a1
and a2, the average outcome will be 4.66. Should he ever play strategy a3 Bebe can average
less then 4.66 (which is a change in her favor). For example should Abe always play a3,
Bebe would average 2.66 a game with her optimal strategy (Q = (1/3, 2/3, 0)). However,
should Abe be stupid enough to always play strategy a3, Bebe could always play strategy
b1 and average 0 points a game. Coincidentally, Abe's optimal strategy is also
P = (1/3, 2/3, 0). It turns out that for any mixture of strategies b1 and b2 that Bebe plays
(when Abe plays his optimal strategy) she will average a loss of 4.66 points a game.
6
However, should Bebe ever play her strategy b3 she will lose more than 4.66 (on average).
G Exercise 1 Which of the following three games have saddlepoints? What are the
value(s) of those games and what are (is) the optimal strategie(s). Of
the game(s) without saddlepoints find an upper bound and a lower
bound for the value of the game (hint: find each player's mini-max
strategy).
Bebe Bebe Bebe
9 1 0 2 3 4 3 5 2
Abe 5 2 4 Abe 1 4 5 Abe 0 5 1
3 1 0 6 5 4 0 9 0
Three Games for Homework Beb

e
b1 b2 b3
Dominant Strategies
a1 0 5 9
Abe a2 9 5 5
Consider Game 4. Abe has four
a3 5 5 5
strategies and Bebe has three strategies. The
a4 0 6 9
mini-max strategy for Abe is to play a2 or a3
Bebe
and assure himself of at least 5 points. The
mini-max strategy for Bebe is to play b2 and Game 4 A Fourb1by Three Game
b2
Abe a2 9 5
assure herself of losing no more than 6 points.
a4 0 6
Since these values are different, there is no
saddlepoint; the value of the game is between 5
Game 5 The Previous Game Re-
and 6; the optimal strategies for both players duced
7
will be mixed (and we still do not know how to calculate mixed strategies). However, it is
possible for us to simplify the game by using ordinary logic and common sense. Frequently
strategies can be eliminated from use. In this case, Abe has no reason to ever play strategy
a3. The reason is that whatever Bebe does, a2 will always perform as well as a3. We say
the strategy a2 dominates the strategy a3. Similarly, strategy a4 dominates strategy a1.
From Bebe's point of view, strategy b2 dominates b3. All together we should eliminate
from consideration strategies a1, a3, and b3. This leaves us Game 5 . It is important to
remember that once strategies have been eliminated, that strategies that were not dominated
or dominating may change status and become dominated or dominating. Then it is possible
to eliminate even more strategies.
8
G Exercise 2 Solve the games given below. By solve I mean find the value for the
game and find optimal strategies for each player. (Hint: since we
have not studied mixed strategies your only hope is to find
saddlepoints and/or to eliminate dominated strategies. If however, the
last problem say, seems to come down to mixed strategies, there
should be an easy way to see what the correct answer is.)
Bebe Bebe
2 4 2 0 2 1
Abe 2 3 2 Abe 3 2 6
3 3 2 2 1 7
Bebe Bebe
8 1 0 0 3 4 0 0
Abe 8 2 3 9 Abe 4 3 0 0
9 4 3 8 5 5 5 0
8 0 1 0 5 5 0 5
Four More Games for Homework
9
The Calculation of Mixed Strategies
We will concentrate on evaluating 2-by-2, 2-by-n, and n-by-2 games. More general
games will be treated in an appendix to this chapter. An important fact about 2-by-2 games,
is that a game has a saddlepoint if and only if it has dominant strategies. This rule does not
hold for larger games.
When examining a 2-by-2 game, just as for
any game, we look for a saddlepoint. The following Bebe
analysis applies only if there is not a saddlepoint. b1 b2
Consider the generic 2-by-2 game without a Abe a1 A B
saddlepoint: Game 6 . We want a strategy (p, 1!p) a2 C D
for Abe such that the expected outcome of the game
is unaffected by Bebe's strategy. In particular the ex- Game 6 Generic 2-by-2
pected outcome would be the same if Bebe played Game
only b1 or only b2. In the first case the expected
outcome is pA + (1!p)C in the second case the expected outcome is pB + (1!p)D. Setting
these equal to one another we get pA + (1!p)C = pB + (1!p)D. Solving for p we get:
Similarly Bebe should play strategy b1 q of the time where

nI
either case the calculation will give you a probability between 0 and 1 exclusive (a
probability of 0 or 1 would be a pure strategy). If your calculation is outside of that range
you failed to observe that there was a saddlepoint.
10
Example
In Game 7 Abe's mini-max strategy is a1
Bebe
since its minimum is 10 versus the minimum of
0 in strategy a2. Bebe's mini-max strategy is b1 b1 b2
since its maximum is 100 versus a maximum of Abe a1 100 10

1000 for b2. Abe can assure himself of always a2 0 1000
doing at least 10 by strategy a1 and Bebe can
assure herself of no worse than 100 by strategy Game 7 A 2-by-2 Game
b1. If these two values were equal we would
have a saddlepoint. As it is, the
optimal strategies are mixed strategies
Bebe
and the value of the game must lie
b1 b2
between 10 and 100. To implement the
above strategy subtract the columns 100 -990
from one another and subtract the rows Abe a1 90 100 10

from one another. It does not matter in a2 -1000 0 1000
what order you subtract one column
from another, just as long as you are Figure 2 Start of Solution of Game 7
consistent.
Bebe
b1 b2
990/1090 100/1090
Abe a1 1000/1090 100 10

In Figure 2 I
a2 90/1090 0 1000
have subtracted the
first column from the Figure 3 Solution of Game 7 Continued
11
second and the first row from the third. When this is done we get a positive answer and a
negative answer, otherwise the game has a dominant strategy and a saddlepoint. The next
step is to take the absolute values of the new entries and to switch them. Lastly, to get the
optimal strategies, we divide each entry by the sum of the entries. This is shown in Figure
3. For Abe, the optimal strategy is to play a1 100/109 of the time and to play a2 9/109 of
the time. For Bebe the optimal strategy is to play b1 99/109 of the time and to play b2
10/109 of the time. If either player plays his or her optimal strategy the average outcome
will be the value of the game. Remember that in larger games such as 2-by-3 either player
can always assure doing as well as the value of the game by playing his or her optimal
strategy. However, if the other player plays badly, it is possible to do better than the value
of the game. In a 2-by-2 game, the outcome is strictly the value of the game as long as
either player plays his or her optimal strategy. To calculate the value of the game, let Abe
play his optimal strategy, and assume the Bebe always plays b1. Then the expected
outcome is:
and the value of the game is thus 91.743. Similarly, we could calculate the value of the
game by assuming that Abe always plays his strategy a2 but Bebe plays her optimal
strategy. Then the expected outcome is:
12
Similarly, the other two analogous computations (Abe plays his optimal strategy and Bebe
plays b2 or Bebe plays her optimal strategy and Abe plays a2) will yield exactly the same
result.1
b1 b2 b1 b2 b1 b2
a1 10 20 a1 10 20 a1 10 0
a2 40 0 a2 40 19 a2 0 100
Three Games for Homework
G Exercise 3 Solve for the values and optimal strategies of the following games.
n-by-2 and 2-by-n Games
We will only consider n-by-2 games because
Bebe
2-by-n games are exactly analogous. Game 8 is a
b1 b2
4-by-2 game. We can immediately reduce it to a 3-
by-2 game since Abe's strategy a2 dominates his a1 4 0
strategy a4. Looking at the 3-by-2 game left by Abe a2 3 3
disregarding strategy a4, we can find no dominated a3 0 4

strategies for either player. Abe's mini-max a4 1 2
strategy is to play a2 and assure himself of at least
3 points. Bebe can play b1 or b2 and assure herself
Game 8 A 4-by-2 Game
of losing no more than 4 points. The value of the
game is between 3 and 4 points. It so happens that Abe will have an optimal strategy that
1
You might object that if either player plays a pure strategy that the other player can do
better than the value of the game, by playing his or her appropriate pure strategy. This is true,
but when do you have an assurance, that the other player will continue to play a pure strategy?
Here we get into the psychology of gamesmanship (or gamespersonship). The point is, if either
player likes the value of the game, he or she can guarantee achieving it regardless of what the
other does.
13
consists of a mixture of 2 of the pure strategies. This is always true for an n-by-2 game
(without a saddlepoint). It is proven by the graphical analysis of n-by-2 games that will
occur in the next section. For the time being we can find Abe's optimal strategy by looking
at the various 2-by-2 games that are sub-games of Game 8 .1 We have three games to
consider: they are the a1-a2 game, the a1-a3 game, and the a2-a3 game. In the a1-a2 game
Bebe has a dominating strategy of b1, and Abe's strategy is a2, and the value is 3 (which is
a saddlepoint). Clearly the a2-a3 game is almost identical and has a value of 3. The a1-a3
has an optimal strategy for Abe of (.5, .5) and a value of 2. Therefore Abe can consider
either the a1-a2 or the a2-a3 game as optimal, and in either case he plays the pure strategy
a2, and it doesn't matter what Bebe does.
G Exercise 4 Find the optimal strategies and the value for Game 9 .
Bebe
b1 b2 b3 b3
Abe a1 0 5 6 4
a2 4 6 1 3
Game 9 A 2-by-4 Game for Homework
1
The meaning of sub-game should be self-evident. It is a game derived from the first
game by eliminating certain strategies from consideration. Anytime we eliminate a dominated
strategy we are going to a sub-game. In this context we will eliminate a strategy that is not
dominated by another single strategy.
14
The Graphical Analysis of Games
Graphical analysis of games is usually done

Bebe
to understand 2-by-n and n-by-2 games, but to
understand the graphical analysis it is best to study b1 b2
2-by-2 games.1 Game 10 is an ordinary 2-by-2 Abe a1 4 1

game with value 16/7. Abe's optimal strategy is a2 0 4
(.571, .429) and Bebe's optimal strategy is
Game 10 The Value is 16/7
(.429, .571).
1
I have seen other texts at this level present the graph for an n-by-2 game as if the
interpretation is obvious. It is not obvious at all. That is why I am starting at the 2-by-2 level.
I don't claim that it is now easy. Take your time and study the example. Continue only when
you feel comfortable.
15
The graph of Game 10 is given in Figure 4. There

are two diagonal axes corresponding to Bebe's 2 strategies.
The main trick to this type of graph is understanding the
bottom axis. The numbers on the bottom axis range from 0
to 1. They represent the probability that Abe plays strategy
a1. For example, if Abe has the mixed strategy (.25, .75)
corresponding to playing a1 25% of the time and playing a2
75% of the time, this strategy is denoted by .25 along the
base axis. The case where he plays a1 0% of the time,
strategy (0, 1) is the case where he plays a2 100% of the
time, and that is why the first vertical axis is denoted by a2.
If you draw a vertical line from the point on the bottom axis
denoted .25 it crosses the b1-line at the height = 1 which is
what the strategy b1 would average against Abe's strategyFigure 4 The Graph of
(.25, .75). The vertical line (at .25) crosses the b2-line at Game 10
3.25 which is what Abe's strategy (.25, .75) averages against b2. Clearly, Bebe does best
against (.25, .75) using b1 rather than b2 or some mix of b1 and b2. According to the graph,
if Abe plays a1 less than .571 (4/7) of the time, Bebe does best with b1 (since Bebe wants
the minimum outcome). If Abe plays a1 more than .571 of the time Bebe does best with b2.
When Abe plays a1 .571 of the time, it doesn't matter what Bebe does: (.571, .429) is Abe's
optimal strategy.
G Exercise 5 Considering the graph of Game 10 , if Abe plays strategy (.25, .75),
and if Bebe plays a mixture of b1 and b2, where on the graph is the
average outcome? (Hint: First look at the average outcomes if Bebe
plays only b1 and and then if Bebe plays only b2).
G Exercise 6 Graph a 2-by-2 game where there is a saddlepoint. What happens?
16
We will study a 3-by-2 game, because it is

Bebe
representative of all 2-by-n and n-by-2 games. In
Game 11 there are no dominated strategies for b1 b2
either player. Abe's mini-max strategy is to play a2 a1 0 4

and to assure himself at least 2 points. Bebe's mini- Abe a2 2 3
max strategy is to play either b1 or b2; she will lose a3 4 1
at most 4 points either way. Therefore there is no
saddlepoint and the value of the game is between 2 Game 11 A 3-by-2 Game
and 4 points. To graph a game where Abe has three strategies to Bebe's 2 strategies, it is
best to graph the game from Bebe's point of view.
In the graph, the two vertical axes correspond to
Bebe's strategies b1 and b2. The bottom axis corresponds
to Bebe's strategy (p, 1!p). At the left end Bebe is playing
(0, 1) (strategy b2) and the axis is labeled b2. At the right
end, Bebe is playing (1, 0) and the axis is labeled b1. If
Bebe plays any strategy between (0, 1) and (a, b) Abe's
best response, shown by the heavy black line, is to play a1
which averages better than a2 or a3. (Note, my graph is not
perfectly scaled.) Between (a, b) and (½, ½) Abe will play
strategy a2. Between (½, ½) and (0, 1) Abe will play a3. It
is precisely at (½, ½) that Abe's strategies a3 and a2 perform
Figure 5 The Graph of
the same with an expected outcome of 2.5. The graph Game 11
indicates that this is the lowest value that Bebe can guarantee. Abe can always play a
strategy that achieves the level indicated by the extra thick line segments. This is lowest (at
2.5) when Bebe plays (½, ½). The graph indicates that if Abe plays strategy a1 when Bebe
plays (½, ½) that Abe does worse than with the other strategies. From Abe's point of view
he should stick to a2 and a3. Analyzing the game as a two strategy game it is clear that
Abe's optimal strategy is to play a2 ¾ of the time and to play a3 ¼ of the time.
17
G Exercise 7 Analyze Game 11 by considering it as 3 different 2-by-2

games that Abe has a choice of playing. Verify that the value
and optimal strategies are the same as given above.
G Exercise 8 Solve Game 8 and Game 9 using the graphical technique.
18
Appendix to Chapter 17
General Solution of Two-Person

Zero-Sum Games
The reason for making this section an

appendix is that it relies on linear Bebe
programming. Whereas many people do b1 b2 b3
consider linear programming a part of a1 3 1 -2

discrete mathematics, it is a subject unto Abe a2 1 2 4
itself and should be studied as such.1 I will a3 -3 1 5
demonstrate the general technique of zero-
sum games by doing an example: Game 1 . Game 12 Game 1 again.
This game is given again as Game 12 . Note
that this game has neither dominated strategies nor a saddlepoint. We are going to find an
optimal strategy (p, q, r) for Abe. Such a strategy must have the quality that it achieves at
least the value of the game regardless of the strategy that Bebe plays. Let us denote the still
unknown value as V. We have 4 very basic linear constraints:
1
Excellent texts on linear programming that also discuss the application to game theory
are:
Linear Programming. Vašek Chvátal. W. H. Freeman. New York, N.Y. 1983.
An Introduction to Linear Programming and Game Theory, 2nd. ed. Paul R. Thie.
Wiley. New York, N.Y. 1988.
19
! 0#p
! 0#q
! 0#r
! p+q+r = 1
To these we add three more constraints that fulfill the condition given above: the average
outcome of Abe's strategy against any of Bebe's strategies must be at least V.
! 3p + 1q + (-3)r $ V (the average outcome against b1 must exceed V)
! 1p + 2q + 1r $ V (the average outcome against b2 must exceed V)
! (-2)p + 4q + 5r $ V (the average outcome against b3 must exceed V)
Altogether we have 7 linear constraints to which we add the linear objective:
! Maximize V
In the usual simplex solution of the linear programming problem the first three non-
negativity constraints will be implicit. However, it is important that V not be constrained
to non-negativity. Hence the simplex formulation might be to write V as the difference of
two non-negative variable: V = V1 ! V2. Also, in the usual formulation, V will be moved
to the left side of the constraints that it appears in. In any case linear programming
problems can be solved using inexpensive software available for today's microcomputers.
In fact problems of this size can be easily solved using the optimization item in some spread-
sheets.
Solving the above game using a linear programming package, we get the value of the
game, V, is 1.66. The optimal strategy for Abe is p = a and q = b with r = 0. Note that
r = 0 despite the fact that strategy a3 is not dominated by either a1 or a2. To find Bebe's
optimal strategy you can either use the same approach just used for Abe's strategy or you
can use the dual variable solutions given for the solution to the above formulation. In this
case it so happens that Bebe's optimal strategy looks just like Abe's: (a, b, 0).
20
1. The first game has a saddlepoint and the value is 2. The optimal strategy for Abe is a2
and the optimal strategy for Bebe is b2.
The second game has no saddlepoint. Abe's mini-max strategy (the row with the
maximum minimum) is a3, with a minimum of 4 points. Bebe's mini-max strategy (the
column with the minimum maximum) is b2 or b3 with a maximum of 5. The true value
of the game must be in between 4 and 5 points.
The third game has a saddlepoint with value 2. Abe's optimal strategy is a1 and Bebe's
optimal strategy is b3.
2. In the first game, Bebe's strategy b3 dominates the other two strategies. Since b3 fixes
the value of the game at 2, it does not matter what Abe does. In fact all three boxes in
the rightmost column are saddlepoints.
In game 2 Abe's strategies a2 and a3 dominate a1. Having removed a1, Bebe's strategy
b2 dominates b1 and b3. At this point Abe will choose a2 and the value of the fame is
2. This again happens to be a saddlepoint.
In game 3 a1 and a4 are dominated. Once they are removed, b1 and b4 are dominated.
After b1 and b4 are removed as well, a3 dominates a2. This leaves Bebe to choose b3.
The optimal strategies are thus a3 and b3, with a value of 3, which happens to be a
saddlepoint.
In game 4 strategies a1 and a2 are dominated. After they are removed, strategies b1 and
b2 are dominated. This leaves a 2-by-2 game that has no saddlepoint and therefore
requires mixed strategies. Since the game is totally symmetric, the optimal strategies are
for Abe to play a3 and a4 each half of the time, and for Bebe to play b3 and b4 each half
of the time. The value of the game is thus 2.5.
3. Game 1: Abe's strategy is (.8, .2); Bebe's is (.4, .6). The value is 16.
Game 2: Abe's strategy is (21&31, 10&31); Bebe's is (1&31, 30&31). The value is
610&31.
Game 3: Abe's strategy is (10&11, 1&11); Bebe's is (10&11, 1&11). The value is
100&11.
4. Strategy b2 is dominated. Looking at the 3 games we get:

b1-b3 game: value is 8&3
b1-b4 game: value is 3.2
b3-b4 game: value is 4 (which is a saddlepoint).
Since Bebe wants the lowest value, Bebe will play b1-b3 with strategy (5&9, 4&9) or in
21
terms of the original game the strategy is (5&9, 0, 4&9, 0). Abe's strategy is (a,b).
5. Were Bebe to play b1 then the outcome is at the intersection of the vertical line at .25
and the line marked b1. Similarly, were Bebe to play b2 then the outcome is at the
intersection of the vertical line at .25 and the line marked b2. For a mixed strategy of b1
and b2 the outcome is on the vertical segment above .25 that connects these two points.
6. For a 2-by-2 game, there is a saddlepoint if and only if someone has a dominating
strategy. When that strategy is graphed versus the other strategy it will be above or
below the other strategy (depending on whether it is Abe's or Bebe's).
7. If you get a different answer than in the text, then one of us has made a mistake.
22
8.
Graph of Game 8
Graph of Game 9
23

37 Games

Uploaded by

Copyright:

Available Formats

37 Games

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

37 Games

Uploaded by

Copyright:

Available Formats

Chapter 37 out of 37 from Discrete Mathematics for Neophytes: Number Theory, Probability, Algorithms, and Other Stuff by J. M.

Game 1 A Two-Person Zero-Sum Game

Game 2 The Previous Game Plus 3 Points

Figure 1 The Game Tree for Game 2

The Fundamental Theorem of Game Theory

Again, we are studying two-person zero-sum games. In this environment, there is

economically expressed using matrix notation as follows: . This is

an excellent example of the utility of matrices.

The best of these outcomes from Abe a2 4 5 7

Bebe Bebe Bebe

Three Games for Homework Beb

Four More Games for Homework

The Calculation of Mixed Strategies

Similarly Bebe should play strategy b1 q of the time where

since its maximum is 100 versus a maximum of Abe a1 100 10

from one another and subtract the rows Abe a1 90 100 10

Abe a1 1000/1090 100 10

Three Games for Homework

strategy a4. Looking at the 3-by-2 game left by Abe a2 3 3

disregarding strategy a4, we can find no dominated a3 0 4

Game 9 A 2-by-4 Game for Homework

The Graphical Analysis of Games

Graphical analysis of games is usually done

2-by-2 games.1 Game 10 is an ordinary 2-by-2 Abe a1 4 1

The graph of Game 10 is given in Figure 4. There

We will study a 3-by-2 game, because it is

either player. Abe's mini-max strategy is to play a2 a1 0 4

G Exercise 7 Analyze Game 11 by considering it as 3 different 2-by-2

General Solution of Two-Person

The reason for making this section an

programming. Whereas many people do b1 b2 b3

consider linear programming a part of a1 3 1 -2

4. Strategy b2 is dominated. Looking at the 3 games we get:

You might also like