Theory of Games 309

9.1 WHAT IS GAME?

A game is a formal description of a strategic situation.
The different Properties of a Game are
1 There are finite numbers of competitors called 'players'. A player is an agent who makes
decisions in a game.
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 plaýer does not know which
strategy is to be chosen.
strategies áre assumed
4 A game is played when each player chooses one of his strategies. The
to be made simultaneously with an outcome such that no player knows his opponents strateg)
until he decides his own strategy.
determines the gain or
The game is a combination of the strategies and in certain units which
loss.
called 'pay-off matrix".
6 The figures shown as the outcomes of strategies in a matrix form are
best course of action which results in
7 The player playing the game always tries to choose the
optimal pay off called 'optimal strategy'.
follow their optimal strategies is known
8. The expected pay off when all the players of the game of a game is to find the value of the
problem
as value of the game'. The main objective of a
game.

9.2 WHAT IS GAME THEORY?

Game theory is the formal study of conflict and cooperation. Game theoretic concepts apply
interdependent. These agents may be individuals,
whenever the actions of several agents are
of game theory provide a language to
groups, firms, or any combination of these. The concepts
strategic scenarios.
formulate, structure, analyze, and understand
one's choice of action is determined after
Game theory is a type of decision theory in which opponent playing the same game, rather
taking into account all possible alternatives available to an theory does not insist on how a game
Game
than just by the possibilities of several outcome results.
which action should be selected. Thus it
should be played but tells the procedure and principles by
situations.
is a decision theory useful in competitive according to a set of rules at the
persons
Game is defined as an activity between two or more game
or suffers loss. The set of rules defines the
end of which each person receives some benefit a play.
participants defines
Going through the set of rules once by the
TERMINOLOGY
9.3 GAME THEORY
1. Competitive game
competitive game.
Acompetitive situation is called a
properties
Competitive gamne has the following four
competitors such thatn>2.
a) There are finite number of
two-person game
In casen=2, it is called a
n-person game.
In casen> 2, it is referred as
finite number of possible activities.
b) Each player has a list of each player chooses one of his activities. The choices
to occur when
c) A play is said made simultaneously i.e. no player knows the choice of the
are
be
assumed to otheruntil he
has decided on his own.
 Operations Research (T. Y.B.M.S)
310
(Sem. - VI)
d) Every combination of activities determines an outcome which results in a gain at
payments to each player, provided each player is playing uncompromisingly to get a
much as possible. Negative gain implies the loss of same amount.
2. Strategy
In a game in strategic form, a strategy is one of the given possible actions of a player. In a
extensive game, a strategy is a complete plan of choices, one for each decision point of theplaver
The two types of strategy are
1. Pure strategy
2. Mixed strategy
Pure Strategy
If a player knows exactly what the other player is going to do, a
deterministic situation is
obtained and objective function is to maximize the gain. Therefore, the pure
rule always to select a particular course of action. strategy is a decision
Mixed Strategy
If a player is guessing as to which activity is to be
selected by the other on any particular
occasion, a probabilistic situation is obtained and objective
gain. Thus the mixed strategy is a selection among pure function is to maximize the expected
strategies with fixed probabilities.
3. Number of persons
A game is called 'n' person game if the
number of persons playing is 'n'. The person means an
individual or a group aiming at a particular objective.
Two-person, zero-sum game
A game with only two players
(player A and player B) is
game', if the losses of one player are equivalent to the gains of the called a two-person, zero-sum
gains is zero. other so that the sum of their net
Two-person, zero-sum games are also called
represented by a payoff matrix in a rectangular form.
rectangular games as these are usually
4. Number of activities
The activities may be finite or
5.
infinite.
Payoff
A payoff is a'number, also
player, for called utility, that reflects the
whatevef-reason. When the outcome is random, desirability of an outcome to a
probabilities.The expëcted payoff incorporates the player's payoffs are usually weighted with their
The quantitative measure of attitude towards risk.
6.
Payoff matrix satisfaction a person gets at the end of each play is
called a payoir
Suppose` the player A has 'm' activities and the
matrix can be formed by adopting the following rules player B has 'n' activities, Then a payoff
Row designations for each matrix
are the activities available to
Colúrnn designations for each matrix are the plaver A
Cell entry Vij is the activities available to player B
and Bchooses the activity j. payment to player A in A'Spayoff matrix when A chooses the
With a zero-sum, activity i
two-person game, the ceIl entry n the player B's
negative of the corresponding cell entry Vj in the payoff matrix will be
matrices for player A and player B is ultimately zero.player A's payoff matrix so that sum of payoff
7. Value of the game
Vabe of the game is the maximum
the nlavers uses their best strategies. guaranteed game to
It isgenerally denoted by player A
V' and it(maximizing
is unigue plaver) if both
 311
TheoryofGames

Strictly Determined Game

statements are
Agame is strictly determined if it has at least one saddle point. The following
ine about strictly determined games:
Allsaddle points in a game have the same payoff value.
for bot
Choosing the row and column through anysaddle noint gives optimal strategies
players.
entry. A fair gane
The value of a strictly determined game is the value of the saddle point
has value of zero, otherwise it is unfair or biased.
9 Fundamental Principles / Assumptions of Game Theory
When analyzing any game, we make the following assumptions about both players:
Each player makes the best possible move.
possible moVe.
Each player knows that his or her opponent is also making the best
10. Minimax Criterion
to minimize his maximum losses
whenever the
Each player should play in such a way as position.
by the opponent to then improve his
resulting choice of strategy cannot be exploited selection were being announced to the opponent
the
ooSelect astrategy that would be best even if minimum
%oPlayer 1 should select the strategy whose
before the opponent chooses a strategy. payoff to player 1 is the
largest, whereas player 2 should choose the one whose maximum
payoff is
Smallest.

GAMES
9.4 CLASSIFICATION OF
into
All games are classified solved by saddle point method.
Some
These games are normally
Pure strategy games - big.
Dominance Principles also can be applied if matrix order is
times game are
methods for solving a mixed strategy
Mixed strategy games - The different
Dominance Principles
Analytical method
Graphical method
Simplex method best
the method varies. By solving a game, we need to find
For solying these two types, of the game.
and also to find the value
strategies for both the players
GAME
AND ZERO-SUM
9.5 TWO-PERSON
Zero-sum game zero-sumif for any outcome, the
sum of the payoffs to all players is zero.
said to be their interests are
Agame is gain is the other player's loss, so
game, one player's
In a twO-player zero-sum
diametrically opposed. deternministic or probabilistic. The determìnistic games.
games may be
Two-person zero-sum exist in such games. In contrast, the probabilistic games
saddle points and pure strategies taken with the help of probabilities.
Will have
saddle points and mixed strategies are
will have no

|9.6 SADDLE POINT

Definition of Saddle point position of such an element in the payoff matrix, which is
saddle point ofa matrix is the its column.
A the maximum in
minimum in itsrow and
Research -(Sem. - VI)
2I/T.Y.B.M.S.Operations
314 Operations Research (T. Y.B.M.S,) (Sem
Example 9.7.4 MUApril 2017
Following payoff matrix refers to a two player game, player A and player B. Each player has
four strategic options.
(Pay off In As.)
Player B

500 260 200 210

Playèr A -50 -100-40 240
Jl 200 400 160 -20
250 300 100 50

i) Find the Maximin Strategy.

i) Find the Minimax Strategy.
ii) What isthe value of the Game?
Solution:
The row minima and column maxima for the given pay -off matrix are shown below:
B's Strategy
A's Strategy BÊ BII BII BIV Row Minima Maximin
AI 500 260 200 210 200 200
AII -50 -100 -40 240 -100
AIII 200 400 160 -20 -20
AIV 250 300 100 50 50
Column 500 400 200 240
maxima

Minimar 200 Saddle Point

i) The Maximin Strategy or Optimal

ii) The Minimax Strategy or Optimal
Strategy for Player Ais AI or ( 1, 0,0,0)
Strategy for Player Bis BIII or (0,0, 1,0)
ii) The game has a saddle point given by AI
BIII. The value of the game = 200.
Example 9.7.5
Given the following pay-off matrix of a
the players and the value of the game : zero-sum game, determine the optimal strategies tor
A's Strategy
B's Strategy
B B
B3 BA
A1 5
9
A2 6
-3
A3 9 15 10
11
A4 2 8 -6
5
 315
Theory of Games

Solution
maxima.
The pay-off matrix is reproduced here along with row minima and column
Row Minima Maximin
A's B's Strategy
Strategy B B B BA
-4
A1 -4 5
-3 3
A2 2
11
9
A3 1 10
5 -6
2 8 -6
A4
15 10 11
Column
maxima
Saddle Point
Minimax
for Player Ais A or (0,0, 1,0)
i) The Maximin Strategy or Optimal Strategy
The Minimax Strategy or Optimal Strategy for Player Bis B, or( 1,0, 0,0)
ii)
Therefore the value of game =9
are same, equal to 9.
ii) Pay-offs for both the strategies
Example 9.7.6 game strictly determinable?
players. Is the following
Determine the optimal strategies for the
Is it fair?
A'sStrategy
B'sStrategy
B2 B3
B1
3
4
A1 4
6
A2 -5 -2
9
A3 given as follows :
matrix, row minima and column maxima are
Solution: The pay-off Row Minima Maximin
B2 B3
BË
0 3
4
A1 4 -2
6
-2
A2 -5
-5
A3 4
Column
maxima -Saddle Point
Minimax
Optimal Strategy for Player Ais A or (1,0,0,0 )
Strategy or
i) The Maximin Strategy for Player Bis B2 or
(0,1,0,0)
Strategy or Optimal
i) The Minimax strategies are same, equal to zero.
Therefore the value of game =9
for boththe
ii) Pay-offs stricity dertminable
and fai.
Hence, the game is
Example 9.7.7 zero-Sum game, as i ws :
pay-off matrix in respect of atwo-person
You are giventhe B's Strategy
A's Strategy B2 B3 B4 Bs
B) -11
10 -3
9
A1 6 6 12
A2 -6 17
7
A3 14 -10 10 22
-12
A4 6 2
-10
A5
316 Operations Research (T. Y.B.M.S) (Sem. -
VI)
a) Write the maximin and minimax strategies
b) Is it a strictly determinable game?
c) What is the value of game?
d) Is this game a fair one?
Solution : The row minima and column maxima for the given pay - off matrix are shown here
B's Strategy
A's Strategy B1 B B3 B4 Bs Row Minima
10
Maximin
A -3 -8 -11 -11
A2 4 6 0 6 12
A: -2 -6 17 -6
A4 -12 14 -10 10 22 -12
As -10 0 6 2 -10
Column 14 10 22
maxima

Minimax Saddle Point

a) The Maximin Strategy or Optimal Strategy for Player Ais Ag or (0, 1,
0,0,0)
The Minimax Strategy or Optimal Strategy for Player Bis B3 or (0,0, 1, 0 ,0)
b) Yes, since a saddle point exists at AgB3
c) Value of game =0.
d) Yes, since the game value is zero
Example: 9.7.8
Find the optimal strategies for player Xand player Y in the
of the game? following game. What is the value
Player X Player Y
YË Y2
90
Y3
130 160
90
110 130
X3 -20
- 40 180
Soution:The row minima and column maxima for the given pay -off matrix are shown here
Player Y
Player X Row Maximin
Y2
Y3 Minima
90 130
160 90
X2 90 110 130
X3
90
20 -40 180
40
Column 90 130 180
Maxima
Minimax
-Saddle Point
) The Maximin Strategy or
Optimal Strategy for Player Xis X1 ie. ( 1,0,0)
or X2 i.e. (0, 1,0)
 317
Theory of Games

ii) The Minimax Strategy or Optimal Strateoy for Plaver Y is Yi i.e. (1, 0, 0,)
90.
ii) The game has a saddle point given by X, Y, or X Y,. The value of the game

Example: 9.7.9
The following game matrix is given
A's Strategy B's Strategy
B4
BË B2 B3
-3 10
A1 12
11
A2 X 15
17
A3 -6 12

Tohave saddle point at A2B3, we should have

i) Any value for Xbut Y <8
ii) Any values for X and Y
ii)) X < 8 and Y> 8
iv) X > 8 and Y> 8
v) X> 8 and Y<8
justification.
Mark the correct statement with
Solution
B'sStrategy
Row Minima Maximin
B2 B3 B4
A's Strategy BË
-3 10 -3
Aj 12
11 8
X 15
A2
Y 17 -6
-6 12
A3
15 17
Column 12
maxima
-Saddle Point
8
Minimax correct
statement (v) that is X >8 and Y <8 is
Erom the above we can conclude that
Ag B3 as 8.
This will give saddle point

OF DOMINANCE
9.8 PRINCIPLES availob e
person zero-sum game, When there are large number of strategies
In a two large matrix to 2 x 2 order. prior to fnal
mlaso mlee of Dominance can be applied to reduce
strategy or.if saddle point exists it can be reduced to l × 1 order size.
analysis for the optimal point exists but is more useful even when saddle point does
used when saddle
This concept is below :
exists. Principles of Dominance given
not
1, Rule for Rows
aments in a Row are less than or equal to the corresponding elements in another
another
Row is said to be dominated by the Row and can be eliminated from the
Row, then this order of the matrix.
matrix to reduce the
318
Operations Research (T YBMS)
(Sem. - VI)
2. Rule of Columns
If all the elements in a Column are greater than or equal to the
corresponding
another Column, then this Column is said to be dominated by the another Column elements
and can Lin
eliminated from the matrix to reduce the order of the matrix.
3. Rule of Averages
If the average elements of two rows or two columns are
found dominated as per the nule of
Rows /Columns, these can be deleted. Thus matrix can be reduced faster.

Example :9.8.1
For the following two - person, zero-sum game, find the optimal strategies for the two plavers
and the value of the game.

Player B
B B2 B3
A1 11 7
Player A A2 8 -10 -9
A3 10 18 12
If the saddle point exists,
Solution
determine it using the principle of dominance.
Let us first examine if saddle
point exists.
Player B BË B B3 Row Maximin
Minima
A 7 11
Player A 5
A2 -10
-10
A3 10 18 12 10
Column Maxima 10 18 12
Minimax 10 -Saddle Point
The saddle point exists at
A3B,. The Value of the game = 10.
Optimal Strategy for Ais A3 i.e.
(0,0,1)
Optimal Strategy for Bis BË i.e. ((1,0,0)
Principle of Dominance :
Step 1 :Row 3
dominates Row land Row 2 both. Deleting
Player B Rows 1 and 2, we get 10. 18, 12.
B B2 Ba
Player AA3 10 18 12
Step 2 : Column 1
dominates
Column land 2, we get only Column 2 and
a single value, 10, Column 3 both in the reduced
which is the saddle point. matrix. Deleting
Player B
B
Player A A3 10

Therefore, sadale Point exists at A3 B,.

 319
Theory of Games

Example:9.8.2
Use principles of dominance to find the value of the game and saddle point if exists. Is it a fair
game?

Player B
B1 B2 B3
0 -1 1
A|
0 2
Player A Ag
-1 -2 3
A3
Solution:
Step 1: Since the entries in Row 2 (A2 ) are >the corresponding ones in Row l(A) ,Kow
2(A2)dominates Row l (A). So delete Row 1(A).
Reducing the Above Game by Dominance
Player B
BË B2 B3
Player A 0 2
A
-1 3
A3
ones in Column (B) as
Step 2 : Since the entries in Column (B2 ) are< the corresponding
well as Column (B3). So delete
well as Column (B3 ), Column (B2) dominates Column (B1) as
Column (B1 ) and Column (B3 ).
Reducing the Above Game by Dominance
B
A 0
Player A -2
A3
Row 3 (A3 ),Row
Step 3: Since the entries in Row 2 (A ) are >the corresponding ones in
2 (A2 )dominates Row 3 (A3). So delete Row 3 (A3).
Reducing the Above Game by Dominance
B2
0
A2
Therefore this is a Fair Game.
The saddle point exists at AB2. The Value of the Game =.0.
Optimal Strategy for Ais Az i.e. (0, 1,0)
Optimal Strategy for Bis B2 i.e. (0, 1,0)

Example : 9.8.3
if
For the following matrix, apply Principle of Dominance to reduce matrix order. Determine.
the saddle point exists.
Player B
BË B2 B3
Player A A1 10 -6
4 -5
A2
A3 7 8
 320 Operations Research(T.Y.B.M.S.)
(Sem. -VI)
Step 1 : Row 3 ( A3 )dominates Row 2(A) ) as all elements of A2 are less than or
elements of A3.Deleting Rows 2 (A ),we get following reduced matrix. equal to
tt
mi
Player B
BI B2 B3
Player A
Ai 10 -6
A3 7

xa
Step 2: Column 3 (B)dominates Column 2 ( B2.) as all elements of B2 are less than o
equal to elements of B,. Deleting Column 2 (B ), we get following reduced matrix.
nd
Player B
Player A
BÊ B3
Aj 10 -6

Pla
A3 7
Saddle point does not exist
No row dominates other row. No column dominates other
column.
So

9.9 CONCLUSION
In this chapter, students have studied basic
understand method to find Saddle Point and valuedefinitions, terminology and theory required to
of the game for deterministic Pure Strategy
Two Person Zero-Sum Game. It also discusses how
to make use of dominance principles to
Large matrix to 1xl order of the matrix to reduce
can be reduced to 2 x 2 order if saddle point determine the saddle point (if exists) otherwise matrix
does not exists.

9.10 PROBLEMS FOR PRACTICE

9.10.1 Given the following pay-off matrix of a
for the players and the value of the
game:
zero-sum game, determine the optimal strategies
1.

A's Strategy B's Strategy

B1 B2 B3
Al 80 40 70
A2 50 -50 30
A3 60 -20 20
2

A's Strategy B's Strategy

" BË B2
Aj 270
B3
210 220
-90 -30 250
A3 350 180 -10
 321
Theory of Games

3.
X's Strategy Y's Strategy
YË Y2 Y3 Y4

X 4 -5 2

4 5 3

-2 2
X3 6 -1

4 -2 6 3
X4

4.

X's Strategy Y's Strategy

YË Y2 Y Y4

220 170 140 370

XË
160 100 120
X2 270

420 40 120 70
X3
60 130 20
X4 -30

zero-sum game, as follows :

9.10.2 Youare given the pay-off matrix in respect of a two-person
B's Strategy
A's Strategy
B2 B3 B4 B
BË
-1 -6 9
11 12
Aj
8 0 14
A2 6
-2 -4 19
A3 9

16 -8 23
A4 9
0 4
As -5

a) Write the Maximin and Minimax Strategies.

b) Is it a strictly determinable game?
c) What is the value of the game?
d) Justify, why this game is a fair one ?

9.10.3 The following game matrix is given

B's Strategy
A's Strategy
B B2 B3 ,B4
-3 6 X
6
Aj
3 -4
A2
16 11 12
10
A3
9 -5 6
A4
322 Operations Research2(T. Y.B. M.S.) (Sem.
.- VI)
To have saddle point at A3B1, we should have :
i) Any value for X but Y < 10
ii) Any values for X and Y
iii)) X> 10and Y > 10
iv) X>10 and Y< 10
v) X< 10 and Y>10
Mark the correct statement with justification.

9.10.4 For the following two - person, zero-sum game, find the optimal strategies for the hun
players and the value of the game.
A's Strategy B's Strategy
bË by b3 b4 bs
2 3 5 6

10 12 11 14 15
3 4 7 5
4 5 3
6 3 1
If the saddle point exists, determine it using the principle of
dominance.
9.10.5. Use principle of dominance to determine, if the saddle
politician l will gain from politician 2? point exists. How many votes

Form of the payoff table for politician 1 for the

political campaign problem
Total Net Votes Won by Politician 1 (in
Units of 1,000 Votes)
Politician 2
Strategy
1
2 4
Politician 1 2 1
0
1
1

9.10.6 Use principle of dominance to

2,x 2 matrix. Solve the game given below in Table after
reducing It

Player B
1 2 3
1 1 2
Player A 2 6 2
3 L 5 6