notes08

Cha p t e r 8 R a tio n a liz a b ilit y

The d e fi ni t i on of a g am e ( N, S , u 1 ,..., u n ) im p l ic it ly a ssu m e s t ha t

1. th e set o f p l a y ers i s N , t he set of a v ai l a bl e s trategi e s t o a pl a y er i is S i , a n d t h e

pl a y e r i tries t o m a x im ize t h e ex p e c ted v a lu e o f u i : S

be l i e f , a n d t h a t

2. eac h pl a y er kno w s 1 , a nd that

3. eac h pl a y er kno w s 2 , a nd that

...

n eac h pl a y er kno w s n − 1

...

ad i n fi ni t u m.

→ R a c c o r d i n g t o s o m e

T h a t is, i t i s i m p licitly a ssum e d t h a t i t i s c o m m on kn ow le dge among t he pl a y ers th at th e g am e i s ( N, S , u 1 ,..., u n ) an d t h a t p la y e r s are r a ti on al (i .e. t h e y a r e exp e cted u t ilit y m a x im ize r s). A s a so lutio n con c e p t, R a tion aliza b ilit y y ie ld s t h e strate gies tha t ar e c o n sisten t w ith t h ese assu m p tion s, cap t u r ing w ha t i s i m p l i ed b y th e m o d el (i.e. t h e ga m e ). O t h e r s o l utio n c o n cep t s i m p o s e f u r th er assu m p tio n s, u s u a lly on p l a y er s’ b e li efs, to o b ta in sh arp e r p red i ctio ns. I n t h i s l ect ure , I w ill fo rm a lly in tro d u c e r atio na lizab ilit y an d p resen t s om e o f i ts a p plica t ion s . T he ou tline i s a s f ollo w s . I w i ll fi rst illus t rate th e idea on a s im p l e e xam p le. I w i l l then pr esen t t h e form al th eo ry . I w i l l fi n a lly a p ply ra tion aliza b ilit y t o C ou rn ot an d B er tran d c om p e titio n s.

73

8. 1 E xam p l e

C o nsid er th e f ollo w i ng ga m e .


2, 0	-1,1
0, 10	0, 0
-1 ,-6	2, 0

1 \ 2 L R T

M B

(8 . 1 )

A p la y e r i s s aid t o b e r a t ion a l i f h e p la y s a b est res p on se to a b elief a b o ut t h e o th er p l a y ers’ stra t eg ies. W h a t d o es ra tion alit y i m p ly for t h i s g a m e?

Cons i d e r P l a y e r 1. H e i s co n t empl a t i n g a b o ut whet he r t o p l a y T , o r M , o r B . A qui c k ins p ect io n o f h is pa y o ff s r e v e a l s t h a t h i s b e s t p l a y d e p e n d s o n w h a t h e t h i n k s t h e o t h e r p l a y er d o es. L e t’ s t hen w r i te p for t h e p r o b a b ilit y h e a ssig n s t o L ( a s P la y e r 2 ’s pla y ), rep r esen tin g h i s b eli e f a b o u t P l a y er 2 ’ s s trateg y . H i s e xp ected p a y o ff s f r o m p l a y i n g T , M, a n d B a r e

U T = 2 p − (1 − p ) = 3 p − 1 , U M = 0 ,

U B = − p + 2 ( 1 − p ) = 2 − 3 p,

resp ecti v el y . T h ese v a lu es as a f u n c tion of p ar e p lo tted in t h e f ollo w i ng gr ap h:

U

U B

U T

U M

2

0

-1

0 p 1

A s it is clear f ro m t he gr ap h, U T is the l arg est w h en p > 1 / 2 , a n d U B is th e l a r g est w h en p < 1 / 2 . A t p = 1 / 2 , U T = U B > 0 . H en ce, i f p l a y e r 1 is ra tion al, t h e n h e w i l l p l a y B whe n p < 1 / 2 , D w h e n p > 1 / 2 , a n d B o r D i f p = 1 / 2 .

N o tice th at, i f P l a y e r 1 i s ratio n a l , t h e n h e w il l n ev er p l a y M – no m a tter w ha t h e b e l i ev es ab o u t t h e P l a y er 2 ’ s p l a y . T h erefo r e, i f w e a ssum e th a t P l a y er 1 i s r a t ion a l (a nd tha t the g am e i s a s i t i s d escrib ed ab o v e), t h e n w e c a n co nclud e th at P l a y er 1 w ill no t p la y M . T h i s i s b eca u s e M is a st ri c t l y dom i nat e d s t r at e g y . I n p ar ticula r, th e m i x e d s t r ate g y t h a t p uts p ro ba bilit y 1 / 2 o n T a n d pro b a b ilit y 1 / 2 o n B y ie lds a h i g h er exp ected p a y o ff tha n stra teg y M no m a tter w h a t ( p u r e) stra teg y P l a y er 2 p la ys. A co nsequence o f t h i s i s t ha t M is n e v e r a w e ak b est resp o n se to a b elief p , a ge neral f ac t th at w i ll b e e s tab lishe d m om en ta ril y .

W e no w w a n t t o u nde r st a n d t he i m pl i c at i o ns o f t h e a s s u mpt i o n t h at pl a y ers k no w th at th e o ther pla y ers a re also ration al. N o w , r ation a l i t y of p l a y er 1 r equ i res t h a t h e do e s not p l a y M . F o r Pl a y er 2 , her b o t h a ct i o ns ca n b e a b e s t re pl y . I f s h e t hi nks t hat P l a y e r 1 i s n o t l i k e l y t o p l a y M , t h e n s h e m u s t p l a y R , a n d i f s h e t h i n k s t h a t i t i s v e r y lik ely t h a t P la y e r 1 w ill p l a y M , th en she m u s t p la y L . H e n c e , r at io n a lit y o f p la y e r 2 do e s not put an y r es t r i c t i on o n he r b e h a v i o r. But , what i f s h e t hi nks t hat i t i s v e r y lik ely t h a t p la y e r 1 is r a tio n a l (a nd th at h i s p a y o ff are a s i n ( 8. 1) )? In t h at c a s e , s i n ce a r at io n a l p la y e r 1 do e s n o t p la y M , s he m u st a ssig n v e ry sm all p rob a bilit y f or p l a y er 1 pl a y i n g M . I n f a c t, i f s h e k no ws t h a t pl a y e r 1 i s r at i o nal , the n s h e m us t b e s ure t ha t h e w ill no t p la y M . I n t h a t c ase , b e in g r atio na l, sh e m u s t p la y R . I n s u m m a r y , if p l a y er 2 i s r a t i onal and s he kn ow s t hat player 1 i s r at i o n a l , t h en she m ust p lay R .

N o tice th at w e fi rst e lim in ate d a l l o f t h e stra t eg ies t h a t a re stric t ly d o m i na ted (n am ely M ), then takin g th e r esu l t i n g g a m e, w e eli m ina t ed a gain a l l o f the stra t e - gies th at ar e s tr i c tly d om inated (n am ely L ). T h is is called tw ic e i te r a te d e lim i n a tio n o f strict l y dom i n at e d st r a t e gi es . T h e r esu l t i n g s tra teg i e s a re the s tra t eg ies t ha t a re con s is - ten t w i th th e a ssum ptio n t h a t p la y e r s a r e r a t ion a l a n d they kno w th at th e o ther pla y ers ar e r ati o n a l.

