Ac a Uni . Sapien iae, In o ma ica, 6, 1 (2014) 71–88
A compu a ional model o ou guessing in
wo-playe non-coope a i e games
Tam´as L´aszl´o BALOGH
Uni e si y o Deb ecen
email: [email p o ec ed]
J´anos KORMOS
Uni e si y o Deb ecen
email: [email p o ec ed]
Abs ac . Se e al beha io al game heo y models aim a explaining why
“sma e “ people win mo e equen ly in simul aneous ze o-sum games,
a phanomenon, which is no explained by he Nash equilib ium concep .
We use a compu a ional model and a nume ical simula ion based on
Ma ko chains o desc ibe playe beha io and p edic payo s.
1 In oduc ion
Since he bi h o expe imen al economics, housands o expe imen s ha e been
conduc ed o obse e he beha io o decision make s in di e en si ua ions
(see e.g. [4]).
Howe e , he mos amous equilib ium concep — he Nash equilib ium [13]—
has p o ed o be unable o explain he ou come o se e al game heo e ical
expe imen s, p edic ing ha human hinking is mo e complica ed han pu e
a ionali y.
Game heo y has also p o ed o be a use ul modelling ool o ne wo k
si ua ions, e.g. elecommunica ion p oblems. Fo a de ailed su ey in his ield,
we e e he eade o [15]. An applica ion can be ound in [1].
Compu ing Classi ica ion Sys em 1998: G.3, I.6, J.4
Ma hema ics Subjec Classi ica ion 2010: 60J20, 62P20, 68U20, 91A10
Key wo ds and ph ases: compu a ional game heo y, non-coope a i e games, ou guessing,
Ma ko chains, easoning, communica ion ne wo ks
DOI:10.2478/ausi-2014-0019
71
72 T. L. Balogh, J. Ko mos
The phanomenon ha human beha io is no pu ely a ional in ce ain in-
e ac i e ne wo k si ua ions led esea che s o cons uc beha io al game he-
o y models. Recen ly, se e al models ha e been buil o explain expe imen al
esul s (e.g. [2,7]).
A popula model class aiming a explaining how playe s ou guess each o he
is he g oup o i e a i e easoning models. I e a i e easoning has been applied
in many se ings o he Rock-Pape -Scisso s game o he Beau y con es - ype
games ([3,5,8,11,12,16]).
The concep o i e a i e easoning and he co esponding main esul s a e
p esen ed in [4, pages 205–236]. A simpli ied concep o non-coope a i e, wo-
pe son, simul aneous games can be de ined as ollows. I Playe A plays a
ce ain ac ion, while Playe B plays he bes esponse o his ac ion, hen we
say ha Playe B ou guessed Playe A and played acco ding o 1- easoning.
I now Playe A ou guesses Playe B, hen Playe A plays acco ding o 2-
easoning. Following his ule, he le el o easoning can be any kposi i e
in ege , whe e he concep is de ined as k- easoning.
In his pape we in es iga e simul aneous, wo-pe son, ze o-sum, epea ed
games ha do no ha e a pu e s a egy Nash equilib ium and he playe s’
decisions depend only on hei ac ions in he p e ious ound o he game.
He e, he s ochas ic p ocesses o he playe s’ decisions and hei expec ed
payo s can be desc ibed by Ma ko chains.
Ou main goal is o poin ou why “sma e ” people win mo e equen ly in
some well-known ze o-sum games. The e a e se e al ways o de ine sma ness.
Ou de ini ion o sma ness is connec ed o he concep o i e a i e easoning
and is in oduced la e on in Sec ion 3.
We ocus on modelling playe s’ op imal s a egy choices and expec ed pay-
o s. These a e bo h s ochas ic p ocesses gi en a ce ain bima ix game and
he le el o i e a i e easoning acco ding o which playe s make hei decisions.
We cons uc ed a Ma lab sc ip ha ca ies ou he eques ed nume ical
analysis o any simul aneous, wo-pe son bima ix game. In ou pape we
p esen he ela ing analy ical esul s, desc ibe ou concep and ecall some
nume ical esul s and isualiza ions. Ou Ma lab sc ip is also a ached o
es ing and expe imen al pu poses.
The es o he pape is o ganized as ollows. Sec ion 2 ecalls some impo -
an esul s in he ield o Ma ko chains ha a e ela ed o ou opic. Sec ion
3desc ibes ou concep and p o ides nume ical e idence. Sec ion 4desc ibes
he Ma lab sc ip . Finally, Sec ion 5concludes.
A compu a ional model o ou guessing 73
2 Ma ko chains—de ini ions and some impo an
esul s
I is necessa y o ecall some basic esul s om he ield o Ma ko chains ha
we use in he upcoming sec ions. Fo a mo e de ailed analysis, we e e he
eade o [6,9,10,14]. This sec ion is a b ie summa y o Chap e 4 in [6,
pages 119–155], ha is ela ed o ou concep . The p oo s a e always omi ed.
De ini ion 1 Le Sbe a coun able ( ini e o coun ably in ini e) se . An S-
alued andom a iable Xis a unc ion om a sample space ωin o S o
which {X=x}is an e en o e e y x∈S.
He e Sneed no be a subse o R, so his ex ends he no ion o a disc e e
andom a iable (o ec o ). The concep s o dis ibu ion, join ly dis ibu ed
andom a iables, and so on, ex end in he ob ious way. The expec a ion o X,
howe e , is no meaning ul unless S⊂R. On he o he hand, he condi ioning
andom a iables in a condi ional expec a ion may be S- alued, and all o he
esul s abou condi ional expec a ion gene alize wi hou di icul y.
De ini ion 2 A ma ix P= (P(i, j))i,j∈Swi h ows and columns indexed by
Sis called a one-s ep ansi ion ma ix i P(i, j)≥0 o all i, j ∈Sand
Pj∈SP(i, j) = 1 o all i∈S.
In pa icula , he ow sums o a one-s ep ansi ion ma ix a e equal o 1.
We call P(i, j), he en y in ow iand column jo he ma ix P, a one-s ep
ansi ion p obabili y.
De ini ion 3 We say ha {Xn}n≥0is a Ma ko chain in a coun able s a e
space Swi h one-s ep ansi ion ma ix Pi X0, X1, . . . is a sequence o join ly
dis ibu ed S- alued andom a iables wi h he p ope y ha
P(Xn+1=j|X0,...,Xn) = P(Xn+1=j|Xn) = P(Xn, j)(1)
o all n≥0and j∈S.
We assume ha he sequence X0, X1, . . . is indexed by ime, and i we ega d
ime nas he p esen , he i s equa ion in (1), known as he Ma ko p ope y,
says ha he condi ional dis ibu ion o he s a e o he p ocess one ime s ep
in o he u u e, gi en i s p esen s a e as well as i s pas his o y, depends only
on i s p esen s a e. The second equa ion in (1) ells us ha P(Xn+1=j|Xn=
i) = P(i, j)does no depend on n. This p ope y is called ime homogenei y.
74 T. L. Balogh, J. Ko mos
The dis ibu ion o X0is called he ini ial dis ibu ion and is gi en by (i) :=
P(X0=i), i ∈S.
A Ma ko chain can be desc ibed by speci ying i s s a e space, i s ini ial
dis ibu ion, and i s one-s ep ansi ion ma ix.
Gi en a Ma ko chain {Xn}n≥0in he s a e space Swi h one-s ep ansi-
ion ma ix P, i can be shown ha , o e e y m≥1,i0, i1, . . . , im∈S, and n≥
0,P(Xn+1=i1,...,Xn+m=im|Xn=i0) = P(i0, i1)P(i1, i2). . . P(im−1, im).
De ini ion 4 We de ine he m-s ep ansi ion ma ix Pmo he Ma ko chain
by
Pm(i, j) = X···X
i1,...,im−1∈S
P(i, i1)P(i1, i2)P(im−1, j)(2)
No ice ha he supe sc ip mcan be in e p e ed as an exponen , his is, he
m-s ep ansi ion ma ix is he m h powe o he one-s ep ansi ion ma ix.
This is alid bo h when Sis ini e and when Sis coun ably in ini e. I is easy o
check ha his allows us o gene alize (2), ob aining P(Xn+m=j|X0,...,Xn) =
P(Xn+m=j|Xn) = Pm(Xn, j) o all n≥0,m≥1, and j∈S.
Gi en i∈S, le us in oduce he no a ion Pi(·) = P(·|X0=i), wi h he
unde s anding ha he ini ial dis ibu ion is such ha P(X0=i)> 0. I can
be shown ha
Pi(X1=i1,...,Xm=im) = P(i, i1)P(i1, i2)···P(im−1, im)(3)
o all i1,...,im∈S.
Gi en j∈S, le us in oduce he no a ion Tj o he i s hi ing ime o s a e
j(o i s e u n ime i s a ing in s a e j) and Nj o he numbe o isi s o
s a e j(excluding isi s a ime 0). Mo e p ecisely, Tj=min {n≥1:Xn=j}
and Nj=P∞
n=11{Xn=j}, whe e min ∅=∞. I also i∈S, we de ine ij =Pi(Tj<
∞) = Pi(Nj≥1). This is he p obabili y ha he Ma ko chain, s a ing in
s a e i, e e isi s s a e j(o e e e u ns o s a e ii j=i). We can now
de ine ansien and ecu en s a es.
De ini ion 5 We de ine s a e j o be ansien i jj < 1 and o be ecu en
i jj =1.
Some impo an ea u es a e poin ed ou in he nex p oposi ions.
Theo em 6 Le ing m→∞i can be shown ha
Pi(Nj=∞) = 0i jis ansien
ij i jis ecu en . (4)
A compu a ional model o ou guessing 75
Theo em 7 Fo a Ma ko chain in Swi h one-s ep ansi ion ma ix P, s a e
j∈Sis
ansien i
∞
X
n=1
Pn
j,j <∞,(5)
ecu en i
∞
X
n=1
Pn
j,j =∞.(6)
Wha is mo e, gi en ha i, j ∈Sis dis inc , i s a e iis ecu en and ij > 0,
hen s a e jis also ecu en and ji =1.
Le us de ine i educible Ma ko chains.
De ini ion 8 A Ma ko chain in Swi h one-s ep ansi ion ma ix P o be
i educible i ij > 0 o all i, j ∈S.
By P oposi ion 2, i a Ma ko chain in Swi h one-s ep ansi ion ma ix P
is i educible, hen ei he all s a es in Sa e ansien o all a e ecu en .
This allows us o e e o an i educible Ma ko chain as ei he ansien o
ecu en .
Now we u n o he analysis o he asymp o ic beha io o Ma ko chains.
Le πbe a p obabili y dis ibu ion on Ssa is ying
πj=X
i∈S
πiP(i, j), j ∈S. (7)
Rega ding πas a ow ec o , his condi ion is equi alen o π=πP. I e a -
ing, we ha e
π=πP =πP2=. . . =πPn, n ≥1. (8)
In pa icula , i {Xn}n≥0is a Ma ko chain in Swi h one-s ep ansi ion
ma ix Pand i X0has dis ibu ion π0, hen Xnhas dis ibu ion πn o each
n≥1. Fo his eason, a dis ibu ion πsa is ying (7) is called a s a iona y
dis ibu ion o he Ma ko chain.
We need one mo e de ini ion o s a e an impo an esul .
De ini ion 9 The pe iod d(i)o s a e i∈Sis de ined o be d(i) = g.c.d.D(i),
D(i) = {n∈N:Pn(i, i)> 0}, whe e g.c.d. s ands o g ea es common di iso .
We i s no ice ha e e y s a e o an i educible Ma ko chain has he same
pe iod.
No e ha i i, j ∈Sa e such ha ij > 0 and ji > 0, hen d(i) = d(j). This
allows us o speak o he pe iod o an i educible Ma ko chain.

76 T. L. Balogh, J. Ko mos
De ini ion 10 I he pe iod is 1, we call he chain ape iodic.
We can now desc ibe he asymp o ic beha io o he n-s ep ansi ion p oba-
bili ies o an i educible ape iodic Ma ko chain.
Theo em 11 I an i educible ape iodic Ma ko chain in Swi h one-s ep
ansi ion ma ix Phas a s a iona y dis ibu ion π, hen i is ecu en and
lim
n→∞ Pn(i, j) = π(j)i, j ∈S. (9)
Fu he mo e, π(i)> 0 o all i∈S.
I ollows om he p e ious s a emen ha i an i educible ape iodic Ma ko
chain in S wi h one-s ep ansi ion ma ix P has no s a iona y dis ibu ion,
hen
lim
n→∞ Pn(i, j) = 0 i, j ∈S. (10)
Thus, an i educible ape iodic Ma ko chain in a ini e s a e space S has a
s a iona y dis ibu ion.
Theo em 12 Le {Xn}n≥0be an i educible ape iodic ecu en Ma ko chain
in Swi h one-s ep ansi ion ma ix P. Then one o he ollowing conclusions
holds:
(a) Ei[Ti]<∞ o all i∈S, and Phas a unique s a iona y dis ibu ion π
gi en by
π(i) = 1
Ei[Ti], i ∈S. (11)
(b) Ei[Ti] = ∞ o all i∈S, and Phas no s a iona y dis ibu ion.
I (a) holds, hen he chain is said o be posi i e ecu en , and Equa ion (9)
holds. I (b) holds, hen he chain is said o be null ecu en , and Equa ion
(10) holds.
In he ollowing sec ion we de ine ou concep and poin ou i s ela ionship
wi h Ma ko chains.
3 The ou guessing equilib ium
This sec ion in oduces ou no ion o ou guessing equilib ium. We i s de ine
he amily o games we analyze.
A compu a ional model o ou guessing 77
De ini ion 13 In a wo pe son simul aneous no mal o m game we deno e
he playe s by i=1, 2. We deno e by Si he pu e s a egy se o playe i, whe e
si∈Siand S="2
i=1SiThe u ili y (o payo ) o any playe iis gi en by
ui(si, s−i)∈R, whe e s−ideno es he s a egy chosen by he o he playe .
Ou main assump ions a e as ollows.
Assump ion 1 We es ic a en ion o gene ic games, i.e. whe e he bes
esponse co espondance is a unc ion. Tha means ha he e exis s only one
bes esponse o any ac ion o any o he wo playe s.
Assump ion 2 The game does no ha e a pu e s a egy Nash equilib ium.
No ice ha i he game had a pu e s a egy Nash equilib ium, mixed s a egies
and p obabili y dis ibu ions would no ha e o be deal wi h.
Assump ion 3 The game is epea ed, he ounds a e deno ed by 1,2,. .. ,n,. . .
Assump ion 4 The playe s a e assumed o keep in mind he s a egy p o ile
o he p e ious ound (i.e. hei own p e ious choice and hei opponen ’s
p e ious choice) and no hing else.
Assump ion 5 Playe s a e assumed o play acco ding o 0- easoning, 1- easo-
ning, 2- easoning, . . . , k- easoning, o a acco ding o a p obabili y dis ibu ion
o he di e en easoning le els. The dis ibu ions a e exogenously gi en and
do no change among di e en ounds o he game.
The de ini ion o he di e en easoning le els a e discussed in Sec ion 1. Be-
sides, we de ine 0- easoning by playing he same s a egy as in he p e ious
ound.
The exogenously gi en dis ibu ion o e he se o easoning le els is de ined
as ollows.
De ini ion 14 Fo any playe iand any easoning le el kle Pik deno e he
p obabili y o ac ing acco ding o k- easoning.
A playe is conside ed sma e han i s opponen i his expec ed easoning
le el is highe han ha o his opponen . This is how we g ab he di e ence
in he complexi y o human hinking and y o poin ou why sma e people
may win mo e equen ly in se e al s a egic in e ac ions.
We begin he analysis wi h he desc ip ion o he equilib ium concep o
he simples case, whe e bo h playe s ha e wo s a egies each.
78 T. L. Balogh, J. Ko mos
3.1 The 2-by-2 model
Ini ially, we es ic a en ion o wo-playe 2x2 games wi h he ollowing gen-
e al payo ma ix:
Playe 2
q 1 −q
Le Righ
Playe 1 pTop uTL; TL uTR; TR
1−pBo om uBL; BL uBR; BR
Table 1: The 2-by-2 game
Acco ding o Table 1, Playe 1’s s a egies a e Top and Bo om, while Playe
2 can choose be ween Le and Righ . p, 1−p, q, 1−qa e he espec i e s a egy
choice p obabili ies. Finally, uij, ij (whe e i∈{T, B}and j∈{L, R}) a e he
wo playe s’ payo le els gi en a ce ain s a egy pai .
Acco ding o Assump ion 2, we assume ha he game does no ha e a pu e
s a egy Nash-equilib ium. A necessa y and su icien condi ion o his is
uTL > uBL, uBR > uTR, TR > TL, BL > BR.(12)
This means ha he bes esponses o bo h playe s a e gi en o any ac ion o
hei opponen . E.g. i Playe 1 chooses Top, hen Playe 2’s bes esponse is
Righ , as TR > TL.
Fo games ha do no ha e a pu e s a egy Nash equilib ium, he classical
solu ion is he mixed s a egy Nash equilib ium. As a e e ence poin , we
p o ide he o mulas o calcula ing he Nash-equlib ium mixing p obabili ies
o he wo playe s o he game using he no a ions o Table 1:
pnash = BL − BR
BL − BR + TR − TL
,(13)
qnash =uBR −uTR
uBR −uTR +uTL −uTR
.(14)
Howe e , he mixed s a egy Nash equilib ium has been c i icized, as se e al
expe imen s poin ed ou ha i does no desc ibe playe beha io p ope ly
(e.g. [2,7]). As desc ibed in he in oduc ion, hese indings led esea che s o
cons uc beha io al game heo y models ha may explain he way o s a egic
hinking mo e p ecisely.
Ou model ies o p o ide a ma hema ical amewo k o playe beha io .
We in oduce ou concep o play his o y in he nex de ini ion.
A compu a ional model o ou guessing 79
De ini ion 15 We use he no ion his o y o he s a egy p o ile o he p e i-
ous ound o he game.
The his o y o he game desc ibed by Table 1can be he ollowing: (Top;Le ),
(Top;Righ ), (Bo om;Le ) and (Bo om;Righ ).
Depending on he his o y, we can de ine ou di e en games, whe e he
s a egies and he payo s a e he same. The only di e ence is ha bo h playe s
keep he his o y in mind and his has an in luence on hei decisions, i.e. hei
s a egy mixing p obabili ies.
The payo and p obabili y ma ices wi h he ou di e en his o ies a e as
ollows.
Playe 2
qTL 1−qTL
Le Righ
Playe 1 pTL Top uTL; TL uTR; TR
1−pTL Bo om uBL; BL uBR; BR
Table 2: The game wi h (Top, Le ) his o y
Playe 2
qTR 1−qTR
Le Righ
Playe 1 pTR Top uTL; TL uTR; TR
1−pTR Bo om uBL; BL uBR; BR
Table 3: The game wi h (Top, Righ ) his o y
Playe 2
qBL 1−qBL
Le Righ
Playe 1 pBL Top uTL; TL uTR; TR
1−pBL Bo om uBL; BL uBR; BR
Table 4: The game wi h (Bo om, Le ) his o y
86 T. L. Balogh, J. Ko mos
Figu e 2: Long- e m expec ed payo s o he wo playe s depending on he
numbe o ounds; 3-by-3 case
5 Conclusions
Beha io al game heo y has been dealing wi h he unde s anding o human
beha io in s a egic in e ac ions. Among se e al di e en app oaches, we ha e
de eloped a beha io al model ha aims a showing why “sma e ” people
ou guess hei opponen s and win mo e equen ly in some well-known ze o-
sum games.
Game heo y is a use ul modeling ool o ne wo k p oblems. We de ined a
beha io al model in a wo-playe non-coope a i e ne wo k.
We used he concep o i e a i e easoning o de ine sma ness. The heo y
o Ma ko chains has p o ed o be a e y use ul echnical ool o p o e he

A compu a ional model o ou guessing 87
main esul o he pape . Namely, an ou guessing equilib ium acco ding o ou
de ini ion exis s and can e en be calcula ed.
A Ma lab sc ip suppo s he calcula ions and p o ides nume ical e idence
o ou concep .
The au ho s wish o emphasize ha he in oduced model can no only be
applied o he games ecalled in he examples, bu o any con lic si ua ion
ha can be modeled by bima ix games.
Al hough he heo e ical esul s a e p o ed, and nume ical e idence is also
p o ided, he e ha e emained some in e es ing ques ions which a e ou o he
scope o his pape . One o hese ques ions is a he echnical: wha ypes o
Ma ko chains (e.g. pe iodic, abso bing e c. . . ) can eme ge gi en a speci ic
bima ix game and ini ial s a egy p o ile? Ano he one deals wi h he game
heo e ic assump ions: i ei he he numbe o playe s, o he simul ani y o
decisions we e al e ed, o we allowed o non-gene ic games, how would he
equilib ium ou come change? These p oblems a e le o u u e esea ch.
Acknowledgemen s
This pape was suppo ed in pa by he T´
AMOP-4.2.2C-11/1/KONV-2012-
0001 p ojec suppo ed by he Eu opean Union, co- inanced by he Eu opean
Social Fund.
Re e ences
[1] T. Alpcan,T. Basa , A Globally S able Adap i e Conges ion Con ol Scheme
o In e ne -S yle Ne wo ks wi h Delay, IEEE/ACM T ans. On Ne wo king 13
(2005) 1261–1274. ⇒71
[2] T. L. Bea d,R. Beil, Do people ely on he sel -in e es ed maximiza ion o o he s?
An expe imen al es ,Managemen Science 40, 2 (1994) 252–262. ⇒72,78
[3] S.C. Cab e a, C. M. Cap a, R. Gomez, The e ec s o common ad ice on one-sho
a elle ’s dilemma games: Explaining beha io h ough an in ospec i e model
wi h e o s, Washing on and Lee Uni e si y wo king pape , 2002. ⇒72
[4] C.F. Came e ,Beha io al Game Theo y: Expe imen s in S a egic In e ac ion,
P ince on Uni e si y P ess, 2003, pp. 199–264. ⇒71,72
[5] C. M. Cap a,J.K. Goe ee, R. Gomez, C. Hol , Anomalous beha io in a elle ’s
dilemma?,Ame . Economic Re iew 89, 3 (1999) 678–690. ⇒72
[6] S. N. E hie ,The Doc ine o Chances, Sp inge , 2010, pp. 119–155. ⇒73
[7] J. K. Goe ee, C. Hol , S ochas ic game heo y: Fo playing games, no jus o
doing heo y, P oc. Na ional Academy o Sciences 96 (1999) 10564–10567. ⇒
72,78
88 T. L. Balogh, J. Ko mos
[8] T. Ho, C. F. Came e , K. Weigel , I e a ed dominance and i e a ed bes - esponse
in expe imen al “p-beau y con es s”,Ame . Economic Re iew 88 (1998) 947–
969. ⇒72
[9] S. P. Meyn, R. L. Tweedie, Ma ko chains and s ochas ic s abili y, Camb idge
Uni e si y P ess, 2009. ⇒73
[10] S. P. Meyn,Con ol Techniques o Complex Ne wo ks, Camb idge Uni e si y
P ess, 2007. ⇒73
[11] H. Moulin,Game Theo y o he Social Sciences, New Yo k Uni e si y P ess,
1986. ⇒72
[12] R. Nagel, Un a elling in guessing games: an expe imen al s udy,Ame . Eco-
nomic Re iew 85, 5 (1995) 1313–1326. ⇒72
[13] J. Nash,Non-coope a i e games,Annals o Ma hema ics 54, 2 (1951) 286-295.
⇒71
[14] J. R. No is,Ma ko chains, Camb idge Uni e si y P ess, 1998. ⇒73
[15] I. A. Shah, S. Jan, I. Khan, S. Qama , An o e iew o game heo y and i s
applica ions in communica ion ne wo ks In . J. Mul idisciplina y Sciences and
Enginee ing 3, 4 (2012) 5–11. ⇒71
[16] Y. So ik, Impossible be s: an expe imen al s udy, Uni e si y o Oslo wo king
pape , 1999. ⇒72
Recei ed: Feb ua y 16, 2014 •Re ised: Ma ch 31, 2014