UNIT II-CHAPTER 2 GAME THEORY

y Introduction y Characteristics of Games Theory y Definitions y Minimax Criteria y Saddle Point y Rectangular Games without Saddle Point y Solution of m x n games by LP Method y Principles of Dominance y Applications of Game Theory

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Introduction
y Game is defined as an activity between two or more persons involving activities by each person according to a set of rules, at the end of which each person receives some benefit or satisfaction or suffers loss (negative benefit). y The set of rules defines the game. y Game theory is a type of decision theory in which one s choice of action is determined after taking into account all possible alternatives available to an opponent playing the same game, rather than just by the possibilities of several outcomes.
6/30/2011 KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Introduction
y The game theory finds use in everyday life situations as

life is a series of struggles & competitions.

y The game theory is fundamentally based upon the

minimax or maximin criterion given by J. Van Neumann who is called the father of game theory.
y The criterion implies that each player will act so as to

maximize his minimum gain or minimize his maximum loss. Here it is assumed that each person will act rationally.
6/30/2011 KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Characteristics of Game Theory

y The various types of games can be classified on the basis of the

following characteristics.
i.

Chance or strategy: If in a game, activities are determined by skill, it is said to be a game of strategy. If they are determined by chance, it is a game of chance. Number of Persons: A game is called a n-person game if the number of persons playing is n. The person means an individual or a group aiming at a particular objective. Number of Activities: These may be finite or infinite.

ii.

iii.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Characteristics of Game Theory

iv.

v.

vi.

Number of alternatives (choices) available to each person: In a particular activity, choices may be finite or infinite. A finite game has a finite number of activities, each involving a finite number of alternatives. Otherwise the same is said to be infinite. Information to the players about the past activities of other players: Completely available, partly available or not available at all Pay off: A quantitative measure of satisfaction a person gets at the end of each play is called a pay off. If Vi = o , where Vi is the payoff to the player Pi ( 1 i n ) then the game is said to be a zero-sum game.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
y Competitive Game: A competitive situation is called a competitive

game if it has the following 4 properties.

 There are finite number (n) of competitors called players such that

n 2. In case n=2, it is called a 2 person game and in case n > 2, it is referred to as n-person game.

 Each player has a list of finite number of possible activities.  A play is said to occur when each player chooses one of his activities.

The choices are assumed to be made simultaneously i.e. no player knows the choice of the other until he has decided on his own. be points, money or anything else whatsoever) which results in a gain of payments (+ve, -ve, zero) to each player, provided each player is playing uncompromisingly to get as much as possible. Negative gain implies the loss of same amount.
KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

 Every combination of activities determines an outcome (which may

6/30/2011

Definitions
y Zero-sum & Non-zero-sum Games: Competitive games are classified according to the number of players involved i.e. as a two-person game, three-person game etc. Another distinction is between zero-sum games and non-zero-sum games. If the players make payments only to each other i.e. the loss of one is the gain of others, and nothing comes from outside, the competitive game is said to be zero-sum. Mathematically, it is represented as Vi = o y A game which is not a zero-sum is called a non zero-sum game. Most of the competitive games are zero-sum games.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
y Strategy: A strategy of a player has been defined as a rule for decision-

making in advance of all the plays he decides the activities he should adopt.
y The strategy may be of two kinds.

a) Pure Strategy: If a player knows exactly what the other player is going to do, a deterministic situation is obtained and the objective function is to maximize the gain. Therefore, a pure strategy is a decision rule always to select a particular course of action. b) 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 the objective function is to maximize the expected gain.
6/30/2011 KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
y Thus the mixed strategy is a selection among pure strategies with fixed probabilities. y Mathematically, a mixed strategy for a player with m ( 2) possible courses of action is denoted by the set S of m nonnegative real numbers whose sum is unity, representing probabilities with which each course of action is chosen. If xi (i = 1, 2, - - m) is the probability of choosing the course i, then

S= (x1, x2, x3 - - - xm) Subject to x1 + x2 + - - xm =1 And x1 o, x2 0, - - xm

6/30/2011 KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
y Two-persons, zero-sum Games [Rectangular Games]:

A game with only 2 players is called a two-person, zerosum game if the losses of one player are equivalent to the gains of the other, so that the sum of their net gains is zero.
y Two-person, zero-sum games are also called rectangular games as they are usually represented by a pay off matrix in rectangular form.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
y Pay off Matrix: Suppose the player A has m activities and the player B

has n activities then a payoff matrix can be formed by adopting the following rules.
y Row designation of each matrix are activities available to player A y Column designations for each matrix are activities available to player B. y Cell entry Vij is the payment to player A in As pay off matrix when A

chooses the activity i and B chooses the activity j.

y With a zero-sum, two-person game, the cell entry in the player B s pay

off matrix will be negative of the corresponding cell entry Vij in the player As pay off matrix so that the sum of pay off matrix for player A and player B is ultimately zero.
6/30/2011 KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Definitions
Player As pay off matrix Player B 1 1 2 Player A i Vi1 Vi2 Vij - Vin V11 V21 2 --j --n Vin

V12 - - - - - - Vij - V22 -

V2j - - V2n

Vm1

Vm2

- -

Vmj - - - Vmn

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Minimax (Maximin) Criterion and Optimal Strategy

y The minimax criterion of optimality states that if a player lists the worst possible outcomes of all his potential strategies, he will choose that strategy to be most suitable for him which corresponds to the best of these worst outcomes. Such a strategy is called an optimal strategy. y This can be illustrated with the help of the following example.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Concept Problem
y Table below illustrates a game, where competitors A & B are assumed to be equal in ability & intelligence. A has a choice of strategy 1 & strategy 2 while B can select strategy 3 or strategy 4.
Competitor B

Strategy Strategy +4 +3

Strategy +6 +5

Competitor A

Strategy

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Concept Problem
y Both competitors know the pay offs for every possible strategy.

The game favours A since all values are +ve. Values that favour B would be -ve. Based upon these conditions, game is biased against B. However, since B must play the game he will play to minimize his losses. y The various possible strategies for the two competitors are
 A wins the highest game value if he plays strategy 1 all the time since

it has higher values than strategy 2  B realizes this situation and plays strategy 3 in order to minimize his losses since the value of 4 in strategy 3 is lower than the value of 6 in strategy 4.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Concept Problem
y The game value is 4 since A wins 4 points while B losses 4 points

each time the game is played, the game value is the average winnings per play over a long number of plays. y The above is a zero-sum game since A wins as much as B loses. y From the above we can conclude that
 The strategy that A should use is one that ensures that his

average gain per play is at least equal to the value of the game (maximizing his minimum gains)
 The strategy that B should use is one that his average loss per

play is no more than the value of the game (minimizing his maximum losses).

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Saddle Point (Equilibrium Point)

y The concept of saddle point is illustrated with the help of the following example.

Player B P
Player A

Q 3 4 3 4

Minimum of row -3 -2 2
2 [Maximin & Minimax]

L M N Maximum of column

-3 -2 2 2

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Saddle Point (Equilibrium Point)

y Player A would gain (-3) if uses strategy L, (- 2) if he uses strategy M &

(+2) if he uses strategy N. So he will play strategy N as it will maximize his minimum gain. This strategy is maximin strategy and his corresponding gain is called the maximin value of the game. Player B, on the other hand, wants to minimize his losses. If he plays strategy P, he can lose no more than max (-3, -2, 2) = 2 regardless of As selection. If he plays his second strategy Q, he stands to lose max (3, 4, 3) = 4. He will, therefore, select that strategy that minimizes his maximum loss. So he chooses strategy P and his max loss will be (2). This is called minimax value of the game. In the instant case, minimax value = maximin value. When the two are equal, the corresponding pure strategies are called optimal strategies and the game is said to have a saddle point or equilibrium point. Saddle point is the number which is lowest in its row and highest in its column.
KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

6/30/2011

Concept Problem 1
y Find the saddle point

Player B X P Player A Q R Maximum of column 1 -9 0 Y 13 5 -3 Z 11 -11 13 Minimum of row

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Concept Problem 2
Find the saddle point
Player B X P Player A Q R Maximum of column -8 6 5 -7 -6 6 3 Y -4 Z 8 Minimum of row

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Rectangular Games without Saddle Point

y In cases where there is no saddle point, players will resort to

mixed strategies.

y In a 2 x 2 game, the following method provides an easy way of

finding the optimum strategies for each player. It consists of the following steps. column 2, ignoring sign. column 1, ignoring sign.

y Step 1: Subtract the two digits in column 1 and write them under y Step 2: Subtract the two digits in column 2 and write them under y Step 3: Similarly proceed for 2 rows. These values are called

oddments. They are the frequencies with which the players must use their courses of action in their optimum strategies.
KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

6/30/2011

Concept Problem 1
y In a game of matching coins, player A wins Rs 2 if there are 2 heads, wins nothing if there are two tails & loses Rs 1 when there is one head and one tail. Determine the payoff matrix, best strategies for each player and the value of game to A.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y The pay off matrix for A will be
Player B H Player A H T Oddments 2 -1 1 [= 0.25] T -1 0 3 [ = 0.75] Oddments 3 [ = 0.75] 1 [ = 0.25]

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y Thus for optimum gains, player A should use strategy H for 25% of the

