AGTA Tutorial sheet 2 (solutions)
1 Question 1
Consider the finite 2 player zero sum game given by the following payoff matrix A, for player 1 (row player):
42925 A=63597 1 4 8 5 7
Copyright By PowCoder代写 加微信 powcoder
Observe that the last row is strictly dominated by the second row. Also, the second column strictly dominates the 5th column (since −2 > −5, −3 > −7, −4 > −7) obtaining in the residual game matrix:
4292 6359 1485
Note that the second column strictly dominates the 3rd column, since −2 > −9,−3 > −5, −4 > −8. Now, row 1 is strictly dominated by row 2, and in the residual game, column 2 strictly dominates column 4, since −3 > −9,−4 > −5, leaving us with the final residual game:
′63 A=14
In order to compute the minmaximizer strategy for player 1, as well as the value of the game v, we have the following LP (primal form) problem: Denote xT = [p1 p2] to represent the minmaximizer strategy for player 1.
Maximize v
Subject to:
6p1 + p2 ≥ v
3p1 + 4p2 ≥ v
p1 + p2 = 1
Using p2 = 1 − p1, the system becomes: Maximize v
subject to:
p1 ≥ v−1 5
p1 ≤ 4 − v
By eliminating p1, we have:
v−1 ≤4−v,wherev≤21 =3.5 56
4−v≥0. wherev≤4.
Note that we choose the condition that is most stringent, in this case v ≤ 3.5. Therefore, by maximizing v, we have that v = 3.5. Therefore p1 = p2 = 0.5.
Taking y = q to represent the maxminimizer strategy for player 2, the
dual of the LP presented above is:
Minimize u
subject to:
6q1 + 3q2 ≤ u
q1 + 4q2 ≤ u
q1 + q2 = 1
Using q2 = 1 − q1, the system becomes Minimize u
subject to
q1 ≤ u−3 3
By eliminating q1, we have: 4−u ≤u−3,i.eu≥7 =3.5
u−3 ≥0,i.eu≥3 3
Since we minimize u, and by the given constraints, we conclude that u = 3.5 and therefore q1 = 61 and q2 = 56 . Note that u = v, which is not surprising, this fact following from the minimax theorem.
2 Question 2
(7,3) (6,4) (5,5) (4,7) G = (4,2) (7,9) (8,6) (8,8)
(6, 1) (9, 7) (2, 4) (6, 9)
Note that column 1 is strictly dominated by column 2. Also, in the residual game bimatrix, row 1 is strictly dominated by row 2. Also, column 3 is strictly dominated by column 4. We are now left with the following residual game:
′ (7,9) (8,8) G = (9,7) (6,9)
It is easy to check that there are no pure . This is because if either player plays a pure strategy, then it is clear by inspection of the game that the unique best response of the other player is a pure strategy, and it is also clear by inspection of the game that no pair of pure strategies constitutes a NE. In every NE of this risidual game, it must be the case that both players use
both of their strategies with positive probability. We use the corollary to Nash’s theorem to compute the unique NE in the residual game as follows: Suppose player 1 plays strategy 1 with probability p and strategy 2 with probability (1-p) in some N.E, where 0 < p < 1. Suppose player 2 plays strategy 1 with probability q and strategy 2 with probability (1-q) in some N.E, where 0 < q < 1. Using the corollary of the Nash theorem, if player 2 is playing against player 1’s mixed strategy, both of player 2’s pure strategies must be a best response to player 1. The same argument applies for player 1. Therefore, 7q + 8(1 − q) = 9q + 6(1 − q) 9p + 7(1 − p) = 8p + 9(1 − p) By doing the arithmetic, we find p = 23 and q = 12. So, a NE for this game is: [(0, 23, 13,0);(0, 12,0, 12)]. The expected payoff for player 1 under this strategy profile is 7.5, whereas the expected payoff for player 2 is 8.33. A strategy that is strictly dominated can not be played with non-zero prob- ability in any NE, and therefore we don’t eliminate NE’s by eliminating strictly dominated strategies. Also, p and q are both uniquely determined so it must imply that there is only one NE in this game. Final answer: [(0, 23, 13,0);(0, 21,0, 12)] 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com