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 | ||
B_{1} | B_{2} | ||
A_{1} | -2 | 4 | |
A_{1} | 8 | 3 | |
A_{1} | 9 | 0 |
Solution.
The game does not have a saddle point as shown in the following table.
Player A | Player B | Minimum | Probability | ||
B_{1} | B_{2} | ||||
A_{1} | -2 | 4 | -2 | q_{1} | |
A_{2} | 8 | 3 | 3 | q_{2} | |
A_{3} | 9 | 0 | 0 | q_{3} | |
Maximum | 9 | 4 | |||
Probability | p_{1} | p_{1} |
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 B_{1} and the value 4 is plotted along the vertical axis under strategy B_{2}. A straight line joining the two points is then drawn.
Similarly, we can plot strategies A_{2} and A_{3} 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 = -2p_{1} + 4p_{2} and
E2 = 8p_{1} + 3p_{2}
Comparing the above two equations, we have
-2p_{1} + 4p_{2} = 8p_{1} + 3p_{2}
Substituting p_{2} = 1 – p_{1}-2p_{1} + 4(1 – p_{1}) = 8p_{1} + 3(1 – p_{1})
p_{1} = 1/11
p_{2} = 10/11
Substituting the values of p_{1} and p_{2} 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 = 3x_{1} + 2x_{2}
subject to
-x_{1} + 2x_{2} ≤ 4
3x_{1} + 2x_{2 }≤ 14
x_{1} – x_{2} ≤ 3
x_{1}, x_{2} ≥ 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
-x_{1} + 2x_{2} + x_{3} = 4
3x_{1} + 2x_{2} + x_{4} = 14
x_{1} – x_{2} + x_{5} = 3
x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ≥ 0
Where x_{3}, x_{4} and x_{5} 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 = 3x_{1} + 2x_{2} + 0x_{3} + 0x_{4} + 0x_{5}
Initial basic feasible solution
Now we assume that nothing can be produced. Therefore, the values of the decision variables are zero.
x_{1} = 0, x_{2} = 0, z = 0
When we are not producing anything, obviously we are left with unused capacity
x_{3} = 4, x_{4} = 14, x_{5} = 3
We note that the current solution has three variables (slack variables x_{3}, x_{4} and x_{5}) with non-zero solution values and two variables (decision variables x_{1} and x_{2}) 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
a_{11} = -1, a_{12} = 2, a_{13} = 1, a_{14} = 0, a_{15} = 0, b_{1} = 4
a_{21} = 3, a_{22} = 2, a_{23} = 0, a_{24 }= 1, a_{25} = 0, b_{2} = 14
a_{31}= 1, a_{32} = -1, a_{33} = 0, a_{34} = 0, a_{35} = 1, b_{3 }= 3
Calculating values for the index row (z_{j }– c_{j})
z_{1 }– c_{1} = (0 X (-1) + 0 X 3 + 0 X 1) – 3 = -3
z_{2 }– c_{2} = (0 X 2 + 0 X 2 + 0 X (-1)) – 2 = -2
z_{3 }– c_{3} = (0 X 1 + 0 X 0 + 0 X 0) – 0 = 0
z_{4 }– c_{4} = (0 X 0 + 0 X 1 + 0 X 0) – 0 = 0
z_{5 }– c_{5} = (0 X 0 + 0 X 0 + 0 X 1) – 0 = 0
Choose the smallest negative value from z_{j} – c_{j }(i.e., – 3). So column under x_{1} is the key column.
Now find out the minimum positive value
Minimum (14/3, 3/1) = 3
So row x_{5} is the key row.
Here, the pivot (key) element = 1 (the value at the point of intersection).
Therefore, x_{5} departs and x_{1 }enters.
We obtain the elements of the next table using the following rules:
- If the values of z_{j }– c_{j}are 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_{j }– c_{j}is least (most negative) as this will maximize the profit.
- 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
x_{3} row
a_{11} = -1 – 1 X ((-1)/1) = 0
a_{12} = 2 – (-1) X ((-1)/1) = 1
a_{13} = 1 – 0 X ((-1)/1) = 1
a_{14} = 0 – 0 X ((-1)/1) = 0
a_{15} = 0 – 1 X ((-1)/1) = 1
b_{1} = 4 – 3 X ((-1)/1) = 7
x_{4} row
a_{21} = 3 – 1 X (3/1) = 0
a_{22} = 2 – (-1) X (3/1) = 5
a_{23} = 0 – 0 X (3/1) = 0
a_{24} = 1 – 0 X (3/1) = 1
a_{25} = 0 – 1 X (3/1) = -3
b_{2} = 14 – 3 X (3/1) = 5
x_{1} row
a_{31} = 1/1 = 1
a_{32} = -1/1 = -1
a_{33} = 0/1 = 0
a_{34} = 0/1 = 0
a_{35} = 1/1 = 1
b_{3} = 3/1 = 3
Table 2
c_{j} | 3 | 2 | 0 | 0 | 0 | ||
c_{B} | Basic variables B |
x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | Solution values b (= X_{B}) |
0 | x_{3} | 0 | 1 | 1 | 0 | 1 | 7 |
0 | x_{4} | 0 | 5 | 0 | 1 | -3 | 5 |
3 | x_{1} | 1 | -1 | 0 | 0 | 1 | 3 |
z_{j}-c_{j} | 0 | -5 | 0 | 0 | 3 |
Calculating values for the index row (z_{j }– c_{j})
z_{1 }– c_{1} = (0 X 0 + 0 X 0 + 3 X 1) – 3 = 0
z_{2 }– c_{2} = (0 X 1 + 0 X 5 + 3 X (-1)) – 2 = -5
z_{3 }– c_{3} = (0 X 1 + 0 X 0 + 3 X 0) – 0 = 0
z_{4 }– c_{4} = (0 X 0 + 0 X 1 + 3 X 0) – 0 = 0
z_{5 }– c_{5} = (0 X 1 + 0 X (-3) + 3 X 1) – 0 = 3
Key column = x_{2 }column
Minimum (7/1, 5/5) = 1
Key row = x_{4} row
Pivot element = 5
x_{4} departs and x_{2 }enters.
Calculating values for table 3
x_{3} row
a_{11} = 0 – 0 X (1/5) = 0
a_{12} = 1 – 5 X (1/5) = 0
a_{13 }= 1 – 0 X (1/5) = 1
a_{14} = 0 – 1 X (1/5) = -1/5
a_{15} = 1 – (-3) X (1/5) = 8/5
b_{1} = 7 – 5 X (1/5) = 6
x_{2} row
a_{21} = 0/5 = 0
a_{22} = 5/5 = 1
a_{23} = 0/5 = 0
a_{24} = 1/5
a_{25} = -3/5
b_{2} = 5/5 = 1
x_{1} row
a_{31} = 1 – 0 X (-1/5) = 1
a_{32} = -1 – 5 X (-1/5) = 0
a_{33} = 0 – 0 X (-1/5) = 0
a_{34} = 0 – 1 X (-1/5) = 1/5
a_{35} = 1 – (-3) X (-1/5) = 2/5
b_{3} = 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
c_{j} | 3 | 2 | 0 | 0 | 0 | ||
c_{B} | Basic variables B |
x_{1} | x_{2} | x_{3} | x_{4} | x_{5} | Solution values b (= X_{B}) |
0 | x_{3} | 0 | 0 | 1 | -1/5 | 8/5 | 6 |
2 | x_{2} | 0 | 1 | 0 | 1/5 | -3/5 | 1 |
3 | x_{1} | 1 | 0 | 0 | 1/5 | 2/5 | 4 |
z_{j}-c_{j} | 0 | 0 | 0 | 1 | 0 |
Since all the values of zj – c_{j} are positive, this is the optimal solution.
x_{1 }= 4, x_{2} = 1
z = 3 X 4 + 2 X 1 = 14.
The largest profit of Rs.14 is obtained, when 1 unit of x_{2} and 4 units of x_{1} are produced. The above solution also indicates that 6 units are still unutilized, as shown by the slack variable x_{3} in the X_{B}column.
3 Comments »