A s w e im p o se fur t he r a ssu m p tio n s a b o u t ra tion alit y , w e k eep iter ativ e l y e lim ina t in g all strictl y d o m ina ted stra teg i es (if t h e re rem a ins a n y ). R eca ll th a t ratio n a l i t y o f p la y e r 1 r equi res h i m t o pl a y T o r B , a nd kno w l e dge o f t he f a c t t h a t pl a y e r 2 i s a l s o r at i o na l do e s not p ut an y r es t r i c t i on on hi s b e h a v i o r– as rat i onal i t y i t s el f d o e s n ot re s t ri ct Pl a y e r

2’s b e h a v ior . N o w , assu m e tha t P l a y er 1 a lso k n o w s (i) t ha t P la y e r 2 is ra tion al an d ( ii) th at P l a y er 2 k no w s th at P l a y er 1 i s r ati o na l ( a n d t h a t t h e g a m e is as in (8 .1)). T h en, as th e a b o v e an a l ysi s sno w s, P l a y er 1 m u s t k no w t ha t P l a y e r 2 w i ll p l a y R . In th a t ca se, b e in g r a t ion a l h e m u s t p la y B . T h e re fo re, c o m m o n k no w l ed ge o f ra tion alit y i m p lies t ha t P l a y e r 1 p la y s B a n d P l a y er 2 p la y s R .

In the n ext secti o n , I w ill ap ply t h ese i d ea s m o r e g en era l l y .

8. 2 T heory

Fi x a ga me ( N, S , u 1 ,..., u n ) . T o b e c on crete, d e fi ne the c on cepts o f b eli e f, b e st resp on se, an d r atio na lit y a s f o l lo w s .

Q

De fi ni ti on 26 Fo r a n y p l a y e r i , a ( c o r r e l a t e d ) b e lief of i ab out t he ot he r p l a y e r s ’ st r a t e - gies is a p r o b a bil i ty d i stribution μ − i on S − i = j = / i S j .

T h e essen t ial p art o f t h i s d e fi nitio n i s th at the b el ief μ − i of pl a y e r i allo w s c o rre la tion b e t w een the o th er pla y ers’ strategies. F or exa m p l e, in a g a m e o f t hr ee p l a y ers i n w h i c h ea c h p l a y er is to c h o o se b e t w een L e ft a n d R igh t , P la y e r 1 m a y b eli e v e th at w i th pro b a - b i lit y 1 /2 b o t h of the o th er p l a y ers w ill p l a y L e ft a n d w ith p ro ba bilit y 1 /2 b o th pla y e r s w ill p l a y R i gh t. H e nce, view ed a s m i xed s trategies, it m a y a p p ea r a s t h o u g h P l a y e rs 2 an d 3 u s e a co m m on ran d o m iza t ion d evi c e, co n t rad i ctin g t h e fact tha t P l a y ers 2 a n d 3 m a k e the i r d e c ision s ind e p e nd en tl y . O n e m a y th en fi nd suc h a c orrel a ted b el i e f u nrea - so na ble. T h is lin e o f re aso n in g i s b a sed on m i sta k e n ly ide n tify in g a p la y e r’s b elief w ith other p la y e rs’ c on scious r an d o m i zation. F or P l a y er 1 t o h a v e s u c h a correl a ted b elief , h e d o es no t n eed t o b eliev e tha t th e o ther p l a y ers c ho o s e t heir d ecisio n s t og eth e r. Ind e ed, he do e s not t hi nk t h a t t h e o t h er pl a y e r s a re us i n g r ando m i z a ti on devi c e . He t h i n ks t h at ea c h of th e o th er pla y ers p la y a p u r e stra t egy t h a t h e d o e s n ot kno w . H e m a y a ssign co rrela ted p ro b a b i lities o n t h e o t h e r p l a y e rs stra teg ies b ecau se h e m a y a ssign p o sitiv e p r ob ab ili t y to v a rio u s t h e o r i e s a n d ea c h o f th ese th eo ries m a y l ead t o a predicti o n a b ou t ho w t he pl a y ers p l a y . F o r e xampl e , h e m a y t h i n k t hat p l a y e rs pl a y Le f t ( a s i n t he c a rs in E n gla n d ) or pla y ers p la y R igh t (a s i n t h e ca rs in F r an ce) w i th ou t k no w i n g w h ic h o f t h e t h e o r i e s i s c o r r e c t .

Dep e ndi ng on whet her o ne al l o w s c o rre l a t ed b e l i e f s , t here are t w o v e rs i o ns o f Rat i o - n a liza b ilit y . B e c a u s e o f t h e a b o v e r ea son i ng , i n t h i s c ou rse , I w ill fo cu s o n c orre la ted

v e rsion o f R at io na lizab ilit y . N o t e t ha t t h e orig in al de fi n i tion s o f B er nh eim ( 19 85 ) a nd P e ar ce (1 98 5) im p o se ind e p e nd en ce, a nd these c on cepts a re iden tical i n t w o p l a y er g a m es.

De fi ni ti on 27 Th e exp ected p a y o ff fr o m a s tr ate g y s i agai n s t a b e l i ef μ − i is

u i ¡ s i , μ − i ¢ =

s − X i ∈ S − i

u i ( s i , s − i ) μ − i ( s − i ) .

i

De fi ni ti on 28 Fo r a n y p l a y e r i , a s t r a t e g y s ∗ is a b e st resp on se to a b elief μ − i if an d

on l y i f

i

u i ( s ∗ , μ − i ) ≥ u i ( s i , μ − i ) , ∀ s i ∈ S i .

H e r e I u se th e n otio n o f a we ak b e st r e pl y , r equ i rin g th at there i s n o o th er str ateg y th at yi elds a s trictl y h igh e r p a y o ff a g a i nst t he b e lief. A n otio n o f str ic t b e s t r ep ly w o u l d req u ire t hat s ∗ yield s a s trictly h ig her e xp ected p a y o ff t h an an y o ther s t rat e g y .

De fi ni ti on 29 F o r a n y pl a yer i , p l a y i n g a s t r a t e g y s i is s a id to b e r a tio n a l i f a n d o n ly if s i is a b est r esp o nse t o s om e b el ief μ − i .

P l a y in g a s tr ategy i s n ot ration al if an d o nly i f i t i s n ev er a w eak b est rep l y . T h is i d ea of rat i onal i t y i s c l o s e l y r el at e d t o t h e f ol l o wi ng not i on of dom i nance .

i

De fi ni ti on 30 A s t r a t e g y s ∗ strictly d o m i na tes s i if a n d o n l y i f

i

u i ( s ∗ , s − i ) > u i ( s i , s − i ) , ∀ s − i ∈ S − i .

s i ∈ S i

S i m i la r l y , a m ix e d str a te gy σ i strictly d om i n ates s i if a n d o n l y i f u i ( σ i , s − i ) ≡ P 0

u i ( s i , s − i ) , ∀ s − i ∈ S − i .

σ i ( s 0 ) u i ( s 0 , s − i ) >

i

That i s , n o m at t e r w ha t t he o t he r p l a y e rs pl a y , p l a yi ng s ∗

is strictly b e tter t h a n

i

pl a y i n g s i for p la y e r i . I n t h a t c a se, if i is ratio n a l , h e w o u ld ne v e r p la y t h e strictly do m i nat e d s t r a t e g y s i . T hat i s , t h e r e i s n o b e l i e f u nde r w hi c h he w o ul d p l a y s i , f o r s ∗ w o u l d a lw a y s y ield a h igh e r e x p ecte d p a y o ff th an s i no m a tter w hat p l a y e r i b e liev e s ab ou t t h e other p la y e rs. 1

De fi ni ti on 31 A s t r a t e g y s i is sa id to b e strictl y d o m i na ted if a n d o n l y i f t h e r e e x ists a p u r e o r m ix e d str a te gy th a t str i c t ly d o m i n a te s s i .

1 A s a s im ple e x e rcise, pro v e t his s t a te men t.

A N otice t ha t n eith er o f th e p u r e s tra t eg ies T , M , a nd B d om ina t es an y s tra t eg y . N e v e rth e less, M i s d om ina t ed b y th e m ixed strategy tha t σ 1 th at p u ts p r ob ab ili t y 1/2 on e a c h of T a nd B. F o r e ac h p , t he pa y o ff fr o m σ 1 is

1 1 1

U σ 1 = 2 (3 p − 1) + 2 (2 − 3 p ) = 2 ,

whi c h i s l a r g e r t ha n 0 , t he pa y o ff from M . R eca ll th at in o u r e x a m p le the r e i s n o b e l ie f

( p ) under whi c h M is a b est resp on se. T h is is ind e ed a g en er al resu lt:

The o rem 9 Pl a y i n g a s t r a t e gy s i is n o t r a t io n a l f o r i (i.e. s i is n e ver a we a k b e st r e sp on se to a b el ie f μ − i ) i f a n d o n l y i f s i is str i ctly d o m i n a te d .

Pr o o f . I w i l l o nl y s ho w t hat i f s i is no t s trictly d o m in ate d it is a w ea k b est resp on se to som e b e lief. (T he con v erse i s straigh t fo rw a r d.) F o r ea c h m i xed s tra t eg y σ i , c o n s i d e r th e u tilit y v e cto r

→ u i ( σ i ) = ( u i ( σ i , s − i )) s − i ∈ S − i ,

an d l et U i b e th e s et of all s u c h v ectors. C learly , U i i s c o nve x . T a k e a ny s i th a t is no t s t ri c t l y domi na t e d, a n d d e fi ne

V i = © v ∈ R S − i | v À → u i ( s i ) ª .

Cl e a r l y , V i is a l so co n v ex, a n d since s i is n o t s trictly d om i n a t ed , U i ∩ V i = ∅ . H e n c e , b y th e sep ara t ing - h y p e rpla ne th eo rem t her e exists μ − i ∈ R S − i suc h th a t μ − i · ( → u i ( σ i ) − v i ) ≤

0 fo r a ll → u i ( σ i ) ∈ U i an d v ∈ V i . B y d e fi ni t i o n of V i , μ − i ≥ 0 . S i n c e → u i ( s i ) is o n th e b o unda ry o f V i , i t i s a l s o t r u e t h a t f o r a l l → u i ( σ i ) ∈ U i , μ − i · ( → u i ( σ i ) − → u i ( s i )) ≤ 0 , s ho wi ng th at

u i ¡ σ i , μ − i ¢ = μ − i · → u i ( σ i ) ≤ μ − i · → u i ( s i ) = u i ¡ σ i , μ − i ¢ .

(I n t hi s p ro of , o ne ca n a l l o w S − i to b e in fi ni t e . )

T h eo rem 9 states th at i f we assum e t h at pl ayers a r e r a ti on al (an d t h at t h e g am e i s as descri b e d), t hen w e c oncl ude t hat n o p l a yer p l a ys a s t r at e g y t hat i s s tri c tl y dom i n at e d (by s om e m i x e d or pu r e st r a t e gy), a nd t h is i s al l w e c an c o n c l u de.

Let u s w ri t e

i

S 1 = { s i ∈ S i | s i is n o t s t r ictly d om in at ed } .

i

By The o re m 9 , S 1 is th e set of a l l s trategies t ha t a re b est r esp o n se to so m e b e lief.

j

− i

Let u s n o w e x pl o r e t he i m pl i c at i o ns of t h e a s s u m p ti on t h a t pl a y er i i s rat i onal and kno w s t hat t he o t he r p l a y e rs are r at i o na l . T o t h i s end, w e c o ns i d er t h e s t r a t e g i e s s i th at a r e b est resp on se to a b eli e f μ − i of i on S − i su c h tha t fo r e ac h s − i = ( s j ) j = / i wi t h μ − i ( s − i ) > 0 an d f or eac h j , t he re ex ists a b elief μ j of j on S − j suc h tha t s j is a b e s t resp onse to μ j . H ere, the fi r s t p a r t ( i . e . s i is a b est resp on se to a b elief μ − i ) c orr esp o n d s t o rat i onal i t y o f i an d t he seco nd p a rt (i .e. i f μ − i ( s − i ) > 0 , t h e n s j is a b est resp on se to a b elief μ j ) c o rresp o n ds to th e a ssu m p tion th at i kno w s t hat j i s rat i onal . B y T heorem 9, ea c h su c h s j is n o t s t r ictly d om in a t ed , i.e., s j ∈ S 1 . H e n c e , b y a n o th er ap plica t ion o f The o r e m 9 , s i is n o t stric t l y do m i nate d g iv en S 1 , i . e ., there d o e s n ot exist a (p o ssi b l y

mi x e d ) s t r a t e g y σ i suc h th at

− i

u i ( σ i , s − i ) > u i ( s i , s − i ) ∀ s − i ∈ S 1 .

O f cou r se, b y T h e o r em 9, the c on v e rse o f t he la st sta t em en t i s a lso t ru e. T h erefore, th e set of str a teg i es tha t a r e r atio na lly p la y e d b y p la y e r i kno w i n g t ha t t he ot he r p l a y e rs i s also rati on al is

i

− i

S 2 = © s i ∈ S i | s i i s n o t s trictly d om i n a t ed giv e n S 1 ª .

B y iter atin g t h i s l o g ic, o n e ob tain s t h e fo llo w in g i ter a tiv e elim in ation p ro ced u r e, ca ll ed iter ative e l i m i nation of strictl y -do m ina t e d str a te gies .

De fi n i ti on 32 (I te r a ti v e E lim ination o f S trictly - D o m i n a ted S tr ate g i e s) Set S 0 =

S , a n d f o r a n y m > 0 and s et

i

− i

S m = © s i ∈ S i | s i is n o t s tr ic tly d o m in a t e d giv e n S m − 1 ª ,

i

i.e . , s i ∈ S m i ff ther e d o e s n ot ex ist a n y σ i su ch tha t

− i

u i ( σ i , s − i ) > u i ( s i , s − i ) ∀ s − i ∈ S m − 1 .

Ca u t i o n : T w o p o in ts a r e c ru cia l :

1. W e elim in ate o nly t he strictl y do m i n a ted stra teg i e s. W e d o n o t e lim i n ate a str ateg y if it is w e ak ly do m i n a te d b ut n o t s trictly d o m in ate d . F or e x am ple, w e do no t

el i m i n ate a n y strategy i n

L R


1,1	0, 0
0,0	0, 0

T B

al t h ough ( T , L ) i s a dom i nan t s t rat e gy e q ui l i b ri um .

2. W e do elim in at e t h e s t rate gies tha t a r e s trictly d om ina t ed b y m i x e d s tra t eg ies (b u t n o t n ecessa rily b y p u r e s trategies). F o r exa m p l e, in the g am e i n ( 8.1 ) , w e d o el i m i n at e M al t h ough ne i t he r T nor B domi nat e s M .

N o tice th at w h en th er e a re o n ly fi n i tely m a n y strat egie s, th is e l im ina t ion p ro c ess m u st sto p a t so m e m , i.e., the r e w ill b e n o d o m i na ted stra teg y to elim in ate a fter a round.

i

