560 Operations Research : Theory and Practice

CHAPTER AT A GLANCE
Start

Write the payoff matrix

Apply maximm-minimax principle

Identify the value of game and write the Yes

optimal strategy of the players

Solve by using analytical (or algebric) or

matrix method for mixed strategic games

No
Use dominance rule to reduce the size
of the payoff matrix to either 2*2
2xw ormx2, size (order)

Yes

Yes
Use graphical method to solve the problem.

Formulate and solve as a LP problem

Stop
Game Theory 561

1L0 Introduction
In the competitive world, it is essential for an executive to study or at least guess
the activities or actions of his competitor. Moreover, he has to plan his course of actions
or reactions or counter actions when his competitor uses certain technique. Such war
or game is a regular feature in the market and the competitors have to make their
decisions in choosing their alternatives among the predicted outcomes so as to
maximise the profits or minimising the loss.

Hie game theory has taken its importance in the business management in 1944,
when Von Neumann published "Theory and practice of Games and Economic
Behaviour".

11.1 Theory of Games: The Terminology Used

A competitive situation is called game, in this context.

11.1.1 Properties of a Game

1. There are finite number of competitors called 'players'.

2. Each player has a finite number of possible courses of action called 'strategies'.
3. All the strategies and their effects are known to the players but player does not
know which strategy is to be choosen.

4. A game is played when each player chooses one of his strategies. The strategies
are assumed to be made simultaneously with an outcome such that no player
knows his opponents strategy until he decides his own strategy.
5. The game is a combination of the strategies and in certain units (usually in
terms of money) which determines the gain (shown in positive figures) or loss
(shown in negative figures).

6. The figures (either gain or loss) shown as the outcomes of strategies in a matrix
form is called "pay-off matrix"

7. The player playing the game always tries to choose the best course of action
which results in optimal pay off, called "optimal strategy11.
8. The expected pay off when all the players of the game follow their optimal
strategies is known as "Value of the game". The main objective of a problem of
games is to fmd the value of the game.

9. The game is said to be 'fair game if the value of game is zero, otherwise it is
known as 'unfair.
562 Operations Research : Theory and Practice

11*1.2 Definitions of Terms Used

1. Startegy: A startegy for a player has been defined as a set of rules or alternative
courses of action available to him in advance, by which player decides the course
of action that he should adopt.Startegy may be of two types :
(a) Pure Strategy : If the players select the same strategy each time, then it is
referred to as pure-strategy. In this case each player known exactly what
the other is going to do i.e., there is a deterministic situation and the
objective of the players is to maximize gains or to minimize losses.
(b) Mixed Strategy : When the players use a combination of strategies and
each player always kept guessing as to which course of action is to be
selected by the other player at a particular occasion then this is known as
mixed-strategy. Thus, there is a probabilistic situation and objective of the
player is to maximize expected gains or to minimize losses. Thus, mixed
strategy is a selection among pure strategies with fixed probabilities.
2. Optimum Strategy : A course of action or play which puts the player in the
most preferred position, irrespective of the strategy of his competitors is called
an optimum strategy. Any deviation from this strategy results in a decreased
pay-off for the player.
3. Value of the Game : It is the expected pay-off of play when all the players of
the game follow their optimum strategies. The game is called/air if the value
of the game is zero and unfair if it is non-zero.
4. Two-Person Zero-Sum Game : There are two types of two person zero-sum
games. In one, the most preferred position is achieved by adopting a single
strategy and therefore the game is known as the pure strategy game. The second
type requires the adoption by both players a combination of different strategies
in order to achieve the most preferred position and is, therefore, referred to as
the mixed strategy game.
5. Payoff Matrix : A two-person zero-sum game is conveniently represented by a
matrix as shown below. The matrix, which shows the outcome of the game as
the players select their particular strategies, is known as the payoff matrix. It is
important to assume that each player knows not only his own list of possible
courses of action but also of his opponent.
Let player A have m courses of action {A^.A^, . . . A^ and player B has n courses
of action (Bx, 3%, . . . Bn). The number n and m need not be equal. The total number
of possible outcome is, therefore (m x n). These outcomes are shown in the following
table.
A }s payoff matrix B 's payoff matrix
Player B Player B
B
\ B2 B
n
au a
\2 ~a\\ ~an ~a\n
Player^ a21 a22 Player^ -an

a a
m\ nm a
m2
Game Theory 563

11.2 Types of Games

Games can be classified into different categories with reference to various
aspects as given below.

11.2,1 With Reference to Number ofPlayers

With reference to the number of players playing the game, the games are
divided into two categories Viz. (1) Two-person games and (2) Multi-person games.
1. Two Person Games : If only two players are playing the game then the game
is said to be two person game. The rows and column in the pay off matrix
represent the strategies of these two players.
e.g.: (a) Chess players
(b) Marketing strategies of Coke and Pepsi in India.
2. Multi-person Game : It is a game in which more than two persons play.
e.g. : Competition among tooth paste producers, soap producers.

11.2,2 With Reference to Nature of Out Comes

1. Zero-sum game. 2. Non-zero sum game.
1. Zero-sum Game : If loss of a player is gain of other player and vice-versa, then
the game is called zero-sum game.
2. Non-zero Sum Game : In contrast to the above, if a gain of player is not a loss
of another player (positive sum game) or loss of a player is not a gain of another
player (negative sum game), then such games are non-zero sum games.

