Cha p t e r 1 0 Re p u t a t i o n F o r ma t i o n

In a c o m p l ete i n f o r m a tion ga m e , i t i s a ssum ed th at th e p la y e rs kno w exactly w h a t o th er p l a y ers’ p a y o ff s a re. I n r ea l l i f e t h i s a ssu m p tio n a l m o st n e v e r h o l ds. W ha t w o u l d h a p p en i n e q ui l i bri u m i f a pl a y e r ha s a sma l l a moun t o f d oubt a b out t he o t he r p l a y e r’ s p a y o ff s? I t t u rns o ut t h at i n dyna m i c g a m e s s u c h s m al l c ha ng es ma y h a v e p ro f o und e ff ects o n th e e q u ilib rium b e h a v i or . I n p ar ticu la r, w h en th e g am e i s l on g a n d pla y e r s a re pa tien t, t h e p l a y e rs ’ c o n c e rn re ga rdi n g f ormi ng a r eput at i o n f or ha vi ng a n a d v a n t a g e o us pa y o ff fu n ction o v erw h elm s all t he other c o n cern s, alter i n g equ ili b r iu m b eh a v i o r d ra m a ti call y . K r eps a nd W ilson (1 98 2) an d M ilg rom a nd R o b e rts ( 19 82 ) h a v e illust rate d t h i s o n e x - a m pl es , s uc h a s c e n ti p e de g a me a n d c ha i n - s t o re para do x. The a nal y s i s i s e xt e n ded l a t e r to m o re gen e ra l r ep ea ted ga m e s, m o st no tab l y b y F ud en b e rg a n d L evin e. In th is l e ctu r e, I w ill illustr a te the b a s ic ide a o n th e c en tip e d e g a m e . I w i ll sta r t w ith a sim p le ex am p l e, w h ic h a lso i llu s tra t es h o w o n e c o m p u tes a m ix ed -stra t eg y seq u e n t ia l e q u ilibr i u m .

1 0 .1 A S im p l e E x a m p le

C o nsid er th e g am e i n F igu r e 1 0.1. In th is gam e , P la y e r 2 do es not k n o w t he p a y o ff s o f P l a y er 1. She t hinks a t t he b e ginning t hat h is pa y o ff s a r e a s i n t h e u p p e r b r a n c h w i t h h i g h pro b ab ilit y 0 .9 , b ut sh e a lso a ssign s t h e sm all p rob a b ilit y o f 0.1 t o t he p o ssib ilit y th at h e is a v erse to p l a y do w n , e xiting the g am e. T h e fi rst t y p e o f p la y e r 1 is called "n o r m a l" t y p e , a n d the s e c o n d t y p e o f p la y e r 1 is c a lled t he " c ra zy " t y p e . If it w e re co m m on k n o w led g e t ha t p la y e r 1 is "n o r m a l" , t h e n b a c k w a r ds in du ctio n w o u ld y i eld t h e

103

(1,-5)

.9

.1

(4 ,4)

(3,3)

1

( 5 , 2)

2

1

(0

1 2 1

, - 5 )

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

Fi g u r e 10 . 1 :

fo llo w i n g : p l a y er 1 g o es do w n in th e l ast d ecision no d e; p l a y er 2 g o es across, a n d p la y er 1 g o e s d o w n i n t h e fi rst n o d e.

W h at ha pp en s i n t h e in co m p lete inform atio n g a m e, i n w h ic h t h e a b o v e c om m o n kn o w ledg e a ssu m p tion is rela xed ? B y seq uen t i a l r ati o n a lit y , the " cr azy" t y p e (in t h e lo w e r b ra nc h ) alw a ys g o es acr oss. In the l a s t d ecisi o n n o d e, th e n o r m a l t yp e a ga i n g o e s do wn. C a n i t b e the c as e t hat t he no rmal t y p e go e s do wn i n hi s fi rst d ecision n o de , a s i n t he c o m p let e inform atio n c a se? It tu rn s o u t tha t th e a n s w e r i s N o. If in a seq u e n t ial e q u ilib rium " n o r m a l" t y p e go e s d o w n in the fi rst d eci s io n n o d e, in h er inform at io n set, p la y er 2 m u st a ssign p r ob a b ilit y 1 to th e c raz y t y p e. ( B y B a y es r u l e, Pr ( cr az y | acr o ss ) = 0 . 1 / (0 . 1+ ( . 9) (0)) = 1 . T hi s i s r e q ui re d f or c o ns i s te nc y . ) G i v e n