N o te th at, f or an y m , a s t r a t e g y s i is in S m if a n d o n l y i f i t i s r at io na lly p l a y e d b y i in a s itu a tio n in w h ic h ( 1 ) i i s rat i onal , ( 2) i k n ow s t h a t e ve r y p l aye r i s r a t i o n a l , i kno w s t ha t e v e ryb o dy kno w s t ha t e v e ry b o dy i s ra ti ona l , a nd . . . ( m ) i kn o w th at ev ery b o dy kno w s t hat . . . e v e ryb o dy kno w s t hat e v e ryb o dy i s rat i o n a l . T ha t i s , s i is a b e s t

resp onse to a b el i e f μ 1 su c h th at ev ery s 1 in t h e s up p o rt o f μ 1

is a b est r esp on se to

− i j − i

so m e b e lief μ 2 su c h th a t ev ery e v e ry s 2 i n t h e s u p p o r t o f μ 2

i s a b est r esp o nse t o s om e

− j k − j

− k

be l i e f μ 3 ... u p t o o r d e r m . I t i s i n t ha t sen se S m is th e set of strategy p r o fi les t ha t

ar e c o n sisten t w ith m th -ord er m u tu al k n o w ledg e o f r a t ion a lit y .

Exe r c i s e 1 2 U s i n g T he or em 9, pr ove t he cl aim i n t he pr evi o u s p a r a gr aph.

R a tio n a l iz ab ilit y c o rre sp o n d s to t h e lim it o f th e i te rativ e e l im ina t ion o f s trictly - do m i nat e d s t r a t e g i e s.

i

De fi n i tio n 3 3 (R a t io n a liza b ilit y ) Fo r a n y p l a y e r i , a str a te gy is said to b e ration al - iza b le if a n d o n l y i f s i ∈ S ∞ whe r e

i

S ∞ =

m i

\ S .

m ≥ 0

R a tio n a l i z ab ili t y corresp on d s to th e s et of stra teg ies t h a t a r e ra tion ally p l a y ed in sit - ua t i ons i n w hi c h i t i s co m m o n kno w l e dg e t hat e v e ryb o dy i s ra t i onal , a s d e fi ne d a t t he b e - g i nni ng o f t h e l ec t u re . W he n a s t rat e gy s i is ra tion aliza b le it c a n b e j u s ti fi ed/ r a t ion a lized

by a n i n d e fi nite c h a i n o f b eliefs μ − i as ab o v e. O n th e o th er h a nd , i f a strategy i s n o t ra tion aliza b le, i t m u s t h a v e b e e n e lim in at ed at so m e stag e m , a n d suc h a s tra t eg y c an no t b e rat i onal i z e d b y a c hai n of b e l i ef s l onge r t han m .

W e ca ll th e e lim ina t ion p ro c ess tha t k e e p s i tera tiv e ly elim in atin g a ll s t rictly d o m - ina t ed str a teg i es u n til t h e re i s no strictl y do m i n a ted s tr ategy Ite r a t e d E l im in a t io n o f S t r i ctly D o m i n a te d S tr a t e g ie s ; w e e lim in ate i n d e fi nitely i f t he p r o c ess d o es n o t s to p. W e cal l a s trategy r a tio n a l iz a b le if an d o nly i f i t s ur v i v e s i tera ted e lim in ation o f s trictly do m i nat e d s t r a t e g i e s.

N a sh E q u i lib r i u m v . R a tio n a liza b ilit y E v ery N ash e q u ilib r iu m i s r at io n a lizab le, w h ic h c an b e sho w n a s a stra igh t forw ard e xercise. C o n v erse is no t t rue. F o r e xam p l e , i n The B at t l e o f T he Se xe s , ( O p e ra , B a l l e t ) i s no t a N a sh e q ui l i bri u m , but b o t h O p e r a a nd B a llet a re ra tion aliza b le strategies. O f co u r se, these s tra t eg ies c o rresp on d t o s om e N ash eq u ilib r ia , b u t on e c an e a sily c o n s tru c t a g a m e in w h ic h s om e r a t ion a liza b le stra teg i es do no t c o rres p o n d t o a n y N a s h e q ui l i bri u m.

Exe r c i s e 1 3 Show t h at i f σ ∗ ( s i ) > 0 fo r s o m e N a s h e qu ilib r i u m σ ∗ , t h e n s i ∈ S ∞ . F i n d

i i

i

a g a m e ( N, S , u 1 ,..., u n ) and a s t r a t e g y s i ∈ S ∞ such tha t no N a sh e q u i l i b r ium a ssign s

p o si ti ve pr ob abil i t y on s i .

Exam pl e: ( B eaut y C on t e st ) Cons i d e r an n - p l a ye r g a m e i n w h i ch e a ch p l aye r i has stra teg i es x i ∈ [0 , 100] , a n d p a y o ff

u i ( x 1 ,..., x n ) = − x i − 3 n

.

µ 2 x 1 + ··· x n ¶ 2

N o tice tha t , i n t h i s g a m e, eac h p l a y er tries t o p la y a strategy th at is equ a l t o t w o th irds o f th e a v e rage strateg y , w h i c h is also a ff ected b y his o w n stra t eg y . E a c h p e rson is th erefo r e in terested g uessing th e o th er pla y ers’ a v era g e s tra t eg i e s, w h i c h d ep end s o n th e o th er p l a y ers’ esti m a te of the a v e r a g e stra teg y . L e t’ s a p p ly o u r p ro cedu re to th is ga m e .

F i rst, sin c e e ac h s tr ateg y m u s t b e l ess t han o r e qual t o 100, the a v e rage cannot exceed 1 0 0 , an d h ence a n y s tr ateg y x i > 200 / 3 is stric t ly d o m i n a t e d b y 2 00 /3 . I nd ee d,

an y s trategy x i > x 1 is strictly d o m i na ted b y x 1 whe r e 2

x 1 = 2 ( n − 1) 100 .

3 n − 2

To s h o w t h a t x i > x 1 is strictly d o m ina t ed b y x 1 , w e fi x a n y ( x 1 ,..., x i − 1 , x i +1 ,... x n )

and s ho w t hat

u i ( x 1 ,..., x i − 1 , x i , x i +1 ,... x n ) < u i ¡ x 1 ,..., x i − 1 , x 1 , x i +1 ,... x n ¢ . (8 . 2 ) B y taki ng the d eri v ati v e o f u i w i th resp ect t o x i , w e o b t a i n

∂x i

3 n

i

∂u i = − 2 µ 1 − 2 ¶ µ x

— 2 x 1 + ··· x n ¶ .

3 n

Cl e a r l y , ∂u i /∂ x i < 0 if

µ x − 2 x 1 + ··· x n ¶ > 0 ,

w h i c h w o u l d b e t h e c a s e i f

i 3 n

i

3 n − 2

j

x > 2 X x . (8 . 3 )

j = / i

P

B u t s i n ce eac h x j ≤ 100 , t h e s u m j = / i x j is l e ss th an or equ a l t o ( n − 1) 100 . H ence, i t su ffi ces t h a t

x i >

2

3 n − 2

( n − 1) 100 = x 1 .

T h erefor e, in th e r eg i o n x i > x 1 , u i i s a s tri c tl y d ecreasi n g f uncti o n o f x i and ( 8. 2) i s sa tis fi ed. T hi s s ho w s t h at al l t he s t ra t e gi e s x i > x 1 are e lim ina t ed in t h e fi rst r ound.

O n the o ther h a n d , e a c h x i ≤ x 1 i s a b est r esp o nse t o s om e ( x 1 ,..., x i − 1 , x i +1 ,... x n )

wi t h

i

3 n − 2

j

x = 2 X x .

j = / i

T h eref or e, at th e e nd of th e fi rst r ound the s et of survi v i n g s trategi e s i s [0 , x 1 ] .

