8. Theory of Games – Operations Research, 2nd Edition

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 decision-maker 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 long-established 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:

  1. There are finite number of participants called players.
  2. Each player has finite number of strategies available to him.
  3. Every game results in an outcome.

Number of players: If a game involves only two players (competitors), then it is called a two-person game. However, if the number of players are more than two, the game is known as n-person 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 zero-sum game. Otherwise it is said to be non-zero 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 pay-off (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 two-person zero-sum game if the gain of one player is equal to the loss of the other.

Pay-off matrix: The pay-offs in terms of gains or losses, when players selected their particular strategies, can be represented in the form of a matrix, called the pay-off matrix.

If the game is zero-sum, the gain of one player is equal to the loss of the other and vice versa. In other words, one player’s pay-off table would contain the same amounts in pay-off table of the other player with the sign changed. If the player A has strategies A1, …, Am and the player B has strategies B1, …, Bn and if aij represent the pay-offs (gain for A) for ith action of A and jth action of B then the pay-off matrix for player A is given by

8.2 TWO-PERSON ZERO-SUM GAME

Basic assumptions of the game:

  1. Each player has available to him a finite number of possible courses of action. The list may not be same for each player.
  2. Player A attempts to maximise gains and player B minimise losses.
  3. The decisions of both players are made individually prior to the play with no communication between them.
  4. 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.
  5. Both the players know not only the possible pay-offs 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 pay-off 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 pay-off. Such a decision-making criterion is referred to as the minimax-maximin principle.

For player A minimum value in each row represents the least gain (pay-off) 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 pay-off 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 pay-off matrix is that position in the pay-off 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 pay-off 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 pay-off 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 three-year settlement. Each of these has 4 strategies.

  1. Hard and aggressive bargaining
  2. Reasoning and logical approach
  3. Legalistic strategy
  4. 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 pay-off 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 two-person zero-sum games are strictly determinable and fair. Give optimum strategies for each player in the case of strictly determinable games.

  1.  
  2.  

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 pay-off which player A can expect to win and the least which player B can lose. The expected pay-off to a player in a game with arbitrary pay-off matrix [aij] of order m × n is defined as

where, P = (p1, p2, …, pm) and Q = (q1, …, qn) denotes the mixed strategies for players A and B. Also, p1 + p2 + … + pm = 1 and q1 + … + qn = 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

  1. Algebraic method
  2. Analytical or calculus method
  3. Matrix method
  4. Graphical method, and
  5. 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 pay-off 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 two-person zero-sum games where a saddle point does not exist.

General rule

  1. If all the elements of a row, say kth, are less than or equal to the corresponding elements of any other row, say rth, then kth row is dominated by the rth row.
  2. If all the elements of a column, say kth are greater than or equal to the corresponding elements of any other column, say rth, then kth column is dominated by rrh column.
  3. Omit dominated rows or columns.
  4. If some linear combination of some rows dominates ith row, then ith row will be deleted. Similar argument follows for columns.

Example 1

Reduce the size of the game whose matrix is given by

Solution:

We observer that no saddle point exists. Consider Ist and IIIrd column’s from the player B’s point of view. We observe that pay-off in the IIIrd column is greater than the corresponding element in the 1st column regardless of player A’s strategy. Evidently, the choice of IIIrd strategy by the player B will always result in the greater loss compared to that of selecting the 1st strategy. Column III is inferior to I and is never to be used. Hence, deleting the IIIrd column which is dominated by I, the reduced size pay-off 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 IInd strategy which is dominated by III. Hence, the size of the matrix can be reduced further by deleting the IInd row. Hence, the reduced matrix is

SOLUTION METHODS OF GAMES WITHOUT SADDLE POINT

Solution of 2 × 2 games: (Standard method)

For any 2 × 2 two-person zero-sum game without any saddle point having the pay-off 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 pay-off matrix is [aij]m × n

Let (p1, p2, …, pm) and (q1, …, qn) be the probabilities with which players A and B adopt their mixed strategies (A1, …, Am) and (B1, B2, …, Bn), respectively. If v is the value of game, then the expected gain to player A for this game when player B selects strategies B1, B2, …, Bn 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,

 

a11p1 + a12p2 + … + a1mpmv
a21p1 + a22p2 + … + a2mpmv

an1p1 + an2p2 + … + anmpmv

where,

p1 + p2 + … + pm = 1   and   pi ≥ 0 for all i.

Similarly, the expected loss to player B when player A adopts strategies A1, …, Am can be determined. Since player B is the loser, we must have, where,

 

a11q1 + a21q2 + … + an1q1v
a12q1 + a22q2 + … + an2q2v

a1mq1 + a2mq2 + … + anmqnv

where,

q1 + q2 + … + qn = 1   and   qj ≥ 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 pay-off matrix, the best strategies for each player and the value of the game to A.

Solution: The pay-off matrix for the given matching coin game is

As the pay-off matrix does not have a saddle point, the game can be solved by algebraic method.

For player A, let p1 and p2 be probabilities of selecting a strategy A1 and A2, respectively. Then, the expected gain to player A when player B uses its B1, and B2 strategies is given by

where,

For obtaining values of p1 and p2 considering these inequalities as equations. From (8.1), (8.2) and (8.3) we get p1 = – 2v and p2 = – 6v

Substituting these values of p1 and p2 in (8.3), we get p1 = 0.25, p2 = 0.75 and v = – 1/8

For player B, let q1 and q2 be the probabilities of selecting strategies B1 and B2, respectively. Then, the expected loss to player B when player A uses its strategies A1 and A2 is given by

Considering (8.4), (8.5) as equations and then solving we get

 

q1 = 2v   and   q2 = – 6v

Substituting the values of q1 and q2 in (8.6)

we get, v = – 1/8, q1 = 0.25   and   q2 = 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 non-matching player (B) which one would you choose and what would be your strategy?

Solution: The pay-off 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:

  1. Optimum strategy for A is (4/15, 11/15)
  2. Optimum strategy for B is (4/15, 11/15)
  3. 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 pay-off 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 two-person zero-sum game with mixed strategies with a square pay-off 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) × (Pay-off matrix Pij) × (Player B’s optimal strategies)