th is b elief a nd the a ctio n s t h a t w e h a v e a lre a d y det e rm in ed , s h e ge ts -5 fro m g o in g

across an d 2 f r om going d o w n , an d s h e m u st go d o w n f o r seq uen t ial r ation a lit y . B u t th en " n orm a l" t y p e sh ou ld go acr o ss as a b est r ep l y , w h i c h con t rad i cts th e a ssu m p tion t h a t he go e s do wn.

S i m ilar l y , o n e c a n also sh o w th at the r e i s n o s e q ue n tial e q u ilibr i u m in w h ic h t h e n o rm al t y p e g o es across w i th pro b a b i lit y 1 . If t ha t w ere t he case, t h e n b y c o n si sten cy , p l a y er 2 w ou ld a ssign 0.9 t o n o r m a l t yp e i n h er inform atio n s et. H er b e st resp on se w o u l d b e t o go acros s f o r sure, and i n t hat c as e t he normal t y p e w o ul d p ref e r t o g o d o w n i n th e fi rst n o d e.

In a n y s eq u e n t ial e q u ilib rium , n orm a l t y p e m u st m ix in h i s fi rst d e cision n o d e. W r ite

α = P r ( acr o ss | nor m a l ) an d β for t h e p r o b a b ilit y o f goin g ac ross fo r p la y e r 2 . W rite also μ f o r t he pro b a b i l i t y pl a y er 2 a s s i gns t o t he upp e r n o d e ( t h e n o r mal t yp e ) i n he r inform at io n set . S in ce n o rm al t y p e m i x e s ( i.e. 0 < α < 1 ), h e is ind i ff er en t. A c ro ss

yi el ds

3 β +5 ( 1 − β )

w h ile d o w n y ield s 4 . T h e re fo re, i t m ust b e t h a t 3 β +5 ( 1 − β ) = 4 , i.e.

β = 1 / 2 .

Si nc e 0 < β < 1 , p l a y e r 2 m u s t b e i ndi ff eren t b et w e en goin g d o w n , w h i c h yield s 2 f o r su re, a n d go i n g a cro ss, w h i c h y ields t he exp e cted pa y o ff of

3 μ + ( − 5) (1 − μ ) = 8 μ − 5 .

Tha t i s , 8 μ − 5 = 2 , a n d

μ = 7 / 8 .

B u t t his b eli e f m u s t b e c on sisten t:

7 0 . 9 α

= μ = .

8 0 . 9 α + . 1

T h erefor e,

α = 7 / 9 .

T h is c o m p let e s t h e com p uta t ion o f t he u n i q u e s e q ue n t ial e q u ilib rium , w h i c h is d e p i cted in F i gu re 10.2.

Exe r c i s e 1 5 C h e c k t hat t he p a i r of m i xe d s t r at e g y p r o fi l e an d t he b e l i ef assessm e nt is in d e e d a s e q u e n t ia l e qu ilib r i u m .

N o tice tha t in sequ e n t ia l e qu il ib rium , a fter o b servin g th a t p l a y er 1 g o e s a cro ss, pla y er 2 i nc rea ses her p rob a b ilit y f o r p l a y er 1 b ein g a c ra zy t y p e w h o w ill go a c ro ss a l l t h e w a y , f r o m 0 . 1 t o 0 . 1 2 5 . I f s h e a s s i g n e d 0 p r o b a b i l i t y t o t h a t t y p e a t t h e b e g i n n i n g , s h e w o u l d n o t c ha n g e h er b e liefs after s h e ob serv e s t h a t h e g o e s a cro ss. In the l a tter c ase, pla y er 1 c ould n e v e r c on vin c e h er th at h e w ill go acr o ss (no m atter h o w m a n y tim e s h e g o e s across), a n d h e w ou ld no t t r y . W hen t h a t p rob a b ili t y i s p o sitiv e (n o m a tter h o w sm all it is), she i n c rea ses he r p rob a b ilit y o f h im b e ing c ra zy after s he see s h im g o in g a cr oss, an d p la y e r 1 w o u l d t ry go ing a c r oss w ith s om e p rob a bilit y e v e n h e i s n o t cra z y .

(1 , - 5 )

.9

 

.1

(4,4 )

(3,3 )

1

( 5, 2)

2

1

(0

1    2  1

, - 5)

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

Fi g u r e 10 . 2 :

100

100

Fi gure 10. 3 : C en ti p e de G a m e