N o w , supp ose t hat a t t he end o f r ound m , t he set o f s u rv iv in g s trat egies i s [0 , x m ] fo r s o m e n u m b e r x m . B y r ep ea ting th e s a m e a n a lysis a b o v e w i th x m in s t e a d o f 1 0 0 , w e c a n c oncl ude t h at at t h e e nd o f ro und m + 1 , t he set of su rviving s tra t eg ies i s [0 , x m +1 ] whe r e

x m +1 = 2 ( n − 1) x m .

3 n − 2

2 He re x 1 is just a r eal n u m b e r, wh ere s up erscript 1 i ndicates t hat w e a re i n Rou n d 1 .

T h e s o l u t ion t o t his e q u a t ion w ith x 0 = 1 0 0 is

∙ ¸

2 ( n − 1) m

x m = 100 .

3 n − 2

T h erefor e, fo r e ac h m , a t t h e e n d o f r o u n d m , a s t r a t e g y x i sur v i v es if a n d o nly i f

0 ≤ x i ≤

100 .

∙ 2 ( n − 1) ¸ m

3 n − 2

Si nc e

∙ ¸

2 ( n − 1) m

lim 100 = 0 ,

m →∞ 3 n − 2

th e o nly r a t ion a liza b le st rate gy is x i = 0 .

N o tice tha t th e s p e ed at w h ic h x m

g o es to zero d eterm i n e s h o w fast w e el im i n a t e

th e s tra t eg ies. If the e li m i na tion is slo w (e.g. w h e n 2 ( n − 1) / (3 n − 2) is la r g e ) , t h e n m a n y strategies are e lim in ated at v e ry h i gh it eratio ns. I n t ha t c ase, p r ed iction s b a sed on ra tion aliza b ilit y w ill h e a v ily rely on s t ron g a ssum p t i o n s a b o u t ra tion alit y , i.e . , e v e ry b o d y k n o w s t h a t e v e r y b o d y k n o w s t h a t . . . e v e r y b o d y i s r a t i o n a l . F o r e x a m p l e , i f n is sm all o r th e r a t i o 2 / 3 is rep l a c e d b y a s m a ll n u m b e r , t h e elim in atio n i s f a s t a n d th e p red i ction s of ratio n a l iz ab ilit y a re m o re relia ble. If th e n is l a rge o r t he ratio 2 / 3 is rep l a c e d b y a n u m b er clo s e t o 1 , t he e l im ina t ion i s s lo w a n d the p re dictio ns o f ra tio n alizab ilit y a r e less relia ble. In p a r t ic ula r , t he p r ed iction s o f r a t ion a liza b ilit y f or th is g a m e is m o re ro bu st in a s m a ll gro u p t h a n a lar g er gro u p .

A g en era l p r ob lem w ith r a t io n a lizab ilit y i s t h a t t he re a r e u su ally to o m an y r a t io n a liz - ab le strategies; th e e li m i na tion p r o cess u su a l ly stop s t o o ear l y . In th a t ca se a r esearc h er ca nn o t m a k e m u c h pr ediction ba sed o n su c h an alysis. F or exam ple, in the M a t c h in g Pe n n i e s g a m e


-1,1	1, - 1
1,-1	-1 , 1

1 \ 2 H e a d T a i l He a d

Ta i l

ev ery s tr ate g y i s r a t ion a liza b le, a nd w e can n o t s a y w h a t the p la y e rs w ill do .

8 . 3 A p p lic a t io n s

8. 3. 1 C ournot C o m p et i t i o n

Con s i d e r n fi rm s. Eac h fi rm i pro d uc es q i ≥ 0 un its o f a go o d a t m a rgin al c o st c ≥ 0

an d sell i t a t p rice

P = m a x { 1 − Q, 0 } (8 . 4 )

whe r e

Q = q 1 + ··· q n (8 . 5 )

i s the t ot a l s u ppl y . Eac h fi rm m a xi m i zes t he exp e cted pro fi t. H e nce, the p a y o ff of fi rm

i is

π i = q i ( P − c ) . (8 . 6 )

A s s u mi ng a l l o f t he ab o v e i s c o m m o nl y k no wn, w e c a n wri t e t hi s a s a ga m e i n no rm a l fo r m , b y s e t tin g

• N = { 1 , 2 ,..., n } as th e set of p l a y ers

• S i = [ 0 , ∞ ) as th e stra t egy s p a ce of p l a y er i , w here a t ypical strategy is the q uan t i t y

q i pro d uce d b y fi rm i , a n d

• π i : S 1 ×· · · × S n → R as the p a y o ff fun c tio n .

X

B e st R e sp onse In o u r a n a lysis, a n d i n t h e rest of th e c ou rse, it w ill b e u sefu l to kn o w th e b est r esp on se of a fi rm i to the p ro d u c tion lev e ls of th e o th er fi rm s. Let u s w rite

Q − i = q j (8 . 7 )

j = / i

f o r t he t o t a l s uppl y o f t he fi rm s o th er th an fi rm i . I f Q − i > 1 , t hen t he price P = 0 and th e b est fi rm i can d o i s t o p ro duce zero and o btai n z ero p ro fi t. N o w a ssu m e Q − i ≤ 1 .

Fo r a n y q i ∈ (0 , 1 − Q − i ) , t he pro fi t o f t h e fi rm i is

π i ( q i , Q − i ) = q i (1 − q i − Q − i − c ) . (8 . 8 )

( T he pro fi t i s n e g a t i v e i f q i > 0 .) B y sett i n g th e d eriv ativ e o f π i w i th resp ect to q i to zero, 3 w e o b ta in th e b est p ro du cti o n l ev el

q B ( Q ) = 1 − Q − i − c . (8 . 9 )

i − i 2

The p r o fi t f u n ction is p l otted i n F i g u r e 8.1 . T h e b est r esp on se fu n ction is plotted i n Fi gure 8. 2.

Profi t

-cq i

q i (1 -Q

0

-i -c )

-0.2

0

(1-Q -c)/2 1-Q -c 1

-i -i

Figure 8.1:

Cour not D uop o l y

N o w , con s id er th e c a s e o f t w o fi rm s. In th a t case, f or i = / j , w e h a v e Q − i = q j .

N a sh E q u ilib r i u m In o r d e r t o h a v e a N a sh e q uilibriu m , w e m u s t h a v e

q = q B ( q ) ≡ 1 − q 2 − c

3 I.e.

1 1 2 2

∂π i =1 − 2 q − Q

— c = 0 .

∂q i

i − i

q i

1  c

2

q i =q i (Q -i )

B

Q -i

1-c

Figure 8.2:

an d

q = q B ( q ) ≡ 1 − q 1 − c .

2 2 1 2

S o lv ing t h ese t w o e q u at io ns sim u ltan eo usl y , w e o bta i n

q ∗ = q ∗ = 1 − c

1 2 3

as th e o n l y N a s h e q u ilibr i u m . G rap h i c a ll y , a s i n F igu r e 8 .3 , w e p lo t t he b est resp on se f u n ction s o f e ac h fi r m a n d i d e n t ify t he in terse c tion s o f t he graphs of these f unctions as N a sh equ i lib ria. In th is case, t h e re is a u n i que i n t ersection , a n d th er efo r e t h e re is a uni q ue N a s h e q ui l i bri u m.

R a tion a liza b ilit y T h e ( l i ne ar) C ournot duop ol y g ame w e c ons i de r h e r e i s " dom i nance so lv a b le" i.e. t he re is a u n i q u e r at io n a lizab le str a te g y . L et u s fi rst c onsider t he fi rst co up le rou n d s o f e lim in atio n t o see th is in tu it iv ely ; w e w ill th en s h o w m a the m a t ically th at t h is is ind e e d th e c ase.

