Robert Aumann
Robert Aumann
 Partially supported by a grant of the Israel Science Foundation. The author thanks Elchanan
Ben-Porath,   Avinash  Dixit,   Andreu  Mas-Colell,   Eyal   Winter   and  Shmuel   Zamir   for   their
comments. A presentation is available at http://www.ma.huji.ac.il/hart/abs/aumann-p.html. The
author  is  affiliated  to  the  Center  for  the  Study  of  Rationality,  the  Department  of  Economics,
and  the  Einstein  Institute  of  Mathematics,   The  Hebrew  University  of  Jerusalem.   Web  page:
http://www.ma.huji.ac.il/hart.
C 
 The editors of the Scandinavian Journal of Economics 2006. Published by Blackwell Publishing, 9600 Garsington Road,
Oxford,   OX4  2DQ,   UK  and  350  Main  Street,   Malden,   MA  02148,   USA.
186   S.   Hart
negotiations   are   often  long-term  affairs.   The   same   is   true   of   employer
employee,   lawyerclient   and  firmsubcontractor   relationships,   of   conflicts
and  agreements  between  political   parties  and  nations,   of  evolutionary  pro-
cesses  in  biology.
In  such  long-term  interactions,   the  different   stages   are  naturally  inter-
dependent.   Decision-makers   react   to   past   experience,   and   take   into   ac-
count   the  future  impact   of   their   choices.   Many  interesting  and  important
patterns of behaviorlike rewarding and punishing, cooperation and threats,
transmitting information and concealing itcan only be seen in multi-stage
situations.
The  general  framework  for  studying  strategic  interaction  is  game  theory.
The  players  are  decision-makersbe  they  individuals,   collectives,   com-
puter programs or geneswhose actions mutually affect one another. Game
theory   studies   interactions   (games)   from  a   rational   decision-theoretic
point   of   view,   and  develops  models  and  methodologies  that   are  universal
and  widely  applicableparticularly  in  economics.
Foremost   among  the  multi-stage  models  are  repeated  games,   where  the
same  game  is  played  at   each  stage.   Such  models  allow  us  to  untangle  the
complexities   of   behavior   from  the   complexities   of   the   interaction  itself,
which  here  is  simply  stationary  over  time.
The  Classical  Folk  Theorem
The  simplest  setup  is  as  follows.  Given  an  n-person  game  G,  let  G
  be  the
supergame  of   G:   the  same  n  players   are  repeatedly  playing  the  game  G,
at   periods  t  =  1,   2, . . . .   (It   is  customary  to  call   G  the  one-shot   game,
and  G
  as  strategies.)
At   the  end  of  each  period,   every  player  is  informed  of  the  actions  chosen
by  all   players   in  that   period;   thus,   before  choosing  his   action  at   time  t,
each  player  knows  what   everyone  did  in  all   the  previous  periods  1,   2, . . . ,
t   1.
The  payoffs  in  G
,   i.e.,   those
strategy  combinations   for   the  n  players   such  that   no  player   can  increase
his   payoff   by  unilaterally  changing  his   strategy?   What   are   the   resulting
1
John F. Nash, Jr., was awarded the 1994 Nobel Memorial Prize in Economics for this work.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   187
outcomes?  The  answer  is  given  in  the  following  result,   which  emerged  in
the   late   fifties.   Its   precise   authorship  is   unknown,   and  it   is   part   of   the
folklore  of  game  theory;  it  is  thus  known  as  the  Folk  Theorem.
2
The  Folk  Theorem.  The  set  of  Nash  equilibrium  outcomes  of  the  repeated
game  G
4
3
4
Fig. 1.   The Folk Theorem for the Battle of the Sexes game
Returning  to  the   Battle   of   the   Sexes   example,   we   have
8
r
1
 = r
2
 =
  3