e.g.; Suppose there are two players, say Colgate and Pepsodent. In a colony
there are 1000 people who either use Colgate or Pepsodent. Now, if say
20 people have changed their brand from Colgate to Pepsodent due to
effective advertisement then the loss of Colgate is gain for Pepsodent, This
is a zero-sum game.
If a group of 30 people has stopped using any toothpaste and use
neem-sticks. Here loss of any player is not a gain to other player. This
game is non-zero sum (negative sum) game.

1L2.3 With Reference to Certainty

1. Deterministic games. 2. Probabilistic games.
1. Deterministic Games : If the game yields a solution with one certain, single
strategy (pure strategy) for each player, the game is deterministic. In this game
the strategies are pure and saddle points exist.

2. Probabilistic Games : If a player adopts more than one strategy with some
probabilities or prepares a blend of two or more strategies, these games are
said to be probabilistic. Here, mixed strategies are used as no saddle points
exist.
564 Operations Research : Theory and Practice
112.4 With Reference to Value of the Game
1. Fair game 2. Unfair game

1. Fair Game : If the value of the game is zero, i.e., neither player wins nor loses
(drawn), the game is said to be fair.

2. Unfair Game : If one of the player wins (other loses), or the value of the game
is non zero (may be positive or negative), it is unfair.

The following is the classification of games shown with a chart.

Fair
s Deterministic <T
Zero-sum./'^ Unfair
games ^C.
Fair
Two-person Probabilisitic < ^
games
Unfair
Non-zero-sum
games

Multiperson
games Same as above

FIGURE I I.I : CLASSIFICATION OF GAMES

11.3 Two Person-zero Sum Games or Rectangular Games

A game with only two persons with a condition that the loss of one player is gain
of the other and vice-versa (so that total sum is zero) is said to be two-person zero-sum
game or rectangular game.

Pay Off Matrix : The qualitative measures of returns of the players in terms of
gains or losses when players select their particular strategies can-be represented in
the form of a matrix in m rows and n .columns, called pay off matrix. The m rows are
the m courses of action of one player while n columns represent the strategies of the
other player. Thus one player say A has m strategies^, A%9 A% . . .Am and player B
has n strategies as Bp B^ B§ . . . Bn. When each player chooses one of his strategies
say Ai and £ -, then the expected out come x^ is represented as the elements of the
matrix. It is a general convention to read the pay off matrix with reference to row
player (here A) always.Thus a positive sign of x- is gain to A or loss to B while the
negative sign of x^ (i.e., - x-) is loss of A or gain of B.
Game Theory 565

Obviously player */!' wishes to maximise his gains while player B wishes to
minimise his loss.

An exemplary pay of matrix of two-person zero-sum game is shown below.

(xj i is pay off when A uses A j strategy and B uses B^ strategy x 12 is pay off when
A applies A y and B applies B% strategies and so on).
Player Bys strategies

*11 x 12 x13 X
\n
x X X
\2 32 2n
x
Player ^4*5 strategies n

11.3-1 Assumptions of the Game

1. Each player has finite number of possible courses of actions (strategies) with
him.

2. The list of strategies of each player need not be same.

3. Player in Rows attempts to maximise his gains while player in columns tries to
minimise his losses.
4. The decision of both players are made individually prior to the play with out
any communication between them.
5. The decision is supposed to be made simultaneously and also announced
simultaneously so that neither player has any advantage over the other due to
the direct knowledge of the other player's decision.
6. Both players know their own pay ofrs as well as the pay off of each other.

7. The positive sign of the pay off indicates the gain to row player or loss to column
player and negative sign indicates loss to row player or gam to column player.

11.3.2 Solving Two Person-zero Sum Games

Two person zero sum games may be deterministic or probabilistic. The
deterministic games will have saddle points and pure strategies exist in such games.
In contrast, the probabilistic games will have no saddle points and mixed strategies
are taken with the help of probabilities. These are explained in following sections.
566 Operations Research : Theory and Practice

Games With Saddle Points - Deterministic Games - with Pure Strategies :

