9.

1 Strictly Determined Games

Game theory is a relatively new branch of mathematics designed to

help people who are in conflict situations determine the best course
of action out of several possible choices. It has applications in the
business world, warfare and political science. The pioneers of game
theory are John Von Neumann and Oskar Morgenstern.
 Von Neumann

{ Von Neumann's awareness of

results obtained by other
mathematicians and the inherent
possibilities which they offer is
astonishing. Early in his work, a
paper by Borel on the minimax
property led him to develop ...
ideas which culminated later in
one of his most original creations,
the theory of games.

{ In game theory von Neumann

proved the minimax theorem. He
gradually expanded his work in
game theory, and with co-author
Oskar Morgenstern, he wrote the
classic text Theory of Games and
Economic Behaviour (1944).
Fundamental principle of Game Theory

{ 1. A matrix game is played repeatedly.

{ 2. Player R tries to maximize winnings.

{ 3. Player C tries to minimize losses.

Two-person zero-sum matrix

{ 1. R chooses (plays) any one of m rows.

{ 2. C chooses (plays) any one of m columns.

An example

{ Suppose you have $10,000 to invest for a period of 5

years. After some investigation and advice from a financial
counselor, you arrive at the following game matrix where
you ( R ) are playing against the economy ( C). Each
entry in the matrix is the expected payoff after 5 years
for an investment of $10,000 in the corresponding row
designation with the future state of the economy in the
corresponding column section. The economy is regarded
as a rational player who can make decisions against the
investor – in any case, the investor would like to do the
best possible irrespective of what happens to the
economy. Find saddle values and optimal strategies for
each player.
Finding the saddle point(s) if they exist
1. R strategy: circle the lowest number in each row (worst case
scenario)
C’s strategy: Put a square around the greatest value of each column. There are
two saddle values located in the first row. So R should choose the first row. C (the
economy) can either fall or have no change. In either case the gain of R is the
corresponding loss to the economy. The value of the game is 5870 and since this value
is not equal to zero, the game is considered to be not fair. .
9.2 Mixed Strategy Games

In this section, we look at non-strictly determined

games. For these type of games the payoff matrix has
no saddle points.
Non-strictly determined matrix games

{ A strategy consisting of possible moves and a

probability distribution (collection of weights) which
corresponds to how frequently each move is to be
played. A player would only use a mixed strategy
when she is indifferent between several pure
strategies, and when keeping the opponent guessing
is desirable - that is, when the opponent can benefit
from knowing the next move.
Penny matching game

{ Two players R and C each have a penny , and they

simultaneously choose to show the side of the coin of their
choice. (H = heads, T = tails) If the pennies match, R wins ( C
loses) 1cent. If the pennies do not match, R loses (C wins) 1
cent. In terms of a game matrix , we have
{ Determination of Strategy

Because there is no saddle point for the penny-matching game, there

is no pure strategy for R. We will assign probabilities corresponding to
the likelihood that R will choose row 1 or row 2. Similarly, probabilities
will be found for C’s likelihood of choosing column one or column 2.
The strategy will be to choose the row with a probability that will yield
the largest expected value.
Expected Value of a Matrix Game For R

{ For the matrix game ⎡a b ⎤

M =⎢ ⎥
⎣ c d ⎦
{ and strategies ⎡ q1 ⎤
P = [ p1 p2 ] Q=⎢ ⎥
⎣ 2 ⎦
q

{ for R and C, respectively, the expected value of the game

for R is given by
E ( P , Q ) = PMQ
Fundamental Theorem of Game Theory
(The number v is the value of the game. If v = 0, the game is said to
be fair. )

For every m x n matrix game , M , there exists

strategies P * and Q* for R and C ,
respectively, and a unique number v such that

P MQ ≥ v
*

for every strategy Q of C and

PMQ ≤ v *

for every strategy P of R.

Solution to a 2 x 2 Non-strictly Determined Matrix
Game

{ For the non-strictly determined game ⎡a b ⎤

M =⎢ ⎥
⎣ c d ⎦
{ the optimal strategies P * and * and the value of
the game are given by
Q
⎡d − b⎤
* = ⎡d − c a − b⎤ ⎢ D ⎥
{ *
⎡ *
P = ⎣ p1 p2 ⎦⎤ ⎢ D D ⎥⎦
⎡ q1* ⎤
⎣ Q =⎢ * ⎥ = ⎢⎢ a − c ⎥⎥
*
{
⎣ q2 ⎦ ⎢⎣ D ⎥⎦
ad − bc
v=
D
{ where D = (a + d ) − (b + c )
Original problem :

{ 1. Identify a,b,c,d : a = 1, b = -1, c= -1, d = 1.

{ 2. Find D: (a+d)-(b+c)=4 (not zero)
{ 3. The value of the game is v = ad − bc
v=
{ v = 0 so it is a fair game D
d −c a −b⎤
{ 4. Find P * = ⎡ p1* p2* ⎤ =⎡⎢ ⎥ = [ 0.5 , 0.5]
⎣ ⎦ ⎣ D D ⎦
⎡d − b⎤
{ 5. Find ⎡ q1* ⎤ = ⎢ D ⎥ = ⎡ 0.5 ⎤
Q =⎢ * ⎥
*
⎢ 0.5 ⎥
⎢ ⎥
⎣ q2 ⎦
⎢a −c ⎥ ⎣ ⎦
⎢⎣ D ⎥⎦
{ 6. Find the expected value of game: E(P,Q)=PMQ=0
9.3 Linear programming and 2 x 2 games :
A geometric approach

This section will introduce the method of solving a

non-strictly determined matrix game without recessive
rows or columns. All such games can be converted
into linear programming problems. The method
applies to a matrix game M that has all positive
payoffs.
The method of this section will be illustrated by an
example.

{ For the payoff matrix M ⎡ 2 −4 ⎤

⎢ −1 3 ⎥ = M
⎣ ⎦
{ find the optimal strategies for the two players.
Continued ….

{ Add 5 to each entry of M { Minimize y subject to

to make all values the given constraints:
positive:

⎡7 1 ⎤ 1
⎢ 4 8 ⎥ = new M y = = x1 + x2
⎣ ⎦ v
ax1 + cx2 ≥ 1
bx1 + dx2 ≥ 1
x1 , x2 ≥ 0
Continued…
{ Substitute the values { .
for a, b, c, d into the
inequalities…
y = x1 + x2
7 x1 + 4 x2 ≥ 1
1 x1 + 8 x2 ≥ 1
x1 , x2 ≥ 0
Solve the linear programming problem

{ Solution is (2/26, 3/26)

Value of the game, v and probability values

{ The value of the game is

given by the equation
{ -This is the probability
1 26 matrix for R:
v= =
x1 + x2 5
⎡2 3⎤
p = [ vx1
*
vx2 ] = ⎢ ⎥
{ The value of the original
⎣5 5⎦
matrix with negative values
is 26/5 – 5 = 1/5
Solve the second linear programming problem to find the
probability matrix for the second player

{ - { -

y = z1 + z2
7 z1 + 1z2 ≤ 1
4 z1 + 8 z2 ≤ 1
z1 , z2 ≥ 0
 Value of the game and probability matrix for second
player

{ - { -
⎡ 52 7 52 3 ⎤
v=
1
=
52 q = [ vz1
*
vz2 ] = ⎢ ⋅ ⋅ ⎥
z1 + z2 10 ⎣ 10 52 10 52 ⎦
⎡7 3⎤
=⎢ ⎥
⎣ 10 10 ⎦
9.4 Linear programming and m x n Games:
Simplex Method and the Dual Problem

In this section, the process of solving 2 x 2 matrix

games will be generalized to solving m x n matrix
games. The procedure will be essentially the same as
the process for the 2 x 2 case, but the solution of the
linear programming problem will incorporate the
simplex method and the dual.
Procedure:

{ Given the non-strictly determined matrix game M, free of

recessive rows and columns, ⎡ r1 r2 r3 ⎤
M =⎢
⎡ q1 ⎤ ⎣ s1 s2 s3 ⎥⎦
{ to find P = [ p1 p2 ] Q* = ⎢q2 ⎥
*
and v
⎢ ⎥
{ proceed as follows: ⎢⎣q3 ⎥⎦

{ 1. If M is not a positive matrix, add a suitable positive constant k

to each element of M to get a new matrix M1

⎡a1 a2 a3 ⎤
M1 = ⎢ ⎥
⎣ 1 2 3⎦
b b b
{ If v1 is the value of game M1 , then the value of the original
game M is given by v = v1 – k
Procedure continued:

{ 2. Set up the two linear programming problems ( maximization

problem is always the dual of the minimization problem) :

y = x1 + x 2
{ A) Minimize
a 1 x 1 + b1 x 2 ≥ 1
{ subject to : a 2 x 1 + b2 x 2 ≥ 1
a 3 x 1 + b3 x 2 ≥ 1
x1 , x 2 ≥ 0

{ B) Maximize: y = z1 + z2 + z3
a1 z1 + a2 z2 + a3 b3 ≤ 1
b1 z1 + b2 z2 + b3 z3 ≤ 1
{ subject to:

z1 , z2 , z3 ≥ 0
Procedure continued:

{ Step 3. Solve the maximization problem, part (B) , the dual of

part (A), using the simplex method as modified in section 5.5.
[You will automatically obtain the solution of the minimization
problem, Part A, as well, by following this process. ]

{ Step 4. Use the solutions from the third step to find the value of
the game , v1 for game M1 and the optimal strategies and value
{ V for the original game, M.
⎡ v1 z1 ⎤
1 1 P * = [ v1 x1 v1 x2 ] Q* = ⎢⎢v2 z2 ⎥⎥
v1 = =
y z1 + z2 + z3 ⎢⎣v3 z3 ⎥⎦

v = v1 − k
An example

{ Suppose that an investor wishes to invest $10,000 in long

and short term bonds, as well as in gold, and he is
concerned about inflation. After some analysis he
estimates that the return (in thousands of dollars) at the
end of a year will be indicated in the following payoff
matrix:
{ Inflation rate
{ up 3% down 3%

⎡ 3 −3 ⎤
{
{ gold

⎢
long term bonds −3 2 ⎥
⎢ ⎥
{

short-term bonds ⎢ −1 1 ⎥⎦
{
⎣
Example continued

{ Assume that fate is a very good player that will attempt to

reduce the investor’s return as much as possible. Find the
optimal strategies for both the investor and fate. What is
the value of the game?
{ 1. We start with the payoff matrix and need to make all
entries positive so we choose to add a constant k = 4 to
each entry:

⎡ 3 −3 ⎤ ⎡ 7 1⎤
⎢ −3 2 ⎥ ⎢2 6⎥
⎢ ⎥ ⎢ ⎥
⎢⎣ −1 1 ⎥⎦ ⎢⎣ 3 5 ⎥⎦
Example continued

2. Write the corresponding linear programming problems:

min y = x1 + x2 + x3

7 x1 + 2 x2 + 3 x3 ≥ 1
subject to:
1 x1 + 6 x2 + 5 x3 ≥ 1
x1 , x2 , x3 ≥ 0
Maximize:
y = z1 + z2
subject to: 7 z1 + z2 ≤ 1
2 z1 + 6 z2 ≤ 1
3 z1 + 5 z2 ≤ 1
z1 , z2 ≥ 0
Example continued:

{ 3. Introduce slack variables and form the simplex tableau

{ and solve the second linear programming problem:

7 z1 + z2 + x1 = 1 z1 z2 x1 x2 x3 y

2 z1 + 6 z2 + x2 = 1 ⎡ 7 1 1 0 0 0 1 ⎤
3 z1 + 5 z2 + x3 = 1 ⎢ 2 6 0 1 0 0 1 ⎥⎥
⎢
− z1 − z2 + y = 0 ⎢ 3 5 0 0 1 0 1 ⎥
⎢ ⎥
⎣ −1 −1 0 0 0 1 0 ⎦
Solution:

{ After performing the steps, the final solution is displayed

below: The value of the game is zero, which means it is a
fair game.

P * = [ 0.25 0 0.75]
⎡0.5 ⎤
Q =⎢ ⎥
*

⎣0.5 ⎦
v=0