Skip to content

Solution of Game Theory Problems with the Help of Graphical, Algebraic, and Simplex Methods

This method can only be used in games with no saddle point, and having a pay-off matrix of type n X 2 or 2 X n.

Example: Graphical Method for Game Theory

Consider the following pay-off matrix

Player APlayer B
 B1B2
A1-24
A183
A190

Solution.

The game does not have a saddle point as shown in the following table.

Player A Player BMinimumProbability
B1B2
A1-24-2q1
A2833q2
A3900q3
Maximum94  
Probabilityp1p1  

Maximin = 4, Minimax = 3

First, we draw two parallel lines 1 unit distance apart and mark a scale on each. The two parallel lines represent strategies of player B. 
If player A selects strategy A1, player B can win –2 (i.e., loose 2 units) or 4 units depending on B’s selection of strategies. The value -2 is plotted along the vertical axis under strategy B1 and the value 4 is plotted along the vertical axis under strategy B2. A straight line joining the two points is then drawn.
Similarly, we can plot strategies A2 and A3 also. The problem is graphed in the following figure.

The lowest point V in the shaded region indicates the value of game. From the above figure, the value of the game is 3.4 units. Likewise, we can draw a graph for player B.

The point of optimal solution (i.e., maximin point) occurs at the intersection of two lines:

E1 = -2p1 + 4p2 and
E2 = 8p1 + 3p2

Comparing the above two equations, we have

-2p1 + 4p2 = 8p1 + 3p2 

Substituting p2 = 1 – p1
-2p1 + 4(1 – p1) = 8p1 + 3(1 – p1)

p1 = 1/11
p2 = 10/11

Substituting the values of p1 and p2 in equation E1

V = -2 (1/11) + 4 (10/11) = 3.4 units

 

Game Theory: 2 x n Games

Games where one player has only two courses of action while the other has more than two, are called 2 X n or n X 2 games.

If these games do not have a saddle point or are reducible by the dominance method, then before solving these games we write all 2 X 2 sub-games and determine the value of each 2 X 2 sub-game.

This method is illustrated by the following example.

 Example: 2 x n Games

Determine the solution of game for the pay-off matrix given below:

 Player B
Player A IIIIII
I-3-17
II41-2

Solution.

Obviously, there is no saddle point and also no course of action dominates the other. Therefore, we consider each 2 X 2 sub-game and obtain their values.

(a)

 Player B
Player A III
I-3-1
II41

The saddle point is 1. So the value of game, V1 is 1.

(b)

 Player B
Player A III
I-37
II4-2

This game has no saddle point, so we use the algebraic method.

Value of game, V2 =(-3) X (-2) – (7 X 4)
————————-
(-3 – 2) – (7 + 4)
=11

8

(c)

 Player B
Player A IIIII
I-17
II1-2

This game has no saddle point, so we use the algebraic method.

Value of game, V3 =(-1) X (-2) – (7 X 1)
———————–
(-1 – 2) – (7 + 1)
=5

11

The 2 X 2 sub-game with the lowest value is (c) and hence the solution to this game provides the solution to the larger game.

Using algebraic method:

A plays ( 3/11, 8/11) 
B plays (0, 9/11, 2/11)
Value of game is 5/11.

Algebraic Method: Game Theory       

In this section, we will talk about the algebraic method used to solve mixed strategy games. Here we have provided formulas and examples of algebraic method.

Consider the zero sum two person game given below:

 Player B
Player A III
Iab
IIcd

Formulas: Algebraic Method

The solution of the game is:

A play’s (p, 1 – p) 

where:

p =d – c
——————–
(a + d) – (b + c)

B play’s (q, 1 – q)

where:

q =d – b
——————-
(a + d) – (b + c)

 

Value of the game, V =ad – bc
——————–
(a + d) – (b + c)

 Algebraic Method Example 1: Game Theory