Ro u n d 1 N o tice th at a stra t eg y q ˆ i > (1 − c ) / 2 is strictly d o m i na ted b y (1 − c ) / 2 . T o see th is, c on sider a n y q j . A s i n F i g u r e 8 . 1 , π i ( q i , q j ) is strictl y i n cr easin g un til q i = ( 1 − c − q j ) / 2 an d str i c tly d ecrea s ing t h e reaf ter. In particular,

π i ((1 − c − q j ) / 2 , q j ) ≥ π i ((1 − c ) / 2 , q j ) > π i ( q ˆ i , q j ) ,

sh o w ing t h a t q ˆ i i s strictly do m i n a ted b y (1 − c ) / 2 . W e t her e fo re elim in ate a ll q ˆ i >

(1 − c ) / 2 fo r e a c h p la y e r i . T h e re sultin g s t r ate g ies a re a s fo llo w s, w h e r e t h e sh ad ed

q 2

q 1 =q 1 (q 2 )

B

1  c

2

q 2 =q 2 (q 1 )

B

q 1

q*

1-c

Figure 8.3:

ar ea is e l im in a t ed :

1-c

1  c

2

1  c

2

1-c

Ro u n d 2 In t h e r emai ni ng gam e q j ≤ (1 − c ) / 2 . C o n sequ en tl y , a n y str ateg y q ˆ i < (1 − c ) / 4 is strictl y d o m i na ted b y (1 − c ) / 4 . T o see th is, t ak e a n y q j ≤ (1 − c ) / 2 an d r ecall f r o m F igur e 8 .1 th at π i i s strictly in creasin g u n til q i = ( 1 − c − q j ) / 2 , w h i c h i s g r e a t e r t h a n o r e q u a l t o (1 − c ) / 4 . H en ce,

π i ( q ˆ i , q j ) < π i ((1 − c ) / 4 , q j ) ≤ π i ((1 − c − q j ) / 2 , q j ) ,

sh o w ing t ha t q ˆ i is stric t ly do m i n a te d b y (1 − c ) / 4 . W e w ill t h e re fo re elim in ate a ll q ˆ i wi t h q ˆ i < (1 − c ) / 4 . T he rem a inin g s tr ate g ies a re a s follo w s :

1-c

1  c

2

1  c

2

1-c

N o tice th at th e r em ainin g gam e i s a sm all e r r eplica o f t h e origi n al gam e . A p p l yi n g th e s a me pro c edure r ep e a t e dl y w e e l i m i nat e a l l s t r at e g i e s e xc ept f o r t h e N a s h e qui l i bri u m. (A f t er ev ery t w o rounds, w e o btai n a sm al l e r r ep lic a .) T h erefore , the o nly r atio na liz a b l e stra teg y is the u n i qu e N ash e qu il ib rium stra teg y:

i

q ∗ = ( 1 − c ) / 3 .

A m ore f orm a l t reatm e n t W e ca n p ro v e th is m o r e form ally b y in v o k i n g th e f ollo w i n g lem m a r ep ea ted l y:

i

Lem m a 2 Gi v e n t h a t q j ≤ q ¯ , e very str a te gy q ˆ i wit h q ˆ i < q B ( q ¯ ) is str i c t ly d o m i n a te d b y

q B ( q ¯ ) ≡ (1 − q ¯ − c ) / 2 . G i v en that q j ≥ q ¯ , e v e r y s t r a t e g y q ˆ i wi th q ˆ i > q B ( q ¯ ) is str i ctly

i

dom i nate d b y q B ( q ¯ ) ≡ (1 − q ¯ − c ) / 2 .

Pr o o f . Le t’ s fi rst p ro v e the fi rst s ta tem en t. T a k e an y q j

i

≤ q ¯ . N o t e t h a t π i ( q i ; q j ) is

strictl y increa sing in q i at an y q i < q B ( q j ) . S i n c e q ˆ i < q B ( q ¯ ) ≤ q B ( q j ) , 4 th is im p lies

th at

i i i

i

π i ( q ˆ i , q j ) < π i ¡ q B ( q ¯ ) , q j ¢ .

i

Tha t i s , q ˆ i is stric t ly do m i n a ted b y q B ( q ¯ ) .

T o pro v e t he secon d statem e n t , t ak e a n y q j

≤ q ¯ . N o t e t h a t π i ( q i ; q j ) is strictly

d ecreasin g in q i at an y q i > q B ( q j ) . S i n c e q B ( q j ) ≤ q B ( q ¯ ) < q ˆ i , t h i s i m p l i e s t h a t

i i i

i

π i ( q ˆ i , q j ) < π i ¡ q B ( q ¯ ) , q j ¢ .

i

4 This is b e cause q B is decreas i ng.

i

Tha t i s , q ˆ i is stric t ly do m i n a ted b y q B ( q ¯ ) .

No w, d e fi ne a s e q ue nc e q 0 , q 1 , q 2 ,... by q 0 = 0 and

i

q m = q B ¡ q m − 1 ¢ ≡ ¡ 1 − q m − 1 − c ¢ / 2 = ( 1 − c ) / 2 − q m − 1 / 2

fo r a ll m > 0 . T h a t i s ,


q 0	= 0
q 1	=	1 − c 2
q 2	=	1 − c 2	— 1 − c 4
q 3	=	1 − c 2	— 1 − c 4	1 − c + 8
		...

q m =

1 − c − 1 − c + 1 − c − ··· − ( − 1) m 1 − c

2 4 8 2 m

...

The o rem 1 0 T h e s e t o f r e m a in in g s tr a t e g ies a fter a n y o d d r o u n d m ( m = 1 , 3 ,.. . ) i s [ q m − 1 , q m ] . T he s e t o f r em ai ni ng s t r a t e gi es aft e r a ny even r o und m ( m = 2 , 4 ,.. . ) i s [ q m , q m − 1 ] .The set o f r ati o n a l i zabl e s t r ate g i e s i s { (1 − c ) / 3 } .

i

i i

£ ¤

Pr o o f . W e us e m a t he m a t i ca l i nduc ti on o n m . F o r m = 1 , w e h a v e a l r e a d y p r o v e n t h e sta t em en t. A ssu m e tha t the s ta tem e n t is true for s o m e o d d m . T h e n , f o r a n y q j a v ailab l e at ev en rou n d m + 1 , w e h a v e q m − 1 ≤ q j ≤ q m . H en ce, b y L e m m a 2 , a n y q ˆ i < q B ( q m ) = q m +1 is strictly d o m ina t ed b y q m +1 a n d e li m i na ted . T h a t i s, if q i surviv es round m + 1 , th en q m +1 ≤ q i ≤ q m . O n t he o t her h and, e v e r y q i ∈ [ q m +1 , q m ] = q B ( q m ) , q B ( q m − 1 ) is a b est r esp on se to so m e q j wi t h q m − 1 ≤ q j ≤ q m , a n d it is n o t e lim in ate d . T h e r e fo re, th e set of strategies tha t sur v i v e t h e ev en ro un d m +1 is [ q m +1 , q m ] .

i

N o w , assu m e th at the s ta tem e n t is true fo r s o m e e v e n m . T he n, f o r a n y q j a v ailab l e at o d d r oun d m + 1 , w e h a v e q m ≤ q j ≤ q m − 1 . H ence, b y L em m a 2, an y q ˆ i > q B ( q m ) = q m +1 is strictly d o m i n a ted b y q m +1 a n d e lim in ate d . M ore o v e r, ev ery q i ∈ [ q m , q m +1 ] =

i

£ q B ( q m − 1 ) , q B ( q m ) ¤ is a b est resp on se to so m e q j wi t h q m ≤ q j ≤ q m − 1 , a n d i t i s n o t

elim in ated. T herefo re, t h e set o f strategies th at su rviv e t h e o d d r o u n d m +1 is [ q m , q m +1 ] .

F i n a ll y , n o t ice t ha t

lim q m = ( 1 − c ) / 3 .

m →∞

Theref ore t he i n tersecti ons o f t he ab o v e i n t erv a l s i s { (1 − c ) / 3 } , w hic h is th e set o f ra tion aliza b le st rate gies.

C o urnot O l i gop ol y

W e w ill n o w c on sider t he ca se of three o r m o r e fi rm s. W h en th er e a re th ree o r m o r e fi rm s, ra tion aliza b ilit y d o e s n ot he lp , i .e ., w e ca n n o t elim in ate a n y stra teg y l ess th an th e mono p o l y pro duc t i o n q 1 = ( 1 − c ) / 2 .

In th e fi r s t r ou nd w e elim in ate a n y strategy q i > (1 − c ) / 2 , u s i ng t h e s a m e a rg um e n t i n t h e c as e o f d uop o l y . B ut i n t h e s e c o n d r ound, t h e m axi m um p o s s i bl e t o t al s uppl y b y th e o ther fi rms i s

( n − 1) (1 − c ) / 2 ≥ 1 − c,

whe r e n is t h e n u m b e r o f fi rm s. T h e b est r esp onse to th is aggregate s up p l y l ev el is 0. H e n ce, w e can n o t e lim in ate a n y stra teg y in rou n d 2. T h e e lim in ati o n p r o cess stop s, yi e l di ng [0 , (1 − c ) / 2] a s the set o f ra tion aliza b le strategies.

O f c o u r se, C o u r n o t o ligo p o l y h as a u n i q u e N ash e q u ilibr i u m as in th e C ou rno t d u o p ol y . W h il e t he N a sh equ i l i b r ium r em a i ns to m a k e stron g p red i ction s as w e in tr o - duce ne w fi rm s, th e p red i c t ion s of rat i o n a lizab ilit y b e com e ra th er w e ak . ( In eq u i lib r iu m an a l y s is th e w eak p red i ctio ns o f ratio n a lizab ilit y rea p p e ar s a s i nsta b i lit y o f e q u ilibriu m , m a king equ ili b r iu m b eha v ior h igh l y sen sitiv e to th e s p eci fi c a ti on of b e l i ef s . )

8. 3.2 B er tran d C om p e ti ti on

Con s i d e r t w o fi rms . Si m u l t aneo us l y , e ac h fi rm i sets a p rice p i . T h e fi rm i w i th the l o w er pri c e p i < p j sel l s 1 − p i un its a n d th e o th er fi rm ca n n o t sell a n y . I f t h e fi r m s set th e sa m e p r ice, th e d em an d i s d ivided b e t w een th em equ a lly . T h a t i s, th e a m o un t o f s a l es fo r fi rm i is

⎪ ⎨

⎧ 1 − p i if p i < p j

2

Q i ( p 1 , p 2 ) = 1 − p i if p i = p j

⎪ ⎩ 0 oth e rw i s e.

⎧ ⎪ ⎨ (1 − p i ) p i if p i < p j

W e assu m e th at i t co sts n o t ing t o p ro du ce th e g o o d (i.e. c = 0 ). T h erefore, the p ro fi t of a fi rm i is

π i ( p 1 , p 2 ) = p i Q i ( p 1 , p 2 ) =

⎪ ⎩

(1 − p i ) p i if p i = p j

2

0 oth e rw ise.

A s s u mi ng al l o f t he ab o v e i s c omm o nl y k no wn, w e c an wri t e t hi s f ormal l y as a g am e in n o rm a l form b y setti n g

• N = { 1 , 2 } as the set o f p l a y ers

• S i = [ 0 , ∞ ) a s the set o f stra teg i es fo r e a c h i , w i t h p r i c e p i a t y p i c a l s t r a t e g y ,

• π i a s the u tilit y f u n ct io n .

O b s e r v e t h a t w h e n p j = 0 , π i ( p 1 , p 2 ) = 0 for e v e ry p i , a nd he nc e e v e ry p i is a b e s t resp on se to p j = 0 . T h i s h a s t w o i m p ort a n t im plica t ion s :

1. E v ery s tra t eg y i s r atio na li zab l e ( w e ca nn ot elim i n ate a n y strategy b e cau s e e ac h o f th em is a b est r ep ly to zero ).

2. p ∗ = p ∗ = 0 is a N a s h e q u ilib rium .

1 2

In th e r est of the n otes, w e w ill fi rs t s ho w t ha t t hi s i s i ndee d t he o n l y N a s h e q ui l i b - riu m . I n o th er w o rd s, ev en w i th t w o fi rm s, w h en th e fi rm s c o m p e te b y settin g p r ices, th e c o m p e tit i v e eq u ilib r iu m w ill e m e rg e. W e w ill th en sho w th at if w e m o d i fy the g am e sligh t ly b y discr etizin g t he se t o f a llo w ab le p r ice s a n d p u t tin g a m in im um p r ice, the n th e ga m e b e c o m e s d om ina n c e -so l v a ble, i.e., o n ly o n e stra t eg y r e m ain s ra tion aliza b le . I n t h e mo d i fi ed g a m e , t he m i nim u m p rice is the o nly r atio na lizab le strat e g y , a s i n c om p e titiv e eq u ilib r iu m . F i na lly w e w ill in tro d uc e s m a ll se arc h cost s o n t he p a rt of con s u m er s, w h o ar e n ot m o de le d a s p la y e rs, w e w ill s e e t h e e q uilibriu m b e h a v i o r is dr am a t ica l ly d i ff er en t fr om t h e e q u ilib rium b e h a v i or in the o rig i n a l g am e a nd co m p e t it iv e e q u ilibriu m .

N a sh E q u ilib r i u m

The o rem 1 1 T h e o n l y N a s h e q u i l i b r i u m i s p ∗ = ( 0 , 0) .

Pr o o f . W e h a v e seen th at p ∗ = ( 0 , 0) is a N ash e q u ilib r iu m . W e w ill s h o w th a t if ( p 1 , p 2 ) is a N a s h e q u ilib riu m , t h e n p 1 = p 2 = 0 . T o d o t his, ta k e a n y N a s h e q u ilib r iu m ( p 1 , p 2 ) . W e fi rst s ho w t hat p 1 = p 2 . T o w ard s a c on trad iction , s u p p ose t h a t p i > p j . I f p j = 0 , t h e n π j ( p i , p j ) = 0 , w h i l e π j ( p i , p i ) = ( 1 − p i ) p i / 2 > 0 . T h a t i s, c h o o sin g p i is a p r o fi ta ble d eviati o n for fi rm j , s h o w i n g t h a t p i > p j = 0 is n o t a N a sh eq u ilibriu m . T h erefor e, in or der p i > p j t o b e an e q ui l i bri u m , w e m u s t ha v e p j > 0 . B u t t h e n , fi rm i ha s a pro fi tabl e d evi a ti on: π i ( p i , p j ) = 0 whi l e π i ( p j , p ij ) = ( 1 − p j ) p j / 2 > 0 . A ll in a l l, t h i s s h o w s t h a t w e c a n n o t h a v e p i > p j in e q uilibriu m . T h e refore , w e m ust h a v e p 1 = p 2 . But i f p 1 = p 2 in a N ash e q u ilibr i u m , t he n i t m u s t b e t h a t p 1 = p 2 = 0 . T h i s i s b ecau se if p 1 = p 2 > 0 , t h e n fi rm 1 w ould ha v e a p ro fi tab l e d eviatio n : π 1 ( p 1 , p 2 ) = ( 1 − p 1 ) p 1 / 2

whi l e π 1 ( p 1 − ε, p 2 ) = ( 1 − p 1 + ε ) ( p 1 − ε ) , w h i c h i s c l o s e t o (1 − p 1 ) p 1 wh e n ε is clo s e

to zero .

R a tion a liza b ilit y w ith d isc r e t e p r i c e s

N o w s up p o se tha t th e fi rm s h a v e t o s e t pri c e s as m u l t i p l e s o f p e nni es , a nd they ca nnot c h a r ge zer o p rice. T h a t is, t he set o f a llo w a ble p rices i s

P = { 0 . 01 , 0 . 02 , 0 . 03 ,.. . } .

T h e i m p o r ta n t assu m p tio n h e re is th at t h e m inim u m a l lo w a b l e p r i c e p min = 0 . 01 yi el ds a p o s itiv e p ro fi t. W e w ill n o w see th at th e g am e i s " do m i n a n ce-solv ab le" u nd er th is ass u m p t i on. I n p art i c u l a r p mi n is th e o n l y r atio na liz a b l e s tr ateg y , an d i t i s t h e o n ly N a sh equ ili b r iu m s tra t eg y . L e t u s s tart w i th th e fi rst s tep.

St e p 1: an y p ri c e p gr e a ter t han t he m o nop o l y pri c e p mon = 0 . 5 i s strict l y dom i n at e d by som e str a t e gy that assi gns s om e p r o b a bil i t y x > 0 to th e p r i c e p min = 0 . 01 an d pr ob abi l i t y 1 − x to th e p r i c e p mon = 0 . 5 .

¡ ¢

Pr o o f . T a ke a n y p l a ye r i and a n y pri c e p i > p mon . W e w a n t t o s ho w t ha t t he mi xe d

stra teg y σ s wi t h σ s ( p mon ) = 1 − x an d σ s p min = x strictly do m i n a tes p i fo r s o m e x > 0 .

T a k e an y s trategy p j > p mon of the o ther pl a y er j . W e h a v e

π i ( p i , p j ) ≤ p i Q ( p i ) = p i (1 − p i ) ≤ 0 . 51 · 0 . 49 = 0 . 2499 ,

whe r e t h e fi r s t i n e q u a l i t y i s b y d e fi n i tion a n d t h e la st ine q ua lit y is d u e to th e f act t ha t

¡ ¢

p i ≥ 0 . 51 . O n t he ot he r h a n d,

π i ( σ s , p j ) = ( 1 − x ) p mon (1 − p mon )+ xp mi n 1 − p mi n

> (1 − x ) p mon (1 − p mon )

= 0 . 25 (1 − x ) .

Th us , π i ( σ s , p j ) > 0 . 2499 ≥ π i ( p i , p j ) w h en ev er 0 < x ≤ 0 . 0004 . C h o o s e x = 0 . 0004 .

¡ ¢ ¡ ¢

No w, p i c k a n y p j ≤ p mon . S i n c e p i > p mo n , w e n o w h a v e π i ( p i , p j ) = 0 . B u t

π i ( σ s , p j ) = ( 1 − x ) p mon (1 − p mon )+ xp min 1 − p min ≥ xp mi n 1 − p mi n > 0 .

Tha t i s , π i ( σ s , p j ) > π i ( p i , p j ) . T heref o re, σ s strictly do m i n a tes p i .

S t ep 1 y ie lds t h e e l im in a t ion s in th e fi rst r ound 1.

Ro u n d 1 By St e p 1, al l s trat egi e s p i wi t h p i > p mon = 0 . 5 ar e e lim in at ed. M o r eo v e r, ea c h p i ≤ p mon is a b est rep l y t o p j = p i + 1 , a n d i s no t e li m i na ted . T h erefo r e, th e s et of rem a in ing s trat egies i s

P 2 = { 0 . 01 , 0 . 02 ,..., 0 . 5 } .

Ro u n d m Supp o s e t ha t t he s e t o f r e m a i ni ng s t ra t e g i e s t o round m is

P m = { 0 . 01 , 0 . 02 ,..., p ¯ } .

¡ ¢

T h en , t h e stra t eg y p ¯ is strictly d o m i na ted b y a m i xed s trictly d om i n a t ed b y the m ixed stra teg y σ s wi t h σ s ( p ¯ − 0 . 01) = 1 − x an d σ s p min = x , a s w e w ill see m o m e n t aril y . W e th en eli m ina t e t h e stra teg y p ¯ . T he re w ill b e no m o r e elim in ation b ec au se ea c h p i < p ¯ is a b est reply t o p j = p i + 0 . 01 .

T o pro v e t ha t p ¯ is strictly d o m in ate d b y σ s , n o t e t hat t he pro fi t f r o m p ¯ fo r p la y e r i

(

is

j

i

π ( p ¯ , p ) = p ¯ (1 − p ¯ ) / 2 if p j = p ¯ ,

0 o t h e rw ise.

O n the o ther hand,

p ¯

π i ¡ σ s , p ¯ ¢ = ( 1 − x ) ( p ¯ − 0 . 01) ( 1 − p ¯ + 0 . 01) + xp min ¡ 1 − p min ¢

> (1 − x ) ( p ¯ − 0 . 01) ( 1 − p ¯ + 0 . 01)

= ( 1 − x ) [ p ¯ (1 − p ¯ ) − 0 . 01 (1 − 2 p ¯ )] .

The n , π i ( σ s , p ¯ ) > π i ( p ¯ , p j ) w h en ev er

x ≤ 1 −

p ¯ (1 − p ¯ ) / 2

.

p ¯ (1 − p ¯ ) − 0 . 01 (1 − 2 p ¯ )

But p ¯ ≥ 0 . 02 , h ence 0 . 01 (1 − 2 p ¯ ) < p ¯ (1 − p ¯ ) / 2 , t h u s t h e righ t h an d s id e i s g reater th an

0. C h o o se

x = 1 − p ¯ (1 − p ¯ ) / 2 > 0

p ¯ (1 − p ¯ ) − 0 . 01 (1 − 2 p ¯ )

p ¯

so tha t π i ¡ σ s , p ¯ ¢ > π i ( p ¯ , p j ) . M o r e o v e r , f o r a n y p j < p ¯ ,

p ¯

π i ¡ σ s , p j ¢ = ( 1 − x ) ( p ¯ − 0 . 01) ( 1 − p ¯ + 0 . 01) + xp min ¡ 1 − p min ¢

≥ xp min ¡ 1 − p min ¢ > 0 = π i ( p ¯ , p j ) ,

p ¯

sh o w ing t ha t σ s

strictly d om i n a tes p ¯ , a n d com p l e ting th e p r o of.

© ª

T h er efo r e, th e p ro cess co n t in ues u n t i l th e s et of rem a inin g s trategies i s p min and i t s t ops t he re . T he ref o re , p min is th e o nly r a t ion a liza b le st rate g y .

¡ ¢

S i nc e p la y e rs c a n p ut p o sitiv e pro b ab ilit y o nly o n r a t ion a liza b le stra teg ie s i n a N a sh eq u ilib r iu m , th e o nly p ossib l e N a s h e q u ilib rium is p mi n , p min , w h i c h is clea rly a N a sh eq u ilib r iu m .

M IT OpenCourseWare http://ocw.mit.edu

1 4.123 Microeconomic Theory III

Spring 2010

For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms .