950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Chapter 6 Game Theory

TWO –PERSON GAMES

This chapter focuses on a simple situation with exactly two sides, or players, involved. These two
players compete for a payoff that one player pays to the other. The two-person game is exactly
participated by two people. The amount won by a player is exactly the same as the amount lost by
the opponent. Whenever this is the case, we call the game a zero-sum game. We can represent the
payoffs in a two-person zero -sum game by a payoff matrix.
A player’s plan of action against the opponent is called a strategy. Game theory attempts to
determine the best strategy so that the player will maximize his payoff.
Example 1
Ali and Chang play a coin-matching game. When the coins match, Ali receive 25 cents. When the
coins differ, Chang receives 25 cents. The payoff matrix is
Chang
H T
H 25 ȼ -25ȼ
Ali T -25 ȼ 25ȼ

In this coin matching game, the choice of a strategy simply amounts to selecting heads or tails.
Notice that when Ali selects the ‘Heads’ he has selected the first row of the payoff matrix. Chang’s
selection of a strategy equivalent to selecting a column of the matrix.
Example 2
The payoff matrix for a game is
C
c1 c2
r1 14 -3
R r2 -6 -5

(a) What are the possible payoff to R if strategy r1 is selected ?

(b) What are the possible payoffs to C if strategy c2 is selected?
(c) What is the payoff when R selects r2 and C selects c1 ?

Solution

1
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

(a) R receives 14 if C selects c1 and R pays 3 if C selects c2.

(b)C receives 3 or 5, depending on whether R selects r1 or r2.
(c) C receives 6 and R pays 6. (The total is zero. Therefore, this is called a zero-sum game.)

Strictly Determined Games.

The best strategy for games that have fixed strategies are called strictly determined games.
Two players, R and C, play a game in which R can take two alternative actions (strategies), called r 1
and r2 and C can take 2 actions, c1 and c2 .Because there are two possible strategies for R and two
for C, a 2 X 2 payoff matrix represents the outcome, or payoff , corresponding to each pair of
strategies selected.

Strategy for a Two- Person Zero- Sum Game

 R marks off the minimum element in each row, and selects the row that has the
largest of these minima.
 C marks off the maximum element in each column, and selects the column that
has the smallest of these maxima.

If the largest of the row minima occurs in the same location as the smallest of the
column maxima, that payoff is the value of the game.
The two strategies leading to the value, the solution, will be the ones that should
be adopted.
When the largest row minimum and the smallest column maximum are the same,
the game said to be strictly determined.
The location of this element is the saddle point of the game.

Here is an example of a payoff matrix:

C
c1 c2
r1 4 -9
R r2 6 8

R and C each wish to gain as much as they can (or lose as little as possible) Which strategies should
they select? First observe that for R to gain as much as possible, R’s strategy attempts to select the
maximum entry. As a gain for C is represented by a negative number, C attempts to select the
minimum entry.
R should select r2 , because R then stands to gain the most, 6 or 8, regardless of C’s strategy. C
should select strategy c1 , because C then risks giving the least away. With the strategies r2 and c1 ,
pays 6 to R. This entry of
The matrix is called the value of the game, its location in the matrix is called a saddle point; and the
pair of strategies leading to the value is called a solution. This game has a value of 6; the (2, 1)
location is the saddle point; and the solution is the pair of strategies r2 and c1

2
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Example 3
The following payoff matrix shows the strategies of a game played by players R and C, with R having
three strategies and C having two strategies:
C
C1 C2
r1 1 2
R r2 3 4
r3 7 5
Determine the value of the game, if it exists.
Solution
First, analyse R’s strategies by selecting the minimum entry from each row and write it on the right
of the matrix. Next, analyse C’s Strategies by finding the maximum entry in each column and write
it below the column. Then select the largest of the minima and the smallest of the maxima
C Row minima
r1 1 2 1
R r2 3 4 3
r3 7 5 5 Largest of Minima
Column 7 5
Maxima smallest of Maxima
Observe that the smallest of the column maxima and the largest of the row minima are the same
and both occur in the (3, 2) location. Thus, the game is strictly determine with value 5. The saddle
point (3, 2) and the strategies r3 for R and c2 for C form the solution.
When the players adopt these strategies, as they should, player R will receive 5 from player.

