8
Theory of Games
8.1 INTRODUCTION TO GAMES
Many a decision is taken in a competitive situation in which the outcome depends not on that decision alone but rather on the interaction between the decisionmaker and that of a competitor. The term ‘games’ now includes not only pleasurable activities of this kind, but also much more earnest competitive situations of war and peace. It was not coincidental that the classic work on the theory of games was first published during the Second World War. Many competitive situations are still too complex for the theory in its present state of development to solve. Other methods of which war games are longestablished examples and business games of more recent origins, have been used. The availability of computers has allowed increasingly large scale operations to be represented with great realism. The theory of games has been represented with great realism. The theory of games has been developed alongside gaming techniques and a knowledge of the concepts involved, especially the importance of the role of chance, helps to clarify the issues in many decision making process.
8.1.1 Some Basic Terminologies
Game: A competitive situation is called as a game if it has the following properties:
 There are finite number of participants called players.
 Each player has finite number of strategies available to him.
 Every game results in an outcome.
Number of players: If a game involves only two players (competitors), then it is called a twoperson game. However, if the number of players are more than two, the game is known as nperson game.
Sum of gains and losses: If in a game the gains of one player are exactly the losses to another player, such that sum of the gains and losses equals zero, then the game is said to be zerosum game. Otherwise it is said to be nonzero sum game.
Strategy: The strategy for a player is the list of all possible actions (or moves or courses of action) that he will take for every payoff (outcome) that might arise. It is assumed that the rules governing the choices are known in advance to the players. The outcome resulting from a particular choice is also known to the players in advance and is expressed in terms of numerical values. Here, it is not necessary that players have a definite information about each other strategies.
Optimal strategy: The particular strategy (or complete plan) by which a player optimises his gains or losses without knowing the competitor’s strategies is called optimal strategy. In other words the strategy that puts the player in the most preferred position irrespective of the strategy of his opponents is called as optimal strategy.
Value of the game: The expected outcome per play when players follow their optimal strategy is called the value of the game.
Pure strategy: It is a decision rule which is always used by the player to select the particular course of action. Thus, each player knows in advance of all the strategies out of which he always selects only one particular strategy irrespective of the strategy others may choose and the objective of the players is to maximise gains or minimise losses.
Mixed strategy: When both players are guessing as to which course of action is to be selected on a particular occasion with some fixed probability, it is a mixed strategic game. Thus, there is a probabilistic situation and objective of the players is to maximise expected gains or to minimise expected losses by making a solution among pure strategies with fixed probabilities.
Two person zero sum game: A game with only two persons is said to be twoperson zerosum game if the gain of one player is equal to the loss of the other.
Payoff matrix: The payoffs in terms of gains or losses, when players selected their particular strategies, can be represented in the form of a matrix, called the payoff matrix.
If the game is zerosum, the gain of one player is equal to the loss of the other and vice versa. In other words, one player’s payoff table would contain the same amounts in payoff table of the other player with the sign changed. If the player A has strategies A_{1}, …, A_{m} and the player B has strategies B_{1}, …, B_{n} and if a_{ij} represent the payoffs (gain for A) for i^{th} action of A and j^{th} action of B then the payoff matrix for player A is given by
8.2 TWOPERSON ZEROSUM GAME
Basic assumptions of the game:
 Each player has available to him a finite number of possible courses of action. The list may not be same for each player.
 Player A attempts to maximise gains and player B minimise losses.
 The decisions of both players are made individually prior to the play with no communication between them.
 The decisions are made simultaneously and also announced simultaneously so that neither player has an advantage resulting from direct knowledge of the other player’s decision.
 Both the players know not only the possible payoffs to themselves but also of each other.
8.2.1 Games with Saddle Point
Minimax and Maximin Principle: Consider the pay matrix of a game which represents payoff of player A. Now, the objective of the study is to know how these players must elect their respective strategies so that they may optimise their payoff. Such a decisionmaking criterion is referred to as the minimaxmaximin principle.
For player A minimum value in each row represents the least gain (payoff) to him if he choose his particular strategy. These are written in the matrix by row minima. He will then select the strategy that gives largest gain among the row minimum values. This choice of player A is called the maximin principle, and the corresponding gain is called the maximin value of the game denoted by v.
For player B (who is assumed to be the loser), the maximum value in each column represents the maximum loss to him if he chooses his particular strategy. These are written in the payoff matrix by column minima. He will then select the strategy that gives minimum loss among the column maximum values. This choice of player B is called the minimax principle, and the corresponding loss is the minimax value of the game denoted by .
Saddle point: A saddle point of a payoff matrix is that position in the payoff matrix where maximum of row minima coincides with the minimum of the column maxima. The saddle point need not be unique.
Value of the game: The payoff of the saddle point is called the value of the game denoted by v.
Fair game: A game is said to be fair if v = 0 = .
Strictly determinable game: A game is said to be strictly determinable if = 0 = .
Procedure to determine saddle point:
Step 1: Select the minimum element in each row and enclose it in a rectangle
Step 2: Select the maximum element in each column and enclose it in a circle
Step 3: Find out the element which is enclosed by the rectangle as well as the circle. Such element is the value of the game and that position is called as the saddle point.
Example 1
Solve the game whose payoff matrix is given by
Solution: Select the row minimum and enclose it in a rectangle. Then, select the column maximum and enclose it in a circle.
It is clear that saddle point is (II, III) and the value of the game v = 1.
Player A uses his course of action II throughout.
Player B uses his course of action III throughout.
The value of the game is 1 (for player A and – 1 for player B)
Example 2
A company management and the labour union are negotiating a new threeyear settlement. Each of these has 4 strategies.
 Hard and aggressive bargaining
 Reasoning and logical approach
 Legalistic strategy
 Conciliatory approach.
The costs to the company are given for every pair of strategy choice.
What strategy will the two sides adopt? Also, determine the value of the game.
Solution: Select the row minimum and enclose it by a rectangle. Then, select the column maximum and enclose it in a circle.
Hence, the saddle point is (I, III) and the value of the game is 12 (for union and – 12 for the company).
Hence, the company will always adopt strategy III–Legalistic strategy and union will always adopt strategy I – Hard and aggressive bargaining.
Example 3
Find the range of values of p and q which will render the entry (2, 2) a saddle point for the game.
Solution: First ignoring the values of p and q determine the maximin and minimax values of the payoff matrix.
Maximin value = 7 = minimax value.
This imposes the condition on p as p ≤ 7 and on q as q ≥ 7. Hence, the range of p and q will be p ≤ 7, q ≤ 7.
Example 4
Determine which of the following twoperson zerosum games are strictly determinable and fair. Give optimum strategies for each player in the case of strictly determinable games.
Solution: (i)
Maximin value = minimax value = 1 = value of the game. Hence, the game is strictly determinable but not fair. The optimum strategies are I for player A and II for player B.
(ii)
Maximin value = Minimax value = 5 = value of the game. Hence, the game is strictly determinable but not fair. The optimum strategies are I for player A and II for player B.
8.2.2 Games without Saddle Point: Mixed Strategies
There are some games for which no saddle point exists. In such cases both the players must determine an optimal combination of strategies to find a saddle (equilibrium) point. The optimal strategy combination for each player may be determined by assigning to each strategy its probability of being chosen. The strategies so determined are called mixed strategies because they are probabilistic combination of available choices of strategy.
The value of game obtained by the use of mixed strategies represents least payoff which player A can expect to win and the least which player B can lose. The expected payoff to a player in a game with arbitrary payoff matrix [a_{ij}] of order m × n is defined as
where, P = (p_{1}, p_{2}, …, p_{m}) and Q = (q_{1}, …, q_{n}) denotes the mixed strategies for players A and B. Also, p_{1} + p_{2} + … + p_{m} = 1 and q_{1} + … + q_{n} = 1. A particular strategy with particular probability a player chooses can also be interpreted as the relative frequency with which a strategy is chosen from the number of strategies of the game.
A mixed strategy game can be solved by different solution methods such as
 Algebraic method
 Analytical or calculus method
 Matrix method
 Graphical method, and
 Linear programming method.
These methods will be discussed in detail in the next section.
Dominance Property of Reducing the Size of the Game
We can sometimes reduce the size of a game’s payoff matrix by eliminating a course of action which is so inferior to another as never to be used. Such a course of action is said to be dominated by the other. The concept of dominance is especially useful for the evaluation of twoperson zerosum games where a saddle point does not exist.
General rule
 If all the elements of a row, say k^{th}, are less than or equal to the corresponding elements of any other row, say r^{th}, then kth row is dominated by the r^{th} row.
 If all the elements of a column, say k^{th} are greater than or equal to the corresponding elements of any other column, say r^{th}, then k^{th} column is dominated by r^{rh} column.
 Omit dominated rows or columns.
 If some linear combination of some rows dominates i^{th} row, then i^{th} row will be deleted. Similar argument follows for columns.
