GAME THEORY

R.RAVIKANTH M.B.A ASSO.PROFESSO DEPARTMENT OF BUSINESS ADMENSTRATION NIT COLLEGE::NARASARAOPETA

What is a Game?
A game is a situation where the participants payoffs depend not only on their decisions, but also on their rivals decisions. This is called Strategic Interactions:
My optimal decisions will depend on what others do in the game.

A Game
Four elements to describe a game:
players; rules: when each player moves, what are the possible moves, what is known to each player before moving; outcomes of the moves; payoffs of each possible outcome: how much money each player receive for any specific outcome.

GAME THEORY MAXIMIN Principles : for player a the minimum values in each row represents the least gain to him, if he chooses his particular strategies. These are written in the matrix by row minima. He will then setup the strategy that gives the largest gain among the row minimum values. This choice of player a is called the maximum principle and the corresponding gain is called the maximin value of the game. Minimax principles: for player b who is assumed to be the looser the maximum value in each column o f the course of action loss to him . If he chose his particular strategies. These are written in the pay off matrix by column maxima. He will their selut the strategies that gives the minimum loss among the column maximum values. This choice of players b is called the minimax principle and the corresponding loss is the minimax value of the game.

PROBLEM: 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 cost to the company are given for every pain of strategy choice Union Company strategies strategi es 1 1 2 3 4 20 25 40 -5 2 15 14 2 4 3 12 8 10 11 4 35 10 5 0

What strategies will the two a drop? Also determine the value of the game.

To find the minimax and maximin values Union Company strategies strategi es 1 1 2 3 4
COLUMN MAXIMIN

ROW MINIMUM 4 35 10 5 0 35 12 8 2 -5
MAXIMUM VALUE

2 15 14 2 4 15

3 12 8 10 11 12

20 25 40 -5 40

(MINIMU M VALUE)

No saddle point (minimum value = maximum value) Minimum value = Maximum value =12= value of game

A saddle point is the combination of strategies in which each player can find the highest possible payoff assuming the best possible play by the opponent. An equilibrium point (also called a Nash equilibrium point) is the combination of strategies in which no player has any benefit from changing strategies assuming that the opponent (or opponents) do not change strategies. Every saddle point is an equilibrium point but not every equilibrium point is a saddle point. A saddle point occurs when each player is achieving the highest possible payoff and thus neither would benefit from changing strategies if the other didnt also change - which is why it is also called an equilibrium point. However, there are equilibrium points in variable sum games where the players are not achieving the best possible payoff (so they arent saddle points) but neither will benefit by changing their strategy assuming the other doesnt also change their strategy which is why they are called equilibrium points.

RULES TO DEVELOPMINE SADDLE POINT

Saddle point is the pay off value that represents both minimax and maximum value of the game. 1. Select the minimum (lowest) element in each row of the payoff matrix and write there under row minimum heading. Then select the largest among these elements and enclose it in a rectangle 2. Select the maximum (largest) element in each column of the pay off matrix and write there under column maxima hedding then select the lowest among these elements and enclose it in a circle 3. Find out the elements (s)that is same in the circle as the well as rectangle and mark the position of such element in the matrix. This element represents the value of the game and is called the saddle or equilibrium point.

The rules (principles) of dominance: the rules of dominance are used to reduce the size of the matrix. These rules help in deleting certain rows and/or columns of the payoff matrix that are inferior to at least one of the remaining rows and / or column, in terms of payoffs to both the players. Rows and/or column once deleted can never be used for determining the optimum strategy for both the players. The rules of dominance are especially used for the evaluation of two-person zero-sum games without a saddle point. Certain dominance principles are stated as follows: 1. For player B, who is assumed to be the loser, if each element in a column, say C is greater than or equal to the corresponding element in another column say Cs in the payoff matrix then the column Cr is said to be dominated by column Cs and there fore, column Cr can be deleted from the payoff matrix in other words , player B will never use strategy that corresponds to column Cr because he will loose more b choosing such strategy. 2. For player A, who is assumed to be the gainer, if each element in a row , say Rr is less than or equal to he corresponding element in another row, say Rs in the payoff matrix in other words player A will never use the strategy corresponding to row Rr because he will gain less by choosing such a strategy. 3. A strategy say k can also be dominated if it is inferior to an average of two or more other pure strategies in this case, if the domination is strict, then strategy k can be deleted. If strategy K dominates the convex linear combination of some other pure strategies then one of the pure strategies involved in the combination may be deleted. The domination would be decided as per rules 1 and 2 above.

Note: Rules of dominance discussed are used when the payoff matrix is a profit matrix for

Problem: a company is currently involved in negotiations with its union on the upcoming wage contract. Positive signs in table represent wage increase while negative sign represents wage reduction . What are the optimal strategies for the company as well as he union? What is the game value? (conditional costs to the company rs in lakes) UNION STRATEGIES COMPANY STRATEGIES C1 C2 C3 C4 U1 .25 .20 .14 .30 U2 .27 .06 .12 .14 U3 .35 .08 .05 .19 U4 -.02 .08 .03 .00

SOL: Suppose company is the gainer player and union is the looser player. Transposing payoff matrix because companys interest is to minimize the wage increase while unions interest is to get the maximum wage increase. COMPANY STRATEGIES C1 U1 UNION STRATEGIES U2 U3 U4 0.25 0.27 0.35 -0.02 C2 0.20 0.06 0.08 0.08 C3 0.14 0.12 0.15 0.13 C4 0.30 0.14 0.19 0.00

In this payoff matrix strategy u4 is dominated by strategy u1 as well as u3. after deleting this strategy, we get

COMPANY STRATEGIES

C1
U1 UNION STRATEGIES U2 U3 0.25

C2
0.20

C3
0.14

C4
0.30

0.27
0.35

0.06
0.08

0.12
0.15

0.14
0.19

A) Companys point of view strategy C1 is dominated by C2 while C4 is dominated C3. deleting strategies C1 and C4 we get. B) Agin strategy U2 is dominated U1 and is, therefore deleted to give A) COMPANY STRATEGIES COMPANY STRATEGIES
U N I O N S T R A T E G I E S

C2 U1 U2 U3 0.20 0.06 0.08

C3 0.14 0.12 0.15

U N IU O N S T R A T E R I E S

C2 U1 U3 0.20 0.08

C3 0.14 0.15

Company strategies C2 Union strategies U1 U3 0.20 0.08 C3 0.14 0.14 0.15 0.08 maximum value row minimum

Column Maximum

0.20

0.15 minimum value

Maximum value minimum value

No saddle point
To follow the dominance principles: company strategies Union Strategies U1 U3 C2 0.20 0.08 C3 0.14 0.15 probability
=(0.15-08)/((0.20+0.15)-(0.08+0.14)) =0.07/0.13 = 0.538 =(0.20-0.14)/((0.20+0.15)-(0.08+0.14))

=0.06/0.13 = 0.461
=(0.15-0.14)/((0.20+0.15)-(0.08+0.14)) =(0.20-0.08)/((0.20+0.15)-(0.08+0.14))

=0.01/0.13 =0.076

=0.12/0.13 =0.923

Optimal strategies for the company:(0,0.076,0.923,0) Optimal strategies for the union : (0.538,0,0.461,0) Value of the game V = 0.538*.20+0.461*0.08 = 0.1076+0.03688 =0.14448

The optimal strategy mixture for each player may be determined by assigning to each strategy its probability of being chosen. The strategies, so determined, are called mixed strategies. This is because they are a probability combination of the available choices of strategy. The value of game obtained by the use of mixed strategies represents the least payoff, which player A can expected to win and the least which player B can lose. A mixed strategy game can be solved by different solution methods such as: 1. ALGEBRAIC METHOD 2. MATRIX METHOD 3. ARITHMETIC METHOD NOTE: For solving a 282 game, without a saddle point, the following formula is also used. If payoff matrix for player A is given by: Player B Player A a11 a12 a21 a22

Then the following formula are used to find the value of game and optimal strategies:
a22-a21 a22-a12

P1= ------------------, 1= ------------------a11+a22-(a12+a21) a11+a22-(a12+a21) Where p2 = 1-p1, q2=1-q1 a11a22-a12a21 And V= --------------------------a11+a22-(a12+a21)

ARITHMETIC METHOD:
The arithmetic method provides an easy method for finding optimal strategies for each player in a payoff matrix of size 2*2, without saddle point. The steps of this method are as follows: 1. Find the difference between the two values in the first row and put it against the second row of the matrix neglecting the negative sign. 2. Find the difference between the two values in the second row and put it against first row of the matrix, neglecting the negative sign. 3. Repeat steps 1 and 2 for the two columns also. The values obtained by swapping the difference represent the optimal relative frequencies of play for both players strategies. These may be converted to probabilities by dividing each of them by their sum. The value of the game can be obtained by applying any of the methods discussed earlier. Note: The arithmetic method should not be used to solve a 2 *2 game that has a saddle point because the method yields an incorrect answer.

Problem: Two competitors are competing for the market share of the similar product. The payoff matrix in items of their advertising plan is shown below. competitor B Competitor No Medium Heavy A advertising advertising advertising No advertising Medium advertising Heavy advertising 10 13 16 5 12 14 -2 15 10

Suggest optimal strategies for the two forms and the net outcome there of.

sol: applying rules of dominance to delete first column dominated by second column and these first row dominated by second as well as third rows from the payoff matrix, we obtain the following reduced payoff matrix.

firm B firm A Medium advertising Heavy advertising Medium Heavy advertising advertising 12 14 15 10

As the payoff matrix does not have a saddle point, firms will use mixed strategies. Applying arithmetic method as explained earlier to get optimal mixed strategies for both the firms, the results are: firm B

14-10=4 p(A2)=4/(4+3) =4/7 15-12 = 3 p(A3)=3/(4+3) =3/7

= 15-10 =5 p(B2)=5/5+2 = 5/7 =14-12 =2 p(B3)=2/5+2 =2/7

Expected gain to firm A 1. 12*(4/7)+14(3/7) = 90/7, firm B adopt B2 2. 15*(4/7)+10(3/7) = 90/7, firm B adopt B3

Expected gain to firm B 1. 12*(4/7)+15(3/7) = 90/7, firm A adopt A2 2. 14*(4/7)+10(3/7) = 90/7, firm A adopt A3

The end

MATRX METHOD:
if the game matrix is in the form of a square matrix, then the optimal strategy mix as well as value of the game may be obtained by the matrix method. The solution of a two-person zero-sum game with mixed strategies with a square payoff matrix may be obtained by using the following formula: [1 1] Padj
Player As optimal strategy = ..... [1 1] Padj 1
1 [1 1] Pcof

Players Bs optimal strategy = .....

[1 1] Padj 1
1

Value of the game = players As optimal strategies * payoff matrix Player Bs optimal strategies Padj= adjoint matrix .

Pcof=cofactor matrix . Player As optimal strategies are in the form of a row vector and Bs optimal strategies are in the from of a column vector. This method can be used to find a solution of a game with size of more than . how ever in rare cases the solution violates the non-negative condition of probabilities, i.e. Pi0,qj0,although the requirement P1+P2+P3+-------------+Pm=1 or q1+q2+q3+-------------qn =1met.

Problem: solve the following game after reducing it to a 2*2 game PALYER B PLAYER A B1 B2 B3 A1 1 7 2

A2

A3 5 1 6 SOL:INNTHE GIVEN GAME MATRIX THE THRID ROW IS DOMINATED BY THE SECOND ROW AND IN THE REDUCED MATRIX SECOND COLUMN IS DOMINATED BY THE FIRSTCOLUMN . SO , AFTER ELIMATION OF THE THIRD ROW AND THE THIRD COLUMN THE GAME MATRIX BECOMES: PLAYERA A1 A2 PLAYER B B1 1 6 7 2

B2

FOR THIS REDUCED MATRIX , LET US CALCULAE Padj AND Pcof as given below: Padj = 2 -6 -7 Pcof 1 = -7 1 2 -6

[1 1] Padj Player As optimal strategy = ..... [1 1] Padj 1

1

[-4 -6] [4 6] =.. =. -10 10

[1 1] Pcof Players Bs optimal strategy = ..... [1 1] Padj 1

1

= [-5 -5]/-10
=[5 5]/10 Optimal solutin can also be broken down into the optimal strategy mixture for player B as q1 =5/10=1/2and q2=5/10=1/2 where q1 and q2 represent the probabilities of player Bs using his strategies B1 and B2 reprectively. Hence: Value of the game V: 2/5 3/5 1 7 1/2 6 2

= 4

Algebraic method:
This is method to determine the probability of using of using different strategies by players A and B. this method becomes quite lengthy when a number of strategies for both the players are more than two. Using the following results the values of p1,p2,q1,q2 and value of game v can be calculated as follows: P1+p2=1 P1=1-p2 q1+q2=1 q1=1-q2 Alternative methods: For players A and B a22-a21 P1= ------------------a11+a22-(a12+a21) Where p2 = 1-p1, q2=1-q1 a11a22-a12a21 And V= --------------------------a11+a22-(a12+a21) , a22-a12 ------------------a11+a22-(a12+a21)

q1=

Problem: solve the game whose payoff matrix is given below:

Player B
P L A Y E R A

B1 A1 A2 3 3

B2 2 4

B3 4 2

B4 0 4

A3
A4

4
0

2
4

4
0

0
8

It is clear that this game has no saddle point . Therefore, we try to reduce the size of the given payoff matrix by using dominance principles: 1. From player As point of view, the first row is dominated by the third row. By deleting the first row. 2. From player Bs point of view, the first column is dominated by the third column. By deleting the first column

Player B
P L A Y E R A

B2 A2 A3 A4 4 2 4

B3 2 4 0

B4 4 0 8

Now it may be noted that none of the pure strategies of players A and B in inferior to any of their other strategies. How ever, the average of payoff due to strategies B3 and B4 {2+4/2=3.4+0/2=2,0+8/4=4}=(3, 2, 4) is superior to be payoff due to strategy B2 of player B. thus strategy B2 may be deleted from the matrix. The new matrix so obtained is: Player B
P L A Y E R A

B3

B4

A2
A3 A4

2
4 0

4
0 8

Again in the reduced matrix , the average of the payoffs due to strategies A3 and A4 of player A1 i.e {(4+0)/2=2,(0+8)/2=4}=(2,4) is the same as the payoff due to strategy A2. therefore , player A will gain the same amount even if the strategy A2 is never used. Hence after deleting the strategy A2from the reduced matrix the following new reduced 2*2 payoff is obtained. This game has no saddle point list player A Player B choose his strategies A3and A4 with probability p1 and p2 respectively, such that P B3 B4 L p1+p2=1. also let player B choose his A3 4 0 AYEAR strategies with probability q1 and q2 A4 0 8 respectively. Such that q1 +q2=1 . Since both players want to retain their interests unchanged therefore, we may write: 4p1+0p2=0p1+8p2 4q1+0q2=0q1+8q2 4p1=8p2 4q1=8q2 P1+p2=1 q1+q2=1 P2=1-p1 q2=1-q1 , 4q1=8(1-q1) 4P1=8(1-p1) 4q1=8-8q1,4q1+8q1=8 4p1=8-8p1 12q1=8,q1=8/12 4p1+8p1=8 q1=2/3, q2=1-q1 12p1=8 q2=1-2/3 , q2=1/3 P1=8/12 q1=2/3,q2=1/3. P1=2/3, p2=1-p1=1-2/3 P1=2/3,p2=1/3

We find hat than the optimal strategies of player A and player B in the original game we (0,0, 2/3,1/3) and (0,0, 2/3,1/3) respectively. The value of the game can be obtained by putting value of p1 or q1 in either of the expected payoff equation above. That is : Expected gain to A 4p1+0p2=4(2/3) =8/3 Expected gain to B 4q1+0q2=4(2/3) =8/3