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
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