Example 4 Look at the analysis of the following two-person game:

c1 c2 c3 Row Minima
r1 3 4 11 3
r2 -5 2 -3 -5
r3 6 6 9 6 Max
Column 6 6 11
Maxima Min Min

3
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Each 6 in this matrix occurs at a saddle point, (3, 1) and (3, 2). The best strategy for R is r 3,
whereas C has the option of either strategy c1 or c2. In either case, the payoff is 6. When more than
1 saddle point occurs, the entries in the matrix at the saddle point are the same, being the value of
the game.
A game may have no saddle point, and thereby is not strictly determined. Here is an example to
illustrate this type of situation.
Example 5 Here is the payoff matrix of a two-person game:
C Row minima
c1 c2
R r1 3 -2 -2 Max
r2 -5 4 -5
Column 3 4
Maxima Min
For a game to be strictly determined, the largest of the row minima and the smallest of the column
maxima must be same and occur in the same location in the matrix. That does not occur in this
game because the largest of row minima is -2 and the smallest of the column maxima is 3, and
they appear in different locations. Thus, there is no saddle point.
Exercises.
Pay off matrices for two-person games are given below. Decide whether the games are strictly
determined. Find the saddle point, value and solution for each strictly determine gam
(1) -3 -5 (2) 1 2 3
2 -1 4 -5 1
2 6 3
(3) 2 0 1
0 -3 4
-3 -2 0

For the following payoff matrices, find the saddle points, values, and solutions , if they exists
4. -3 2 1 5. -1 2 3
0 2 3 4 -1 0
-1 -4 2 0 1 -1

6. 1 -2 1 7. -1 -2 3
5 7 3 5 0 2
-1 3 -4 4 -1 1
4
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Answers
(1) Strictly determined, the saddle point is (2, 2), value = -1 and the solution row 2 and column 2.
(2) Not strictly determined.
(3) Strictly determined, saddle point (2, 1), value = 0, and the solution row 1 and column 2.
(4) Strictly determined, the saddle point (2, 1), value = 0, solution row 2 column 1.
(5) Not strictly determined because the largest row minimum does not equal the smallest column
maximum.
(6) ) Strictly determined , saddle point (2,3), value = 3, and the solution row 2 and column 3.
(7) Strictly determined, saddle point (2, 2), value = 0, and the solution row 2 and column 2.

6.3 Games With Mixed Strategies

Consider a two-person zero-sum game given by the pay-off matrix below.
Player B
I II

Player A (
I −2 3
II 3 −4 )
Max { min }=−2

Min{max} = 3
Since max{min} ≠min{max}, then no saddle point. We should only consider a mixed
strategy.

Example 1 ( 2 x 2 game)

A and B play a zero-sum game which is represented by the following pay-off matrix for A.

B plays I B plays II

|
A plays I 4 −2
A plays II −5 3 |
a) Verify that A and B should play mixed strategies.
b) Determine the mixed strategy each player should adopt, and the value of the game
to each player.

Solution

B plays I B plays II Row minimum

a)
A plays I 4 −2
A plays II −5 3| −2
−5 |
Column maximum 4 3

Maximin = -2 and minimax = 3,

Since maximin ≠ minimax , hence no saddle point, therefore both player A and player B
5
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

could profit by using mixed strategy.

b) Let A plays strategy I with a probability p,

strategy II with a probability 1 - p,

If B plays strategy I , A’s expected gain : 4p - 5( 1 - p ) = 9p - 5

If B plays strategy II , A’s expected gain : - 2p + 3( 1 - p ) = 3 - 5p

Optimal strategy for player A when 9p – 5 = 3 – 5p

4
p=
7
4 3
Therefore, optimal Strategy for player A is ( , )
7 7

Let B plays row I with a probability q,

row II with a probability 1 - q,

If A plays column I , B’s expected gain : - 4q + 2( 1 - q ) = - 6q + 2

If B plays column II, A’s expected gain : 5q - 3( 1 - q) = - 3 + 8q

Optimal strategy for player B when - 6q + 2 = - 3 + 8q

5
q=
14
5 9
Therefore, optimal strategy for player B is ( , )
14 14

5 −1
The value of the game for B = - 6( ¿+2=
14 7

4 1
The value of the game for A = 3 - 5( ) =
7 7

**The sum of the values of the game to each player must be zero.

Alternative method:

pay−off ¿ (da bc )

6
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

3−−5 3−−2 4 (3 )−(−2 ) (−5 )

P = q= v=
( 4−−2 ) +(3−−5) ( 4−−2 ) +(3−−5) ( 4 — 2 ) +( 3 — 5 )
4 5 1
= = =
7 14 7

Example 2 ( 2 x 3 game)

Alvin and Peter play a zero-sum game, represented by the pay-off matrix below for Alvin.

Peter plays Peter plays II Peter plays III

I
Alvin plays I -5 2 -1
Alvin plays II 2 -3 1

Show that there is no play safe strategy for both Alvin and Peter.
Determine Alvin’s best strategy and the value of the game to him.

Solution

Peter plays Peter plays Peter plays III Row

I II minimum
Alvin plays I -5 2 -1 -5
Alvin plays II 2 -3 1 -3
Column 2 2 1
maximum

Maximin = - 3 and minimax = 1,

Since maximin ≠ minimax , there is no stable solution.

Alvin has only two choices so it will be possible to determine his strategy.

Let Alvin play strategy I with probability p and strategy II with probability 1-p

If Peter plays strategy I : Alvin’s expected gain = - 5p + 2( 1- p ) = 2 – 7p

If peter plays strategy II : Alvin’s expected gain = 2p - 3( 1- p ) = 5p - 3
If Peter plays strategy III : Alvin’s expected gain = - p + ( 1- p ) = 1 - 2p

Alvin’s expected gain

2
0 1-2p 4 5p-3
1
5 7
-2
Optimal solution
-4
5 2-7p

12
-6
p=0 p=1
7
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Look from the “ bottom up “ to find the highest point.( lower envelope)
Choose the intersection point that gives the highest minimum gains. ( maximin)

Optimal solution when 2 - 7p = 5p - 3

5
p=
12
5 −11
Value of the game = 2 - 7 ( ¿=
12 12

5 7
Best strategy/ optimal strategy for Alvin : ( , )
12 12

Example 3 ( 4 x 2 game )

The table show a pay-off matrix for player A and player B in a zero-sum game.

Player B
strategy I II
I -2 0
II 3 -1
Player A III -3 2
IV 5 -4

Use a grahical method to determine the optimal strategy for player B.

Solution

Suppose that Player B chooses strategy I with probability q and

strategy II with probability ( 1 – q ) :

Strategy of Player A Player B’s expected pay-off

I - 2q + (1 – q )( 0 ) = - 2q
II 3q + ( 1 – q )( -1 ) = 4q - 1
III - 3q + (1 – q )( 2 ) = - 5q + 2
IV 5q + ( 1 – q )( - 4 ) = 9q - 4

8
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

expected pay-off for Player B

5
9q-4

4q-1 3
q
2

q
0
1
-2q
-1 -2

-5q+2 -3

-4
q=0 q=1

Look from the “ top down “ to find the lowest point.( Upper envelope)
Choose the intersection point that gives the lowest maximum loss. ( minimax)
At P (Minimax),
-5q + 2 = 4q -1
1
q=
3

1 2
Optimal strategy for player B : ( , )
3 3
Exercise : Page

6.4 Strategy Dominance

Learning Outcomes :

- Use a dominance argument to reduce a pay-off matrix.

- Determine optimal mixed strategies for a game with no stable solution.
- Use a graphical method to solve a game, where appropriate

Dominated strategy : ( Reduction of a pay-off matrix by dominance arguments )

A dominated row is a row whose elements are _______________ than or

_______________ to the corresponding elements of any other row.

A dominated column is a column whose elements are _______________ than or

_______________ to the corresponding elements of any other column.

A dominated row or column will never be used and therefore can be __________________
to simplify the pay-off matrix.

Example 6.4.1
Reduce each of the following pay-off matrices using dominance arguments.
9
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

( )
−1 −5 9
(a) 3 1 −9 
7 −3 −6

( )
−1 2
(b) 0 1 
−2 2

( )
5 2 3
(c) 3 3 6 
4 −1 1

( )
−7 0 −3
(d) −1 4 1 
2 1 −3

Steps needed to solve a game theory problem :

Step 1. Check the saddle point

Player B

I II

Player A
I
 0 10  Max{min} = 1
II 1 2 
 
Min{max} = 1
Saddle point: 1
Pure strategy: (A – plays II, B – plays I)
Value of the game: v = 1

Step 2. If there is no saddle point, it is not a pure strategy game but a mixed
strategy game. Reduce the marix ( dominance )

10
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Step 3. Solving 2 x n and m x 2 game with the aid of graphical interpretation.

Step 4. Equalizing strategy ( use formula for 2 x 2 )

Equalizing strategies: ( Mixed strategy )

Player B
q 1-q

Player A
p  a b
1  p  d c 
Player A: (p,1-p) , Player B: (q,1-q)

cd cb
p q
 a  b   c  d  ,  a  b   c  d  ,
Value of the game is ,

v  pa  d (1  p )
 cd   (c  d ) 
 a   d 1  
 ( a  b )  (c  d )   ( a  b)  (c  d ) 
ac  bd

 a  b   c  d 

Example 6.4.2

The pay-off matrix below shows a two person zero-sum game, which played by John and
Linda. Find the optimal strategy by reduction of a pay-off matrix followed by
graphical method.

Linda
L1 L 2 L3

( )
J1 3 1 4
. John J 2 −1 2 5 .
J 3 3 −1 2

Step 1 :

Step 2 :
11
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Step 3 :

Step 4 :

Exercise : Page 213 Ex. 6.3 Q1 – Q4.

Page 215 Revision Exercise Q1 – Q7.

2013 STPM 950/3

6. Players P and Q play a game with the pay off matrix.

Q
I II III
P I -1 2 3
II 2 0 3
Determine the optimal strategy for each player. [ 6 marks ]

( )
2 3 2 3
{ ans : P , , Q( , , 0) }
5 5 5 5

2013 STPM 950/3 ( U )

5. The pay-off matrix od a game for players R and S is shown in the table below.
S
I II III
R I 4 3 1
II 0 1 2

Using a graphical method, determine the value of the game and the optimal mixed strategy
for each player. [ 9 marks ]
8
( ) (
2 3
5 5
1
5
4
{ ans : value of game = , R , , S , 0 , }
5 5 )
2014 STPM 950/3
6. Player P and Q each has two cards with different numbers which are black or red.
Player P has a black 4 and a red 3 while player Q has a black 1 and a red 6. They play a
zero-sum game.
Each player selects a card of his own. If the numbers are of the same colour, player P
scores the sum of the two numbers shown. If the numbers are of different colours, player Q
scores twice the smaller of the two numbers shown. Construct a pay off matrix for player P.
[ 3 marks ]
ans :

12
950/3 Mathematics M ( Management ) Paper 3 Chapter 6 Game Theory

Player Q
B1 R6
B4 5 -8
Player P
R3 -2 9

8. Two newly opened restaurants compete for the same customers. Restaurant A and
Restaurant B offer two and three meal sets respectively. The pay off matrix shows the
increase of customers for Restaurant A.
Restaurant B
B1 B2 B3
Restaurant A A1 -10 20 60
A2 90 -50 -60

(a) Show that there is no play safe strategy for both Restaurants A and B. [ 2 marks ]
(b) Using a graphical method, determine the optimal mixed strategy for Restaurant A.
[ 7 marks ]
(c) Find the optimal expected increase in customers for Restaurant A. [ 2 marks ]
(d) Determine the optimal mixed strategy for Restaurant B. [ 4 marks ]

{ ans : b} A : ( 1417 , 173 )c ¿ 130

17
= 7.65 @ 7.647 d ¿ B :¿ ,
10
17
,0)}

2014 STPM 950/3 ( U )

4. Players P and Q play a zero-sum game. The table shows the pay-off matrix for player P.
Player Q
Q1 Q2 Q3
Playe P1 3 1 -2
rP P2 0 2 -3
P3 2 3 1
Determine the play-safe strategy for each player and the value of the game. [ 5 marks ]

{ ans : Player P : Strategy P 3, Player Q : strategy Q 3 , value of the game = 1 }

13