《博弈论》（英文版） ps1 Due Friday, September

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 find the answer in the literature. This is certainly the case for the current 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 stuff 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 finite game G=(N, (Ai, wieN ), an action ai is a best reply to some possibly correlated) probability distribution a-i∈△(A-) iff there is no a;∈△(A)such that ui(ai, a-i)>ui(ai, a-i)for all a-i E a-i NOTE: this is Lemma 60.1 in OR. It is also proved in the notes for Lecture 2, using LP lowever, 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 find 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 stuff like that. Do some detective work

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 find 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 stuff 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 finite game G = (N,(Ai , ui)i∈N ), an action ai is a best reply to some (possibly correlated) probability distribution α−i ∈ ∆(A−i) iff there is no αi ∈ ∆(Ai) such that ui(αi , a−i) > ui(ai , a−i) for all a−i ∈ a−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 find 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 stuff like that. Do some detective work! 1

I do not mean to insult your intelligence and knowledge, but based on last years 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 finite game G=(N, (Ai, uiieN). Define the constrained best response corre- spondence cri: 2A-i\10)=24\0 as follows: for any B_i C A-i such that B-i+ 0, ai E cri (B_i)iff there exists a probability distribution a-i E A(A-i) such that:(i) ui(ai,a-i2ui(a, a-i) for all a; E Ai, and(ii)a-i(B-i) Correlated rationalizability can then be defined as follows: for every i E N, let A= Ai then,forn≥1 and for every i∈N,letA=cr;(4x1) (i)[trivial] Prove that there exists N> l such that An= A for all n>N (ii)Prove that an action profile a is in A, i.e. is correlated rationalizable, iff there exists a set b= Ilen Bi C A(i.e. B is a Cartesian product)such that(i)aE B, and (ii)for every z∈N,B1Ccr;(B- Gi) 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 A includes any set b=llen B, with the property that, for every iE N, Bi C 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. Payoffs are determined as follows: first, the average a of the N numbers is computed; then, the individuals whose number is closest to a are deemed winners; finally, 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,183,35.1,64.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 finite game G = (N,(Ai , ui)i∈N ). Define the constrained best response corre￾spondence cr i : 2A−i \ {∅} ⇒ 2 Ai \ {∅} as follows: for any B−i ⊂ A−i such that B−i 6= ∅, ai ∈ cr i(B−i) iff there exists a probability distribution α−i ∈ ∆(A−i) such that: (i) ui(ai , α−i) ≥ ui(a 0 i , α−i) for all a 0 i ∈ Ai , and (ii) α−i(B−i) = 1. Correlated rationalizability can then be defined as follows: for every i ∈ N, let A0 i = Ai ; then, for n ≥ 1 and for every i ∈ N, let An i = cr i(A n−1 −i ). (i) [trivial] Prove that there exists N ≥ 1 such that An i = AN i for all n ≥ N. (ii) Prove that an action profile a is in AN , i.e. is correlated rationalizable, iff there exists a set B = Q i∈N Bi ⊂ A (i.e. B is a Cartesian product) such that (i) a ∈ B, and (ii) for every i ∈ N, Bi ⊂ cr i(B−i). (iii) If we modify cr i 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 = Q i∈N Bi with the property that, for every i ∈ N, Bi ⊂ cr i(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. Payoffs are determined as follows: first, the average a¯ of the N numbers is computed; then, the individuals whose number is closest to 1 2 a¯ are deemed winners; finally, 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