Example 1
Reduce the size of the game whose matrix is given by
We observer that no saddle point exists. Consider I^{st} and III^{rd} column’s from the player B’s point of view. We observe that payoff in the III^{rd} column is greater than the corresponding element in the 1^{st} column regardless of player A’s strategy. Evidently, the choice of III^{rd} strategy by the player B will always result in the greater loss compared to that of selecting the 1^{st} strategy. Column III is inferior to I and is never to be used. Hence, deleting the III^{rd} column which is dominated by I, the reduced size payoff matrix is obtained.
Again, if the reduced matrix is looked at from player A’s point of view, it is seen that the player A will never use the II^{nd} strategy which is dominated by III. Hence, the size of the matrix can be reduced further by deleting the II^{nd} row. Hence, the reduced matrix is
SOLUTION METHODS OF GAMES WITHOUT SADDLE POINT
Solution of 2 × 2 games: (Standard method)
For any 2 × 2 twoperson zerosum game without any saddle point having the payoff matrix for player A
The optimum mixed strategies
where,
and the value of the game is
Algebraic Method
This method can be used to determine probability value by using different strategies by players A and B. This method becomes quite lengthy when number of strategies for both are large.
Consider a game where payoff matrix is [a_{ij}]_{m × n}
Let (p_{1}, p_{2}, …, p_{m}) and (q_{1}, …, q_{n}) be the probabilities with which players A and B adopt their mixed strategies (A_{1}, …, A_{m}) and (B_{1}, B_{2}, …, B_{n}), respectively. If v is the value of game, then the expected gain to player A for this game when player B selects strategies B_{1}, B_{2}, …, B_{n} one by one is given by left hand side of simultaneous equations respectively. Since player A is the gainer and expects at least v, we must have where,
a_{11}p_{1} + a_{12}p_{2} + … + a_{1m}p_{m} ≥ v
a_{21}p_{1} + a_{22}p_{2} + … + a_{2m}p_{m} ≥ v
⋮
a_{n1}p_{1} + a_{n2}p_{2} + … + a_{nm}p_{m} ≥ v
where,
p_{1} + p_{2} + … + p_{m} = 1 and p_{i} ≥ 0 for all i.
Similarly, the expected loss to player B when player A adopts strategies A_{1}, …, A_{m} can be determined. Since player B is the loser, we must have, where,
a_{11}q_{1} + a_{21}q_{2} + … + a_{n1}q_{1} ≥ v
a_{12}q_{1} + a_{22}q_{2} + … + a_{n2}q_{2} ≥ v
⋮
a_{1m}q_{1} + a_{2m}q_{2} + … + a_{nm}q_{n} ≥ v
where,
q_{1} + q_{2} + … + q_{n} = 1 and q_{j} ≥ 0 for all j
Now, to get the values of and from inequalities (1) and (2), these inequalities are considered as equations and are then solved for given unknowns. However, if the system of equations so obtained is inconsistent, then at least one of the inequalities must hold as strict inequality. The solution can now be obtained only by applying trial and error method.
Example 1
In a game of matching coins with two players, suppose A wins one unit of value when there are two tails and loses 1/2 unit of value when there is one head and one tail. Determine the payoff matrix, the best strategies for each player and the value of the game to A.
Solution: The payoff matrix for the given matching coin game is
As the payoff matrix does not have a saddle point, the game can be solved by algebraic method.
For player A, let p_{1} and p_{2} be probabilities of selecting a strategy A_{1} and A_{2}, respectively. Then, the expected gain to player A when player B uses its B_{1}, and B_{2} strategies is given by
where,
For obtaining values of p_{1} and p_{2} considering these inequalities as equations. From (8.1), (8.2) and (8.3) we get p_{1} = – 2v and p_{2} = – 6v
Substituting these values of p_{1} and p_{2} in (8.3), we get p_{1} = 0.25, p_{2} = 0.75 and v = – 1/8
For player B, let q_{1} and q_{2} be the probabilities of selecting strategies B_{1} and B_{2}, respectively. Then, the expected loss to player B when player A uses its strategies A_{1} and A_{2} is given by
Considering (8.4), (8.5) as equations and then solving we get
q_{1} = 2v and q_{2} = – 6v
Substituting the values of q_{1} and q_{2} in (8.6)
we get, v = – 1/8, q_{1} = 0.25 and q_{2} = 0.75
Hence, the optimal strategies for players A and B are (0.25, 0.75) and (0.25, 0.75), respectively and the value of the game is v = – 1/8.
Arithmetic Method
Arithmetic method provides an easy technique for obtaining the optimum strategies for each player in (2 × 2) games without saddle point. This method consists of the following steps:
Step 1: Find the difference of two numbers in column I and put it under the column II, neglecting the negative sign if occurs.
Step 2: Find the difference of two numbers in column II, and put it under the column I, neglecting the negative sign if occurs.
Step 3: Repeat the above two steps for the two rows also.
The values thus obtained are called the oddments.
These are the frequencies with which the players must use their courses of action in their optimum strategies.
Example 1
Two players A and B showing each other, put on a table a coin, with head or tail up. A wins 8 when both the coins show head and 1 when both are tails. B wins 3 when the coins do not match. Given the choice of being matching player (A) or nonmatching player (B) which one would you choose and what would be your strategy?
Solution: The payoff matrix for player A is given by
Since no saddle point, is found the optimal strategies will be mixed strategies.
Step 1: Taking the difference of two numbers in column I, we find 8 – (– 3) = 11, and put it under column II.
Step 2: Taking the difference of two numbers in column II, we find (– 3 – 1) = – 4 and put the number 4 (neglecting the – ve sign) under column I.
Step 3: Repeat the above two steps for the two rows also.
Thus, for optimum gains, player A must use strategy H with probability 11/15 and strategy T with probability 4/15, while player B must use strategy H with probability 4/15 and strategy T with probability 11/15.Step 4: To obtain the value of the game any of the following expressions may be used.
Using B’s oddments
Using A’s oddments
The above values of v are equal only if the sum of the oddments vertically and horizontally are equal. Cases in which it is not so will be discussed later.
Thus, the complete solution of the game is:
 Optimum strategy for A is (4/15, 11/15)
 Optimum strategy for B is (4/15, 11/15)
 Value of the game to A is v = (– 1/15)
Thus, player gains (– 1/15), i.e., he loses (1/15) which B, is turn, gets.
Remark: Even though arithmetic method is easier than algebraic method but it cannot be applied to larger games.
8.2.3 Matrix Method
If the payoff matrix of a game is a square matrix, then optimal strategy mixture as well as value of the game obtained by the matrix method. The solution of a twoperson zerosum game with mixed strategies with a square payoff matrix may be found by using the following formulae:
Player A’s optimal strategy =
Player B’s optimal strategy =
Value of the game = (Player A’s optimal strategies) × (Payoff matrix P_{ij}) × (Player B’s optimal strategies)
where P_{adj} = adjoint matrix, P_{cof} = cofactor matrix. Player A’s optimal strategies are in the form of a row vector and B’s optimal strategies are in the form of a column vector.
This method can be used for finding a solution of a game with size more than 2 × 2. However, in rare cases, the solution violates the nonnegative condition of probabilities that is p_{i} ≥ 0, q_{i} ≥ 0 although the requirement p_{1} + … + p_{m} = 1 or q_{1} + … + q_{n} = 1 is satisfied.
Solve the following game after reducing it to a 2 × 2 game.
Solution:
Reduction to 2 × 2 matrix.
In the given payoff matrix, the third row is dominated by second row and third column is dominated by the first column. Hence, by the dominance property, the matrix is reduced to
Calculation of P_{adj} and P_{cof}
This solution can be broken into the optimal strategy combination for player A as p_{1} = 4/10 = 2/5 and p_{2} = 6/10 = 3/5, where p_{1} and p_{2} represent the probabilities of player A’s using his strategies A_{1} and A_{2} respectively.
Similarly, the optimal strategy combination for player B is obtained as player B’s optimal strategies
This solution can also be broken down into the optimal strategy combination for player B as q_{1} = 5/10 = 1/2 and q_{2} = 5/10 = 1/2, where q_{1} and q_{2} represent the probabilities of player B’s using his strategies B_{1} and B_{2}, respectively.
Value of the game
Another Form of Matrix Method (Matrix Oddment Method for n × n games)
Algorithm:
Step 1: Let A = (a_{ij})_{n × n} be a payoff matrix of a game. Obtain a new matrix C, whose first column is obtained from A by subtracting the second column from the first; the second column is obtained by subtracting A’s third column from the second, and so on until the last column of A is taken care of. Thus, C is an n × (n – 1) matrix.
Step 2: Obtain a new matrix R, from A, by subtracting its successive rows from the preceding ones, in exactly the same manner as was done for columns in step 1. Thus R is an (n – 1) × n matrix.
Step 3: Determine the magnitude of oddments corresponding to each row and each column of A. The oddment corresponding to the i^{th} row of A is defined as the determinant C_{i} where C_{i} is obtained from C by deleting the i^{th} row. Similarly, the oddment corresponding to the j^{th} column of A = R_{j} is defined as the determinant where R_{j} is obtained from R by deleting its j^{th} column.
Step 4: Write the magnitude of oddments (after ignoring negative signs, if any) against their respective rows and columns.
Step 5: Check whether the sum of row oddments is equal to the sum of column oddments. If so, the oddments expressed as fractions of the grand total yields the optimum strategies. If not, the method fails.
Step 6: Calculate the expected value of the game corresponding to the optimum mixed strategy determined above for the row player (against any move of the column player).
Example 1
Solve the following problem by the method of matrices:
Solution: The matrices C and R are as follows:
The augmented payoff matrix is
Sum of column oddments = Sum of row oddments
Thus optimum strategies for player A are or .
The optimum strategies for player B are or .
The value of the game
8.3 GRAPHICAL METHOD (FOR 2 × n OR FOR m × 2 GAMES)
The graphical method is useful for the game where the payoff matrix is of the size 2 × n or m × 2. That is, the game with mixed strategies that has only two pure strategies for one of the players in the two persons zerosum game. Optimal strategies for both the players assign nonzero probabilities to the same number of pure strategies. Therefore, if one player has only two strategies, the other will also use the same number of strategies. Hence, this method is useful in finding out which of the two strategies can be used.
Consider the 2 × n payoff matrix of a game without a saddle point.
Let the mixed strategy for player A be given by , where p_{1} + p_{2} = 1 and p_{1} ≥ 0, p_{2} ≥ 0.
Now, for each of the pure strategies available to B, expected payoff for player A would be as follows:
B’s pure move  A’s expected payoff E(p)  
B_{1}  E_{1} (p) = a_{11} p_{1} + a_{21} p_{2}  
B_{2}  E_{2} (p) = a_{12} p_{1} + a_{22} p_{2}  
⋮  ⋮  
B_{n}  E_{n} (p) = a_{1n} p_{1} + a_{2n} p_{2} 
The player B would like to choose that pure move B_{j} against S_{A} for which E_{j} (p) is a minimum for j = 1, …, n. Let us denote this minimum expected payoff for A by
v = min {E_{j} (p), j = 1, …, n}
The objective of player A is select p_{1} and hence p_{2} in such a way that v is as large as possible. This may be done by plotting the straight lines.
E_{j}(p) = a_{ij} p_{1} + a_{2j} p_{2} = (a_{ij} – a_{2j}) p_{1} + a_{2j} (j = 1, 2, …, n) as linear function of p_{1}.
The highest point on the lower boundary of these lines will give maximum expected payoff among the minimum expected payoffs on the lower boundary (lower envelope) and the optimum value of probability p_{1} and p_{2}.
Now the two strategies of player B corresponding to those lines which pass through the maximum point can be determined. It helps in reducing the size of the game to (2 × 2).
The (m × 2) games are also treated in the same way except that the upper boundary (upper envelope) of the straight lines corresponding to B’s expected payoff will give the maximum expected payoff to player B and the lowest point on this boundary will then give the minimum expected payoff (minimax value) and the optimum value of probability q_{1} and q_{2}.
Example 1
Solve the following 2 × 5 graphically
Solution: The game does not have a saddle point. Let the probability of player A playing A_{1} and A_{2} in the strategy combination is denoted by p_{1} and p_{2}, respectively where p_{2} = 1 – p_{1}. Then, the expected payoff (gain) to player A will be
B’s pure strategies  A’s expected payoff (Ei) 

B_{1}  2p_{1} – 2p_{2} 
B_{2}  – p_{1} + 4p_{2} 
B_{3}  5p_{1} – 3p_{2} 
B_{4}  – 2p_{1} + p_{2} 
B_{5}  6p_{1} + 0p_{2} 
These five expected payoff lines are plotted on the graph below.
Here, p_{1} is measured on the xaxis. Since p_{1} cannot exceed 1, the xaxis is cutoff at p = 1. The expected payoff of player A is measured along yaxis. From the game matrix, if player B plays B_{1}, the expected payoff of player A is 2 when A plays A_{1} with p_{1} = 1 and – 2 when A plays A_{2} with p_{1} = 0. These two extreme points are connected by a straight line, which shows the expected payoff of A when B plays B_{1}. Four other straight lines are similarly drawn for B_{2}, B_{3}, B_{4} and B_{5}.
The maximin point shows that the reduced payoff matrix is for player A is
Let
be the mixed strategies for player A.
Then,
p_{2} = 1 – p_{1} = 1 – 3/7 = 4/7
Let
be the optimum strategies for player B.
Then,
and,
q_{2} = 1 – q_{1} = 4/7
Value of the game
The optimum strategy are given by
and value of the game is v = – 2/7.
Remark: We observe that by using graphical method, the 2 × n game is converted into a 2 × 2 game and then solved by using standard method.
Example 2
Obtain the optimal strategies for both persons and the value of the game for zerosum twoperson game whose payoff matrix is as follows:
Solution: We observe that the given problem does not posses any saddle point. So, let the player B play the mixed strategy with q_{2} = 1 – q_{1} against player A. Then, B’s expected payoffs against A’s pure moves are given by
A’s pure move  B’s expected payoff E (q_{1}) 

A_{1}  q_{1} – 3q_{2} 
A_{2}  3q_{1} + 5q_{2} 
A_{3}  – q_{1} + 6q_{2} 
A_{4}  4q_{1} + q_{2} 
A_{5}  2q_{1} + 2q_{2} 
A_{6}  – 5q_{1} + 0q_{2} 
The expected payoff equations are then plotted as functions of q_{1} in the following graph.
Since the player B wishes to minimise his maximum expected payoff, we consider the minimax point on the upper envelope of B’s expected payoff equations. Hence, the given payoff matrix of the game is reduced to
be the optimal strategy of player A.
Then,
Hence,
p_{2} = 1 – p_{1} = 2/5
Let
be the optimal strategies of the player B.
Then,
and so
q_{2} = 1 – 4/5 = 1/5
and the value of the game
Remark: Using dominance property a m × n game can be converted into a 2 × n or a m × 2 game and the graphical method may be applied to convert it into a 2 × 2 game. Finally, standard method for a 2 × 2 game can be applied.
Example 3
Use the notation of dominance to simplify the rectangular game with the following payoff, and solve it graphically.
Solution: Column I is dominated by column II. Column III is dominated by column IV. Hence, omit column I and column III.
The given payoff matrix is reduced to a 4 × 2 matrix
Now, the given problem can be solved by graphical method.
From the graph it is clear that the reduced 2 × 2 matrix is
Let and be the optimum strategies for player A and B, respectively. By applying the standard method we can get p_{1} = 4/9, p_{2} = 5/9, q_{1} = 5/9, q_{2} = 4/9 and the value of the game v = 38/9.
8.4 SOLUTION OF m × n SIZE GAMES
Linear Programming Method
A two person zerosum game can also be solved by linear programming approach. The major advantage of using linear programming technique is that it solves mixed strategy of any size.
To illustrate the connection between a game problem and linear programming let us consider (m × n) payoff matrix (a_{ij}) for player A.
Let
be the optimum strategies for player A and player B respectively.
Then,
Then, the expected gains g_{j} (j = 1, …, n) of player A against B’s pure strategies will be
g_{1} = a_{11} p_{1} + a_{21} p_{2} + … + a_{m1} p_{m}
g_{2} = a_{12} p_{1} + a_{22} p_{2} + … + a_{m2} p_{m}
⋮
g_{m} = a_{1n} p_{1} + a_{2n} p_{2} + … + a_{mn} p_{m}
and the expected loss l_{i} (I = 1, … n) of player B against A’s pure strategies will be
l_{1} = a_{11} q_{1} + a_{12} q_{2} + … + a_{1n} q_{n}
l_{2} = a_{12} q_{1} + a_{22} q_{2} + … + a_{2n} q_{n}
⋮
l_{n} = a_{m1} q_{1} + a_{m2} q_{2} + … + a_{mn} q_{n}
The objective of player A is to select p_{i} (i = 1, 2, …, m) such that he can maximise his minimum expected gains and the player B desires to select q_{j} (j = 1, 2, …, n) that will minimise his expected loss.
Thus, if we let
and,
the problem of two players could be written as
Player A: Maximise u = minimize
subject to the constraints
Player B: Minimise v = maximise
subject to constraints
Assuming u > 0, v > 0, introduce a new variable defined by and
(i = 1, 2, …, m, j = 1, 2, …, n)
Then, the pair of linear programming problem can be rewritten as
Player A: Minimise
subject to
It is easy to note that the LPPs of the 2 players represent a primal dual pair. Therefore, by fundamental theorem of duality one can read the optimum solution of one player, just from the optimum simplex table of the opponent. That is, solve one player’s LPP.
Remark: In case there are negative elements in the payoff matrix add a suitable constant, then value of the game = value of the game – constant.
Solve the following game by using simplex method
Solution: Since some of the entries in the payoff matrix are negative, we add a suitable constant, say c = 4 to each element.
Let the strategies for 2 players be
where p_{1} + p_{2} + p_{3} = 1, q_{1} + q_{2} + q_{3} = 1
The linear programming problem for B is
Minimise v = maximise
subject to
5y_{1} + 3y_{2} + 7y_{3} ≤ 1,
7y_{1} + 9 y_{2} + y_{3} ≤ 1,
10y_{1} + 6y_{2} + 2y_{3} ≤ 1,
y_{j} ≥ 0 for j = 1, 2, 3 where y_{j} = q_{j}/v, j = 1, 2, 3
Introduce slack variables s_{1} ≥ 0, s_{2} ≥ 0, and s_{3} ≥ 0
Starting Table:
TABLE 8.1
From Table 8.1 we observe that y_{3} enters into the basis and s_{i} leaves the basis.
First iteration: Introduce y_{3} and drop s_{1}.
TABLE 8.2
From Table 8.2, we observe that y_{2} enters into the basis and s_{1} leaves the basis.
Second iteration:
Since all z_{j} – c_{j} ≥ 0 the current solution is optimum.
The value of the game
v = v – 4
= 5 – 4
= 1
Optimum strategies for B are
Making use of duality, the optimum strategies for player A are obtained as
Summary of systematic methods for solving a twoperson zerosum game:
 Look for saddle point or points. If it is found, the game is readily solved.
 Look for dominance. If it is found, delete the dominated row(s) and/or column(s). Each matrix so formed must be checked for dominance.
 If the size of the reduced matrix becomes (2 × 2), it can be solved by arithmetic and algebraic methods.
 If the size of the reduced matrix becomes (2 × n) or (m × 2), use the graphical method to reduce it to (2 × 2) matrix and then solve it by arithmetic or algebraic method.
 If the reduced size of the matrix becomes (3 × 3) or higher, algebraic method, method of matrices or simplex method of linear programming can be applied.