Consider the game of matching coins. Two players, A & B, put down a coin. If coins match (i.e., both are heads or both are tails) A gets rewarded, otherwise B. However, matching on heads gives a double premium. Obtain the best strategies for both players and the value of the game.

 Player B
Player A III
I2-1
II-11

Solution.

This game has no saddle point.

p =1 – (-1)
———————–
(2 + 1) – (-1 – 1)
=2
—-
5

1 – p = 3/5

q =1 – (-1)
———————–
(2 + 1) – (-1 – 1)
=2
—-
5

1 – q = 3/5

V =2 X 1 – (-1) X (-1)
————————– 
(2 + 1) – (-1 – 1)
=1
—-
5

Example 2: Algebraic Method in Game Theory

Solve the game whose payoff matrix is given below:

 Player B
Player A III
I17
II62

Solution.

This game has no saddle point.

p =2 – 6
———————–
(1 + 2) – (7 + 6)
=2
—-
5

1 – p = 3/5

q =2 – 7
———————–
(1 + 2) – (7 + 6)
=1
—-
2

1 – q = 1/2

 

V =1 X 2 – (7 X 6)
————————– 
(1 + 2) – (7 + 6)
=4

 

Simplex Method: Example 1

Maximize z = 3x1 + 2x2

subject to

-x1 + 2x2 ≤ 4
3x1 + 2x≤ 14
x1 – x2 ≤ 3

x1, x2 ≥ 0

Solution.

First, convert every inequality constraints in the LPP into an equality constraint, so that the problem can be written in a standard from. This can be accomplished by adding a slack variable to each constraint. Slack variables are always added to the less than type constraints.

Converting inequalities to equalities

-x1 + 2x2 + x3 = 4
3x1 + 2x2 + x4 = 14
x1 – x2 + x5 = 3
x1, x2, x3, x4, x5 ≥ 0

Where x3, x4 and x5 are slack variables.

Since slack variables represent unused resources, their contribution in the objective function is zero. Including these slack variables in the objective function, we get

Maximize z = 3x1 + 2x2 + 0x3 + 0x4 + 0x5

Initial basic feasible solution

Now we assume that nothing can be produced. Therefore, the values of the decision variables are zero.
x1 = 0, x2 = 0, z = 0

When we are not producing anything, obviously we are left with unused capacity
x3 = 4, x4 = 14, x5 = 3

We note that the current solution has three variables (slack variables x3, x4 and x5) with non-zero solution values and two variables (decision variables x1 and x2) with zero values. Variables with non-zero values are called basic variables. Variables with zero values are called non-basic variables.

Simplex Method: Table 1

a11 = -1, a12 = 2, a13 = 1, a14 = 0, a15 = 0, b1 = 4
a21 = 3, a22 = 2, a23 = 0, a24 = 1, a25 = 0, b2 = 14
a31= 1, a32 = -1, a33 = 0, a34 = 0, a35 = 1, b= 3

Calculating values for the index row (z– cj)

z– c1 = (0 X (-1) + 0 X 3 + 0 X 1) – 3 = -3
z– c2 = (0 X 2 + 0 X 2 + 0 X (-1)) – 2 = -2
z– c3 = (0 X 1 + 0 X 0 + 0 X 0) – 0 = 0
z– c4 = (0 X 0 + 0 X 1 + 0 X 0) – 0 = 0
z– c5 = (0 X 0 + 0 X 0 + 0 X 1) – 0 = 0

Choose the smallest negative value from zj – c(i.e., – 3). So column under x1 is the key column.
Now find out the minimum positive value
Minimum (14/3, 3/1) = 3
So row x5 is the key row.
Here, the pivot (key) element = 1 (the value at the point of intersection).
Therefore, x5 departs and xenters.

We obtain the elements of the next table using the following rules:

  1. If the values of z– cjare positive, the inclusion of any basic variable will not increase the value of the objective function. Hence, the present solution maximizes the objective function. If there are more than one negative values, we choose the variable as a basic variable corresponding to which the value of z– cjis least (most negative) as this will maximize the profit.
  2. The numbers in the replacing row may be obtained by dividing the key row elements by the pivot element and the numbers in the other two rows may be calculated by using the formula:
 New number=old number-(corresponding no. of key row) X (corresponding no. of key column)
  pivot element

Calculating values for table 2

x3 row

a11 = -1 – 1 X ((-1)/1) = 0
a12 = 2 – (-1) X ((-1)/1) = 1
a13 = 1 – 0 X ((-1)/1) = 1
a14 = 0 – 0 X ((-1)/1) = 0
a15 = 0 – 1 X ((-1)/1) = 1
b1 = 4 – 3 X ((-1)/1) = 7

x4 row

a21 = 3 – 1 X (3/1) = 0
a22 = 2 – (-1) X (3/1) = 5
a23 = 0 – 0 X (3/1) = 0
a24 = 1 – 0 X (3/1) = 1
a25 = 0 – 1 X (3/1) = -3
b2 = 14 – 3 X (3/1) = 5

x1 row

a31 = 1/1 = 1
a32 = -1/1 = -1
a33 = 0/1 = 0
a34 = 0/1 = 0
a35 = 1/1 = 1
b3 = 3/1 = 3

Table 2

 cj32000 
cBBasic variables
B
x1x2x3x4x5Solution values
b (= X
B)
0x3011017
0x40501-35
3x11-10013
zj-cj 0-5003 

Calculating values for the index row (z– cj)

z– c1 = (0 X 0 + 0 X 0 + 3 X 1) – 3 = 0
z– c2 = (0 X 1 + 0 X 5 + 3 X (-1)) – 2 = -5
z– c3 = (0 X 1 + 0 X 0 + 3 X 0) – 0 = 0
z– c4 = (0 X 0 + 0 X 1 + 3 X 0) – 0 = 0
z– c5 = (0 X 1 + 0 X (-3) + 3 X 1) – 0 = 3

Key column = xcolumn
Minimum (7/1, 5/5) = 1
Key row = x4 row 
Pivot element = 5
x4 departs and xenters.

Calculating values for table 3

x3 row

a11 = 0 – 0 X (1/5) = 0
a12 = 1 – 5 X (1/5) = 0
a13 = 1 – 0 X (1/5) = 1
a14 = 0 – 1 X (1/5) = -1/5
a15 = 1 – (-3) X (1/5) = 8/5
b1 = 7 – 5 X (1/5) = 6

x2 row

a21 = 0/5 = 0
a22 = 5/5 = 1
a23 = 0/5 = 0
a24 = 1/5
a25 = -3/5
b2 = 5/5 = 1

x1 row

a31 = 1 – 0 X (-1/5) = 1
a32 = -1 – 5 X (-1/5) = 0
a33 = 0 – 0 X (-1/5) = 0
a34 = 0 – 1 X (-1/5) = 1/5
a35 = 1 – (-3) X (-1/5) = 2/5
b3 = 3 – 5 X (-1/5) = 4

Don’t convert the fractions into decimals, because many fractions cancel out during the process while the conversion into decimals will cause unnecessary complications.

Simplex Method: Final Optimal Table

 cj32000 
cBBasic variables
B
x1x2x3x4x5Solution values
b (= X
B)
0x3001-1/58/56
2x20101/5-3/51
3x11001/52/54
zj-cj 00010 

Since all the values of zj – cj are positive, this is the optimal solution.
x= 4, x2 = 1
z = 3 X 4 + 2 X 1 = 14.

The largest profit of Rs.14 is obtained, when 1 unit of x2 and 4 units of x1 are produced. The above solution also indicates that 6 units are still unutilized, as shown by the slack variable x3 in the XBcolumn.

3 Comments »

Leave a Reply

error: Content is protected !!
%d bloggers like this: