Cha p t e r 9

C o r r e l a t e d a n d S e q u e n t ia l E q u ilib r i a

In t h is le ctu r e, I w ill co v e r t w o im p o rta n t e q u ilib r iu m c on cep ts, n am ely c orre la ted e q u i - libriu m an d s e q ue n t ial e q u ilib rium . C orre la ted e q u ilib rium r e lax e s t h e assu m p tio n in th e N a sh equ i l i b r ium t h a t t h e p l a y ers’ m i xed s tra teg ies a re i n d e p e n d e n t (h en ce th e n am e). It is th erefore w ea k e r t h a n N ash e q u ilib rium . I t i s stro n g e r t h a n r a t ion a liza b ilit y . O n th e o th er h a nd , seq u e n t ia l e q u ilib rium is a n eq u i lib r iu m r e fi ne m e n t . U nl i k e o t h e r re - fi ne m e n t s, se q u e n tial eq u ilibriu m m a k e s t h e p l a y ers’ b e lie f s a b o u t th e o the r pla y ers’ stra teg i es as an exp l ici t p a rt o f equ i l i b r ium , in a d d i tion to stra teg y p r o fi les. It is on e of th e m ost c om m o n l y u sed solu tion co ncepts, esp ecially in d y n a m i c g a m es w i th in co m - p l ete i n f o r m a tion . F o r a m o r e d eta i l e d d iscu ssion o f th ese top i cs, see F u d e n b erg a nd T i rol e ’s c h ap ter s 2.2 a n d 8. 3.

9 . 1 C o r r e la t e d E q u ilib r i u m

I n a m i x e d - s t r a t eg y N a s h e qui l i b ri um i t i s a s s u m e d t ha t t he s t rat e gi e s a r e i nde p e nde n t l y d i stribu ted . A s it is expla i ned i n t h e previou s lecture, th er e i s n o r ea son t o b el iev e tha t a p la y e r’s b elief a b o u t th e o th er pla y ers’ strategies a r e i n d e p e n d e n t . L ik ew ise, fro m an econ om etrici an’s p o in t o f v iew t he distrib u ti on of the s trategy p ro fi le s m a y co n t a i n co rrela tion . C or relat e d e q u ilib rium dro p s t he in d e p e nd en ce a ssu m p tion .

T h e r e a r e t w o w a y s t o d e fi n e co rrela ted equ i l i b r ium . O n e w a y i s to d escr i b e e a c h p l a y er’s in fo rm ation s truc tu re e x plicitly an d i m p o s e t he a ssum p t i o n th at ev ery p la y e r i s a b est resp on se. A n oth e r w a y is to co n s i d er the d istrib uti o n i n d u c ed b y su c h a m o d el

95

96 CHAPTER 9 . C ORRELA TED AND S E QUENTI AL EQUI LI BRI A

on the s tr ateg y p ro fi le. T h e la tte r d istribu t io n i s t h e n c h a ra cter iz ed b y usin g a s im p l er red u ced fo rm stru c tu re. I w ill fi rst p resen t t h e fi r s t f o r m u l a t i o n , w h i c h m a k e s t h e l o g i c of th e s olu t ion c o n c e p t s a n d it s r elatio n t o r a t ion a liza b ilit y c le are r .

De fi ni ti on 34 A ( c o mmo n - p r i o r ) inform atio n s t r uc tur e is a l ist ( Ω , I 1 ,..., I n , p ) whe r e Ω is a ( fi n ite ) s ta te sp a c e , p is a p r o b a bility d i str i b u tio n o n Ω an d I i i s t h e i nf ormat i on p a r titio n o f p l a yer i fo r e a c h i .

I w ill w r ite I i ( ω ) fo r t h e cel l o f th e p artitio n I i tha t co n t ain s ω . H er e, i f th e t ru e sta t e i s ω , p l a y e r i is i n fo rm ed tha t th e t r u e state is in I i ( ω ) , a nd he do e s not g e t an y o th er in fo rm a t ion . S u c h an i n fo rm ation s tru c ture arises if eac h pla y er o b serv es a sta t e-d e p e nd en t s ign a l, w h er e I i ( ω ) is the set of sta t es in w h ic h t he v a lu e o f t he sign al of pla y er i i s id en tica l t o t he v a lue o f t he si g n a l at state ω .