time and strategy T for 75% of the time while player B should use strategy H 25% of the time and strategy T 75% of the time. y To obtain the value of the game, we can use either As oddments or B s oddments.
y Using A s oddments:

B plays H, value of game = V = {1 x 2 3 x 1} / {3 + 1} = -1 / 4 B plays T, V = [1 x -1 + 3 x 0] / [3 + 1] = -1 / 4 y Using B s oddments: A plays H, V = [1 x 2 1 x 3] / [3 + 1] = -1 / 4 A plays T, V = [-1 x 1 + 0 x 3] / [3 + 1] = -1 / 4

y Thus the final solution of the game is

A (1, 3) B (1, 3) V = - 1 / 4
y This is the value of the game to A, i.e. A gains Rs (-1 / 4) i.e. he loses Rs

1/4 which B, in turn gets.

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution of m x n games by LP (Simplex method)

y The procedure to solve the game by simplex method is described below by means of an example. y Solve the following 3 x 3 games by simplex method
Player B I Player A I II III II III

3 -3 -4

-1 3 -3

-3 -1 3

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y Step 1 : First apply Minimax (Maximin) criteria to find the value of the

game
Row Min

3 -3 -4
Column Max 3

-1 3 -3
3 Minimax =3

-3 -1 3
3

-3 -3 -4 Maximin = -3

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y Since maximin value is -3, the value of the game may be negative or

Zero as -3< v <3 y A constant C is added to all the elements of the matrix which is at least equal to the negative of the maximin value. y i.e., C 3; let c = 5, then the matrix can be rewritten as
Player B I Player A I II III II III

8 2 1

4 8 2

2 4 8

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y Players B s LPP is y Maximize , y0 = Y1 + Y2 + Y3 Subject to

8Y1 + 4Y2 + 2Y3 1 2Y1 + 8Y2 + 4Y3 1 Y1 + 2Y2 + 8Y3 1 Y1, Y2, Y3 0 y Step 2 : Introduce slack variables and construct the simplex table 8Y1 + 4Y2 + 2Y3 + S1 = 1 2Y1 + 8Y2 +4Y3 + S2 = 1 Y1 + 2Y2 + 8Y3 +S3 = 1
KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

6/30/2011

Solution
CJ = 1 1 1 0 0 0

BV S1 S2 S3

CB 0 0 0 y0 = 0

YB 1 1 1

Y1 8 2 1 -1

Y2 4 8 2 -1

Y3 2 4 8 -1

S1 1 0 0 0

S2 0 1 0 0

S3 0 0 1 0

Min Ratio 1/8 1

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
CJ = 1 1 1 0 0 0

BV Y1 S2 S3

CB 1 0 0

YB 1/8 3/4 7/8

Y1 1 0 0 0

Y2 1/2 7 3/2 -1/2

Y3 1/4 7/2 31/4 -3/4

S1 1/8 -1/4 1/8 1/8

S2 0 1 0 0

S3 0 0 1 0

Min ratio 1/2 3/14 7/62

y0 = 1/8

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
CJ = 1 1 1 0 0 0

BV Y1 S2 Y3

CB 1 0 1

YB 3/31

Y1 1

Y2 14/31

Y3 0

S1 4/31

S2 0

S3

Min ratio -1/31 3/14 14/31 11/196 4/31 3/31 7/12

11/31 0 7/62 0 0

196/31 0 6/31 -11/31 1 0

-6/31 1 -1/62 0 7/62 0

y0 = 13/62

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
BV Y1 Y2 Y3 CB 1 1 1 YB 1/14 Y1 1
Y2 Y3 0 1 0 0 0 1 0 S1 1/7 -3/98 -1/98 5/49 S2 -1/14 31/196 -3/98 11/196 S3 0 -1/14 1/7 1/14 Min ratio

11/196 0 5/49 0
0

y0 = 45/196

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

Solution
y y y y y y y y y

Solution for B s Problem is y1 = Y1/y0 = 1/14 / 45/196 = 14/45 y2 = Y2/y0 = 11/196 / 45/196 = 11/45 y3 = Y3/y0 = 5/49 / 45/196 = 20/45 The optimal strategies for player A are given by duality rules x0 = y0 = 45/196 X1 = 4 = 5/49 X2 = 5 = 11/196 X3 = 6 = 1/14

y x1 = X1/x0 = 20/45 y x2 = X2/x0 = 11/45 y x3 = X3/x0 = 14/45 y Therefore V = [1/y0] C = [196/45] -5 = -29/45 y Value of the game = -29/45 [for B] y Value of the game for A = 29/45.
KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS

6/30/2011

6/30/2011

KOPPAR & ASSOCIATES, CHARTERED ACCOUNTANTS