Skip to content
Advertisements

DS/U3 Topic 4 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 A Player B
  B1 B2
A1 -2 4
A1 8 3
A1 9 0

Solution.

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

Player A   Player B Minimum Probability
B1 B2
A1 -2 4 -2 q1
A2 8 3 3 q2
A3 9 0 0 q3
Maximum 9 4    
Probability p1 p1    

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   I II III
I -3 -1 7
II 4 1 -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   I II
I -3 -1
II 4 1

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

(b)

  Player B
Player A   I II
I -3 7
II 4 -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   II III
I -1 7
II 1 -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   I II
I a b
II c d

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   I II
I 2 -1
II -1 1

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   I II
I 1 7
II 6 2

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

  cj 3 2 0 0 0  
cB Basic variables
B
x1 x2 x3 x4 x5 Solution values
b (= X
B)
0 x3 0 1 1 0 1 7
0 x4 0 5 0 1 -3 5
3 x1 1 -1 0 0 1 3
zj-cj   0 -5 0 0 3  

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

  cj 3 2 0 0 0  
cB Basic variables
B
x1 x2 x3 x4 x5 Solution values
b (= X
B)
0 x3 0 0 1 -1/5 8/5 6
2 x2 0 1 0 1/5 -3/5 1
3 x1 1 0 0 1/5 2/5 4
zj-cj   0 0 0 1 0  

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.

Advertisements
Advertisements
Advertisements

3 Comments »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: