Eco514|Game Theory Problem Set 1: Due Friday, September 30 NOTE: On the \ethics" of problem sets Some of the theoretical exercise I will assign are actually well-known results; in other cases, you may be able to nd the answer in the literature. This is certainly the case for the current problem set. My position on this issue is that, basically, if you look up the answer somewhere, it’s your problem. After all, you can buy answer keys to most textbooks... The fact is, you will not have access to such, ehm, supporting material when you take your generals, or, in a more long-term perspective, when you work on your own research. You just cannot learn this stu without (re)doing the key proofs yourselves and spending considerable time working out actual problems. It is not enough to come to class and do the readings. The only enforcement mechanism I will use is that, regardless of your, ehm, \external" sources, I will ask you to turn in your own individual write-up. It’s OK to work with your colleagues, of course, as long as each of you turns in a separate homework. Sorry to bug you with this sort of things, but, as we say in Italy, patti chiari, amicizia lunga (roughly speaking, \if we agree on the rules beforehand, we shall be friends for a long time.") 1. The Best Reply Property and Strict Dominance Prove that, in a nite game G = (N;(Ai;ui)i2N), an action ai is a best reply to some (possibly correlated) probability distribution i 2 (A i) i there is no i 2 (Ai) such that ui( i;a i) >ui(ai;a i) for all a i2a i. NOTE: this is Lemma 60.1 in OR. It is also proved in the notes for Lecture 2, using LP. However, I would like to ask you to prove it using the separating hyperplane theorem. A good reference is A. Takayama, Mathematical Economics, Cambridge University Press, pp. 39-49, but you can nd other sources, too. Please state the exact version of the theorem you are using: you must be careful with strict vs. weak inequalities, closed vs. open sets, and stu like that. Do some detective work! 1 I do not mean to insult your intelligence and knowledge, but based on last year’s ex- perience, it’s probably helpful to remind you that probabilities are nonnegative. You will (hopefully!) see why I am pointing this out. 2. Correlated Rationalizability as a Fixpoint Solution Concept Consider a nite game G = (N;(Ai;ui)i2N). De ne the constrained best response corre- spondence cri : 2A i nf;g) 2Ai nf;g as follows: for any B i A i such that B i 6= ;, ai 2 cri(B i) i there exists a probability distribution i 2 (A i) such that: (i) ui(ai; i) ui(a0i; i) for all a0i2Ai, and (ii) i(B i) = 1. Correlated rationalizability can then be de ned as follows: for every i2N, let A0i = Ai; then, for n 1 and for every i2N, let Ani = cri(An 1 i ). (i) [trivial] Prove that there exists N 1 such that Ani = ANi for all n N. (ii) Prove that an action pro le a is in AN, i.e. is correlated rationalizable, i there exists a set B = Qi2N Bi A (i.e. B is a Cartesian product) such that (i) a2B, and (ii) for every i2N, Bi cri(B i). (iii) If we modify cri so as to incorporate the restriction that beliefs must be independent probability distributions, the preceding argument obviously goes through and leads to an alternative characterization of (independent) rationalizability. Conclude that any strategy in the support of a Nash equilibrium is rationalizable. (iv) Prove that AN includes any set B = Qi2N Bi with the property that, for every i2N, Bi cri(B i). 3. The Beauty Contest Game Consider the following situation: N individuals are asked to (simultaneously) write down an integer ai between 0 and 100. Payo s are determined as follows: rst, the average a of the N numbers is computed; then, the individuals whose number is closest to 12 a are deemed winners; nally, winners share (equally) a prize P > 0, while all other individuals receive 0. First, what would you do in this situation, if you could not think about it for more than 30 seconds? [You will obviously not be graded on this: I’m just curious!] Now analyze the game using the notions of correlated rationalizability and Nash equi- librium. How did you do, based on your gut feeling? If you did poorly, don’t worry: the overwhelming majority of people do. 4. From OR: 18.2, 18.3, 35.1, 64.1 2