LP and Game Theory
► Game: A competitive situation between two or more opponents
(usually referred to as players).
► Each player has several choices (called strategies).
► Often, a player selects his/her strategies without any knowledge
of the strategies adopted by other players.
► Two-person zero-sum game: In cases where the gain of one
player signifies an equal loss to the other.
► In a Two-person-Zero-sum game, the outcome of a game is
conventionally expressed in terms of the Payoffs to Player A.
LP and Game Theory
► Consider a coin-matching game involving two players
► Each player selects either head (H) or tail (T) and then tosses his/her coin.
► Assume that if the outcomes match (H and H or T and T), player A wins $1.00 from B.
► Otherwise, (H and T or T and H), player B wins $1.00 from A.
► This Two-Person Zero-Sum game yields the following (2x2) game matrix.
Player B
H T
H 1 -1
Player A
T -1 1
► Purpose of Game Theory is to deal with determination of ‘optimal’ strategies
Minimax (Maximin) Criterion
Player B Row
Strategy I II III IV Minimum
I 8 2 9 5 2
Player A II 6 5 7 8 5 Maximin
value
III 7 3 -4 7 -4
Column Maximum 8 5 9 8
Minimax value
Player A’s selection is called the Maximin strategy and the
corresponding gain is called maximin (or lower) value of the game.
Player B’s selection is called the Minimax strategy and his
corresponding gain Is called Minimax (or upper) value of the game
Minimax (Maximin) Criterion: Pure
Strategies
Selection made by A and B are based on the Minimax (Maximin) Criterion.
❖ A conservative attitude that guarantees the best of the worst results.
Player B Row
Strategy I II III IV Minimum
I 8 2 9 5 2
Maximin
Player A II 6 5 7 8 5
value
III 7 3 -4 7 -4
Column Maximum 8 5 9 8
Minimax value
When Minimax value = Maximin value, the game is said to have a Saddle Point
and in such cases, Pure Strategies are applied to secure ‘optimal’ solution.
Pure Strategy: Another Example
Player B
I II III IV Min
Pl I 8 -2 4 -3 -3
a II 6 5 7 8 5
y III -9
e
8
-2 54 7
-9 99
r MaxiMin
A
Saddle Point
Max MiniMax
Player A tries to maximize the minimum gain
Best of worst for each player
Player B tries to minimize A’s maximum gain
When Minimax value = Maximin value, a platform is
created to adopt pure strategies for ‘optimal’ plan of
action.
A game having a Saddle Point is given by the common
entry of the ‘optimal’ value of the game.
Neither player is tempted to change his/her strategy.
Otherwise, the opponent can counteract by selecting
another strategy which would yield a worse payoff.
❖ In absence of a saddle point in the Payoff
matrix, MIXED STRATEGIES come into play
as genuine option.
❖ In general, the value of the game must
satisfy the following inequality,
Maximin value ≤ Value of the game ≤ Minimax value
Mixed Strategies
In the game given below, Minimax value of 4 ≥ the Maximin value of 2.
Player B Row
Strategy I II III IV Minimum
I 5 -10 9 0 -10
Player A II 6 7 8 1 1
III 8 7 15 2 2 Maximin
value
IV 3 4 -1 4 -1
Column Maximum 8 7 15 4
Minimax value
❖ No saddle point.
❖ Cannot use the maximin-minimax criterion as their optimal strategies.
❖ Optimal solution lies in the use of mixed strategies.
❖ Each player may play all the available strategies as per predetermined ratios.
Game Theory
Dominance Property and its use
Player B
I II III
Pl I 2 1 4
a II 2 0 1
y
III -1 -2 0
er
A
Game Theory
Dominance Property
Player B
I II III
Pl I 2 1 4
a II 2 0 1
y
III -1 -2 0
er
A
Game
Value
Game Theory
Mixed Strategy
Player B
I II III Min
Pl I 0 -2 2 -2
a II 5 4 -3 -3
y III -4
e MaxiMin
52 55 2
-4
r
A MiniMax
Max No Saddle point exists
If A plays strategy I Then B plays strategy II
If B plays strategy II Then A plays strategy III
If A plays strategy III Then B plays strategy III
If B plays strategy III Then A plays strategy I
Game Theory
Mixed Strategy
Player B
Probabilit
I II Oddment
y
Pla I 5 -3 9 9/17
ye
rA II -4 5 8 8/17
Oddment 8 9 Strategy for A: [(9/17), (8/17)]
Probabilit
8/17 9/17 Strategy for B: [(8/17), (9/17)]
y
Game Value = 5*(9/17)+(-4)*(8/17) = 13/17 (for A) if B goes for Strategy I
Game Value = (-3)*(9/17)+5*(8/17) = 13/17 (for A) if B goes for Strategy II
Game Value = 5*(8/17)+(-3)*(9/17) = 13/17 (for B) if A goes for Strategy I
Game Value = (-4)*(8/17)+5*(9/17) = 13/17 (for B) if A goes for Strategy II
Graphical Solution of (2xn) and (mx2) Games
Player B
I II …… n Probability
Play
I a11 a12 ……. a1 n X
er A
II a21 a22 ……. a2 n 1-x
Probability y1 y2 ….…. yn
B’s Pure Strategy A’s Expected Payoff
1 (a11 – a21) x + a21
2 (a12 – a22) x + a22
. .
. .
n
(a1n – a2n) x + a2n
Game Theory
Mixed Strategy [2 X 4]
Player B
I II III IV Min
Pl I 2 2 3 -1 -1
ay
er 2
II 4 3 2 6
A 6
3 3
Max 4
MaxiMin
MiniMax
No Saddle point exists
Graphical Solution of (2x4) Game
Player B
I II III IV Probability
Pla I 2 2 3 -1 x
yer
A II 4 3 2 6 1-x
Probability y1 y2 y3 y4
B’s Pure Strategy A’s Expected Payoff
I (a11 – a21) x1+ a21 = (2 - 4) x + 4 = -2x + 4
II (a12 – a22) x1+ a22 = (2 - 3) x + 3 = - x + 3
III (a13 – a23) x1+ a23 = (3 - 2) x + 2 = x + 2
IV (a14 – a24) x1+ a24 = (-1 - 6) x + 6 = -7x + 6
Mixed Strategy
IV
6 6
MaxiMin
I
4 4
II
2 2
III
0 0
-1 -1
X=0 X=1
Value of x corresponding to Maximin = ½
Game Value or A’s Payoff
Game Value or Payoff for Player A
(2-3) x + 3 = - x + 3 = - ½ + 3 = 2½
Game Value = (3-2) x + 2 = x + 2 = ½ + 2 = 2½
(-1-6)x + 6 = -7x + 6 = (-7)½ + 6 = 2½
Since there is no saddle point in the Payoff
matrix, MIXED STRATEGY becomes the only
option for choice. However, if there is a
scope to reduce the size of the problem, you
can apply ‘Dominance Property’.
Critically examine whether Player B would
be interested to go for strategy I.
The same [2x4] problem: Mixed Strategy
Apply Dominance Property
Player B
I II III IV Min
Pl I 2 2 3 -1 -1
ay
er 2
II 4 3 2 6
A 6
3 3
Max
MaxiMin
MiniMax
No Saddle point exists
Mixed Strategy
Player B
Pl II III IV Probability
ay
er I 2 3 -1 x
A
II 3 2 6 1-x
Player A
For Strategy II of Player B => 2x+3(1-x) = -x+3
For Strategy III of Player B => 3x+2(1-x) = x +2
For Strategy IV of Player B => -1x+6(1-x) = -7x +6
Mixed Strategy
IV
6
MaxiMin
4
II
2
III
X=0 X=1
Player B
II III Oddment Probability
Pla I 2 3 1 ½
yer
A II 3 2 1 ½
Oddment 1 1
Probability
½ ½
Strategy for A: [(1/2), (1/2)]
Strategy for B: [0, (1/2), (1/2), 0]
Game Value (for A) = 2*(1/2) + 3*(1/2) = 2½
Game Value (for B) = 2*(1/2) + 3*(1/2) = 2½
Game Theory
Player B
III IV Oddment Probability
I 3 -1 4 1/2
Play
er A II 2 6 4 1/2
Oddment 7 1
Probability 7/8 1/8
Strategy for A: [(1/2), (1/2)]
Strategy for B: [0, 0, (7/8), (1/8)]
Game Value = 3*(1/2) + 2*(1/2) = 2.5 (for A)
Game Value = 3*(7/8) + (-1)*(1/8) = 2.5 (for B)
Game Theory
Mixed Strategy [4 X 2]
Player B
I II Min
I 6 -7 -7
Pl
ay II 1 3 1
er MaxiMin
III 3 1 1
A
IV 5 -1 -1
Max 6 3
MiniMax
No Saddle point exists
Game Theory
Mixed Strategy
Player B
I II
Player B
I 6 -7 6y-7(1-y) = 13y-7
Playe II 1 3 y+3(1-y) = -2y+3
rA III 3 1 3y+1(1-y) = 2y+1
IV 5 -1 5y-1(1-y) = 6y-1
Probability y 1-y
Mixed Strategy
MiniMax
6 6
4 II 4
2 III 2
IV -2
-2
-4 -4
-6 -6
-8 I -8
y=0 y=1
Game Theory
Player B
I II Oddment Probability
II 1 3 2 1/2
Play
er A III 3 1 2 1/2
Oddment 2 2
Probability 1/2 1/2
Strategy for B: [(1/2), (1/2)]
Strategy for A: [0, (1/2), (1/2), 0]
Game Value = 1*(1/2) + 3*(1/2) = 2 (for A)
Game Value = 1*(1/2) + 3*(1/2) = 2 (for B)
Game Theory
Mixed Strategy
MiniMax
6 6
4 II 4
2 III 2
IV -2
-2
-4 -4
-6 -6
-8 I -8
y=0 y=1
Game Theory: Another Example
Player B
I II Oddment Probability
II 1 3 6 3/4
Play
er A IV 5 -1 2 1/4
Oddment 4 4
Probability 1/2 1/2
Strategy for B: [(1/2), (1/2)]
Strategy for A: [0, (3/4), 0, (1/4)]
Game Value = 1*(3/4) + 5*(1/4) = 2 (for A)
Game Value = 1*(1/2) + 3*(1/2) = 2 (for B)