where Padj = adjoint matrix, Pcof = 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 non-negative condition of probabilities that is pi ≥ 0, qi ≥ 0 although the requirement p1 + … + pm = 1 or q1 + … + qn = 1 is satisfied.

Example 1

Solve the following game after reducing it to a 2 × 2 game.

Solution:

Reduction to 2 × 2 matrix.

In the given pay-off 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 Padj and Pcof

This solution can be broken into the optimal strategy combination for player A as p1 = 4/10 = 2/5 and p2 = 6/10 = 3/5, where p1 and p2 represent the probabilities of player A’s using his strategies A1 and A2 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 q1 = 5/10 = 1/2 and q2 = 5/10 = 1/2, where q1 and q2 represent the probabilities of player B’s using his strategies B1 and B2, respectively.

Value of the game

Another Form of Matrix Method (Matrix Oddment Method for n × n games)

Algorithm:

Step 1: Let A = (aij)n × n be a pay-off 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 ith row of A is defined as the determinant |Ci| where Ci is obtained from C by deleting the ith row. Similarly, the oddment corresponding to the jth column of A = |Rj| is defined as the determinant where Rj is obtained from R by deleting its jth 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:

Now

The augmented pay-off 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 pay-off 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 zero-sum game. Optimal strategies for both the players assign non-zero 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 pay-off matrix of a game without a saddle point.

Let the mixed strategy for player A be given by , where p1 + p2 = 1 and p1 ≥ 0, p2 ≥ 0.

Now, for each of the pure strategies available to B, expected pay-off for player A would be as follows:

  B’s pure move A’s expected pay-off E(p)
  B1 E1 (p) = a11 p1 + a21 p2
  B2 E2 (p) = a12 p1 + a22 p2
 
  Bn En (p) = a1n p1 + a2n p2

The player B would like to choose that pure move Bj against SA for which Ej (p) is a minimum for j = 1, …, n. Let us denote this minimum expected pay-off for A by

 

v = min {Ej (p), j = 1, …, n}

The objective of player A is select p1 and hence p2 in such a way that v is as large as possible. This may be done by plotting the straight lines.

Ej(p) = aij p1 + a2j p2 = (aija2j) p1 + a2j (j = 1, 2, …, n) as linear function of p1.

The highest point on the lower boundary of these lines will give maximum expected pay-off among the minimum expected pay-offs on the lower boundary (lower envelope) and the optimum value of probability p1 and p2.

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 pay-off will give the maximum expected payoff to player B and the lowest point on this boundary will then give the minimum expected pay-off (minimax value) and the optimum value of probability q1 and q2.

Example 1

Solve the following 2 × 5 graphically

Solution: The game does not have a saddle point. Let the probability of player A playing A1 and A2 in the strategy combination is denoted by p1 and p2, respectively where p2 = 1 – p1. Then, the expected pay-off (gain) to player A will be

B’s pure strategies A’s expected pay-off (Ei)
B1 2p1 – 2p2
B2 p1 + 4p2
B3 5p1 – 3p2
B4 – 2p1 + p2
B5 6p1 + 0p2

These five expected pay-off lines are plotted on the graph below.

Here, p1 is measured on the x-axis. Since p1 cannot exceed 1, the x-axis is cut-off at p = 1. The expected pay-off of player A is measured along y-axis. From the game matrix, if player B plays B1, the expected pay-off of player A is 2 when A plays A1 with p1 = 1 and – 2 when A plays A2 with p1 = 0. These two extreme points are connected by a straight line, which shows the expected pay-off of A when B plays B1. Four other straight lines are similarly drawn for B2, B3, B4 and B5.

The maximin point shows that the reduced pay-off matrix is for player A is

Let

be the mixed strategies for player A.

Then,

and,

p2 = 1 – p1 = 1 – 3/7 = 4/7

Let

be the optimum strategies for player B.

Then,

and,

q2 = 1 – q1 = 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 zero-sum two-person game whose pay-off 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 q2 = 1 – q1 against player A. Then, B’s expected pay-offs against A’s pure moves are given by

A’s pure move B’s expected pay-off E (q1)
A1 q1 – 3q2
A2 3q1 + 5q2
A3 q1 + 6q2
A4 4q1 + q2
A5 2q1 + 2q2
A6 – 5q1 + 0q2

The expected pay-off equations are then plotted as functions of q1 in the following graph.

Since the player B wishes to minimise his maximum expected pay-off, we consider the minimax point on the upper envelope of B’s expected pay-off equations. Hence, the given pay-off matrix of the game is reduced to

Let

be the optimal strategy of player A.

Then,

Hence,

 

p2 = 1 – p1 = 2/5

Let

be the optimal strategies of the player B.

Then,

and so

q2 = 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 pay-off, 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 pay-off 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 p1 = 4/9, p2 = 5/9, q1 = 5/9, q2 = 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 zero-sum 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) pay-off matrix (aij) for player A.

Let

be the optimum strategies for player A and player B respectively.

Then,

Then, the expected gains gj (j = 1, …, n) of player A against B’s pure strategies will be

 

g1 = a11 p1 + a21 p2 + … + am1 pm
g2 = a12 p1 + a22 p2 + … + am2 pm

gm = a1n p1 + a2n p2 + … + amn pm

and the expected loss li (I = 1, … n) of player B against A’s pure strategies will be

 

l1 = a11 q1 + a12 q2 + … + a1n qn
l2 = a12 q1 + a22 q2 + … + a2n qn

ln = am1 q1 + am2 q2 + … + amn qn

The objective of player A is to select pi (i = 1, 2, …, m) such that he can maximise his minimum expected gains and the player B desires to select qj (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 re-written 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 pay-off matrix add a suitable constant, then value of the game = value of the game – constant.

Example 1

Solve the following game by using simplex method

Solution: Since some of the entries in the pay-off matrix are negative, we add a suitable constant, say c = 4 to each element.

Let the strategies for 2 players be

where p1 + p2 + p3 = 1, q1 + q2 + q3 = 1

The linear programming problem for B is

Minimise v = maximise

subject to

5y1 + 3y2 + 7y3 ≤ 1,
7y1 + 9 y2 + y3 ≤ 1,
10y1 + 6y2 + 2y3 ≤ 1,

yj ≥ 0 for j = 1, 2, 3  where  yj = qj/v, j = 1, 2, 3

Introduce slack variables s1 ≥ 0, s2 ≥ 0, and s3 ≥ 0

Starting Table:

 

TABLE 8.1

From Table 8.1 we observe that y3 enters into the basis and si leaves the basis.

First iteration: Introduce y3 and drop s1.

 

TABLE 8.2

From Table 8.2, we observe that y2 enters into the basis and s1 leaves the basis.

Second iteration:

Since all zjcj ≥ 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 two-person zero-sum game:

  1. Look for saddle point or points. If it is found, the game is readily solved.
  2. 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.
  3. If the size of the reduced matrix becomes (2 × 2), it can be solved by arithmetic and algebraic methods.
  4. 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.
  5. 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 n-PERSON ZERO-SUM GAME

These games are usually treated as if two coalitions are formed by the n-persons 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 zero-sum game. Thus, in a four-person zero-sum 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 three-person zero-sum game in which player A has two choices X1 and X2; player B has two choices Y1 and Y2, and player C also has two choices Z1 and Z2. The pay-off matrix is given in Table 8.3.

 

TABLE 8.3

Solution: There are three possible coalitions:

  1. A against B, C
  2. B against A, C
  3. C against A, B

A against B, C

The pay-off 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 X1.

B’s and C’s best combination of strategies is Y1, Z2 with the value of game v = 0.

B against A, C

The pay-off 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 pay-off matrix is

 

TABLE 8.6

and value of the game is

C against A, B

The pay-off 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 pay-off 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:

  1. Players
  2. Pay-off matrix
  3. Outcome

3. Define the following:

  1. Strategy
  2. Pure strategy
  3. 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 two-person zero-sum 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:

  1. Fair game
  2. Strictly determinable game

14. For the game with pay-off matrix

Determine the best strategies for players A and B. Also, determine the value of the game. Is the game

  1. fair
  2. strictly determinable

[Answer: Best strategy for player A is A1 and that for B is B3, value of the game = –2. The game is strictly determinable but not fair.]

15. Consider the game with the following pay-off

  1. Show that game is strictly determinable, whatever λ may be.
  2. 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 pay-off matrix is given by

  1.  
  2.  
  3.  

[Answer: (a) Optimal strategy for A : A2, B : B3 value of the game = 4, (b) optimal strategy for A : A3, B : B3, v = 1, (c) optimal strategy for A : A2, B : B3, 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 pay-off 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

  1.  
  2.  
  3.  

[Answers:

  1. Saddle point (A2, B2), v = 5,
  2. Saddle point (II, III), v = 4,
  3. Saddle point (I, I), v = 6]

21. Solve the game whose pay-off matrix is given by

[Answer: Saddle point is (A1, B1)] or (A1, B3) and v = 1.]

22. The following games have saddle point solutions. Determine the saddle point and the optimum strategies for each player.

  1.  
  2.  

[Answer:

  1. Saddle point: (x1, y1) or (x1, y3), v = 4
  2. Saddle point: all the points are saddle points, v = 4.]

23. Determine the optimum strategies and values of the following game:

[Answer: Saddle point: (A2, B3), v = 6.]

Section 8.3

24. Solve the following 2 × 2 games without saddle points:

  1.  
  2.  
  3.  

[Answers:

  1.  
  2.  
  3.  

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

  1.  
  2.  

[Answer:

  1.  
  2.  

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 pay-off matrix is

29. Solve the following games by reducing them to 2 × 2 games by graphical method

  1.  
  2.  
  3.  
  4.  

[Answer:

  1.  
  2.  
  3.  
  4.  

30. Solve the following games by reducing them to 2 × 2 games by graphical method: (a)

  1.  
  2.  
  3.  

[Answer:

  1.  
  2.  
  3. Saddle point (A2, B1), v = 6.]

Section 8.4

31. Solve (3 × 3) game by the simplex method of linear programming whose pay-off 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 pay-off matrix

Use linear programming to determine the best strategies for both the players.

33. Solve the following games by linear programming

  1.  
  2.  

[Answer:

  1.  
  2.  

34. For the following pay-off table, transform the zero-sum-game into an equivalent linear programming problem and solve it by simplex method.

[Answer: