Linear programming solution of

games

1
Example
B 𝐵1 𝐵2 𝐵3
A
𝐴1 40 30 60 B 𝐵1 𝐵2 𝐵3 𝐵4
𝐴2 60 50 80 A
𝐴3 70 10 50 𝐴1 40 30 60 65
𝐴2 60 50 80 5
𝐴3 70 10 50 40
B 𝐵1 𝐵2 𝐵3
A
𝐴1 40 30 60
𝐴2 60 50 80
𝐴3 70 10 50
𝐴4 65 5 40
2
 Linear programming solution of games
Consider the following payoff matrix of a two person
zero sum game :
B 𝐵1 𝐵2 … 𝐵𝑚
A
𝐴1 𝑎11 𝑎12 … 𝑎1𝑚
𝐴2 𝑎21 𝑎22 … 𝑎2𝑚
. . . .
. 𝑎𝑖𝑗 ; i=1,2, ..n, j=1,2, ..m
. . . .
𝐴𝑛 𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑚

3
 Linear programming solution of games
Player A will use a mixture of his strategies with respective
probabilities xi ; i=1,2, ..n, and player B will use a mixture
of his strategies Bj , with probabilities yj; j=1,2, ..m,
Probability y1 y2 … ym
Probability B 𝐵1 𝐵2 … 𝐵𝑚
A
x1 𝐴1 𝑎11 𝑎12 … 𝑎1𝑚
x2 𝐴2 𝑎21 𝑎22 … 𝑎2𝑚
. . . . .
. . . . .
xn 𝐴𝑛 𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑚
4
For player A:
𝐸 𝐴 𝐵1 = σ𝑛𝑖=1 𝑎𝑖1 𝑥𝑖
𝐸 𝐴 𝐵2 = σ𝑛𝑖=1 𝑎𝑖2 𝑥𝑖
. . . .
. . . .
𝑛
σ
𝐸 𝐴 𝐵𝑚 = 𝑖=1 𝑎𝑖𝑚 𝑥𝑖
In general:
𝑛
σ
𝐸 𝐴 𝐵𝑗 = 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ; j= 1, 2, …, m
Where, σ𝑛𝑖=1 𝑥𝑖 = 1

5
 For player A:
• Player A will choose the value of 𝑥𝑖 ; i= 1, 2, …, n
that maximizes the minimum expected profits.
So, player A’s optimal probabilities can be determined
by solving the following maximin problem:
Find 𝑥𝑖 ; i= 1, 2, …, n that
max {min (σ𝑛𝑖=1 𝑎𝑖1 𝑥𝑖 , σ𝑛𝑖=1 𝑎𝑖2 𝑥𝑖 , ... , σ𝑛𝑖=1 𝑎𝑖𝑚 𝑥𝑖 )},
s.t.
σ𝑛𝑖=1 𝑥𝑖 = 1, This model does
𝑥𝑖 ≥ 0; i= 1, 2, …, n not a linear
programming
model
6
For player A:
Let
𝑣 = min ( σ𝑛𝑖=1 𝑎𝑖1 𝑥𝑖 , σ𝑛𝑖=1 𝑎𝑖2 𝑥𝑖 , … , σ𝑛𝑖=1 𝑎𝑖𝑚 𝑥𝑖 )

The equation implies that:

σ𝑛𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≥ 𝑣 ; j= 1, 2, …, m

Therefore,

𝑣 - σ𝑛𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≤ 0 ; j= 1, 2, …, m

7
Player A’s problem can be written as:

Find 𝑥𝑖 ; i= 1, 2, …, n, and 𝑣 that

max 𝑍 = 𝑣, This model is a linear
programming model
s.t.
𝑛
σ
𝑣 - 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≤ 0 ; j= 1, 2, …, m
σ𝑛𝑖=1 𝑥𝑖 = 1,
𝑥𝑖 ≥ 0; i= 1, 2, …, n
𝑣 is unrestricted in sign
Note that the value of the game, 𝑣, is unrestricted
in sign.
8
For player B:
𝐸 𝐵 𝐴1 = σ𝑚
𝑗=1 𝑎1𝑗 𝑦𝑗
𝐸 𝐵 𝐴2 = σ𝑚
𝑗=1 𝑎2𝑗 𝑦𝑗
. . . .
. . . .
𝐸 𝐵 𝐴𝑛 = σ𝑚
𝑗=1 𝑎𝑛𝑗 𝑦𝑗
In general:
𝑚
σ
𝐸 𝐵 𝐴𝑖 = 𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ; i= 1, 2, …, n
Where, σ𝑚
𝑗=1 𝑦𝑗 = 1
9
 For player B:
• Player B will choose the value of 𝑦𝑗 ; j= 1, 2, …, m
that minimizes the maximum expected loss.
So, Player B’s optimal probabilities can be determined
by solving the following minimax problem:

Find 𝑦𝑗 ; j= 1, 2, …, m that
𝑚 𝑚 𝑚
σ σ σ
min { max( 𝑗=1 𝑎1𝑗 𝑦𝑗 , 𝑗=1 𝑎2𝑗 𝑦𝑗 , .. , 𝑗=1 𝑎𝑛𝑗 𝑦𝑗 )},
s.t.
σ𝑚
𝑗=1 𝑦𝑗 = 1,
𝑦𝑗 ≥ 0; j= 1, 2, …, m
10
For player B:
Let
𝑣 = max ( σ𝑚 𝑎 𝑦
𝑗=1 1𝑗 𝑗 , σ𝑚
𝑎 𝑦
𝑗=1 2𝑗 𝑗 , .. , σ𝑚
𝑗=1 𝑎𝑛𝑗 𝑦𝑗 )

The equation implies that:

σ𝑚
𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ≤ 𝑣 ; i= 1, 2, …, n

Therefore,

𝑣 -σ𝑚
𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ≥ 0 ; i= 1, 2, …, n

11
Player B’s problem can be written as:

Find 𝑦𝑗 ; j= 1, 2, …, m, and 𝑣 that

min 𝑤 = 𝑣,
s.t.
𝑣 -σ𝑚
𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ≥ 0 ; i= 1, 2, …, n
σ𝑚
𝑗=1 𝑦𝑗 = 1,
𝑦𝑗 ≥ 0; j= 1, 2, …, m
𝑣 is unrestricted in sign

12
The two problems optimize the same
(unrestricted) variable v, the value of the game.
The reason is that B’s problem is the dual of A’s
problem. This means that the optimal solution
of one problem automatically yields the optimal
solution of the other.

13
 Example 1
Construct LP to solve the following game
Y1 Y2 Y3
X1 3 −1 −3
X2 −2 4 −1
X3 −5 −6 2

𝐸 𝐴 𝐵1 = 3𝑥1 - 2𝑥2 - 5𝑥3

𝐸 𝐴 𝐵2 = −𝑥1 + 4𝑥2 - 6𝑥3
𝐸 𝐴 𝐵3 = −3𝑥1 - 𝑥2 + 2𝑥3
𝐸 𝐵 𝐴1 = 3𝑦1 − 𝑦2 − 3𝑦3
𝐸 𝐵 𝐴2 = −2𝑦1 + 4𝑦2 − 𝑦3
𝐸 𝐵 𝐴3 = −5𝑦1 − 6𝑦2 + 2𝑦3 14
• The player A’s LP model is:
Find 𝑥𝑖 ; i= 1, 2, 3, and 𝑣 that
max 𝑍 = 𝑣,
s.t.
𝑣 -3𝑥1 + 2𝑥2 + 5𝑥3 ≤ 0 ,
𝑣 +𝑥1 - 4𝑥2 + 6𝑥3 ≤ 0 ,
𝑣 +3𝑥1 + 𝑥2 - 2𝑥3 ≤ 0 ,
𝑥1 + 𝑥2 + 𝑥3 = 1
𝑥𝑖 ≥ 0; i= 1, 2, …, n
𝑣 is unrestricted in sign
15
Player A

16
• The player A’s LP model is:

Find 𝑥𝑖 ; i= 1, 2, 3, and 𝑣 that

The optimum solution is

𝑥1 = 0.39,
𝑥2 = 0.31,
𝑥3 = 0.29,
and 𝑣 = -0.91

17
• The player B’s LP model is:
Find 𝑦𝑗 ; j= 1, 2, 3, and 𝑣 that
min 𝑤 = 𝑣,
s.t.
𝑣 -3𝑦1 + 𝑦2 + 3𝑦3 ≥ 0 ,
𝑣 +2𝑦1 − 4𝑦2 + 𝑦3 ≥ 0 ,
𝑣 +5𝑦1 + 6𝑦2 − 2𝑦3 ≥ 0 ,
𝑦1 + 𝑦2 + 𝑦3 = 1
𝑦𝑗 ≥ 0; j= 1, 2, …, m
𝑣 is unrestricted in sign
18
 Player B

y1 y2 y3 s’1 s’2 s’3 Sol.

w 0 0 0 -0.39 -0.31 -0.29 -0.91
y3 0 0 1 -0.06 -0.03 0.09 0.6
y1 1 0 0 0.12 -0.09 -0.03 0.32
y2 0 1 0 -0.06 0.12 -0.06 0.08

19
• The player B’s LP model is:

Find 𝑦𝑗 ; j= 1, 2, 3, and 𝑣 that

The optimal solution is

𝑦1 = 0.32,
𝑦2 = 0.08,
𝑦3 = 0.60,
and 𝑣 = -0.91

20
 Example 2
If the following is the final simplex table of the 3x3
matrix :

𝑣 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑠3 Sol
𝑧 0 0 8.17 0 0.91 0.09 0 9.17
𝑥3 0 0 0.83 1 -0.02 0.02 0 0.83
𝑠3 0 0 8.4 0 -0.17 -0.83 1 7.5
𝑥1 0 1 0.17 0 0.02 -0.02 0 0.17

21
Example 2

1- The probability that A will use 𝐴1 is :

a) 0 b) 1/6 c) 5/6 d)none
2- The probability that A will use 𝐴2 is :
a) 0 b) 1/6 c) 5/6 d)none
3- The probability that A will use 𝐴3 is :
a) 0 b) 1/6 c) 5/6 d)none

22
Example 2

4- The probability that B will use 𝐵1 is :

a) 0 b) 5/54 c)49/54 d)none
5- The probability that B will use 𝐵2 is :
a) 0 b) 5/54 c) 49/54 d)none
6- The probability that B will use 𝐵3 is :
a) 0 b) 5/54 c) 49/54 d)none
7- The value of the game is :
a) 0 b) 55/6 c) 49/54 d)b and c

23
 Notes:

1- Every two-person zero-sum game can be represented by

a pair of primal-dual linear programs.

2- The addition of a constant to all the elements of a payoff

matrix in a two-person zero-sum game can affect only the
value of the game, not the optimal mix of strategies.

3- In game theory, dual is employed by column player who

wishes to minimize his maximum loss while his opponent
(i.e. row player) applies primal to maximize his minimum
gains. However, if one problem is solved, the solution for
other also can be obtained from the simplex tableau
24
 Write the payoff matrix Apply minimax- maxmini principle

Identify the value of game and write Yes Is there a

the optimal strategy of the players saddle point ?

No
Yes
Solve by using algebraic method for mixed Is it 2x2 payoff
strategic game matrix?

Yes No

Is it reduced to Use dominance rule to reduce the

2x2 size? size of payoff matrix
No
Yes No
Use graphical method to Is it 2xm or nx2 Formulate and solve as an
solve the problem payoff matrix? LP problem

25