Exe r c i s e 1 6 In th e a b o v e ga m e ,c o m p u te th e s e q u e n t ia l e qu ilib riu m fo r a n y in itia l p r o b - a b ility π ∈ (0 , 1) of cr azy t yp e ( in the fi gu r e π = 0 . 1 ).

1 0 .2 R e p u tation in C e n t ip e d e G am e

C o nsid er th e p erfect-i n f o r m a tion ga m e d e p i cted in F i gu re 10 .3. I n t his g a m e, th ere a re t w o p la y e rs in a r e l a t ion s h i p. T h e p la y ers alte rna t in gly g et a n o p p o rt un it y to end th e rela tion sh i p a n d g et extra p a y o ff in th e e xp en se of th e o th er pla y er. S ta ying in th e rela tion sh ip is b e n e fi cial fo r e a c h p l a y er, so tha t a p l a y er w ou ld lik e t o r em ain i n t h e

rela tion sh i p if she k no w s tha t th e o th er p l a y er w i l l sta y in th e r elatio nsh i p i n t h e follo w i n g p e ri o d . I f t he other p la y e r b reaks u p i n t he n e xt p e rio d , h o w ev er, s h e w o uld l o s e f ro m sta y in g i n f or a n oth e r p erio d . In p a rticu l ar , s he lose s 1 un it if th e o the r p l a y er br eak s up in the n ex t p e r io d a n d g a in s 1 un it if the o th er pla y e r s r e m a i n s in th e r e l a t ion s h i p a nd s h e b r e a k s u p t w o p e r i o d s l a t e r . A s i t i s s e e n i n t h e fi gure, p l a y e rs’ p a y o ff s a ccu m u la te to l a rg e n u m b e rs if th ey sta y i n th e g am e f o r a l o n g w hile.

U n f o rt unat e l y , ho w e v e r, bac k w a rds i nduct i o n l ea ds t o a u ni que o ut co m e : p l a y e r 1 bre a ks up i n t h e fi rs t p e r i o d, yi el di ng a l o w pa y o ff o f 1 t o e a c h p l a y e r . I n t h e v e r y l a s t pe r i od , p l a y e r 2 g o e s d o w n . K n o w i n g t h i s , i n t h e pe r i od be f o r e t h e l a s t p e r i o d , p l a y e r 1 go es do w n , i n o r d er to a v oi d a unit loss f r om pla y er 2’s b reaking u p i n t he next p e rio d . Kno w i n g t hi s , i n t h e p re vi o u s p eri o d, pl a y e r 2 g o e s d o w n, a n d s o o n.

Exe r c i s e 1 7 S h o w th a t th er e i s a u n iq u e N a s h e q u i lib r iu m o u t c o m e in th e c e n tip e d e gam e ab ove.

D e spite t h e sim p licit y o f t he argu m e n t , t he b a c k w a rd s i nd uction ou tcom e i s p ar a - do xi cal f or m a n y . T here is a f eel i ng that one s hould t ry and see w h ether t he other p la y e r sta y in th e g am e g i v en th e h igh p a y o ff s l ater in the g a m e. K r eps a n d W ilson h a v e sho w n th at the a rg um en t i s i n d eed v er y f ra gile w i th resp ect to in com p lete in for m ati o n . T h ey in tro d u c e a sm all a m o un t o f i n f or m a ti o n in suc h a w a y th at in th e r esu lting i n c om plete- inform at io n g a m e t he re is a u n i q u e seq u e n t ia l e q u ilib rium , a n d in th at eq u i lib rium th e pl a y e r s r emai n i n t he g a me un t i l n ea r t he end o f t he g a me a n d s ta rt m i xi ng t h ere a f t e r . I w ill p r esen t thei r a na lysis i n g reat d e ta i l . B eforeh a n d , I w a n t t o e m p h a si ze th at th e ba c k w a rds i nduc t i on a r gum e n t hea v i l y r e l i e s o n t he a s s u mpt i o n that t h e p a y o ff s a n d t h e ra tion alit y o f t h e p l a y e r s i s m utu a lly k n o w n a t h igh o rd er s, i.e., ev e r y b o d y k n o w s tha t th e p a y o ff s a r e a s i n t h e fi gure , e v e ryb o dy kno w s t hat e v e ryb o dy kno w s t ha t t he pa y o ff s ar e a s i n t he fi gure . . . up t o v e ry hi gh orde rs . I n t he l a s t p e ri o d , P l a y e r 2 g o es do wn b y hi s r at i o na l i t y a l o ne . I n t he previ o us p e ri o d , P l a y e r 1 g o e s do wn not o nl y b e c a us e h i s pa y o ff s a r e a s i n t h e fi gu re bu t a lso b ecau se h e kno w s t h a t P la y e r 2 is ration al an d h er pa y o ff s a r e a s i n t h e fi g u re. I n t w o p e ri o d s b efo r e t h e end , P l a y er 2 g o e s d o w n b ecau se s h e i s r a t i o na l a nd her p a y o ff s a r e a s i n t h e fi gu re an d s h e kn o w s t h a t p la y e r 1 is ration al wi t h t h e p a y o ff s i n t h e fi gur e an d w i l l r em ain t o k n o w t h a t P l a y e r 2 is ration al and h as th e p a y o ff in th e fi gu re. L ik ew ise , P l a y er 1 g o e s d o w n i n t h e fi r s t p e r i o d b e c a u s e h e i s ration al kn o w s t hat P la y e r 2 i s ration al and t hat P l a y e r 2 w i l l rem a in to b e liev e that

{.9 99} 197 5 4 3 2 1 = n

1 2 2 1 2 1 2 10 0

10 0

…

1 0 96

1 3 99

98 97 99

98 10 0 99

98

10 1

1 2 2 1 2 1 2

{.0 01}

 5  3  1

…

-1 -1

98 99

Fi gure 10. 4 : C en ti p e de G a m e w i th D o ubt

Pl a y er 1 i s r at i o na l and that . . . up to 19 8 i t e r a tion s. W h en the h igh e r-o r der b el iefs ar e n o t a s in th e m o d el, p la y e rs’ b eh a v io r w ill n o t l o o k lik e t h e o n e p resc rib e d b y t h e ba c k w ards i nduct i o n a ppl i e d t o t he mo de l .

K r ep s a n d W i lso n co nsid er th e i ncom p l ete-i n form atio n g a m e i n F igu r e 1 0 . 4. N o w , Pl a y er 2 i s n ot certai n t hat P l a y e r 1 ’ s pa y o ff s a re a s i n t he c e n t i p e de g a me . S he do e s a s s i gn v e ry hi gh proba b i l i t y o n t he ev en t t ha t P l a y e r 1 ’ s pa y o ff s a re a s in the c en tip e d e ga m e . S h e th in k s , h o w ev e r , t h a t w it h t h e sm all p ro ba bilit y o f 0 .0 01 , P la y e r 2 m a y b e a v e r se to ex itin g t he relat i o n ship . T h i s s itu a tio n is m o d e led b y u sing t w o t y p e s fo r P l a y e r 2 . W i th p r o b a b ilit y 0 .9 99 , P la y e r 1 is o f "n or m a l" t y p e , w ith p a y o ff s a s i n t h e or i g inal cen tip e de gam e , a n d w i th p r ob ab ili t y 0.001, h e is of "crazy" t yp e w ho gets -1 fr om e x iting a n d 0 f ro m n ot ex iting .

A l th ou gh the l a tter p ro ba bilit y i s s m a ll, w hen s h e ob serv es t h a t P la y e r 1 rem a in s i n t h e g a m e , Pl a y e r 2 m a y up da te he r b el i ef a nd as s i g n a h i g he r p robabi l i t y t o the c r az y t y p e . I n p a r ticu lar, i f sh e e xp ects th at th e n o r m a l t yp e p la ys as in th e o rig i n a l c en tip e d e gam e , t hen a f t er observi ng that Pl a y er 1 r em ai ns i n the g am e, she b ecom es con v i n ced th at P l a y er 1 i s of c r azy t y p e (assig n in g p ro b a b i l i t y 1 o n t h e crazy t yp e). In t h at c a se, h e r b est resp o n se w o u l d b e t o r em a i n i n t he g a m e u n til t h e v e ry en d. O f co urse, i f t h i s

w e re th e e qu il ib riu m stra teg y , th en th e n orm a l t yp e o f t h e p l a y er 1 w ou ld rem a in un til h i s l a s t d e c ision n o d e, lea d in g t o a c on tra d ic tion . T ha t i s, the n o r m a l t y p e m u s t g o ac ross w i th p o sitiv e p r ob a b ilit y i n t h e fi rst p er i o d . Ind eed , a s I m e n t ion e d b efo r e, i n seq u e n t ia l e q u ilib rium h e g o es ac ross a l l t h e w a y t o h is last d ecision no d e w i th p o sitiv e p r ob ab ili t y .

