Game Theory 0-Sum Games
MATH 4321 Spring 2013 Assignment Solution 0-Sum Games 2 1. Reduce by dominance to 2x2 games and solve.
5 4 4 3 (a) 0 1 1 2 1 0 2 1 4 3 1 2
10 0 7 1 (b) 2 6 4 7 6 3 3 5
Solution: (a). Column 2 dominates column 1; then row 3 dominates row 4; then column 4 dominates column 3; then row 1 dominates row 2. The resulting submatrix consists of row 1 and 3 vs. columns 2 and 4. Solving this 2 by 2 game and moving back to the original game we find that value is 3/2, I’s optimal strategy is p (1 2, 0,1 2,0) and II’s optimal strategy is q (0,3 8, 0,5 8). (b). Column 2 dominates column 4; then (1/2)row 1+ (1/2)row 2 dominates row 3; then (1/2)col 1+(1/2)col 2 dominates col 3. The resulting 2 by 2 game is easily solved. Moving back to the original game we find that the value is 30/7, I’s optimal strategy is (2/7,5/7,0) and II’s optimal strategy is (3/7,4/7,0,0).
2. Reduce by dominance to a 3x2 matrix game and solve:
0 8 5 8 4 6 . 12 4 3
Solution: Note that 5/8xCol2 + 3/8xCol1 uniformly dominates Col3. Therefore, we can delete Col3 to get
0 8 * 8 4 * . Then, we use the graphical method in the following. 12 4 *
1/ 3 2 / 3 0 4 / 12 0 8 5 8 /12 8 4 6 0 12 4 3
Answer: The optimal strategy for I is (4/12, 8/12, 0) The optimal strategy for II is (1/3, 2/3, 0) Value = 16/3
3. Solve the following magic square game.
16 3 2 13 5 10 11 8 . 9 6 7 12 4 15 14 1
Solution: In an n n magic square, A aij , there is a number s such that
i aij s for all j , and j aij s for all i. If Player I uses the mixed strategy (1 n ,1 n ,,1 n ) his average payoff isV s n no matter what Player II does. The same goes for player II, so the value is s n and p is optimal for both players. In the example, n 4 and s 34 , so the value of the game is 17/2 and the optimal strategies are both
(1 4,1 4,1 4,1 4) .
4. Player II chooses a number j
5 4 4 3 (a) 0 1 1 2 1 0 2 1 4 3 1 2
10 0 7 1 (b) 2 6 4 7 6 3 3 5
Solution: (a). Column 2 dominates column 1; then row 3 dominates row 4; then column 4 dominates column 3; then row 1 dominates row 2. The resulting submatrix consists of row 1 and 3 vs. columns 2 and 4. Solving this 2 by 2 game and moving back to the original game we find that value is 3/2, I’s optimal strategy is p (1 2, 0,1 2,0) and II’s optimal strategy is q (0,3 8, 0,5 8). (b). Column 2 dominates column 4; then (1/2)row 1+ (1/2)row 2 dominates row 3; then (1/2)col 1+(1/2)col 2 dominates col 3. The resulting 2 by 2 game is easily solved. Moving back to the original game we find that the value is 30/7, I’s optimal strategy is (2/7,5/7,0) and II’s optimal strategy is (3/7,4/7,0,0).
2. Reduce by dominance to a 3x2 matrix game and solve:
0 8 5 8 4 6 . 12 4 3
Solution: Note that 5/8xCol2 + 3/8xCol1 uniformly dominates Col3. Therefore, we can delete Col3 to get
0 8 * 8 4 * . Then, we use the graphical method in the following. 12 4 *
1/ 3 2 / 3 0 4 / 12 0 8 5 8 /12 8 4 6 0 12 4 3
Answer: The optimal strategy for I is (4/12, 8/12, 0) The optimal strategy for II is (1/3, 2/3, 0) Value = 16/3
3. Solve the following magic square game.
16 3 2 13 5 10 11 8 . 9 6 7 12 4 15 14 1
Solution: In an n n magic square, A aij , there is a number s such that
i aij s for all j , and j aij s for all i. If Player I uses the mixed strategy (1 n ,1 n ,,1 n ) his average payoff isV s n no matter what Player II does. The same goes for player II, so the value is s n and p is optimal for both players. In the example, n 4 and s 34 , so the value of the game is 17/2 and the optimal strategies are both
(1 4,1 4,1 4,1 4) .
4. Player II chooses a number j