8.5 nPERSON ZEROSUM GAME
These games are usually treated as if two coalitions are formed by the npersons involved. The characteristics of such a game are the values of the various games between every possible pair of coalitions. For example, with four players A, B, C and D, the following seven coalitions can be formed.
A against B, C, D
B against A, C, D
C against A, B, D
D against A, B, C
A, B against C, D
A, C against B, D
A, D against B, C
If the value of the game for B, C, D coalition is v, then the value of the game for A is –v, since it is a zerosum game. Thus, in a fourperson zerosum game, there will be seven values or characteristics for the game, which are obtained from the seven different coalitions.
Example 1
Find the values of the threeperson zerosum game in which player A has two choices X_{1} and X_{2}; player B has two choices Y_{1} and Y_{2}, and player C also has two choices Z_{1} and Z_{2}. The payoff matrix is given in Table 8.3.
TABLE 8.3
Solution: There are three possible coalitions:
 A against B, C
 B against A, C
 C against A, B
The payoff matrix in A’s terms is given in Table 8.4.
TABLE 8.4
Thus, the game has a saddle point. So, A’s best strategy is X_{1}.
B’s and C’s best combination of strategies is Y_{1}, Z_{2} with the value of game v = 0.
B against A, C
The payoff matrix in B’s terms is given in Table 8.5.
TABLE 8.5
Saddle point does not exist. We try to reduce the size of the game by using dominance, if any. All the elements of column II are greater than or equal to the respective elements of column I. So column II is deleted. Similarly, column IV is dominated by column III and so column IV is deleted.
The resulting payoff matrix is
TABLE 8.6
C against A, B
The payoff matrix in C’s terms is given in Table 8.6.
TABLE 8.7
Saddle point does not exist and so apply the dominance property. Now columns III and IV are dominated by column I and so they are deleted. Thus, the resulting payoff matrix is
Thus, the characteristics are
γ (A) = 0; γ (B, C) = 0
γ(B) = –1/4; γ(A, C = 1/4
γ(C) = 1/4; γ(A, B) = –1/4
EXERCISES
Section 8.1
1. Give a comprehensive explanation of the term “game theory”.
2. Define with the help of an example, the following:
 Players
 Payoff matrix
 Outcome
 Strategy
 Pure strategy
 Mixed strategy
4. Explain the difference between a pure strategy and a mixed strategy.
5. What are the assumptions made in game theory?
6. State the major limitations of game theory.
Section 8.2
7. Explain twoperson zerosum game by giving suitable example.
8. Explain: Minimax and maximin principle used in the theory of games.
9. What is a game in game theory? What are the properties of a game? Explain the ‘best strategy’ on the basis of minimax criterion of optimality.
10. Define ‘saddle point’. Is it necessary that a game should always posses a saddle point.
11. Game theory provides a systematic quantitative approach for analysing competitive situations in which the competitors make use of logical processes and techniques in order to determine an optimal strategy for winning. Comment.
12. Define value of the game.
13. Define the following terms:
 Fair game
 Strictly determinable game
14. For the game with payoff matrix
Determine the best strategies for players A and B. Also, determine the value of the game. Is the game
 fair
 strictly determinable
[Answer: Best strategy for player A is A_{1} and that for B is B_{3}, value of the game = –2. The game is strictly determinable but not fair.]
15. Consider the game with the following payoff
 Show that game is strictly determinable, whatever λ may be.
 Determine the value of the game.
[Answer: (ii) Value of the game v = 2.]
16. Determine whether the following game is strictly determinable and fair or not.
[Answer: Not fair value of game = 1.]
17. Solve the following games whose payoff matrix is given by
[Answer: (a) Optimal strategy for A : A_{2}, B : B_{3} value of the game = 4, (b) optimal strategy for A : A_{3}, B : B_{3}, v = 1, (c) optimal strategy for A : A_{2}, B : B_{3}, v = 1.]
18. Find out whether there is any saddle point in the following problem
[Answer: Saddle point does not exist.]
19. For the game with payoff matrix:
Determine the best strategies for players A and B and also the value of the game for them. Is the game (i) fair? (ii) strictly determinable?
[Answer: Saddle point (I, III), v = –2. Game is strictly determinable and not fair.]
20. Find the saddle point (or points) and hence solve the following games
[Answers:
 Saddle point (A_{2}, B_{2}), v = 5,
 Saddle point (II, III), v = 4,
 Saddle point (I, I), v = 6]
21. Solve the game whose payoff matrix is given by
[Answer: Saddle point is (A_{1}, B_{1})] or (A_{1}, B_{3}) and v = 1.]
22. The following games have saddle point solutions. Determine the saddle point and the optimum strategies for each player.
[Answer:
 Saddle point: (x_{1}, y_{1}) or (x_{1}, y_{3}), v = 4
 Saddle point: all the points are saddle points, v = 4.]