T o c o m p u t e t he seq u e n t ia l e q u ilib rium , d en ote t he n o des w ith r esp ect t o h o w fa r th ey are f ro m t he end o f t he g a m e , b y w riting n = 1 f o r t he last p e rio d (w here P l a y er 2 m o v es), n = 2 for t h e p e r i o d b e fo re th e l a s t p erio d ( w h ere P l a y e r 1 m o v es), a n d so o n , as in the fi g u re. I w ill dev e l o p t he ar gu m e n t as sm a l l step s, w h ic h a re sta t ed as l e m m as. The fi rs t o bs erv a t i on i s t h at t h e c raz y t y p e m u s t go ac ros s wi t h probabi l i t y 1 at al l o f h i s i n f o r m a tion sets:

Lem m a 3 In any s e q uen t i a l e qu i l i b ri um , t he cr azy t yp e p l a ys acr o ss wi th pr ob abil i t y 1 at every i nfo r m a tio n s et Player 1 m oves.

In deed , a t a n y in fo rm a t ion s et, t h e cra z y t yp e g ets 0 from exiting a n d 1 f r o m n ev er exitin g, a n d h en ce b y sequ e n t ia l r ati o na lit y o f t he "cr a zy" t yp e a t t h e n o d e , h e m u s t g o across w i th p r ob ab ili t y 1. T h i s further i m p lies t h a t P la y e r 2 n e v e r e x i ts for s u r e b ef ore th e l ast p erio d :

Lem m a 4 In a n y s e q u e n tia l e qu ilib riu m , P la y e r 2 p l a y s a cr o s s w ith p o s itive p r o b a b i lity at every i nfo r m a tio n s et of h e r w ith n > 1 .

Pr o o f . Su p p os e t h a t t h e le m m a is false a nd let n ˆ

> 1 b e t h e l arge s t no de (i . e .

t he

ea rliest p e r i o d ) a t w h i c h P l a y e r 2 g o e s d o w n w ith p rob a b ilit y 1. T h en, b y s e q ue n t ial ra tion alit y , in the p re v i o u s p erio d ( i.e. a t n ˆ + 1 ) , t h e n o r m a l t y p e m u s t g o d o w n w i t h p r ob ab ili t y 1. T h i s is b ecause g oin g do w n yi elds 1 u n i t m or e p a y o ff t h an goi n g a c r os s a n d l e t t i n g P l a y e r 2 g o e s d o w n . B u t n o t e t h a t t h e i n f o r m a t i o n s e t n ˆ of Pl a y er 2 i s rea c he d w ith p ositiv e p r o b a b i lit y as b o th P l a y er 2 a nd th e c ra zy t y p e of pla y e r 1 g o across un til i n f or m a ti o n set n ˆ . H en ce, b y con s isten c y , P l a y er 2 m ust a ssign p r ob ab ili t y 1 o n t h e c r a z y t y p e a t n ˆ . I n t ha t c a se, b y sequ e n t ia l r a t ion a l i t y of P l a y er 2 a t n o d e n ˆ , sh e m u s t g o a cr oss w ith p r o b a b i l i t y 1, a c on trad iction .

L e m m as 3 a nd 4 i m m ediatel y im ply t hat a l l of P l a y er 2’s i nf orm a tion sets a re reac hed:

Lem m a 5 In a n y s e q u e n tia l e qu ilibr i u m , eve r y in fo r m a t io n s et o f P l a y e r 2 i s r e a ch e d w ith p o s itive p r o b a b ility.

By t h e a rg um e n t i n t he pro of of L e m ma 4 , t h i s i m pl i e s t hat t he no rm a l t y p e of Pl a y e r 1 a lso p la y s acr o ss w i th p o sitiv e p r ob a b ilit y :

Lem m a 6 In a n y s e q u e n tia l e q u ilibr i u m , t h e n o r m a l ty p e P l a y e r 1 p la ys a c r o ss w i th p o si ti ve pr ob abil i t y at every i nf orm a t i o n s et wi th n > 2 .

Pr o o f . If the n orm a l t yp e p l a ys do w n w i th probabi l i t y 1 a t n , t h e n a t n − 1 , w h i c h i s rea c he d w it h p ositiv e p rob a b ilit y b y L e m m a 5 , P la y e r 2 as sig n s p r o b a b i lit y 1 t o c ra zy ty p e . I f n − 1 > 1 , s h e th en g o es across a t n − 1 w i th p r o b a b ilit y 1 . I n t h a t c a se, th e n o rm al t y p e o f p l a y er 1 p la y s a c ro ss w i th p r o b a b ilit y 1 at n .