Tutorial 1: solution sketches
1. Let’s first consider the tie-breaking rule in which all players who are closest to half the average split the payoff. We claim that the unique pure NE of the game is when all players guess 1. This situation is clearly a NE, for any player unilaterally changing their guess will get payoff 0 instead of 1/n. To show uniqueness, we show that no other profile is a pure NE. For contradiction, assume (s1, . . . , sn) is a different pure NE. k > 1 be be the largest number that any player plays. Let i be a player who plays k. Since k is the largest number anyone guesses player i can only get non-zero payoff from guessing k if all players guess k, in which case the payoff of 1 is split equally among all players. But since k > 1, then player i can switch to k − 1 instead and raise its payoff from 1/n to 1.
Thus, there is no player who plays a number k > 1 in a pure Nash equilibrium.
(In fact, we can also show no player plays a number k > 1 with positive probability in a mixed NE, in such a game. So, the only NE is the pure NE where everyone plays the number 1.)
Copyright By PowCoder代写 加微信 powcoder
In the second tie-breaking rule, all players who are closest to half the average get the full payoff of 1. Intuitively, this means that a player wants to “win”, but doesn’t care about how many other players are winning simultaneously with it, unlike in the previous version, where players prefer to win alone if they can. This means that we get more NEs. Specifically, for any k ∈ {1, . . . 1000}, all players guessing k is a pure NE, as everyone gets the maximum payoff of 1 and thus cannot improve by switching. We claim that there are no other NEs. Suppose for contradiction that there is some other pure NE. In such a pure NE, at least two different players must play different numbers. Let k be the largest number played, and let k′ be the next smaller number played. We claim that k′ must be strictly closer to half the average. That’s because half the average, h, clearly satisfies h < k/2, and thus any number k′ such that 1 ≤ k′ < k is strictly closer to h than k. Thus, players playing k are better off switching, and this is not an NE. Thus, no two players can play different numbers in any pure NE. (In fact, we can show this is also true in a mixed NE.) 2. (a) The expected payoff for Player 1 is given by U1(x) = x1(i)x2(j)u1(i, j) = x1(i)x2(j)u1(i, j) i,j ij = 41(23u1(1,1)+ 13u1(1,2))+ 21(23u1(2,1)+ 13u1(2,2))+ 41(23u1(3,1)+ 31u1(3,2)) = 14(23 ·7+ 13 ·6)+ 12(23 ·4+ 13 ·5)+ 14(23 ·6+ 13 ·3) (b) Let us first note that the 4th pure strategy of player 2 strictly dominated all other strategies. This is because regardless what (pure) strategy player 1 plays, player 2 is strictly better off (i.e., gets a strictly higher payoff) playing pure strategy 4, than playing any other pure strategy. Thus, player 2 will necessarily prefer strategy 4 to any other strategy. We can thus “reduce” the game to the residual game in which player 2 only has that single pure strategy, yielding the bimatrix: (4, 7) (5, 8) (5, 9) In the remaining bimatrix, strategy 1 of Player 1 is strictly dominated by strategy 2 (and by strategy 3), so we end up with the bimatrix (5, 8) (5, 9) Player 1 will get expected payoff 5 no matter what it does in this risidual game, whereas Player 2 has no choices remaining. Thus in this reduced game, the set of Nash equilibria is {(x1, x2) | xi a mixed strategy for Player i and (x1, x2) is a NE } = {((p,1−p),1) | p ∈ [0,1]}. This means that in the original game the are given by pairs (x1, x2) where x1 is of the form (0, p, 1 − p) and x2 = (0, 0, 0, 1). In particular, we have two pure NEs: in one Player 1 plays strategy 2 while Player 2 plays strategy 4 and in the other one Player plays strategy 3 while Player 2 plays strategy 4. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com