Question

1.31 The third column of the matrix A-8 4 12 4 3 is dominated by a convex combination. Reduce the matrix and solve the game. 1.32 Four army divisions attack a town along two possible roads. The town has three divisions defending it. A defending division is dug in and hence equivalent to two attacking divisions. Even one division attacking an undefended road captures the town. Each commander must decide how many divisions to attack or defend each road. If the attacking commander captures a road to the town, the town falls. Score 1 to the attacker if the town falls and -1 if it doesn't. (a) Find the payoff matrix with payoff the attacker's expectation of winning the town (b) Find the value of the game and the optimal saddle point. a4 аз аз 1.33 Consider the matrix game A a1 a a , where a1 < 42 <<as a a2 a4 a3 Use dominance to solve the game. 1.34 Aggie and Baggie are fighting a duel each with one lemon meringue pie starting at 20 paces. They can each choose to throw the pie at either 20 paces, 10 paces, or 0 paces. The probability either player hits the other at 20 paces is 3; at 10 paces it is and at 0 paces it is 1. If they both hit or both miss at the same number of paces, the game is a draw. If a player gets a pie in the face, the score is-1, the player throwing the pie gets +1. Set this up as a matrix game and solve it. 1.35 Consider the game with matrix -2 35-27 5 3 2-1 Someone claims that the strategies X* = (, 0, , 0) and Y* = (0, (a) Is that correct? Why or why not b) Ifx1 33, 0, 3) is optimal and (A)3 find , 0) are optimal. , , 긁, 0, 끓) is optimal and u(A)--26,

Need solution for 1.35

Answer 1

(1.35)

1. Saddle point testing Players Player B B1 B2 B3 B4 41 2 3 5 -2 42 3 -4 1 -6 A353 2 1 A41-1-322 Player A We apply the maximin (minimax) principle to analyze the game Player B Row B) 3 Minimum I-2] 3 5 2 2] 3 -4 1 6 5 3 1 -1 3 2 (2) .A PlayerA -5 -3 Column 3 3 5 (2) Maximum Select minimum from the maximum of columns Column MaxiMin (2) Select maximum from the minimum of rows Row MiniMax [2]

Here, Column MaxiMin Row MiniMax .. This game has no saddle point. 2. Dominance rule to reduce the size of the payoff matrix Using dominance property Player B 3, B2 B3 B4 A 2 3 5 -2 A2 3 -4 1 -6 A31-532-1 A4 -3 2 2 Player A column-3 2 column-4, so remove column-3 Player B B1 B2 B A1 2 3 2 A2 3 -4 6 A35 3 -1 A41-1-32 Player A

So the value of the game lies between -2 and 2 It is possible that the value of game may be negative or zero Thus, a constant k is added to all the elements of pay-off matrix. Let k 2, then the given pay-off matrix becomes Player B B1 B2 B4 A10 5 0 42 5 2 4 A31-351 44 11 4 Player A Let V value of the game Pi:P2:P3 p4 probabilities of selecting strategies A,A2, A3, A4 respectively 11. q2- 93 - probabilities of selecting strategies B, B2. B4 respectively Player B B1 B2 B4 Probability Player A 3 5 1 1 1 4 Probability 1 42 43

player A's objective is to maximize the expected gains, which can be achieved by maximizing v, i.e., it might gain more than V if company B adopts a poor strategy The expected gain for player A will be as follows 5P1-2P2+ 5P3 -P42 Dividing the above constraints by V, we get P2 To simplify the problem, we put In order to maximize V, player A can Minimize Zp x1 x2 x3 + x4

subject to 5x1-2x2 5x3-X,2 1 and xx X 20 player B's objective is to minimize its expected losses, which can be reduced by minimizing V. i.e., player A adopts a poor strategy The expected loss for player B will be as follows 541- 242-4g3 s V Dividing the above constraints by V, we get 91 ア1-017| | I1 q3

To simplify the problem, we put 91 293 In order to minimize V, player B can Maximize Zg-V-yitv1" уз subject to 1-2+433 S1 and y12V 0 Now, solve this problem using simplex method.

subject to 51 22 43s1 and y1V2V3 2 0; The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate 1. As the constraint-1 is of type''we should add slack variable S 2. As the constraint-2 is of type' 'we should add slack variable S2 3. As the constraint-3 is of type 'we should add slack variable S3 4. As the constraint-4 is of type' 'we should add slack variable S After introducing slack variables subject to 5 уг 5y1 - 2y2 - 4y3

Iteration-1 MinRatic 3 y2 уз S1S.SS S, -24 -0.2 S3 C,-Z, 1. So the entering variable is Positive maximum C,- Z, is 1 and its column index is 1. So, the entering variable is y1 Minimum ratio is 0.2 and its row index is 2. So, the leaving basis variable is S2 The pivot element is 5. Entering -y1 Departing -S2. Key Element - +R2(new)-R2(old) 5

+ R1(new) R1(old) + R;(new) R3(old)3R2(new) R4(new) = R4(old)-R2(new) Iteration-2 MinRatio 19 24 = 6 = 0.1667 →

Positive maximum C -Z, is and its column index is 3. So, the entering variable is y3 Minimum ratio is 0.1667 and its row index is 4. So, the leaving basis variable is S 24 . The pivot element is 24 Entering 3. Departing -S. Key Element + R4(new)- R(old)24 +R(new) R1(old) + R^(new) R2(old) + R4(new) + Rs(new (old) + 5R4(new)

Iteration-3 MinRatio 29 13 24 644 24 25 = 87 = 0.5057 24 24 13 13 Positive maximum Ci-Z is and its column index is 2. So, the entering variable is v2 Minimum ratio is 0.2 and its row index is 1. So, the leaving basis variable is S :. The pivot element is 5 Entering - Departing S, Key Element 5

+ R,(new)R,(old) +5 +R,(new)R,(old)+R(new) 29 + Rs(new) Rs(old)- Ri(new) + R4(new)R4(old) + Ri(new)

Iteration-4 S, MinRatio 30 133 120 29 40 24 24 40 13 40 13 40 120 24 Z. g 40 Since all C. Z,s0 Hence, optimal solution is arrived with value of variables as 30. 120 Max Zq 40 23

Max Z g 40 1 33 g V 40 40 player B's optimal strategy 40 13 52 40 8 43 40 23 23 33 12099 Hence, player B's (Bỉ, B2. B.) optimal strategy is ( 0 Hence, playerBs(Bi,44) optimal strategy is (52123) 33, 05 player A's optimal strategy The values for x] x2x3,x4 can be obtained from the z c, row of final simplex table 13 t40283 40 13 13

40 1 5 2 338 33 40 40 3 5 33 8 11 13 5 5 Hence, player A's (A1,42, 43, 44) optimal strategy is ,0, 11 52 8 23) 99 3399 So, finally player B's B, B2, B3, B4 optimal strategy is 13 5 5 and player A's (Ai, A2, Α3: A.) optimal strategy is ( 33, 33, 0T