4
,
and   the   set   of   feasible   and   individually   rational   outcomes   in   G  is   the
darkly  shaded  area  in  Figure  1.   The  Folk  Theorem  says   that   this   is   pre-
cisely  the  set   of  outcomes  of  all   Nash  equilibria  of  the  infinitely  repeated
game  G
.
An  informal   proof  of  the  Folk  Theorem  is  as  follows  (complete  formal
proofs  require  many  technical  details;  see  for  instance  Aumann,   1959,   and
1989,   Ch.   8).
One  direction  consists   of   showing  that   the  payoff   vectors   of   the  Nash
equilibria of G
  to  at  most  r
i
  (which  is  less  than  or  equal  to  the  payoff  a
i
  that  he  is
getting under the plan)so no increase in payoff is possible. Thus the threat
of   punishment   ensures  that   each  player   fulfills  his  part   of   the  joint   plan.
We   will   refer   to   the   special   Nash   equilibria   constructed   above   as
canonical  equilibria.
The  Import  of  the  Folk  Theorem
By  their  very  nature,   repeated  games  are  complex  objectsfor  players  to
play,   and  for   theorists   to  analyze.   There   are   a   huge   number   of   possible
strategies,   even  when  the  game  is  repeated  just  a  few  times;
11
in  addition,
many of these strategies are extremely complex. This makes the equilibrium
analysis  appear,   at  first,   unmanageable.
The   Folk   Theorem  shows   that   in   fact   this   is   not   so.   The   resulting
geometric   characterization   of   the   equilibrium   outcomes   is   extremely
9
If  more  than  one  player  deviated  at  the  same  time,   choose  one  of  them.
10
Since the plan consists of a sequence of pure actions, any deviation is immediately detected.
11
The  number  of  strategies  is  doubly  exponential  in  the  number  of  repetitions.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
190   S.   Hart
simple  (again,   see  Figure  1).   What   is   more  important   however   is   the  re-
sulting  behavioral   characterization:   every  equilibrium  of   G
  is   outcome-
equivalent to a canonical equilibrium, which consists of a coordinated plan,
supported  by  the  threat  of  appropriate  punishments.
12
The   most   valuable   insight   from  the   analysis   is   the   connection  that   is
established between the so-called non-cooperative and cooperative the-
ories.   The  Folk  Theorem  relates  non-cooperative  behavior   in  the  repeated
game (i.e., equilibrium in G
.
This  is  the  fundamental   message  of   the  theory  of   repeated  games  of   com-
plete   information;   that   cooperation  may  be   explained  by  the   fact   that   the
games  people  playi.e.,  the  multiperson  decision  situations  in  which  they
are   involvedare   not   one-time   affairs,   but   are   repeated  over   and  over.   In
game-theoretic   terms,   an   outcome   is   cooperative   if   it   requires   an   outside
enforcement   mechanism  to   make   it   stick.   Equilibrium  points   are   self-
enforcing;   once   an  equilibrium  point   is   agreed  upon,   it   is   not   worthwhile
for   any   player   to   deviate   from  it.   Thus   it   does   not   require   any   outside
enforcement   mechanism,   and   so   represents   non-cooperative   behavior.   On
the   other   hand,   the   general   feasible   outcome   does   require   an  enforcement
mechanism,   and   so   represents   the   cooperative   approach.   In   a   sense,   the
repetition  itself,   with  its   possibilities   for   retaliation,   becomes   the   enforce-
ment  mechanism.
Thus,   the   Folk  Theorem  shows,   first,   that   one   can  succinctly  analyze
complex   repeated   interactions;   second,   that   simple,   natural   and   familiar
behaviors  emerge;  and  third,  how  non-cooperative  strategic  behavior  brings
about   cooperation.   This  emergence  of  cooperation  from  a  non-cooperative
setup  makes  repeated  games  a  fascinating  and  important  topic.
The   result   of   the   Folk   Theorem   has   turned   out   to   be   extremely
robust.   The  extensions  and  generalizations  are  concerned  with  varying  the
12
The  Revelation  Principle  in  mechanism  design  is  of  a  similar  type:   everything  that   can
be  implemented  can  also  be  implemented  by  a  simple  direct  mechanism.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   191
equilibrium  concept,   the   long-run   evaluation   of   the   payoffs,   imposing
restrictions   on  strategies,   bounded  rationality,   modifying  the   structure   of
the  game,   introducing  asymmetric  information,   imperfect   monitoring,   and
so on. It should be emphasized that many of the results in this vast literature
are  not   just   simple  extensions;   they  almost   always  embody  new  ideas  and
important   insights,   while   overcoming  the   many  conceptual,   and  at   times
also  technical,   complexities  of  the  models.
A  Historical  Note
The  Folk  Theorem  was  essentially  known  to  most   people  working  in  the
area   in   the   late   fifties.   However,   it   had   not   been   published.   Perhaps   it
was   considered   too   simple   a   result;   perhaps,   too   complicated   to   write
rigorously.
13
The  discounted  repeated  Prisoners  Dilemma  with  discount   factor  close
enough  to  1  is   mentioned  in  Luce   and  Raiffa   (1957,   p.   102)   as   having
equilibria  yielding  efficient   outcomes;   Shubik  (1959b,   Sec.   10.4)  presents
a  more  detailed  analysis.
Aumann (1959, 1960, 1961) was the first to provide an extensive analysis
of   infinitely   repeated   games.   After   setting   up   the   model   in   an   explicit
and  rigorous  manner,  he  showed  that  the  two  approachesnon-cooperative
for   the   repeated   game   G
) and the
cooperative  approach  (the  core  of   G).   In  fact,   this  work  led  Aumann  and
others   to  the  development   of   the  theory  of   general   cooperative  games
non-transferable  utility  games
19
which  are  most  important  in  economic
theory;  see  Aumann  (1967).
Asymmetric  Information
A  most  important  and  fascinating  extension  of  the  Folk  Theorem  is  to  the
case  of   asymmetric  information,   where  different   players   possess   different
knowledge of the relevant parameters of the one-shot game that is repeatedly
played; for instance, a player may not know the utility functions of the other
players.
Now,   information   is   valuable.   But   how   should   it   be   used   advant-
ageouslyto  gain  a   competitive   edge,   to  attain  mutual   benefits   through
cooperation,   or  both?
To illustrate the issues involved, assume for concreteness that one player,
call   him  the   informed  player,   has   private   information  which  the   other
players  do  not   possess.   In  a  one-shot   interaction,   the  informed  player  will
clearly   utilize   his   information   so   as   to   gain   as   much   as   possible;   this
will   often  require  him  to  play  different   actions   depending  on  his   private
18
Specifically,   the  so-called  -core.
19
Prior  to  this,   only  transferable  utility  or  side  payment  games  were  studied.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
194   S.   Hart
information.   However,   if   the  situation  is   repeated,   then  the  other   players,
by  observing  the  action  taken  by  the  informed  player,   may  infer  what   his
information was. But then the informed player will no longer have an infor-
mational  advantage  in  future  periods.  So,  what  good  is  private  information
to  the  informed  player  if  he  cannot  use  it  to  his  benefit?  The  problem  here
is   to  find  the  right   balance:   to  use  the  information  as   much  as   possible,
while  revealing  it  as  little  as  possible.
This  is  one  side  of  the  coin.  The  other  is  that  there  are  situations  where
the  informed  player  would  like  to  convey  his  information  to  the  others,   so
that  their  resulting  actions  will  benefit  him.   But  that  is  not  always  easy  to
do;  can  the  uninformed  players  trust  him?  (Should  one  trust  a  shop  owner
who  claims   that   buying  from  him  is   a   good  deal?   Wouldnt   he   claim
the  same  even  if  it  werent  so?)  The  problem  is  how  to  make  the  revealed
information  credible,   so  that  everyone  benefits.   Of  course,   repetitioni.e.,
the  long-term  relationshipis  essential  here.
In   the   mid-sixties,   following   the   Harsanyi
20
(19671968)   model   of
incomplete   information   games,   Aumann   and   Michael   Maschler   founded
and  developed  the  theory  of  repeated  games  with  incomplete  information.
In   a   series   of   path-breaking   reports   written   in   1966,   1967   and   1968,
21
Aumann   and   Maschler   set   up   the   basic   models,   and   showed   how  the
complex  issues   in  the   use   of   information  alluded  to  above   can  actually
be  resolved  in  an  explicit  and  elegant  way.
As  suggested  by  the  Folk  Theorem,   there  are  two  issues  that  need  to  be
addressed:   individual   rationality  and  feasibility.   We  will   deal   with  each  in
turn.
Individual  Rationality  and  the  Optimal  Use  of  Information
We  start   with  individual   rationality:   determining  how  much  a  player   can
guarantee   (no   matter   what   the   other   players   do).   We   will   illustrate   the
issues   involved  with  three   simple   examples.   In  each  example   there   will
be  two  players  who  repeatedly  play  the  same  one-shot   game,   and  we  will
consider  individual   rationality  from  the  point   of  view  of  the  row  player.
22
The  row  players  payoffs  are  given  by  either  the  matrix  M1  or  the  matrix
M2;   the  row  player  is  informed  of  which  matrix  is  the  true  matrix,   but
the  column  player  is  nothe  only  knows  that  the  two  matrices  are  equally
20
John C. Harsanyi was awarded the 1994 Nobel Memorial Prize in Economics for this work.
21
These  unpublished  reports  to  the  Mathematica  Institute  were  widely  circulated  in  the  pro-
fession.   They  are  now  collected  in  one  book,   Aumann  and  Maschler   (1995),   together   with
very  extensive  notes  on  the  subsequent  developments.
22
The game may thus be thought of as a zero-sum game, with the row player as the maximizer
of  his  payoffs,   and  the  column  player  as  the  minimizer.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   195
likely.   After  each  stage  both  players  observe  the  actions  taken,   but  not  the
payoffs.
23
The  first  example  is
Game  1
M1
 
probability =
1
2
:
L   R
T   4   0
B   0   0
M2
 
probability =
1
2
:
L   R
T   0   0
B   0   4
Again,  the  question  we  ask  is,  How  much  can  the  row  player  guarantee?
If   he  were  to  play  optimally  in  each  matrix,   i.e.,   T  when  the  true  matrix
is   M1,   and  B  when  it   is   M2  (this   is   the  only  way  he  may  get   positive
payoffs),   then   his   action   would   reveal   which   matrix   is   the   true   matrix.
Were  the  column  player   to  play  R  after   seeing  T,   and  L  after   seeing  B,
the  row  player  would  get   a  payoff  of
24
0.   If,   instead,   the  row  player  were
to  ignore  his  information,  he  would  face  the  average  non-revealing  game
with  payoff  matrix
25
1
2
 M1 +
  1
2
 M2:
L   R
T   2   0
B   0   2
Here  the  best   he  can  do  is  to  randomize  equally  between  T  and  B,   which
would  guarantee  him  a  payoff  of  1.   This  is  better  than  0,   and  it   turns  out
that 1 is in fact the most the row player can guarantee in the long run here
(the  proof  is  by  no  means  immediate).   So,   in  Game  1,   the  row  player  can
23
Thus information is transmitted only through actions (if the column player were to observe
the   payoffs,   he   could  determine   immediately  which  matrix  is   the   true   matrix).   This   is   a
simplifying  assumption  that   allows  a  clear  analysis.   Once  these  games  are  studied  and  well
understood, one goes on to the general model with so-called signaling matrices (where each
combination of actions generates a certain signal to each player; the signal could include the
payoff, or be more or less general; this is discussed already in Aumann (1959, Sec. 6, second
paragraph).
24
Except,   perhaps,   in  the  first  period  (which  is  negligible  in  the  long  run).
25
In  each  cell,   the  payoff  is  the  average  of  the  corresponding  payoffs  in  the  two  matrices.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
196   S.   Hart
guarantee  the  most  by  concealing  his  information  and  playing  as  if  he  did
not  know  which  matrix  is  the  true  matrix.
We  modify  the  payoffs  and  get  the  second  example:
Game  2
M1
 
probability =
1
2
:
L   R
T   4   4
B   4   0
M2
 
probability =
1
2
:
L   R
T   0   4
B   4   4
In  this  game,   if   the  row  player   ignores  his  information,   then  the  average
game  is
1
2
 M1 +
  1
2
 M2:
L   R
T   2   4
B   4   2
in  which  he  can  guarantee  a  payoff  of  3  (by  randomizing  equally  between
T  and  B).   If,   however,   the  row  player   were  to  play  T  when  the  true  ma-
trix  is  M1  and  B  when  it   is  M2,   he  would  be  guaranteed  a  payoff   of   4,
which  clearly  is   the   most   he   can  get   in  this   game.   So,   in  Game   2,   the
row  player  can  guarantee  the  most  by  usingand  thus  fully  revealinghis
information.
The  third  example  is
Game  3
M1
 
probability =
1
2
:
L   C   R
T   4   2   0
B   4   2   0
M2
 
probability =
1
2
:
L   C   R
T   0   2   4
B   0   2   4
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   197
Using  his   information  fullyplaying  T  when  the  true  matrix  is   M1  and
B  when  it   is   M2guarantees   only  a  payoff   of   0  to  the  row  player   (the
column  player  plays  R  after  seeing  T,   and  L  after  seeing  B).   Ignoring  the
information  leads  to  the  average  game
1
2
 M1 +
  1
2
 M2:
L   C   R
T   2   0   2
B   2   0   2
in which the row player can again guarantee only a payoff of 0 (the column
player   plays   C).   At   this   point   it   may  appear   that   the   row  player   cannot
guarantee  more  than  0  in  this  game  (since  0  is  the  most   he  is  guaranteed,
whether  concealing  or  revealing  the  information).   But   that   turns  out   to  be
false:  by  partially  using  his  informationand  thus  partially  revealing  it
the  row  player  can  guarantee  more.  Indeed,  consider  the  following  strategy
  for  the  row  player:
Strategy    of  the  row  player
If  M1:
( p)
be  the  supergame  when  the  row  player   is  informed  of   the  chosen  matrix
and  the  column  player  is  not  (this  is  called  information  on  one  side).
Theorem,   Aumann  and  Maschler   (1966).   The  minimax  value  function  of
the  repeated  two-person  zero-sum  game  with  information  on  one  side  G
 =
 
val G.
That   is,   for  every  prior  probability  p,   let   w( p) :=val G( p)  be  the  mini-
max value of the one-shot average game G( p); let  w  denote the concavifi-
cation  of  w,  i.e.,  the  minimal  concave  function  that  is  everywhere  greater
than  or   equal   to  w  (i.e.,  w( p) w( p)   for   all   0  p 1);   the   Aumann
Maschler   Theorem  says   that   val G
(p)
1
prior
posteriors
1
2
1
4
  
3
4
1
2
Fig. 2.   Value function of the one-shot average game (left), and of the repeated game (right,
bold line) in Game 3
Figure 2 illustrates this for our third example, Game 3 (note how the value
of G
) for p
:
L   R
T   3, 3   0, 0
B   3, 3   0, 0
M2
 
probability =
2
3
:
L   R
T   4, 0   3, 3
B   4, 0   3, 3
Two  players  repeatedly  play  a  one-shot   game  with  payoffs  given  by  either
the  bimatrix  M1  or  the  bimatrix  M2  (this  is  now  a  non-zero-sum  game).
M2 is twice as likely as M1, and only the row player is informed of whether
M1  or  M2  is  the  true  bimatrix;  finally,  the  actions,  but  not  the  payoffs,  are
observed  after  each  stage.
30
The outcome (3, 3) appears in both bimatrices; to obtain it, the informed
row player must communicate to the uninformed column player whether the
true bimatrix is M1 or M2, e.g. by playing T in the first period if it is M1,
and B if it is M2; after T the column player will play L, and after B he will
play R. However, this plan is not incentive-compatible: the row player will
cheat  and  play  T  in  the  first   period  also  when  the  true  bimatrix  is  M2,
since he prefers that the column player choose L rather than R also when it
is M2 (he gets a payoff of 4 rather than 3)! Thus the communication of the
row  player  cannot   be  trusted.   It   turns  out   that   the  row  player  has  no  way
to  transmit  his  information  credibly  to  the  column  player,  and  the  outcome
(3, 3) is not  reachable. (The only feasible outcome is for the column player
always  to  play  R,   which  yields  an  expected  payoff   vector   of   only  (2,   2).)
Thus   the   presence   of   asymmetric   information  hinders   cooperationeven
when  it   is  to  the  mutual   advantage  of   both  players.   The  informed  player
wants  to  convey  his  information,   but  he  cannot  do  so  credibly.
The   above   example   is   due   to  Aumann,   Maschler   and  Stearns   (1968),
where   this   theory   is   first   developed.   That   paper   exhibits   equilibria   that
consist   of   a  number   of   periods  of   information  transmission  (by  the  in-
formed  player)   interspersed  with  randomizations  (by  both  players),   which
30
The  payoffs  correspond  to  a  standard  signaling  setup,   as  in  principalagent   interactions:
the row player possesses the information and the column player determines the outcome (the
two  rows  yield  identical   payoffs,   so  the  informed  players  actions  have  no  direct   effect   on
the  outcome).
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   201
ultimately lead to certain combinations of actions (like (i) in the section The
Classical Folk Theorem, above); this whole plan (of communications and
actions)   is   sustained   in   equilibrium  by   appropriate   punishments   when   a
deviation   is   observed   (like   (ii)   in   the   same   section,   based   on   the
individual   rationality  results   above).   The  complete  characterization  of   all
equilibria,   and  their  canonical   representation  in  terms  of  communications,
joint  plans  and  punishments,  is  provided  by  Hart  (1985);  see  also  Aumann
and  Maschler  (1995,  Postscript  to  Ch.  5),  and,  for  a  related  setup,  Aumann
and  Hart  (2003).
The   study   of   repeated   games   of   incomplete   informationwhich   has
flourished  since  the  pioneering  work  of   Aumann  and  Maschlerclarifies
in  a  beautiful   way  the  strategic  use  of   information:   how  much  to  reveal,
how much to conceal, how much of the revealed information to believe.
SummaryRepeated  Games
The   model   of   repeated  games   is   an  extremely  simple,   fundamental   and
universal   model   of   multi-stage  interactions.   It   allows  participants  truly  to
interact  and  react  to  one  another;  their  behavior  may  be  simpleor  highly
intricate and complex. The analysis is deep and challenging, both conceptu-
ally  and  technically.  In  the  end,  the  results  are  elegant  and  most  insightful:
simple  and  natural  behavior  emerges.
Aumann  has  been  the  leader  in  this  area.  The  highlights  of  his  contribu-
tion  are  (in  chronological  order):
(A)   The   initial   study   of   repeated   games:   showing   how   to   analyze
repeated  games,   and,   most   importantly,   showing  how  repeated  inter-
action  yields   cooperative  outcomes   (the  classical   Folk  Theorem,   and
Aumann,   1959).
(B)   Asymmetric  information:   introducing  the  essential   ingredient   of   infor-
mation,   and  showing  how  to  use  information  optimally  and  rationally
in  long-run  strategic   interactions   (Aumann  and  Maschler,   1966,   and
Aumann,   Maschler  and  Stearns,   1968).
(C)   Credible  threats   and  perfectness:   making  the  equilibria  more  natural
and  robust  and  thus  of  much  wider  applicability,  which  paved  the  way
for   their   wide  use,   in  particular   in  economics  (Aumann  and  Shapley,
1976,   and  Rubinstein,   1976).
Each   one   of   these   three   on   its   own   is   a   landmark   contribution;
taken  together,   they  complement   and  strengthen  one  another,   providing  a
cohesive  and  significant   big  picture:   the  evolution  of   cooperative  (and
other)  patterns  of  behavior  in  repeated  interactions  between  rational  utility-
maximizing  individuals.
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
202   S.   Hart
For   further   reading,   see   Aumanns   highly  influential   surveys   and  lec-
ture   notes   throughout   the   years   (1967,   1981,   1985,   1987b,   1992);   and,
more  recently,   Mertens,   Sorin  and  Zamir   (1994),   the  Handbook  of   Game
Theory,   with   Economic   Applications,   in  particular   the   chapters   of   Sorin
(1992),   Zamir   (1992)   and   Forges   (1992),   the   extended   postscripts   of
Aumann   and   Maschler   (1995),   and   the   chapters   in   Part   C  of   Hart   and
Mas-Colell  (1997).
III.   Knowledge,   Rationality  and  Equilibrium
In   this   section   we   discuss   the   two   topics   of   correlated   equilibrium  and
interactive knowledge, together with a beautiful connection between them
all  introduced  by  Aumann.
Correlated  Equilibrium
Consider a given and known game, and assume that, before playing it, each
player receives a certain signal that does not affect the payoffs of the game.
Can  such  signals  affect  the  outcome?
Indeed,   they   can:   players   may   use   these   signals   to   correlate   their
choices.   Aumann  (1974)   defined  the  notion  of   correlated  equilibrium:   it
is  a  Nash  equilibrium  of  the  game  with  the  signals.   When  the  signals  are
(stochastically)   independent,   this   is   just   a  Nash  equilibrium  of   the  given
game.   At   the  other   extreme,   when  the  signals   are  perfectly  correlated
for   instance,   when  everyone   receives   the   same   public   signal   (such  as
sunspots)it   amounts  to  an  average  of  Nash  equilibria  (this  is  called  a
publicly correlated equilibrium). But in general, when the signals are private
and  partially  correlated,   it   leads  to  new  equilibria,   which  may  lie  outside
the  convex  hull  of  the  Nash  equilibria  of  the  game.
For  example,   take  the  two-person  Chicken  game:
LEAVE   STAY
LEAVE   4, 4   2, 5
STAY   5, 2   0, 0
There  are  two  pure  Nash  equilibria,   (STAY,   LEAVE)  and  (LEAVE,   STAY),   and
also  a  mixed  Nash  equilibrium  where  each  player  plays  LEAVE  with  proba-
bility
  2
3
  and  STAY  with  probability
  1
3
;   the  payoffs  are,   respectively,   NE1 =
(5,   2),   NE2 =  (2,   5)  and  NE3 = (3
1
3
, 3
1
3
);  see  Figure  3.
Consider   now  a  public  fair-coin  toss  (i.e.,   the  common  signal   is  either
H  or  T,  with  probabilities
  1
2
 
  1
2
);  assume  that  after  H  the  row  player
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
Robert  Aumanns  game  and  economic  theory   203
Payo  to  player  1
Payo  to  player  2
NE3
NE1
NE2
CE2
CE1
Fig. 3.   Nash equilibria and correlated equilibria for the game of Chicken (see text; figure
not drawn to scale)
plays  STAY  and  the  column  player  plays  LEAVE,  whereas  after  T  they  play
LEAVE  and  STAY,  respectively.  This  is  easily  seen  to  constitute  a  Nash  equi-
librium  of   the  extended  game  (with  the  signals),   and  so  it   is   a  publicly
correlated   equilibrium  of   the   original   Chicken   game.   The   probability
distribution  of  outcomes  is
LEAVE   STAY
LEAVE   0
  1
2
STAY
  1
2
  0
and  the  payoffs   are  CE1 = (3
1
2
, 3
1
2
)   (see  Figure  3;   the  set   of   payoffs   of
all   publicly   correlated   equilibria,   which   is   the   convex   hull   of   the   Nash
equilibrium  payoffs,   is  the  gray  area  there).
But  there  are  other  correlated  equilibria,  in  particular,  one  that  results  in
each  action  combination  except   (STAY,   STAY)   being  played  with  an  equal
probability  of
  1
3
:
LEAVE   STAY
LEAVE
  1
3
1
3
STAY
  1
3
  0
C 
  The  editors  of  the  Scandinavian  Journal  of  Economics  2006.
204   S.   Hart
Indeed,   let   the   signal   to   each   player   be   L   or   S;   think   of   this   as   a
recommendation to play  LEAVE or  STAY, respectively. When the row player
gets  the  signal   L,   he  assigns  a  (conditional)   probability  of
  1
2
  to  each  one
of   the   two   pairs   of   signals   (L,   L)   and   (L,   S);   so,   if   the   column   player
follows  his  recommendation,   then  the  row  player   gets  an  expected  payoff
of 3 =
  1
2
  4 +
  1
2
  2 from playing  LEAVE, and only of 2
1
2
 =
  1
2
  5 +
  1
2
  0 from
deviating  to  STAY.   When  the  row  player  gets  the  signal   S,   he  deduces  that
the   pair   of   signals   is   necessarily  (S,   L),   so  if   the   column  player   indeed
follows  his  recommendation  and  plays  LEAVE  then  the  row  player  is  better
off   choosing   STAY.   Similarly   for   the   column   player.   So   altogether   both
players   always   follow  their   recommendations,   and   we   have   a   correlated
equilibrium. The payoffs of this correlated equilibrium are CE2 = (3
2
3
, 3
2
3
),
which  lies  outside  the  convex  hull  of  the  Nash  equilibrium  payoffs  (again,
see  Figure  3).
The  notion  of  correlated  equilibrium  is  most  natural  and  arises  in  many
setups.   It   is   embodied  in  situations   of   communication  and  coordination,
when there are mediators or mechanisms, and so on. In fact, signals are all
around  us,   whether  public  or  private;   it   is  unavoidable  that   they  will   find
their  way  into  the  equilibrium  notion.
Common  Knowledge  and  Interactive  Epistemology
In  multi-agent   interactive  environments,   the  behavior  of  an  agent   depends
on what he knows. Since the behavior of the other agents depends on what
they know, it follows that what an agent knows about what the others know
is  also  relevant;  hence  the  same  is  true  of  what  one  knows  about  what  the
others  know  about   what   he  knowsand  so  on.   This  leads  to  the  notions
of  interactive  knowledge  and  interactive  beliefs,   which  are  fundamental   to
the  understanding  of  rationality  and  equilibrium.
An  event   E  is   common  knowledge   among  a   set   of   agents   if   every-
one  knows  E,   and  everyone  knows  that   everyone  knows  E,   and  everyone
knows that everyone knows that everyone knows E, and so on. This concept
was  introduced  by  the  philosopher  David  Lewis  (1969)  and,  independently,
by  Aumann  (1976).   Aumanns  work  went   far  beyond  this,   formalizing  the
concept  and  exploring  its  implications.
Formally,   the  information  of   an  agent   in  a  certain  state  of   the  world
  is  described  by  the  set   of   all   states  that   he  considers  possible  when  
is   the  true  state,   i.e.,   those  states