23. Determine the optimum strategies and values of the following game:
[Answer: Saddle point: (A_{2}, B_{3}), v = 6.]
Section 8.3
24. Solve the following 2 × 2 games without saddle points:
[Answers:
25. Two players A and B match coins. If the coin matches, then A wins one unit of value, if the coins do not match, then B wins one unit of value. Determine optimum strategies for the players and the value of the game.
[Answers: Strategy for player A is
Strategy for player B is and v = 0.
26. Solve the following game using dominance property
[Answer:
27. Using dominance property solve the following games
28. A and B play a game in which each has three coins, a 5p, a 10p, and a 20p. Each selects a coin without the knowledge of the others choice. If the sum of the coins is odd amount, A wins B’s coin, if the sum is even B wins A’s coin. Find the best strategy for each player and the value of the game.
[Answer: The payoff matrix is
29. Solve the following games by reducing them to 2 × 2 games by graphical method
30. Solve the following games by reducing them to 2 × 2 games by graphical method: (a)


 Saddle point (A_{2}, B_{1}), v = 6.]
Section 8.4
31. Solve (3 × 3) game by the simplex method of linear programming whose payoff matrix is given as follows
32. Two companies A and B are competing for the same product. Their different strategies are given in the following payoff matrix
Use linear programming to determine the best strategies for both the players.
33. Solve the following games by linear programming
[Answer:
34. For the following payoff table, transform the zerosumgame into an equivalent linear programming problem and solve it by simplex method.
[Answer: