Cha p t e r 7

P r e lim in a r y N o t io n s in G a m e The o ry

I a ssu m e th at y o u r eca ll th e b a s ic solu tion c o n c e p ts, n a m e ly N a sh E q uilibr i u m , B a y esian N a sh E q u ili b r iu m , Su b g a m e-P e rfect E q u i lib rium , a nd P e rfect B a y esian N a sh E q u ili b - riu m , f ro m 1 4.12 2 v ery w ell . In th e n ext t w o lectu r es, I w ill sum m a r ize s o m e o th er im p o rta n t s o l u t ion c o n c e p t s i n G a m e T he or y , n a m e ly R a tion a l iz ab ilit y , C o rr elate d E q ui - l i b ri um, a nd Se que n ti al Equi l i bri u m , and i l l us t r at e t he m i n s o m e a ppl i c at i o ns . T he no te s in this c h ap ter d escrib e t h e p r elim i n ar y n otion s tha t y o u m ust k n o w a lread y an d t h e n o ta tion th at w ill b e u sed in th e c ou rse.

T h e g am es ca n b e r epresen ted i n t w o form s:

1. T h e n or m a l ( strategic) form ,

2. T h e e xten siv e form .

I fi rst d escr i b e t h ese r e p r esen t a tio n s illust rate ho w o n e ca n g o f rom o n e re pr esen ta tion to the o th er.

7. 1 N orm a l f or m

De fi ni ti on 15 (N orm a l f orm ) A n n - player gam e is an y l i s t G = ( S 1 ,..., S n ; u 1 ,..., u n ) , w h er e, for e a c h i ∈ N = { 1 ,..., n } , S i i s t h e s et of al l s t r at e g i e s t hat a r e av ai l a bl e t o

61

62 CHAPTER 7 . P RELI MI NAR Y NOTI ONS I N G AM E THEO R Y

player i , a n d u i : S 1 × ... × S n → R is pl a yer i ’s vo n N eum a n n -M or gen stern u til i ty fu n c tio n .

N o tice tha t a p la y e r ’ s u til i t y d e p e nd s n o t o n ly on h i s o w n stra teg y b u t a l so o n th e stra teg i es p l a y ed b y other p la y e rs. M o r eo v e r, eac h p l a y er i tries to m a x im ize the ex p e cted va l u e o f u i (w here th e e xp ected v a l u e s are co m p uted w i th resp ect t o h is o w n b eliefs); i n other w ord s , u i is a v o n N e um an n - M o rg en stern u tili t y fun ctio n . W e w i l l s a y th at pla y er i is ration al i ff h e t r i e s t o m a x i m i z e t h e e x p e c t e d v a l u e o f u i (giv en his b eli e fs).

It i s al s o as s u me d t hat i t i s c omm o n k no wl e d ge that t h e p l a y e rs are N = { 1 ,..., n } ,

th at th e set of strategies a v ai lable t o e ac h p la y e r i is S i , a n d t h a t e a c h i tries t o m ax im iz e exp ected v a l u e o f u i giv e n h is b e l i ef s.

W h en there a re only t w o p l a y e rs, w e c an represen t the ( norm al f o rm ) g am e b y a b i m a t r ix ( i .e ., b y t w o m a t r i c e s ) :

1 \ 2 up

do wn

l e f t r i g h t

H e r e , P la y e r 1 h a s s trategies u p a nd do w n , a n d P l a y er 2 h as th e s tra teg ies l eft a nd righ t. In eac h b o x t he fi r s t n u m b e r i s P l a y e r 1 ’ s p a y o ff a n d the seco nd o n e i s P la y er 2 ’s (e.g ., u 1 ( up, l e f t ) = 0 , u 2 ( u p ,left ) = 2 .)

I w il l u se the f ollo w i ng no tati o n a l con v en tio n th rou g h o u t th e c o u rse. G i v e n a n y list

X 1 ,..., X n o f sets w i th g e n eric e lem e n ts x 1 ,..., x n , I w ill

• wri t e X = X 1 ×· · · × X n and d e s i gnat e x = ( x 1 ,..., x n ) as th e g en eric elem en t,

• wri t e X − i = Q j = / i X j and d e s i gnat e x − i = ( x 1 ,..., x i − 1 , x i +1 ,..., x n ) as the g eneri c el em en t f or an y i , a n d

• wri t e ( x j , x − i ) = ( x 1 ,..., x i − 1 , x j , x i +1 ,..., x n ) .

i i

Fo r e x a m p l e ,

• S = S 1 ×· · · × S n is th e set o f str a teg y p ro fi les s = ( s 1 ,..., s n ) ,

• S − i is th e set o f strategy p r o fi les s − i = ( s 1 ,..., s i − 1 , s i +1 ,..., s n ) other t h a n p la y e r

i , a n d

7.2. E X T E N S IV E F O R M 63

• ( s j , s − i ) = ( s 1 ,..., s i − 1 , s j , s i +1 ,..., s n ) i s th e s tr ateg y p ro fi le in w h ic h i pl a y s s j

i i i

and t he ot hers pl a y s − i .

7. 2 E xt ens i v e f o rm

T h e e x t en siv e fo rm con t ains all t h e in form ation a b o ut a g am e e x p licitl y , b y d e fi ni ng w h o m o v es w h en , w h a t e a c h p la y e r k n o w s w h en he m o v e s, w h at m o v e s a re a v a i l a b l e t o h i m , an d w h e re eac h m o v e lea d s t o, etc. In con t r a st, t h ese are i m p li citly i n c o r p o rated i n stra teg i es in th e n orm a l f o r m . (In a w a y , the n o r m a l f orm i s a ‘ s um m a ry’ r epr esen tation .) We fi rst i n t ro duce s om e f orm a lism s .

De fi ni ti on 16 A tr ee is a d ir e c te d g r a p h (i.e . a s e t o f n o d e s w i th d i r e c t e d e d ge s t h a t c o nn e c t s om e o f t he no des) such that

1 . ther e i s a n i nitial n o d e, fo r w h i ch th er e i s n o i nc o m ing e dge;

2 . fo r e v e r y o t h e r n o d e , th er e i s o n e in c o m i n g e d ge ;

3. every n o d e i s c on ne ct e d t o t h e i n i t i al no de by a u n i qu e p ath.

De fi ni ti on 17 T h e n o d es that ar e n ot f o l l ow e d by an other n o d e a r e c a l l e d ter m ina l . Th e o t h e r no d e s a r e c a l l e d non-term inal .

De fi ni ti on 18 ( Ext e ns i v e f o r m ) A Ga me c o nsist s of a s et of pl ayers, a t r e e, an al l o c a t i o n o f n on -t erm i nal n o d es of t h e t r e e t o t he pl ayers, an i n f o rm ati o n a l p artit i o n o f th e n on -term i n a l n o d es, a n d p a yo ff s f or e a ch pl aye r at e a c h t e r m i n al no de .

T h e s et of pla y ers i ncl udes t he agen ts taking part in the g am e. H o w e v e r, i n m a n y g a mes t he re i s ro o m f o r c hance , e . g. t h e t hro w o f di ce i n bac k g a m mon o r t he ca rd dra w s in p o k e r. M o re bro a d l y , w e need to co nsid er “ c h a n c e” w h en ev er th ere i s u n c erta i n t y ab ou t s om e r elev an t f act. T o rep r esen t these p ossi b ili ti es w e in tro d uce a fi ction a l p l a y e r: N a ture. T here is no pa y o ff f o r N a t ure a t e nd no des , and e v e ry t i m e a n o d e i s a l l o c a t e d to N a tu re, a p r ob ab ilit y d istribu t ion o v e r t h e b r an c h e s th at follo w n e e d s to b e sp ec i fi ed, e.g . , T ail w ith p ro ba bilit y o f 1 /2 an d H e a d w ith p ro ba bilit y o f 1 /2 .

An in fo r m a tio n s et i s a c o l lection of p o in ts (no d es) { n 1 ,..., n k } su c h th at

1. th e s am e p la y e r i i s to m o v e at eac h of these n o des;

2. th e s am e m o v es are a v a ilab l e a t e ac h o f t hese no des.

He r e t h e p l a y e r i , w ho is to m o v e a t th e i nform a tio n set, is a ssum e d t o b e u n a b l e t o d i sti n g u ish b et w een th e p o i n t s i n the in fo rm a tion set, b u t a b le to distin gu ish b et w een th e p o i n t s o u t side the i n f o r m a tion set from tho s e i n i t. F or i n s ta nce, co n s i d er the g am e i n Fi gure 7. 1. Here , P l a y e r 2 kno w s t hat P l a y e r 1 has t ak en ac t i on T o r B and n ot ac t i on X ; b u t P la y e r 2 can n o t k no w f o r sure w h eth e r 1 h a s t ak en T o r B . T he sa m e ga m e is d e p i c ted in F i gu re 7 . 2 s ligh tly d i ff eren tly .

1 x

L R

Figure 7.1:

1 x

Figure 7.2:

An in fo r m a t io n p a r titio n is a n a llo cat i o n of ea c h n o n - term ina l no de of the t re e t o a n inform ati o n s et; t h e sta r ting no d e m u st b e "a l o ne".

To s u m u p : a t a n y n o d e , w e k n ow : w h i ch p l aye r i s t o m o ve , w h i c h m o ve s a r e av a i l a b l e to the p la y e r, a n d w h i c h inform atio n s e t con t ain s the n o d e, sum m a r izing t h e pla y er’s inform ati o n a t t h e no d e . O f c ou rse, if t w o n o d es are i n t h e sam e i n form atio n set, t h e a v a i l abl e mo v e s i n t he s e no de s m us t b e t he s a me, f or ot herwi s e t he pl a y er c o ul d d i s t in g u ish t h e n o de s b y t h e a v aila ble c h o ice s . A ga in, a ll t h e s e a re a ssum e d t o b e co m m on k n o w led g e . F o r i n s ta nc e, in th e g a m e i n F igu r e 7 .1 , p la y e r 1 k n o w s t h a t , if pl a y e r 1 t a k e s X , pl a y e r 2 w i l l kno w t h i s , b ut i f he ta k e s T or B, pl a y er 2 w i l l no t k no w w h ic h o f t h ese t w o a ctio ns h a s b een ta k e n. (S he w i l l kn o w th at eith er T o r B w ill ha v e be e n t a k e n . )

7. 3 S t r ategi e s

De fi ni ti on 19 A s tr ateg y of a p l a yer i s a c o m pl e t e c o n t i nge n t - pl a n determ inin g w hich act i o n h e w i l l t ake a t e ach i n f orm a ti on set h e i s t o m ove ( including t he inf o rm ati o n s ets t h at wi l l n o t b e r e a che d ac c o r d ing t o t hi s s tr at e g y).

F o r c erta in pu rp o ses it m i g h t s u ffi ce to lo ok at th e r edu c ed-form s tr ateg ies. A r ed u ced f o rm strategy i s de fi n e d a s a n i ncom plete c o n tin g en t p la n t ha t d eter m i nes w h i c h a ction th e a g e n t w i ll tak e at eac h in fo rm a t ion s e t h e is to m o v e an d t h a t h as no t b een pre c lud e d b y th is p l an . B u t for m a n y o ther p u rp oses w e need to l o ok a t a l l t he stra tegies. L et u s n o w c on sid e r s o m e e xam p les:

G a m e 1: M a tc hi ng P e nni e s w i t h P erf e ct Inf o rm ati o n

(-1 , 1 )

1

, -1 )

(- 1, 1)

T h e t ree c o n sists o f 7 n o des. T h e fi rst o n e is a llo cat e d t o p la y e r 1 , a n d th e n ex t t w o to p l a y e r 2 . T he f o ur end- no des h a v e p a y o ff s a ttac h ed to th em . S ince there a re two p l a ye r s , p ayo ff v ecto r s h a v e t w o elem en ts. T h e fi rs t n um b er i s t he pa y o ff of pla y er 1 a n d t h e s e c o n d i s t h e p a y o ff of p l a y er 2. T h ese p a y o ff s a r e von N eum a nn -M o r gen stern u t ilities . T h at i s, eac h pla y er tries t o m axim i z e t h e exp ected v alue of h i s o w n p a y o ff s giv e n h is b e lie f s a b o u t h o w t he oth e r p la y e rs w ill p l a y the g a m e..

T h e i n f orm a tional partition i s v ery s i m p l e; all n o des ar e i n t h e ir o w n i nform a ti on set. In other w ord s , a ll inform ati o n sets a re sing leto ns (h a v e o n l y o n e elem en t). T h i s im p lies th at th ere i s n o u ncerta in t y reg a rd in g t he p r evio us p l a y (h i s tory) i n t h e ga m e . R ecall t h at i n a t re e, e a c h no de i s re ac he d t hrough a u ni que p at h. The r ef ore , i f al l i nf ormat i on sets a r e sin g leto n s , a p l a y er can c on stru ct the hi st ory p e rfectl y . F or i nstan c e i n t h i s ga m e , p l a y e r 2 kn o w s w h e th er p l a y er 1 c ho se H e ad o r T a il. A n d p la y e r 1 kn o w s t ha t w h e n h e p l ay s H e a d o r T a i l , P l aye r 2 w i l l k n ow w h a t p l aye r 1 h a s p l aye d . ( G a m e s i n w h ic h a ll infor m at io n s ets a r e s ing l eto n s a re c a lled gam es o f p erfe ct in form ation .)

In th is g a m e, t he set of str a tegies fo r p la y er 1 is { H ead , T a il}. A stra teg y o f pla y er 2 d e t e r mi ne s w hat t o d o d e p endi ng o n wha t pl a y er 1 d o e s . So , h i s s t rat e gi es a r e:

H H = H ea d i f P la y er 1 pla y s H ea d, a n d H ea d i f P l a y er 1 pla y s T ail; H T = H ea d i f P l a y e r 1 pl a y s H ea d, a n d T a i l i f P l a y e r 1 pl a y s T ai l ; TH = T a i l i f P l a y e r 1 pl a y s H e a d, a nd H ea d i f P l a y e r 1 pl a y s T ai l ; T T = T a i l i f P la y e r 1 pla y s H ea d, a n d T a i l i f P la y e r 1 p l a y s T ail.

W h at are t he p a y o ff s g en era ted b y eac h stra teg y p a i r ? If p l a y er 1 p la ys H e ad a n d P l a y e r 2 p la y s H H , the n th e o u t co m e is [P la y e r 1 c h o o ses H e a d a n d P la y e r 2 c h o o ses H e ad] and t h us t h e p a y o ff s a re ( - 1, 1 ) . I f p l a y e r 1 pl a y s H e a d a nd 2 p l a ys H T , t he ou tcom e i s t h e sa m e , h en ce the p a y o ff s are (-1,1). If P la y e r 1 pla y s T ail a nd P l a y er 2 p l a y s H T , t h e n th e o u t co m e is [P la y e r 1 c h o o ses T a il a n d P la y e r 2 c h o o se s T ail] a n d th u s the p a y o ff s a re on ce a g a i n ( -1 , 1 ). H o w e v e r , if P l a y er 1 p la ys T a i l an d P la y er 2 pla y s H H , th en th e o u t co m e is [P la y e r 1 c h o o ses T a il an d P la y e r 2 c h o o ses H e a d ] a n d th us th e pa y o ff s are (1,-1 ) . O n e ca n c om pu te the p a y o ff s for th e o th er stra teg y pa irs s im ilarl y .

T h er efo r e, th e n orm a l o r the stra tegic for m g a m e co rresp o n din g to this g a m e is

HH HT TH TT

He a d Ta i l

In fo rm a t ion sets a re v e ry im p o rta n t. T o see this, c o n si d e r t he follo w i n g ga m e .

G a m e 2: M a tc hi ng P e nni e s w i t h I m p erf e ct I n form ati o n

(-1 , 1 )

- 1 )

1

(1 , - 1 )

(-1 , 1 )

G a m e s 1 a n d 2 a p p e ar v e ry si m i l a r b u t in fact th ey co rresp o n d t o t w o v e ry d i ff er en t situ atio ns. I n G a m e 2 , w h e n s he m o v es, p l a y er 2 d o e s n ot kn o w w h eth e r P la y e r 1 c h o s e H e a d o r T a il. T h is is a g a m e o f i m p e rfe c t i n f orm a ti on . ( That i s , s om e o f t he i n f o rmat i o n sets c on tain m o r e th an on e n o d e.)

T h e s tra t egies f o r p l a y er 1 a re ag ain H ea d a n d T a il. T h is tim e p l a y er 2 h a s also o n ly t w o s t r a t eg i e s : H e ad and T ai l ( a s he do e s not k no w w hat 1 ha s p l a y e d) . T he no rm a l fo rm r e p r esen tation for t h i s g a m e w i l l b e:

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

Ta i l

Exe r c i s e 1 0 W h a t is th e n o r m a l-fo rm r e p r ese n ta tio n f o r th e f o l lo w i n g ga m e :

1 A 2 α 1 a

(1, - 5)

D

(4, 4 ) (5, 2 ) (3, 3 )

Ca n y ou fi n d anot her e xten si ve-f orm g am e t hat h as t he s am e n orm a l - form r e pr esen - ta tio n ?

[H in t: F or e ac h e x t en si v e -form g am e, there i s o n l y o n e no rm a l -for m r epr esen ta tion ( up t o a re na mi ng o f t he s t r a t eg i e s ) , b ut a n o r mal - f o rm ga me t y pi c a l l y ha s m o r e t ha n on e e xten siv e -for m r ep resen ta tion . ]

In m a n y ca ses a p l a y e r m a y n o t b e a ble t o g uess exactly w h i c h stra teg i es the o th er p l a y ers p la y . In o r d e r t o c o v er th ese situ atio ns w e in tro d u c e t he m i xed s tra t egies:

De fi ni ti on 20 A m i xed stra teg y of a p l a yer i s a pr ob abi l i t y dist ri but i on over the s et of his s t r at e g i e s.

If p l a y er i ha s stra tegies S i = { s i 1 , s i 2 ,..., s ik } , t h e n a m i x e d s t r a t e g y σ i fo r p la y e r i is a f u n c t io n o n S i suc h th at 0 ≤ σ i ( s ij ) ≤ 1 and σ i ( s i 1 )+ σ i ( s i 2 )+ ··· + σ i ( s ik ) = 1 . He r e σ i ca n b e t ak en to b e the o ther p l a y ers’ b eliefs ab o u t w h i c h str a teg y i wo u l d p l a y .

The e x p ec t e d p a y o ff of a p la y e r f rom a m i xed s trategy p r o fi le σ = ( σ 1 , σ 2 ,..., σ n ) is

u i ( σ ) = X u i ( s ) σ 1 ( s 1 ) ··· σ n ( s n ) .

s ∈ S

H e r e , i t i s a s s u m e d t h a t σ 1 , σ 2 ,..., σ n are s to c h asti cal l y i n dep e nden t. If σ i s correl ated, th en

u i ( σ ) = X u i ( s ) σ ( s ) ,

s ∈ S

whe r e σ ( s ) i s n o t n ecessa rily in th e m u l ti p lica t iv e f orm o f σ 1 ( s 1 ) ··· σ n ( s n ) .

7. 4 D om i n an t- st rat e gy equi l i bri u m

De fi ni ti on 21 A s t r a t e g y s ∗ w e a k l y do m i na te s s i if an d only if

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

7 . 4 . DOMI NANT- S T RA TE GY E Q UI L I BRI U M 69

an d

fo r s o m e s − i ∈ S − i .

u i ( s ∗ , s − i ) > u i ( s i , s − i )

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

is at le ast a s g o o d a s

pl a y i n g s i , a nd there a re som e con t ingencies i n w hi c h pla y ing s ∗ is strictly b e tter t h a n s i . I n t h a t c ase, i f ration al, i wo u l d p l a y s i o n ly if he b e liev e s t ha t t h ese con t in g e n c ies w i l l n e v e r o c c u r . I f h e i s c a u t i o u s i n t h e s e n s e t h a t h e a s s i g n s s o m e p o s i t i v e p r o b a b i l i t y f o r e ac h c on ti n g en cy , h e w i l l n ot pla y s i . I us e t he not i o n o f w e a k domi na nc e t o d e fi ne a d omi n an t s t r at e g y:

De fi ni ti on 22 A s t r a t e g y s ∗ is a (w eakl y) dom i nan t strategy f o r p l a y e r i i f a n d o n l y i f

s ∗ we a k l y do m i nates a l l the o ther str a te gies of p l ayer i .

W h e n t h e r e i s a w e akl y dom i nan t s t rat e gy , i f t he pl a y er i s rat i onal and c aut i ous ( i n th e sen se th at h e ass i g n p o sitiv e p r o b a b ilit y o n a ll of oth e r p la y e rs’ s tra t eg ies), t he n h e w ill pla y th e d om i n a n t s tra t eg y .

Exa m p l e:

1 \ 2 hi re

do n’ t h i r e

w o r k h a r d s h i r k

In th is g a m e , p la y e r 1 ( fi rm ) h as a s trictly d o m in an t s tra t egy : “h i r e.” P la y e r 2 ha s on ly a w ea kly d om i n a t ed stra teg y . If p l a y ers a r e r a tion a l , a nd in a d d i tion p l a y er 2 i s c a uti o us , t he n p l a y e r 1 hi res a nd pl a y er 2 s hi rks : 1

1 \ 2 hi re

do n’ t h i r e

w o r k h a r d s h i r k

De fi ni ti on 23 A s t r a t e g y p r o fi le s ∗ = ( s ∗ , s ∗ , ....s ∗ ) is a do m i n a n t stra t eg y e qu i lib rium ,

1 2 N

if a n d o n l y i f s ∗ is a w e a kly d o m in a n t s tr a t e g y f o r e a c h p l a yer i .

1 This is th e o nly o utcome, p ro vided t hat e ac h p la y e r i s r ational a nd p l a y er 2 k no ws that pl a y er 1 i s rational–as w e w ill see i n a momen t .