F i n a ll y , p i s a c ommon p ri or on Ω . I w ill assu m e w i th ou t l oss o f g en era lit y t h a t e a c h inform ati o n set I i ( ω ) h a s p ositiv e p ro b a b i lit y , i.e., p ( I i ( ω )) > 0 . H ence, b y B a y es’ rul e , ob ser ving th at th e t ru e state is in I i ( ω ) , p l a y e r i u p d a te s h is b e lief t o p ( ·| I i ( ω )) , w h i c h is a p ro ba bilit y d istrib utio n o n I i ( ω ) , w h e r e

0 p ( ω 0 ) 0

p ( ω | I i ( ω )) = p ( I

( ∀ ω

( ω ))

∈ I i ( ω )) .

De fi ni ti on 35 An ad ap ted s trategy p r o fi le ( s 1 ,..., s n ) w i th r esp ect t o in fo r m a t io n stru ctu r e ( Ω , I 1 ,..., I n , p ) is a l ist o f m a p p i n g s s i : Ω → S i such t h at s i ( ω ) = s i ( ω 0 ) w h en ever I i ( ω ) = I i ( ω 0 ) .

H e r e , t he last c o n d itio n g ua ran t ees th a t pla y e r i k n o w s w h a t s t r a t e g y h e i s p l a y i n g .

De fi ni ti on 36 A co rrela ted e q u ilibr i u m w i th r esp ec t t o info rm a tion s tructur e ( Ω , I 1 ,..., I n , p )

is a s tr a t e g y p r o fi le ( s 1 ,..., s n ) wi th r e s p e c t t o ( Ω , I 1 ,..., I n , p ) s u ch th a t fo r e a c h i an d

ω , s i ( ω ) is a b est r esp o n s e t o s − i und e r p ( ω 0 | I i ( ω )) , i.e ., fo r a l l s i ,

E [ u i ( s i ( ω ) , s − i ) | I i ( ω )] ≡

≥

ω ∈ I i ( ω )

ω ∈ I i ( ω )

u i ( s i ( ω ) , s − i ( ω 0 )) p ( ω 0 | I i ( ω ))

u i ( s i , s − i ( ω 0 )) p ( ω 0 | I i ( ω )) ≡ E [ u i ( s i , s − i ) | I i ( ω )] .

9 . 1. COR R EL A T ED EQ UI LI BRI U M 97

T h e c o n d i t i o n i n t h e d e fi n i ti o n is, o f c ou rse, equ i v a len t to s i b e in g a b est r esp on se i n the e x- an te stage. T h at i s ,

E [ u i ( s i , s − i )] ≡ X u i ( s i ( ω ) , s − i ( ω )) p ( ω ) ≥ X u i ( s 0 ( ω ) , s − i ( ω )) p ( ω ) ≡ E [ u i ( s 0 , s − i )]

i i

ω ∈ Ω ω ∈ Ω

f o r a n y ad ap ted s trategy s 0 .

Exa m p l e 3 A s a n exa m p l e, stud y t he c o rr elate d e q uil i bria o f th e g am e i n F igur e 2 .4 in F u denb er g a nd T i r o l e .

N o te th a t fo r a n y ω , s i ( ω ) i s a b est r esp o n se to a c orrelated b elief p i, ω ab ou t t h e

other p l a y e rs’ s trategy p ro fi le s w h e re p i,ω ( s − i ) = P ω 0 ∈ I ( ω ) , s

( ω 0 )= s

p ( ω 0 | I i ( ω )) . B y t h e

sa m e to k e n , for e ac h s j wi t h p i,ω ( s j ) > 0 , s j i s a b e s t r e s p o n s e t o a b e l i e f p j,ω 0 , w h e r e

s j ( ω 0 ) = s j , a nd th i s is tru e a d in fi n i tu m . H e n ce, s i ( ω ) is ra tion aliza b le for p la y e r i . T h ere f or e, co rrela ted e q u ilibr i u m is str o n g er th an r a tio n a l iz ab ilit y . N o te m o re o v er th at, u n lik e r atio na liz a b ilit y , w hic h d o es n o t p u t a n y r estric t io n a b o ut t h e b eliefs o t h e r t h a n th e a b o v e b est resp on se con d i ti o n , t he b e l i ef sequ e n ces ob tain ed a b o v e e xhib it str i n g en t p r op erties, as th ey a r e d eriv ed fro m a c o m m o n p rio r p usi n g t he B a y es’ rule. T his i s ind e ed th e o n l y d istinction b e t w een t h e t w o c on cep t.

A c om m o n - p r ior i n f o r m a tion stru ctu r e a ssu m e s t h a t t he pla y ers’ sh are a com m on p r ior b elief. In a m o r e g en era l inform atio n/ b e lief s tru ctu re, e a c h p la y e r w o u ld h a v e h i s b e l i ef at eac h i n fo rm ation set of h i s, a n d t h i s c a n b e rep r esen t ed b y a list o f p rob a b ili t y di st ri but i o n s p 1 ,..., p n on Ω , w h e r e p i repr esen t t h e (h y p oth e tical) p r io r d i s tribu t ion

of p l a y er i . T h e com m on -p rior i n f o rm ation s tructu re assu m e s t h a t p 1 = ··· = p n .

R a tion aliza b ilit y c o rresp on d t o e a c h p la y e r p la y i n g a b es t r e s p o n s e a t e v e ry in fo rm a t ion set i n a g en era l i n fo rm a t ion s tru c tu re.

In th e a b o v e d e fi n i t i o n , w e h a v e a n e x p l i c i t i n f o r m a t i o n s t r u c t u r e . O n e m a y b e o n l y in tere s ted i n t he p r o b a b ilit y d istribu t io n o n t he st rate gy pr o fi l e s i nduce d b y ( s , ( Ω , I 1 ,..., I n , p )) . In th a t case, w e c an use a sim p ler f or m u latio n a s fo ll o w s.

De fi ni ti on 37 A c o r r e la te d e q u ilibr i u m is a p r o b a b i lity d i str i b u tio n p on S su c h th a t fo r ea c h s i an d s 0 ,

X u i ( s i , s − i ) p ( s − i | s i ) ≥ X u i ( s 0 , s − i ) p ( s − i | s i ) . (9 . 1 )

s − i ∈ S − i s − i ∈ S − i

N o te tha t th i s d e fi ni t i on i s a s p e c i al c a s e of the p re vi ous o ne i n whi c h t he i n f o rmat i o n stru ctu r e i s a s f o l l o w s

Ω = S (9 . 2 )

I i ( s ) =

{ s i }× S − i = ©¡ s i , s 0 ¢ | s 0

∈ S − i ª .

C o n v er sel y , in ord e r t o c ap tu re pr ob ab ilit y d istrib u t ion s in d u ce d b y c o rrela ted e q u ilib ria w i th resp ect t o a rbi t rary in form atio n s tru c tu res, it su ffi ces t o c on sid e r t his l im ited set o f inform at io n s tru c tu res. T o see this, t ak e a n y co rrela ted e q u ilib rium ( s , ( Ω , I 1 ,..., I n , p )) . T h e d istr ib u t ion p ˜ in du ced b y ( s , ( Ω , I 1 ,..., I n , p )) on S is giv e n b y p ˜ ( s ) = ω ∈ Ω , s ( ω )= s p ( ω ) . N o w s up p o se th at in stea d o f l etti n g i kn o w tha t th e t ru e sta te is in I i ( ω ) , w e o n l y i n f o r m hi m t hat h e n ee ds t o pl a y s i ( ω ) accord ing t o s i . S in ce he d i d n o t ha v e a n inc e n t iv e t o d e viate u n d er an y i nform a tion (b y d e fi nitio n of corr elated equ ili b r iu m ) , b y s u r e-th in g p r inci p l e, he do es no t h a v e a n i n cen ti v e to deviate. H e n ce, th e n ew inform ati o n s tructu re w i th lim ite d inform atio n i s a lso a c o rrela ted e q u ilibr i u m . S in ce u i d o es no t d ep en d o n