These games can be solved by using one of the following methods.
1. Minimax and Maximin principle.
2. Dominance principle.
Minimax and Maximin Criteria :
In a given pay off matrix of two players, it is evident that the row player will
maximise his minimum profits, thus applies maxi-min principle. Similarly, the
column player attempts to minimise his maximum loss using his mjM-max rule.
For example for player^ (in rows), minimum value in each row represents his
least gain when he chooses to play that particular strategy. In other words, it is the
minimum gain he can be confident, what so ever the strategy that his opponent uses.
Thus in each row, when such minimal values are calculated, among all these least
gains, he wishes to select the maximum of these values. This selection of maximum
gains (largest value) among the row minimum values is referred to as Maxi-Min
principle.
Similarly, for player in columns (say B) who is assumed to be loser, the
maximum value of each column denotes the maximum loss to him if he adopts that
particular columns strategy. In other words, it is the worst case of B for which he must
be prepared. These are written beneath the pay off matrix called column maxima
from which he can choose least (to minimise his losses). This is called Mini-max
principle. If maximum value of row minima i.e., maximin value of row player is equal
to the minimax value of column player (i.e., minimum value of column maxima), then
the game is said to have 'Saddle (Equilibrium) Points', and the corresponding strategies
are said to be 'Optimal Strategies'. The value of the pay off (say V) at this saddle
(equilibrium) point is known as 'Value of the Game'. A game may have more than one
saddle point but the value will be same.
Steps To Find Saddle Points by Applying Minimax-Maximin Criteria :
Step 1: Write pay off matrix.
Step 2 : Select the minimum value in each row of the pay off matrix under the head row
minimum written at right end of each row put a circle (0) over these elements
in the pay off matrix.
Step 3 : Select largest among the row minima found from step-2 and write beneath the
row minima.
Step 4 ; Select largest value (maximum) of each column and put a box or rectangle
(L_l ) over these values in the pay off matrix. Write these values of column
maximum beneath the pay off matrix.
Step 5 : Select minimum value of column maxima (found in step-4) and write this at the
right end.
Step 6 : If Max (R^) = Min (Cmax) i.e., value in step - 3 equals value in step-5 then
saddle point exits. Thus saddle point is found at the element on which both
circle and box are enclosed. Note this pay off element as the value of the game.
Game Theory 567

This is illustrated with the following numerical example.

ILLUSTRATION 1 :

Players Adithi andSahithi haue a competition to reach college early. Each has
two strategies viz going by car or going by a two-wheeler. If both go by cars,
Sahithi reaches 5 minutes early but if both go by two-wheelers, Adithi can reach
4 minutes early. If Adithi goes by car andSahithi by a two wheeler, Adithi reaches
2 minutes early while Adithi by two wheeler and Sahithi by car keeps Sahithi
7 minutes early. If both can choose their strategies independently and
simultaneously and know these estimated pay offs each other, find who will win.
What will be outcome of the game and their optimal choices.

Solution :
Step 1 : To Write Pay OffMatrix .Let us first formulate the information into the pay off
matrix.
Assume Adithi is the row player and Sahithi is column player. With this
assumption, we can say that gains to Adithi are positive and that to Sahithi are negative.
The pay offs for various alternatives are as follows.

Adithi by car when Sahithi by car is -5 (since Sahithi wins by 5 min).

Adithi by car when Sahithi by two wheeler is 2 (since Adithi wins by 2 min).

Adithi by two wheeler when Sahithi by car is -7 (since Sahithi wins by 7 min)

Adithi by two wheeler while Sahithi by two wheeler is 4 (since Adithi wins by 4
min).

Now, these pay offs are arranged in a matrix form as follows :

Sahithi
Car Two Wheeler
Adithi Car -5 2
Two Wheeler -7 4

Step 2 : Find row minima and encircle these values.

Sahithi
Car Two Wheeler J?min
Adithi Car o 2 -5
Two Wheeler Q 4 -7
568 Operations Research : Theory and Practice

Step 3 : Find maximum of row minima

Sahithi

Car Two Wheeler Rn

Adithi Car 2

Two Wheeler 0 4 -7
- 5 <- Max (Rmm)

Step 4 : Find column maxima and enrectangle these elements.

Sahithi

Car Two Wheeler jRmin

Adithi Car -5

Two Wheeler -7

- 5 <- Max (tfm

Step 5; Find Minimum of column maxima

Sahithi
Car Two Wheeler Rmin

Adithi Car y 2

Two Wheeler
y -7
_ gs- 5 <- Max (Rum) (Maximin)
O
Min(C max )
(Minimax)
As Maximin = Minimax or Max CRmin) = Min (C m a x ) the saddle point exists at
first row-first column element which is both encircled and enrectangled.

The Optimal Strategies :

For Adithi — TO GO BY CAR
For Sahithi — TO GO BY CAR
Value of the game = -5
Which means Sahixiii will win by 5 minutes or Adithi will lose by 5 minutes.
[It is a deterministic (pure strategies) unfair game]
Game Theory 569
ILLUSTRATION 2

Solve thefollowing game

Bj B2 B3 B4
-5 -2 0 7
A A2 5 -6 -4 8
A3 4 0 2 3
Solution :
Finding Rrr^n and then maximim among i?D

B2 £
4 min

A A,
0 -2 0 7 -5

5
Q -4 8 -6
4
® 2 3 0

Find C max and then min of C max

B% BA Rm\,
4 ^min

A 4i
0 -2 0 7 -5

5
0 -4 8 -6

4 K5) 2 3
0 Max(i? mill )

Min(C m a x )

Saddle point exists atA$, B%

A uses pure (deterministic) strategy A§

B uses pure (deterministric) strategy B<^
and value of the game (v) = 0
i,e., Game is drawn (i.e., neither^ nor B wins)
(This is a fair game as v = 0 )
570 Operations Research : Theory and Practice

11.4 Dominance Principle

The dominance principle is used to reduce the order of the pay off matrix.
Thus if saddle points exist, the matrix can be reduced to a matrix with one element
which is equal to value of the game.
Similarly, we can say that the dominance principle is used to delete rows and/
or columns of the pay off matrix which are inferior (i.e., less attractive) to at least one
of the remaining rows and / or columns (strategies) in terms the pay offs. The deleted
rows or columns would never be used by both the players for determining their
optimum strategy.
The dominance principle is composed of the following rules.
Rule 1 : Row Dominance :
For a row player, in a pay off matrix, if every element in a particular row is less
than or equal to the corresponding element of another row, then the former row is
said to be inferior or dominated by the latter. Therefore the row player will never
employ the former row (strategy) for whatever strategy that is used by nis opponent.
Hence this row can be deleted from the pay off matrix for further iteration.
B

i?2 dominates R\
since R%i>Ru (Ri
e.g. can be deleted)
R*

In the above pay off every element in R j is less than or equal to its corresponding
element in i?2- (4<5, 6=6 and -5<-3). Therefore Rl can be deleted since row player
(A) will never use R± for whatever strategy B uses among Cj, C2, and C3.
Note : The rule cannot be applied even if one element does not obey rule.

Rule - 2 : Column Dominance :

For a column player, in a pay off matrix if every element in a column is greater
than or equal to corresponding element of another column, the former column
strategy never yields any better result than the latter and therefore the former column
will never be used whatsoever may be the opponent's strategy. Hence the former
column can be deleted from the pay off matrix for further iteration.
B

2 C% dominates C\
e.g. since C%j< C\j
R* «iiii -1
(C\ can be deleted)

In the above pay off matrix, every element of Cj is either greater than or equal
its corresponding element of C2- This suggests* that, first column is inferior to the
second in any case and hence deleted.
Game Theory 571

Rule 3 : Modified Row Dominance :

When no single row (pure) strategy has dominance over the other, then the
comparison may be made between a row and the average of a group of rows, if every
element is less than or equal to average of corresponding elements of a group, then
the former row can be removed. If a row dominates over the average of group of rows,
then the group may be discarded.
Player B

e.g. 1 Player^

In Ax ScA2

Ax8cA3

A2 8c A%

Thus there is no pure row dominance.

But by comparing the Ax average values of A2 andA$ we have,

>2 of/^ and

>2

Therefore the row A^ is inferior to average of A% andv43. Hence A^ can be

"5 0]
deleted thus we reduce matrix to
0 8J
B

In the above pay off, between

Ax8cA2 8< 15 but 3 > - l
Ax8cAs 8>1 but 3<4

A2ScAs 15 > 1 but -1<4

Thus there is no pure dominance.
But comparing average of^42 &^s with^j, we have
572 Operations Research : Theory and Practice

8cAs = 8<8

-1+4 3
= 9"-

Therefore the average is dominated by^4x and hence both^42 and A% are deleted
leaving the matrix as [1 4]
Rule - 4 : Modified Column Dominance :

Similar to the above rule, when no pure column dominance exists, a convex
linear combination i.e., average of certain pure strategies may be compared with
another pure strategy applying rule 2, i.e., if every element in a column is greater than
or equal to corresponding element of other column the former is omitted.
Player B

8=
15+1
Player ,4 HI 15 1 2
e.g. -1 + 4
iHSl -i 4
Clearly, their is neither pure column nor pure row dominance exist in the above
pay off. But the average (convex linear combination) of 5 2 and B$ is greater than or
equal to corresponding element of first column. Therefore B^ can be deleted.
Thus we get,

P i]
These rules used to solve the games are illustrated through following numerical
examples.
ILLUSTRATION 3
Let us the take the game of illustration -1 and solve by using dominance :
After formulating we get
Sahithi
Car Two-wheeler
5
Adithi Car
Two-wheeler
isrffe C2j > = Cij (C% can be deleted)

Solution :
Now, from Sahithi's point of view, she never uses her second strategy i.e.,
two-wheeler since, for what ever Adithi's strategy, she will be the loser. Therefore her
car strategy dominates over two-wheeler strategy (every element of first column is less
Game Theory 573
than or equal to corresponding element of second column). Hence Sahithi's
two-wheeler strategy is deleted.

Thus we get,
Sahithi
Car
Adithi Car
R% <R\i (i?2 can be deleted)
Two-wheeler

Now, as Adithi has her better strategy with car (her loss is less here), she will
never got for two-wheeler strategy. (Every element in first row is greater than or equal
to the corresponding element in the second row). Hence second row is deleted.
Now the game is reduced to a single element matrix i.e., both using car strategy
with value of the game as - 5. i.e., Sahithi wins by 5 units.
ILLUSTRATION 4

An engineering student was frequently absent to the classes in a semester. To

safe guard himself he can choose one of the alternatives given below and the
professor also had four strategies. The student has approximated the probable
percent of marks in thefollowing pay off matrix against various strategies.
The students strategies are showing reasons as
Sx: due to ill health S2: to attend sister fs marriage are S3: went on project work S4
: attended inter college celebrations. The professor's strategies are Px: Not
giving attendance P2: Giving exam tough P3: Evaluating strictly PA:
Complaining to principal.
Thepay of is

1*2 1*4
55 53 32 62
s2 4O 30 74 5O
s3 57 54 44 53
54 54 72 56

Use dominance principle so that the student may choose his optimal strategy.

Solution :
In the given pay off, by examining thoroughly we find that every element of
P 2 column is less than or equal to the corresponding element of Pj column, hence
professor will never use the P± strategy (P2 dominates P^, hence Pj is deleted. The
pay off is then reduced to
574 Operations Research : Theory and Practice

P\j>P<2j {P% dominates and Pi is

deleted). After Pi is deleted S$ can be
deleted in the next iteration, Since

deleted
From the above pay off, it is clear that, the student will never use 5 S because
every element of 5 4 is greater than or equal to corresponding elemerit of 5 3 (5 4
dominates S3 ). Hence by using the principle of dominance we delete S3 and revise
the pay of as
p
t p P

Si. 53 • 32 ^ ^ ^ p P4j>P2j (P4 is deleted)

s2 30 74" ^ ^ ^ ^

s4 54

Again P 2 dominates P 4 , hence P 4 is deleted, we get

P
3
i (S\ is deleted)

s2 30 74
54 72

Now, S 4 dominates Sj, hence S± is deleted.

P3/ > P% (P3 can be deleted)

Now, As P 2 dominates P 3 , P 3 is deleted

(52 can be deleted)

54

Now, S4 dominates S2, hence S2 is deleted. Thus student uses S 4 strategy while
professor uses P 2 strategy i.e. The professor gives the exam tough when student claims
that his absence is due to attending intercoUege celebrations and the value of the game
is 54.
Game Theory 575

ILLUSTRATION 5

Let us consider the example in illustration - 2.

B
Bj
**1 BJ*2
2 B3 B4
Ai ' -5 -2 0 7
5 -6 -4 8
4 0 2 -3

S o Iution i
In this game, on observing we can notice the dominance of B2 over B$ and JB4.
(by Rule - 2)
The game reduces to
B

Now, A% dominates over Al and^ z is deleted, So, we get

B

-6

mm o
Now, as B% dominates B± and so, we delete
B

A$A$ is dominating A2 we have the value of game as 'zero'.

i.e., Fair game (drawn)
A uses Aj strategy and B uses B2 strategy.
576 Operations Research : Theory and Practice

Modified Dominance :
ILLUSTRATION 6 ——-
Use dominance principle to reduce thefollowing game to 2*2 game, Is the game
stable. nw n
Player B
Bt B2 B3 B4
6 -10 9 0
Player A
A2 6 7 8 1
A3 8 7 15 1
A4 3 4 -1 4
Solution ;

We can easily verify that the above game has no saddle points. Therefore it is
not stable.

Now using row dominance, the third row^43 dominates overy4x as well
Therefore^ and^42 are deleted (shaded in the pay off matrix of the problem given
above).
Thus the play reduces to
Player B
£>i JDc, £>o BA

Player^

Now, we can delete second column ( B2 strategy) as it is dominated by fourth

strategy (every element is less than or equal to corresponding element).
Player B
1 3
15
Player^
A, IKS 1

A4 SKtif -i 4

Now, there is no pure dominance, however we can apply modified dominance

with a convex combination of B's B$ and B± strategies dominates his first strategy.

=8<8
Game Theory 577
Therefore B's B±, strategy is deleted.
Thus the game reduces to
Player B

Player ,4

This game can be solved by using either algebraic or any other suitable method,
which will be explained in the sections to follow.

1L5 Games Without Saddle Points: Mixed Strategy

In certain cases, no pure strategy solutions exist for the game. In other words,
saddle points do riot exist. In all such game, both players may adopt an optimal blend
of the strategies called Mixed strategy to find a saddle (equilibrium) point. The
optimal mix for each player may be determined by assigning each strategy a
probability of it being chosen. Thus these mixed strategies are probabislitic
combinations of available better (or dominant) strategies and these games hence
called probabilistic games.
Summarily, when saddle points do no exist in the game, we can use the
dominance principle to reduce to 2 x 2 game or at least 2 x n or m x 2 matrices. If this
is also not possible we can formulate it as Linear programming problem.
Thus the probabilistic mixed strategy games without saddle points are
commonly solved by any of the following methods :
S.No. Method Applicable to
L Algebraic method 2 x 2 games
2. Graphical method 2 x 2 , m x 2 and 2xn games
3. Linear programming method 2 x 2 , ffix2, 2xn and m xn games.

These are explained here below :

1. Algebraic Method :
Suppose a general game without saddle points as given below :
Player B

player A

Since it is assumed that there are no saddle points, A wishes to use a mixed
strategy ofA i and A% with the probabilities of/? i and p%t and B to use a mixed strategy
of B i and JB2 with the probabilities of qy and q% respectively.
578 Operations Research : Theory and Practice
According to the assumption that A always tries to maximise his minimum
returns and B tries to minimise his maximum losses, they employ their strategies most
optimally such that the B's minimax losses will be equal A9s maximin gains.
Hence, out come of probability mix (of px andjf?2) by A in his Ax and^42
strategies when if use's his Bx strategy i.e., apx + cp2 is the value of the game.

Otherwise, when B uses his B2 strategy, A's returns will be apx + dp2, is also the
value of the game. These both must be equal.

(a-b)px = (d-c)p2

— =~ (i)
Pt a ~ b
Similarly, from B 's. point of view
aqx + bq2 = cq^ + dq2
i.e., (a-c)ql = (d-b)q2

q2 (a - c)

From the rule of probabilities, we know thatpi +p2 = 1 and qx + q2 = 1

Thus we have
or
P\ = l -P2 P2=l ~Pv • • • • (iiO
and qx = 1 - q2 or q2 = 1 - qx . . - . (iv)

Thus we have (on solving the equations )

(d-c) (c-d) (c-d)
P
-b) (c-d)-(a-b) (b + c)-(a + d
(d-b) = ib-d) _ (b-d)
b) + (a-c) (b-d)-(a-c) (b + c)-(a + d
Wherep2= l-px, q2= 1 -qx,
(and v - api + cp2 or bpx + dp2 or aqx + bq2 or c^j + d^2 )
ad - be
i.e., v=
(a + d) - (b + c)
This method is illustrated with the following numerical example.
Game Theory 579

* Illustration - 6 is continued :
Previous to this section, the problem in Illustration - 6 was reduced from
4 x 4 to 2 x 2 and left unsolved there.
Now we can use the above formulae and find the solution.
Player B
B
3

15 1
Player^
A4 -1 4
Assuming the probabilities p] 8cp2 for A and q± h!c£2 for B to use
t and 2*3, B4 respecitvely, we have

-1-4 14
H- 19
1-4 3 16
(-1 + 1)-(15+ 4) " 19 19
(15) ( 4 ) - ( - ! ) ( ! ) 61
( )( )

[ 5 14^
—, — while B uses his £3
w
h
. ., u _ ... . , u i, • , , . r u -61 . . .
strategies with probabilities —, — and the value of the game = — i.e., A wins.
r li/ 1 J I J. ZJ

ILtUSTRATIOK 7
Children Srija and Himaja play a game who have some 25^ paise coins and
SOpaise coins. Each draw a coin from their bags with out knowing other rs choice.
If the sum of coins drawn by both is even Srija wins them, otherwise Himaja wins.
Find the best strategyfor each player and alsofind the value of the game.
Solution :
First let us formulate the game. According to the data given Le.s each has some
25 paise coins and some 50 paise coins in their bags and draw one at a time.
Now, from this we can say that each has two strategies.
Strategy 1: Drawing 25 paise coins.
Strategy 2 : Drawing 50 paise coins.
Let us choose Srija as row players and Himaja as column player.
Now if Srija draws 25 paise (say strategy Sj) and Himaja draws 25 paise (say,
strategy H±), then the sum is even. Therefore Srija wins them. Her gains (pay off) is
25 paise.
Similarly, if Srija draws 25 paise (strategy S^) and Himaja draws 50 paise (say
strategy i/ 2 ) then Himaja wins these coins and her gain (pay off) is 25 paise or
otherwise Srija's loss i.e., -25 paise.
580 Operations Research : Theory and Practice

Again, if Srija draws 50 paise (strategy S 2 ) and Himaja draws 25 paise ( strategy
Hx), then Himaja wins 50 paise or Srija's loss i.e., - 50 paise.
Also, when both draw 50 paise ( S2 and H% ) Srija wins 50 paise.
Thus, the pay off is as follows.
Himaja
Hl (25 paise) H% (50 paise)
Srija Sx (25 paise) 25 -25
(50 paise) - 50 50
On examination we can find that there are no saddle points/ therefore the
players use their mixed strategies, say with the probabilities as fa andjf?2 for Srija on
Si and S2 respectively, and as q± and q% for Himaja on Hi andi/ 2 respectively.
Thus we have,
25px-50p2 =-25pi + 5Qp2 (1)
25qi-25-q2=-5Oql + 5Qq2 . . . . (2)
Also P1+P2 = 1 -. - • • (3)

From(l) 50^!= 100

r-fl • • • • (5)
Pz
From (3) and (5)
We get Pi=-; p2 = -
Also from (2) we have
75 qY = 7 5 ? 2

^=1 ,...(6)
n
From (4) and (6)

Thus Srija is expected to use her strategies 5 r andS 2 (i.e., Drawing

25 paise and 50 paise coins respectively) in probabilities of (2/3, 1/3).
While for Himaja it is optimal to use her strategies with (1/2, 1/2) probability
of H i and // 2 , i.e., drawing 25 paise and 50 paise coins respectively.
The value of the game is zero.
And it is fair game (V= 0)

[Since V - 25 x - | - 2 5 x | = 0

V = - 5 O x | + 5Ox|=

or 7=25xf-50x- = -
Game Theory 581
ILLUSTRATION 8

Find the best strategy and the value of thefollowing game:

I II III
I -1 -2 8
II 7 5 -I
III 6 0 12
[JNTU (CSE) 97/S]
ITERATION TABLEAU 1:

B
II III Row Minima
I -1 -2 8 -2
II 7 5 -1 -1
III 6 0 12 0 <- Max (Rmin)
Column 12 5
Maxima Min (CmJ

S o I M+ion \

By minimax (maximin) principle, we have no saddle points as

Max(# min )*Min(C max ).

Hence, we check the principle of dominance. It is found that Row ^4111 is

dominating AT, since every element in^4(III) is > the corresponding element oL4(I).

Therefore A will never use the strategy A(I), hence deleted. Now, the new
iterated pay off is
ITERATION TABLEAU 2 :

B
I II III
A II -1
III 12

The column 5(11) dominates B(l) since every element in 5(11) is less than its
corresponding element of B(I)..Hence B(I) is deleted (B will never use B-l as it yields
more losses against any strategy played byyl).
582 Operations Research : Theory and Practice

ITERATION TABLEAU 3 :
B
II III
II 5 -1
II 0 12
Now, they play a mixed strategies with probabilities. Since there are neither
saddle points nor any dominance.
Let A use the strategies II & III with probabilities^ and^ 2 respectively and B
use the strategies II 8c III with the probabilities q^ ancl^ respectively.
then Pi+p2= l>1l+<l2=1
And from the pay off we know that
and
p l
o A9l 13
— = 2 and — = -z~
5
Pl ft
2 1
13 5

. e 2 10
and the value of the game is 5 x —= —.
(by substituting in any of the above probability expressions).

Thus, the mixed strategies of A are (II, III) with the probabilities — and — .
L j
the mixed strategies of B are (II and III) with the probabilities (13/18 and 5/18).

The expected value of the game is — (A wins the game).

ILLUSTRATION 9
A and B play a game in which each has three coins a 5P, a 10P and 20P. Each
selects a coin with out the knowledge ofthe others choice. If the sum ofthe coins is
an odd amount, A winsBfs coins. If the sum is even B wins A fs coins. Find the best
strategy for each player and the value ofthe game.
[JNTU (Mech.) 99/CCC, (ECE) 99/CCC]

Solutiorv ;
When A draws 5p, if B draws bp, then B gains 5p of A, if B draws 10 p, A wins
\0p and if B draws 20^ then alsoy4 wins 10^ and so on.
Thus, the pay off matrix for player^ is formulated as :
Player B
5p 10p 20p

PlayeM bp
iOp
20p
Game Theory 583

It is clear that this game has no saddle point. Therefore, further we try to reduce
the size of the given pay off matrix. Note that every element in column £3 is more
than or equal to every corresponding element of column J52- Evidendy, the choice of
strategy B 3 by the player B will always result in more losses as compared to that of
selecting the strategy B%. Thus strategy B% is inferior toB%. Hence, deleting53 strategy
from the pay off matrix. The reduced pay off matrix is shown below:
Player B

Player^ A} -5 10
5 -10

After the column B§ is deleted, it may be noted that strategy A% of player^ is

dominated by his A$ strategy, since the profit due to strategy A% is greater than or
equal to the profit due to strategy A§, regardless of which strategy player B selects.
Hence strategy A% (row 3) can be deleted from further considerations. Thus the
reduced pay off matrix is
Player B

Player yl -5 10
5 -10
Since in the reduced 2 x2 matrix, the maximin. value is not equal to the
minimax value. Hence there is no saddle point and one cannot determine the point
of equilibrium. For this type of game situation, it is possible to obtain a solution by
applying the concept of mixed strategies.
Let p\ ,p2 and <?i » £2 be th e probabilities of A and B playing the strategies
{Ax ,A% ) and (Bl, B% ) respectively and we h a v e ^ +p2 = 1 and q\ + q%= 1.
Now, from the above pay off,
= 1 0 jf?a —

and - 5 q± + 10 q% - 5 q^ - 10 q%

Thus we have — = 1 and — = 2.

By solving the above equations, we have

l l 2 l
* * A

A n d t h e v a l u e of t h e g a m e is - 5 x — + 5 x — = 0 t h u s t h e m i x e d s t r a t e g y of

AQiiiA^) is w i t h t h e p r o b a b i l i t i e s o f —,— a n d t h a t o f B (Bx, B2 ) is — , — t h e

I J I J
value of the game is zero (fair game).
584 Operations Research : Theory and Practice

11.6 Graphical Solutions

Graphical solutions are helpful for the two-person zero-sum games of order
2 x n or m x 2 i.e., when one of the players have only two dominant strategies to mix
while other has many strategies to play. However, graphical solutions used with an
assumption that 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 also should have to use same (two) number of strategies. This method is
helpful in finding out which two strategies can be used.

Here we have two cases viz 2.x n and m x 2 cases.

Case (i) : 2 x n games :

In this case, row player has two. strategies to play while column player has n
strategies. The graphical method is applied to find which two/strategies of column
player are to be used.
Suppose a pay off given below :
PlayerB
B
2 Bs • •:• Bn.

Player^ ^1 a
A2 a
22
a
23 a
2n

If player A mixes his strategies^ and A% with probabilities p± and P2-Q where
Pi + p2 = 1 » t n e n f° r e a c n strategy of B, A will have the expected pay off as follows.
Es pure- strategy A's pay off

B2

B
n \ 2
As A is assumed to always try to maximise his minimum gains. The highest point
of lower envelop (lower boundary) formed by drawing these as straight lines represents
the optimal probability mix: The lines corresponding to this point will yield a 2 x 2
matrix from which the value of the game, optimal strategies and their probability mix
can be found.
Thus the two series are to represented on two parallel axes and these are joined
to represent respective pay offs. Then the lower envelop is identified and upon this
highest point is located. The coefficients of these lines make a 2 x 2 matrix for further
iteration / calculation.
The above method is illustrated through the following example :
Game Theory 585
ILLUSTRATION 1 0 —
Solve thefollowing game graphically.
V-e o 6 -3/2
\_7 -3 -8 [JNTU (Mech.) 2001]
Solution :
Let Row player's (say^4) strategies are^j and^42 are used with the probabilities
p j and p2, then his expected pay offs when his opponent (column player) uses his pure
strategies are shown below :
Column players pure strategies Row player (A's) expected pay off

III
IV
These are graphically represented as follows as two parallel axes of unit distance
apart.
Ax s 2 Axi s i

9- •9

Q Q
o • • o

7- • 7

6- •6
\ /
/
•

5- • 5
\ I: -6p, + 7 p 2 /
4- \ •4

3- •3

2- •2
1- • 1

-1- •-1

-2- •-2

3- y\ \ Maximum \ \ / ^ , •-3
S
-4- (<W?ot \W^
-5- • / < <
•-5

-6- •-6
v •
-7-
-8-
/ \ \\\ N
•-7

•-8
Lower envelope \ \

FIGURE I 1.2 :
586 Operations Research : Theory and Practice
The highest point on lower envelop appear at the intersection of the lines
represented by column players I and II strategies.
7p2 and
The required 2 x 2 matrix is
?l ?2

- 3°1J
Pi r-6
Pi L 7
We have Pl + 7pl =* 6p ! = i0^ 2
P1+P2 = 1
10 5 3 3
Pi " 16 ~ 8 ' 6~8
and l-Sft =» 131?l = 3^2
_ 3
and ?1 "*" ?2 = ^[
__3_ 13
9.1 ~ 16 " 16
.\ Row player will use his strategies with the probabilities as (5/8,3/8)
respectively where the column player uses the first two strategies mix at the
probabilities of (3/16, 13/16).
The value of the game

or
The column player wins the game with a gain of 9/8 units or row player loses
the game with a loss of 9/8 units.

? (ii) : m x 2 games :•
In this case a column player has two strategies while row player can choose
optimal mix of best two among m strategies. The graphical method is usedto Find
which two strategies of rows player would be the best.
Suppose a pay off of two players A and B is given below
Player B
B B
l 2
u
an

Player A

a
m\
Game Theory 587
When player B mixes his strategies Bx and £ 2 with non-zero probabilities
and #2 where q± + q% = 1, then for each strategy of A, B's expected pay off is given
by
A's pure strategy B's pay off

a
\2(i\+a22<l2

Now, as B is assumed to be the looser always, he will try to minimise his

maximum losses. Thus when these expected pay offs of B, when drawn as straight
lines between two parallel axes the lowest point (minimising) of the upper envelop
(maximum losses) represents his optimal strategy. The line consisting of this point
will represent the best two strategies at its edges on the two parallel axes of unit
distance apart. TTie perpendicular drawn from the minimum point of envelop on to
x-axis divides segment on x-axis into two parts equal to the probabilities used by B.
This is illustrated through the following example.
{ I L L U S T R A T I O N 11
Solve thefollowing game graphically.

1 —3
3 5
-1 6
4 1
2 2
-5 O

I Solution ;
Let B's strategies By and 252 t*e used with the probabilities q^ arid# 2 where
= 1. Then the pay offs of B for each of the strategies used by A are given below.
A's pure strategy B's expected pay off
A
\ 9\~ ^?2
588 Operations Research : Theory and Practice

The above pay offs against A'5 strategies are drawn as straight lines between two
parallel axes of unit distance apart.
Since.column player B wishes to minimise his maximum expected pay off (loss),
we consider the lowest point (minimum) of intersection G in the upper envelop
EFGH (maximum) which represents the minimax of B's expected pay off.
The minimax point G is the point of intersection of the lines A2 and^44. Thus
the pay off ofA is found most optimal with the blend ofA% and^44 strategies. Thus the
6 x 2 matrix reduces to 2 x 2 matrix with A's A2 and^44 and B's Z^ and B% strategies
which can be evaluated by algebraic method.
Axis 1 Axis 2

FIGURE
B
«1 -
.5
1
Now, ifpi and^?2 a r e th e probabilities of^4 to and q± and q% are
the probabilities of B to play B x and B2 then
Game Theory 589

3p j'+ 4p2 = bpl+p2 = V (the value of the game)

and Sqy + bq2 = 4q\+ q2 = V (the value of the game)
Where pi +pi = 1 and "£i + ft = l-
Solving the above equations we get,

and pi + p 2 - 1
3 and 2
P\ " 5 "5
4
Also
$2
and ai + ao
4 ' 1
?l = "g" . a n d ft = 5"
plays his^2 and^44 strategies with the probabilities (3/5, 2/5) while 5
applies his B^ and JB2 strategies with the probability mix (4/5, 1/5) and the value of
the game
1T '4 1 17

Remark : Observe the strategies A j, ^5 an6? ^4g an^f compare each with A%- You can find
is dominating these three since it is up over these in graph

11.7 Linear Programming Method

When a two person zero sum games are in larger size (say mxn) these can be
solved by linear programming method. This is the major advantage of this method
and hence can be considered as universal method.
To illustrate this method first let us consider a 3 x 3 matrix given below :
B
*\ B2
Ax an an
A A2 a
21 Ht
A, a31 aS2

Now, as per the assumptions, A always attempts to choose the set of strategies
with the non-zero probabilities say p^p^^ndp^ ( where p\+p2+p3= 1) t n a t
maximises his minimum expected gains.
Similarly, according to B, he would choose the set of strategies with the non-zero
probabilities, say qlf q2 and q$. (where qY + q2 + q$ = 1), that minimises his maximum
expected losses.
From the above statements, we can draw the following conclusions.