ω , t h e la tter i n f o r m a tion stru ctu r e c an b e represen ted b y ( 9 . 2).

Exe r c i s e 1 4 F i n d a l l t h e c o rr ela t e d e q u i lib r ia ( a s d is tr ibu tio n s o n S ) f o r t h e g a m e o f F i gu r e 2 . 4 i n F u d en b e r g an d T ir o l e.

9 . 2 S e q u e n t ia l E q u ilib r ia

C o nsid er th e g am e i n F igu r e 9 .1. O n e ca n e a s ily c h ec k t h a t t he s t rate gy p r o fi le in dica ted w i th thic k l in es is a N a s h e q u ilibriu m . S in ce t h e g am e d o e s n o t h a v e a p ro p e r s u b g a m e , it is a l so a s u b g a m e-p e rfe c t e q u ilibr i u m . N e v er the l e ss, th e e q u ilibriu m pre scrib e s th e irra tion al m o v e L f or P l a y er 2 a t t h e in for m a t i o n set sh e m o v es. A t th e i n f or m a ti o n set sh e m o v es, s he kn o w s t h a t P la y e r 1 h a s p l a y e d T or B . N o m a tter w h at sh e b eli e v e s a b o u t th e lik e l ih o o d of T o r B , s h e fi nd s R a b etter m o v e t ha n L , b ecau se con d itio na l o n T a n d B , R d om ina t es L . S e q u en tia l eq u ilibriu m ex p l ic itly sp e c i fi e s t h e b e l i e f s o f p l a y e r s a t e a c h inform ati o n set th at th ey m o v e an d r equ i res t h a t t h e pla y ers a ct ra tion ally accord ing t o th ese b e liefs a n d t h a t t he b e liefs a r e c on sisten t w i t h t h e so lutio n .

F o rm a lly , c o n si d e r a n e xten siv e form g a m e . C on sider a n i n f o r m a tion set h at w h ic h a p l a y e r i ( h ) m o v e s, w h ere h is a c o l le ction o f n o d es th at i i s to m o v e an d c an not d i s t i n g u i s h f r o m e a c h o t h e r . A t h , p l a y e r i ( h ) k n o w s t h a t h e i s a t o n e o f t h e n o d e s h ,

X

(2,6)

L R

( 0 , 1 ) (3 ,2) (-1 ,3 ) ( 1 , 5)

F i gu re 9.1: A s u b gam e-p e rfe c t e q u ilibriu m w i th seq u e n t ia lly i rr ation a l m o v es

b u t h e d o e s n ot a n y t h i ng m o re th an th at. H en ce, b e in g a n e x p ec ted u tilit y m ax im iz er, h e ha s a b e lief a b o u t th e n o d es, a p ro b a b i lit y d istrib utio n μ ( ·| h ) on h . A b e l i ef system μ i s a l i s t o f s uc h p roba bi l i t y d i s t r i but i o ns , o ne f o r e ac h i nf o r ma ti on s e t .

R eca ll a l so th at a m ixed strategy σ i of a p la y e r i i s a c ompl et e c on t i nge n t p l a n t hat m a p s ea c h in for m ati o n set h of pl a y e r i t o a m i x e d a c t i o n σ i ( ·| h ) th at is a v a i l a ble a t h . An a sse ssm en t is a p a i r ( σ, μ ) of a s tr ategy p ro fi le σ an d a system o f b e l i efs μ .

De fi ni ti on 38 An a s s e s s m e n t ( σ, μ ) is seq u e n t ia lly r atio na l if a t e a ch in fo r m a t io n s e t h , p l a y i n g a c c o r d i n g t o σ i ( h ) in th e c o n tin u a tio n g a m e is a b es t r e s p o n s e f o r i ( h ) to be l i e f μ ( ·| h ) a n d t h e b e lief th a t th e o th e r p l a y er s w il l p la y a c c o r d in g t o σ − i ( h ) in th e

c o n t in u a tio n g a m e, i.e ., fo r a n y str a te gy σ 0 ,

Z u i ( σ i , σ − i ) dμ ( ·| h ) ≥ Z

u i ( σ 0 , σ − i ) dμ ( ·| h ) .

F o r e x a m p le, i n F igu r e 9 .1, f o r pla y er 2 , g i v e n a n y b e lief μ , L y i e l d s

U 2 ( L ; μ ) = 1 · μ ( T | { T, B } )+3 · μ ( B | { T, B } )

whi l e R y i e l ds

U 2 ( R ; μ ) = 2 · μ ( T | { T, B } )+5 · μ ( B | { T, B } ) .

H e nc e , s e q ue n t i a l r a t i o nal i t y r equi res t ha t p l a y e r 2 pl a y s R . G i v en pl a y e r 2 p l a ys R, th e o n l y b est r eply for p l a y e r 1 i s T . T h erefo r e, fo r a n y b e li ef assessm en t μ , t h e o n l y sequ e n t i a lly ratio n a l strategy p r o fi le is ( T, R ) .

1

L R

(0 , 10) (3 ,2 ) ( - 1 , 3 ) ( 1, 5)

F i gu re 9 . 2: A n i n co nsisten t b e l i ef assessm en t

In o r d e r t o h a v e a n e q u ilib rium , w e a lso n e e d t o r eq u i re th at μ is c o n s isten t w i th σ . R ou gh ly sp eakin g , c o n si sten cy requ ires th at pla y ers k no w w h i c h (p o ssi b l y m ixed ) stra teg i es a r e p la y e d b y t h e o t h e r p la y e rs. F or a m o t iv ation , c o n s ide r F i gu re 9 . 2 a n d call t h e n o d e o n t h e l e f t n T and t he no de on t h e r i g h t n B , w r i t i n g a l s o h 2 = { n T , n B } Gi v e n th e b el iefs μ ( n T | h 2 ) = 0 . 1 and b ( n B | h 2 ) = 0 . 9 , s t r a t e g y p r o fi le ( T, R ) is s e q u en tially ration al. S trategy T i s a b est r esp on se to R . T o c h e c k th e seq u e n t ia l r atio na lit y f or R , it su ffi c e s t o n o t e t h a t , g i v e n t h e b e l i e f s , L yi el ds

( . 1) (10) + ( . 9) (3) = 3 . 7

whi l e R yi el ds

( . 1) ( 2 ) + ( . 9) (5) = 4 . 7 .

( N o t e t hat t he re i s no c o n t in uation gam e .) B u t ( T, R ) i s no t e v e n a N a s h e q ui l i bri u m in th is ga m e . T h i s i s b ec au se in a N a s h e q u ilibriu m p l a y er k n o w s t he o t h e r p la y e r’s s t rat e gy . She w o ul d k no w t ha t p l a y e r 1 pl a y s T , a nd he nc e s he w o ul d a s s i g n pro b a b i l i t y 1 o n n T . I n c on tr ast, accordin g t o μ , s he as s i g n s o nl y p ro ba bi l i t y 0 . 1 o n n T .

T h er efo r e, as an e q uilibr i u m co nd ition , o n e w ou ld also lik e t o i m p o s e t ha t t he b e lie f s μ ( h ) are c on sisten t w ith t h e strategy pro fi le σ , i n t h a t t h e b e liefs ar e d eriv ed from σ us i n g B a y es ’ r ul e . That i s , w he n σ ( h ) > 0 , f o r e a c h no de x ∈ h , μ ( x | h ) = σ ( x ) /σ ( h ) , whe r e σ ( x ) i s t h e p ro ba bi l i t y of re a c hi ng no de x under σ and σ ( h ) = x ∈ h σ ( x ) . F o r exa m p l e, in o r d e r a b e lief a ssessm en t μ to b e co nsisten t w i th ( T, R ) , w e n e e d

μ ( n

| h ) = P r ( n T | ( T, R ) ) = 1 = 1 .

Pr ( n T

| ( T, R )) + P r ( n B

| ( T, R )) 1+0

U n f o rt unat e l y , i n ge ne ral , t h e r e c an b e i n f o rmat i o n s e t s t ha t a re not s upp o s ed t o b e reac hed a ccording t o t he strategy pro fi le, i .e ., σ ( h ) = 0 . I n t h a t c ase, B a y e s’ ru le d o es no t a ppl y , and c o ndi ti onal b e l i ef s a re arbi tra r y . F o r s uc h i nf ormat i o n s e t s , w e p e r turb th e s tra t eg y p ro fi le sligh t l y , b y a ssu m i n g tha t pla y ers m a y "tr e m b le ", a n d a p p ly th e B a y e s r u l e u sin g th e p ertu rb ed stra teg y p r o fi le. T o see th e g eneral i d ea , c o n sid e r t h e gam e in Figure 9.3. T h e i nform a ti on set of pla y er 3 i s o ff th e p ath o f t he stra teg y p r o fi le ( X, T , L ) . H ence, w e c an n o t a p p ly th e B a y es ru le. B u t w e ca n s til l see th at the b el iefs th e fi g u re are i n c o n sisten t. L e t u s p ertu rb th e stra t eg ies o f p la y e r s 1 a n d 2 a ssu m i n g th at p l a y ers 1 an d 2 tre m ble w ith p rob a bilities ε 1 an d ε 2 , r esp ectiv el y , w h ere ε 1 and ε 2 are s m a ll b u t p o s itiv e n um b e rs. T ha t i s, w e p u t p ro ba bilit y ε 1 on E an d 1 − ε 1 on

X (i n s tead of 0 a nd 1, resp ectiv e ly) a n d 1 − ε 2 on T an d ε 2 on B (in s tea d of 1 a n d 0,

resp ecti v ely). U n d er th e p erturb ed b e liefs,

ε 1 ( 1 − ε 2 )

Pr ( n | h ,ε ,ε ) = = 1 − ε ,

T 3 1 2

o (1 − ε )+ ε ε 2

1 2 1 2

whe r e n T i s t h e n o d e t h a t f o l l o w s T , a n d h 3 is the i n f o r m a tion set P l a y er 3 m o v es. As ε 2 → 0 , Pr ( n T | h 3 , ε 1 , ε 2 ) → 1 . T he ref o re , f o r c o ns i s t e nc y , w e ne ed μ ( n T | h 3 ) = 1 . F o r m a l l y , c on sisten cy is d e fi ned a s f ollo w s .

De fi ni ti on 39 An a s s e s s m e n t ( σ, μ ) is co n s i s ten t if th e r e e x i sts a s e qu en c e ( σ m , μ m ) of assessm e nt c o nver gi ng to ( σ, μ ) s u c h t h at f o r e ac h m ,

• σ m is c o m p lete ly m i x e d ( i.e . σ m

( a | h ) > 0 fo r e v e r y h a n d e very a ctio n a av ai l a b l e

at h ),

• and μ m ( ·| h ) is d e r i v e d f r o m σ m usi n g B ayes’ r ul e a t e ach h :

m σ m ( x )

μ ( x | h ) = σ m ( h ) ∀ x ∈ h.

De fi ni ti on 40 A seq u e n t ia l e q u ilib rium is a s e q u e n t ia l l y r a t io n a l a n d c o n s iste n t a s s e ss - me n t .

Exa m p l e 4 In th e g a m e i n F igu r e 9 .3 , t h e u n iqu e su b g a m e- p e r f e c t e q u ilibr i u m is s ∗ = ( E, T , R ) . L et us ch e c k t hat ( s ∗ , μ ∗ ) wh e r e μ ∗ ( n T | h 3 ) = 1 is a p erfe ct B a yesia n N a sh e q ui li bri u m . W e ne e d t o che c k t hat