Ti le: Compu a ional Complexi y Aspec s o Pa h-Fo ming Games
Au ho : O iol Saguillo Gonzalez
Ad iso : Albe A se ias Pe i
Depa men : Compu e Science Depa men
Academic yea : 2024
Mas e o Science in
Ad anced Ma hema ics and
Ma hema ical Enginee ing
Uni e si a Poli `ecnica de Ca alunya
Facul a de Ma em`a iques i Es ad´ıs ica
Mas e in Ad anced Ma hema ics and Ma hema ical Enginee ing
Mas e ’s hesis
Compu a ional Complexi y Aspec s
o Pa h-Fo ming Games
O iol Saguillo Gonzalez
Supe ised by Albe A se ias Pe i
June, 2024
I would like o exp ess my deepes g a i ude o my amily and iends o hei unwa e ing suppo and
encou agemen h oughou his jou ney. A special hanks o my u o , Albe A se ias, o his in aluable
guidance, men o ship and showing me he beau y o Compu a ional Complexi y. I am also g a e ul o
Juanjo Rue o his insigh ul ad ice du ing my mas e ’s p og am, and o my iends a EPFL o hei
cons an suppo and companionship.

Abs ac
This hesis explo es he cu en S a e o he A ega ding he compu a ional complexi y o a ious wo-
playe in ini e games, ocusing on Pa i y Games, Mean Payo Games, and Simple S ochas ic Games.
Ini ially, we del e in o he applica ion o uni e sal ees in he ealm o Pa i y Games, ha simpli ied he
g oundb eaking quasi-polynomial ime algo i hm de eloped by Calude, Jain, Khousaino , Li, and S ephan in
2017. This app oach has since been a ca alys o he de elopmen o simila complexi y algo i hms in his
domain. We o e iew he wo k o Fijalkow e al. in 2020 who buil on his ounda ional concep o ex end
he use o uni e sal objec s o design algo i hms o Mean Payo Games. He e, we analyze a amily o alue
i e a ion algo i hms ha demons a e he u ili y o uni e sal g aphs, an app op ia e gene aliza ion o he
uni e sal ees, in op imizing s a egies o Mean Payo Games. Fu he mo e, we assess he o e a ching
complexi y o Simple S ochas ic Games, aiming o d aw pa allels and dis inc ions in s a egies ac oss hese
game ypes. Th ough his s udy, we aim o enhance he unde s anding o algo i hmic solu ions in game
heo y and p o ide a consolida ed iew o he complexi y landscape ac oss di e en game amewo ks.
Keywo ds
Game Theo y, Compu a ional Complexi y, Economics and Compu a ion, Algo i hmic Game Theo y,
In elligen Agen s, G aphs, Combina o ics
1
Con en s
1 In oduc ion 3
2 P elimina ies 5
2.1 Basic De ini ions ........................................ 5
2.2 Games De ini ion ....................................... 8
2.3 Value I e a ion Algo i hms .................................. 11
3 Pa i y Games 13
3.1 Uni e sal T ees ........................................ 13
3.2 P og ess Measu e ....................................... 17
3.3 Quasi-polynomial Algo i hm .................................. 18
4 Mean Payo Games and Ene gy Games 20
4.1 Reduc ion Pa i y Games o MPG ............................... 21
4.2 Uni e sal G aphs ........................................ 21
4.3 Uppe and Lowe Bounds on Uni e sal G aphs ........................ 23
5 Simple S ochas ic Games 27
5.1 Reduc ion MPG o SSG .................................... 27
5.2 Complexi y o SSG is NP ∩coNP .............................. 30
6 Conclusions 33
2
1. In oduc ion
The NP s P p oblem [5] is one o he mos impo an open ques ions in compu e science and ma hema ics,
dealing wi h he e iciency o sol ing p oblems and he ela ionship be ween wo classes o p oblems: P and
NP. P (Polynomial Time) ep esen s p oblems ha can be sol ed quickly by an algo i hm. ”Quickly” means
in polynomial ime, which is a way o measu e how he ime o sol e he p oblem inc eases wi h he size
o he inpu . Examples o p oblems in P include so ing numbe s and inding he sho es pa h in a g aph.
NP (Nonde e minis ic Polynomial Time) ep esen s p oblems o which a solu ion can be checked quickly,
gi en he solu ion. Examples o p oblems in NP include checking i some subse o a gi en se o num-
be s adds up o a a ge numbe (Subse Sum) and de e mining i a Boolean o mula can be sa is ied (SAT).
The main ques ion in he NP s P p oblem is whe he e e y p oblem whose solu ion can be checked
quickly can also be sol ed quickly. Fo mally, his asks i P=NP. I P=NP, i would mean ha e e y
p oblem o which a solu ion can be e i ied quickly can also be sol ed quickly. This would ha e a huge
impac on ields like c yp og aphy, op imiza ion, and a i icial in elligence, as many cu en ly di icul p ob-
lems would become easy o sol e. On he o he hand, i P=NP, i means he e a e p oblems in NP ha
canno be sol ed quickly, e en hough hei solu ions can be checked quickly. This aligns wi h ou cu en
expe ience, whe e many impo an p oblems seem o lack e icien solu ions.
P oblems ha lie in he in e sec ion o NP and coNP, deno ed as NP ∩coNP, a e pa icula ly in igu-
ing. These p oblems can be bo h e i ied and e u ed in polynomial ime, depending on he gi en answe .
One eason hese p oblems a e o signi ican in e es is ha hey p o ide insigh in o he s uc u e o NP
and coNP. I a p oblem in NP ∩coNP is also p o en o be NP-comple e, i would imply ha NP equals
coNP, a majo un esol ed ques ion in compu a ional complexi y heo y. Such a esul would ha e p o ound
implica ions, sugges ing ha e e y p oblem o which a solu ion can be e i ied quickly can also ha e i s
nega ion e i ied quickly.
On he o he hand, Game Theo y s udies he s a egic in e ac ions be ween a ional agen s, whe e he
decisions o each pa icipan in luence he ou comes o all in ol ed. I aims o p edic he ou comes o
hese in e ac ions and o ind op imal s a egies o each playe . The undamen al concep s o Game Theo y
include playe s, s a egies, payo s, and games. Playe s a e he decision-make s, s a egies a e he possible
ac ions hey can ake, and payo s a e he ewa ds o ou comes esul ing om he chosen s a egies. A
cen al concep is he Nash equilib ium, a s a e whe e no playe can imp o e hei payo by unila e ally
changing hei s a egy.
The in e sec ion o Game Theo y and Compu a ional Complexi y o ms a c ucial heo e ical ounda ion
wi h as implica ions o a ious ields, including economics, compu e science, and ope a ions esea ch.
One o he mos ema kable esul s in his a ea is he cha ac e iza ion o he complexi y class PPAD
(Polynomial Pa i y A gumen s on Di ec ed g aphs) in oduced by Ch is os Papadimi iou [8]. This class
cap u es he complexi y o inding Nash equilib ia in games, showing ha his p oblem is PPAD-comple e.
This means ha while Nash equilib ia a e gua an eed o exis , inding hem can be as compu a ionally
challenging as he ha des p oblems in PPAD. The ongoing esea ch a he con luence o hese ields con-
inues o p o ide deep insigh s and p ac ical ools o ackling complex, s a egic decision-making p oblems.
Simple S ochas ic Games (SSGs) a e a class o wo-playe games ha in ol e bo h de e minis ic and
3
C.C. Aspec s o Pa h-Fo ming Games
p obabilis ic ansi ions. These games a e played on a ini e di ec ed g aph, whe e he playe s aim o
each designa ed a ge s a es wi h he highes p obabili y. SSGs a e pa icula ly in e es ing due o hei
applica ions in a eas such as e i ica ion, syn hesis, and p obabilis ic algo i hms. The seminal wo k by
Anne Condon [4] es ablished he ounda ional complexi y esul s o SSGs, showing ha he p oblem o
deciding he winne in hese games lies in NP ∩coNP. This esul indica es ha while i is compu a ionally
challenging o de e mine he winne , he p oblem is bo h e i iable and e u able in polynomial ime, gi en
a co ec solu ion.
In ou s udy, we will explo e a majo b eak h ough in he ealm o Pa i y Games [2], which a e simple han
Simple S ochas ic Games (SSGs) and also belong o he complexi y class NP ∩coNP. A b eak h ough
in his a ea is he ecen de elopmen o a quasi-polynomial algo i hm o Pa i y Games. This algo i hm,
de ailed in [7], has signi ican ly ad anced ou unde s anding and spa ked enewed in e es in he ield. The
exis ence o such an algo i hm aises he in iguing possibili y ha NP ∩coNP could equal P o hese
games.
Value i e a ion is he s a egy used o ob ain his quasi-polynomial algo i hm, hanks o he eliance on
Uni e sal T ees, a s uc u e ha has a quasi-polynomial space. Value i e a ion algo i hms play a pi o al
ole in sol ing hese games. Fo ene gy games, Casa es and Ohlmann [3] discussed he ESL algo i hm,
which highligh s he e iciency imp o emen s possible wi h alue i e a ion echniques. Simila ly, Fijalkow e
al. [6] in es iga ed alue i e a ion using uni e sal g aphs o Mean-Payo Games (MPGs), demons a ing
i s impac on he complexi y o hese games.
We will u he explo e how hese s uc u es wo k o Mean-Payo Games (MPG) and assess hei po-
en ial o yield a quasi-polynomial ime algo i hm, making u he p og ess owa ds de e mining whe he
NP ∩coNP is indeed in P. The complexi y o MPGs has been a opic o signi ican esea ch, wi h oun-
da ional esul s p o ided by Zwick and Pa e son [10]. Thei wo k laid he g oundwo k o unde s anding
he compu a ional challenges associa ed wi h MPGs, and subsequen esea ch has buil on hese insigh s
o de elop mo e e icien algo i hms.
This b eak h ough has p o ound implica ions o compu a ional complexi y, sugges ing ha e icien al-
go i hms may exis o some class o p oblems p e iously hough o be in ac able. The de elopmen o
he quasi-polynomial algo i hm o Pa i y Games has he e o e become a ocal poin in he unlikely ques
o mos o he scien i ic communi y o de e mine i he p oblems in he complexi y class NP ∩coNP a e
in P, inspi ing u he esea ch and explo a ion in his exci ing a ea o s udy in he bigges conjec u e o
he Theo e ical Compu e Science.
4
De ini ion 2.24 (Value p oblem G(u)).Fo each o he games desc ibed we ace he ollowing compu a-
ional ques ions, o each o hem assume Gbe a Game and o some e ex u∈G:
•PG: G(u) = 1?
•MPG: G(u)>0?
•DMPG: G(u)>0?
•SSG: G(u)>1/2?
2.3 Value I e a ion Algo i hms
Value I e a ion algo i hms a e c i ical compu a ional ools used o sol e a a ie y o game heo y p oblems,
such as Pa i y Games, Mean Payo Games, and Simple S ochas ic Games, e c. These algo i hms a e
essen ial because hey o e a sys ema ic way o de e mine op imal s a egies in games wi h complex and
in ini e s a es, which a e common in hese ypes o games.
Theo em 2.25 (Kleene ixed poin heo em).Le (X,≤)be a la ice and O:X→X a mono onic
ope a o , hen Ohas a leas ixed poin which is also he leas p e- ixed poin . Fu he mo e:
•i X is ini e he sequence by u0=⊥and uk+1 =O(uk)is s a iona y and i s limi is he leas ixed
poin o O.
•i Op ese es sup ema hen he leas ixed poin o Ois sup{Ok(⊥) : k∈N}.
Le us conside a la ice(X,≤): he bina y ela ion ≤is a pa ial o de , and e e y pai o elemen s has a
leas uppe bound and a g ea es lowe bound. ⊥ o he las elemen in Xand ⊤ o he g ea es elemen .
An ope a o O:X→Xis mon onic i o all x,y∈Xs. . x≤ywe ha e O(x)≤O(y), and p ese es
sup ema i O(supnxn) = supnO(xn) o all inc easing sequences (xn)n∈N.xis a p e- ixed poin i O(x)≤x
and pos - ixed i O(x)≥x.
Le us conside a game G. We le FVdeno e he se o unc ions V→Y, i is a la ice when equipped
wi h he componen wise (pa ial) o de induced by Y: we say ha µ≤µ′i o all e ices we ha e
µ( )≤µ′( ). The main ing edien is an ope a o OG:FV→FV. The in en is o ob ain he unc ion
Gas a ixed poin o he ope a o OG, using he wo di e en app oaches o ixed poin s we in oduced
abo e. Whene e Gis clea om he con ex , we simply w i e Oins ead o OG.
P ope y 2 (Fixed poin h ough mono onici y): Fo all games G, he ope a o OGis mono onic, and
Gis he leas ixed poin o OG.
Rema k 5 (G ea es e sus leas ixed poin ). Whene e echnically con enien o mo e in ui i e,
we will ob ain he alue unc ion as he g ea es ixed poin o OG. Fo alue i e a ion algo i hms, only
small adjus men s a e necessa y. This will be di e en o s a egy imp o emen algo i hms, in he nex
sec ion.
Theo em 4 u he s a es ha Gis he limi o he sequence (OG(⊥))k
k∈N. The pseudocode is gi en
in 1.
11

C.C. Aspec s o Pa h-Fo ming Games
Algo i hm 1 A gene ic alue i e a ion algo i hm based on ixed poin h ough mono onici y – nai e e sion.
1: o ∈Vdo
2: µ( )←⊥
3: end o
4: epea
5: µ←OG(µ)
6: un il µ=OG(µ)
7: e u n µ
Theo em 2.26 (Gene ic alue i e a ion algo i hm h ough mono onici y).Assume P ope y 2 ( ixed poin
h ough mono onici y) and ha Y is ini e. Then he gene ic alue i e a ion algo i hm ou pu s Gwi hin
a mos n · |Y|i e a ions.
P oo . I Yis a ini e la ice hen so is FV. Fo each , he sequence (Ok(µ)( ))k∈Nis non-dec easing, so
i can be s ic ly dec eased a mos |Y| imes. A each i e a ion he alue o a leas one e ex is s ic ly
dec eased. Hence he e a e a mos n· |Y|i e a ions.
I Yis no ini e hen he sequence (OG(µ)k)k∈Ncon e ges owa ds Gbu u he analysis is equi ed o
e alua e he con e gence speed.
12
3. Pa i y Games
To sol e pa i y games using a quasi-polynomial algo i hm, we mus u ilize a alue i e a ion algo i hm.
Howe e , be o e del ing in o he algo i hm, i is essen ial o in oduce some key concep s ha will help us
es ablish he p ocess and co ec ness o he algo i hm.
To unde s and he quasi-polynomial algo i hm p oposed in [2], we need o i s de ine some undamen al
da a s uc u es, namely Uni e sal T ees and P og ess Measu es. These concep s a e c ucial o quan i ying
he playe ’s p og ess owa ds achie ing pa i y. The main e e ence o his chap e can be ound in [7].
3.1 Uni e sal T ees
The ees we conside ha e h ee p ope ies: hey a e oo ed, e e y lea has he same dep h, and he
child en o a node a e o ally o de ed. Fo mally, a ee o heigh 0 is a lea , and a ee o heigh h+ 1 is
an o de ed lis [ 1, ... , k] o sub ees each o heigh h. We conside wo pa ame e s o ees: he heigh ,
and he size which is de ined o be he numbe o lea es.
We say ha a ee embeds in o ano he ee Ti :
•ei he bo h a e lea es,
•o le = [ 1, ... , k] and T= [T1, ... , Tk], he e exis i1<· · · <iksuch ha o all j∈[1, k], we
ha e ha jembeds in o Tij.
Ano he possible de ini ion and pe spec i e o his embedding is o conside i as an isomo phism o a
smalle ee wi hin a la ge ee. Fo mally, le Tand T′be ees, wi h Tbeing he smalle ee and T′ he
la ge ee. We say ha Tis embedded in T′i he e exis s an injec i e homomo phism ϕ:T→T′such
ha o e e y e ex ∈T,ϕ( ) and i s co esponding edges in Tp ese e he adjacency ela ionships in
T′. This embedding main ains he s uc u al p ope ies o Twi hin T′, e ec i ely mapping Tin o T′.
De ini ion 3.1. A ee is (n, h)-uni e sal ee i i embeds all ees o size n and heigh h.
Figu e 5: On he le , a ee o heigh h= 2, which is he smalles (5, 2)-uni e sal ee: i has size 11
(meaning i has 11 lea es). On he igh , a ee o size 5 and one possible embedding o he uni e sal ee.
[7]
An impo an aspec o hese ees is hei cons uc ion, which is c ucial o demons a ing how o model
a pa i y game using he la ice om he i s le el o he uni e sal ee. Addi ionally, i is essen ial o
13
C.C. Aspec s o Pa h-Fo ming Games
no e ha a quasi-polynomial algo i hm can be achie ed h ough he cons uc ion o he Uni e sal T ee o
Pa i y Games. The complexi y o Value I e a ion algo i hms depends on he s uc u e being i e a ed o e
and i s size o he numbe o possible s a es du ing he algo i hm’s execu ion.
Theo em 3.2. The e exis s an (n,h)-uni e sal ee wi h size (n,h)sa is ying he ollowing:
• (n,h) = (n,h−1) + (⌊n/2⌋,h) + (n−1− ⌊n/2⌋,h)
• (n, 0) = 1
• (0, h) = 0
An uppe bound is gi en by
(n,h)≤n·h−1 + ⌊log2(n)⌋
⌊log2(n)⌋≤n2.45+log2(1+ h−1
log2(n))
, which is quasi-polynomial in n and h in gene al, and polynomial i h =O(log2(n)).
P oo . In o de o p o e ha we can gene a e an (n,h)-uni e sal ee wi h size (n,h) we a e going o
build he ee wi h he ollowing cons uc ion:
•Tle be a (⌊n/2⌋,h)-uni e sal ee.
•Tmiddle be a (n,h−1)-uni e sal ee.
•T igh be a (n−1− ⌊n/2⌋,h)-uni e sal ee.
We a e going o me ge wi h he same oo Tle and T igh and inse be ween hem a child, which is Tmiddle .
Le Tbe he (n,h)- ee cons uc ed his way. We p o e ha Tis (n,h)-uni e sal by induc ion on h:
•Fo he base case h= 0, Tis a single lea and n= 1, which is clea ly (1, 0)-uni e sal.
•Fo he induc i e case, assume a h>0 and ix an (n,h)- ee = [ 1, ... , k]. We wan o show ha
Tembeds . The main ques ion is how can we cu his ee and ha e he maps o T igh ,Tmiddle
and Tle . We know ha he sum is a mos n, i no we canno embed ha ee iin he uni e sal
one. The e o e, he e exis s a unique p∈[1, k] s. . he sum o he lea s om 1 o p−1≤ ⌊n/2⌋
and he es is <⌊n/2⌋. Because we know ha Tmiddle has a size o n, hen o he pselec ed we
ha e ha he o al lea s o p+1 o kis ≤n−1− ⌊n/2⌋. To embed in o T we p oceed as ollows:
– he ee [ 1, ... , p−1] has a mos ⌊n/2⌋lea es, so i embeds in o Tle by induc ion hypo hesis;
– he ee phas heigh h−1 and a mos nlea es, so i embeds in o Tmiddle by induc ion
hypo hesis;
– he ee [ p+1, ... , k] has a mos n− ⌊n/2⌋lea es, so i embeds in o T igh by induc ion
hypo hesis.
14
O de ing he lea es
Now we will need o de ine an o de o he lea s in o de o ha e a la ice o compa e di e en lea s
in he ee. The main idea o concep ha we need o ex ac is how can we say i we a e in a pos - ixed
o p e- ixed poin . This is going o be a key s ep owa ds he Value I e a ion algo i hm.
Le ’s conside a ee o heigh h, and de ine d= 2h. A lea o is gi en by a lis o di ec ions in-
dexed by odd numbe s p∈[1, d] downwa ds (e.g. d= 10 a lea is gi en by (D9,D7,D5,D3,D1)).
We w i e Y o he se o in e nal nodes and lea es o and ≤ o he lexicog aphic o de on Y . The
in e p e a ion is ha i l≤l′, wo nodes, i and only i lis o he le o l′.
The se o ela ions ◁po e Y o each p∈[1, d]. Fo a lea l= (Dd−1, ..., D1) we w i e l≥p o
he uple (Dd−1, ..., Dp) o odd pand (Dd−1, ..., Dp+1) o e en numbe s, which we call he p- unca ed
b anch o l.
•Fo podd, we say ha l◁pl′i l≥p<l′
≥p
•Fo pe en, we say ha l◁pl′i l≥p≤l′
≥p
Figu e 6: Illus a ion o he ela ions ◁p. In ed, we see ha ℓ2◁1ℓ3;ℓ2◁2ℓ3;ℓ3◁2ℓ2;ℓ1◁3ℓ2;
ℓ1◁2ℓ2.
Lemma 3.3. The ela ions ◁p o [1, d]induced by a ee sa is ies he ollowing p ope ies:
•◁dis he ull ela ion, i.e. ∀b,b′(b◁db′)
•l◁pl′∧l′◁ql′′ ⇒l◁max(p,q)l′′
•◁pis non- e lexi e i p is odd.
•◁1is o al.
• o d <p e en we ha e l ◁pl′⇐⇒ ¬(l′◁p+1 l)
Wi h he o de p ope ies we ha e om he uni e sal ees we can eph ase he no ion o embedding
be ween ees wi h he o de ing o lea es as ollows:
15
C.C. Aspec s o Pa h-Fo ming Games
Lemma 3.4. (Equi alence be ween embedding and o de s). Le ,T be wo ees o heigh s h and d = 2h.
Then embeds in o T i and only i ∃µ:Y →YTs. . o all lea es l,l′∈ , and all p ∈[1, d]:
l◁
pl′⇒µ(l)◁T
pµ(l′)
This lemma is going o be he mos impo an one, he main usage is how can we model om a Pa i y
Game G aph he s uc u e o a Uni e sal T ee. The e o e, we will be able o ob ain a Uni e sal G aph o
all he Pa i y Games and he g aph s uc u e hey a e unde lined.
In o de o p o e he p e ious lemma we can use induc ion on he ollowing lemma o e e y lea in
he ee.
Lemma 3.5. Supose ha o e e y in e n node u o , exis s an in e n node u′o T such ha
dep h(u) = dep h(u′). Le L be he se o lea s unde u in . Then, µ(L)a e lea es unde u′in T.
P oo . We p oceed by induc ion on he heigh o he sub ee oo ed a each in e nal node uin .
Base Case: Fo he lea es o , he lemma holds i ially since each lea lin maps di ec ly o a
co esponding lea µ(l) in Tby de ini ion o he embedding unc ion µ. This sa is ies he condi ion ha
he dep h o a lea in is equal o he dep h o i s image in T.
Induc i e S ep: Assume ha o all in e nal nodes o a dep h k<h, he e exis s a co esponding
in e nal node ′in Tsuch ha :
1. dep h( ) = dep h( ′),
2. The se o lea es L unde in maps o he se o lea es unde ′in T ia µ.
Now conside an in e nal node uin a dep h k+ 1. By he induc i e hypo hesis, o each child o u
(which is a dep h k), he e exis s a co esponding node ′in Tsuch ha :
1. dep h( ) = dep h( ′),
2. The se o lea es unde maps o he se o lea es unde ′.
Since uis he pa en o nodes like a dep h k+ 1, and uagg ega es he lea es unde i s child en , we
need o ind a node u′in T ha :
1. Is a he same dep h as u(dep h(u) = k+ 1),
2. Agg ega es he lea es unde i s co esponding child en ′.
Such a node u′exis s because embeds in o T, implying he e is a s uc u al p ese a ion o pa en -child
ela ionships and lea agg ega ions unde hese ela ionships. By de ini ion o embedding, he in e nal node
u′in Twill also espec he hie a chical s uc u e such ha µmaps he lea es unde u o he lea es unde u′.
Hence, µ(Lu)⊂Lu′, sa is ying he lemma’s equi emen s.
16

3.2 P og ess Measu e
In o de o quan i y om a ee which s a es a e be e han o he o achie e he pa i y, we will need a
la ice (Y ,≤) and a mono onic unc ion δ :Y ×[1, d]→Y . The se Y is going o be he lea es o
wi h an ex a elemen ⊤de ined as ℓ∈Y , and ≤is he lexicog aphic o de on lea es wi h ⊤as he
g ea es elemen .
δ (ℓ,p) = min
≤{ℓ′∈Y |ℓ < ℓ′≤p}.
This in u n induces a mono onic ope a o O :FV→FVde ined by:
OT(µ)(u) = (min{δ (µ(u), p)|up
−→ ∈E}i u∈VE e,
max{δ (µ(u), p)|up
−→ ∈E}i u∈VAdam,
whe e VE e and VAdam a e e ex se s in he pa i y game.
Le Gbe a pa i y game, a p og ess measu e is a unc ion µ:V→Y , which is a p e- ixed poin :
O(µ)≤µ.
Un olding he de ini ions, his means ha o all e ices u, we ha e:
∃up
−→ ∈E:δ (µ(u), p)≤µ(u) i u∈VE e,
∀up
−→ ∈E,δ (µ(u), p)≤µ(u) i u∈VAdam.
Lemma 3.6 (Fundamen al Lemma o p og ess measu es o e g aphs).Le G be a game and a e ex.
Then G sa is ies pa i y om i he e exis s a ee and a p og ess measu e µ:V→Y s. . µ( )=⊤.
P oo . Le us assume ha he e exis s a ee and a p og ess measu e µ:V→Y such ha µ( )=⊤
and o all edges up
−→ ∈Ewe ha e µ( )◁pµ(u). To show ha Gsa is ies pa i y om , we show ha
any cycle eachable om is e en. Le us conside such a cycle:
1
p1
−→ 2
p2
−→ 3· · · k
pk
−→ 1.
Since he cycle is eachable om and µ( )=⊤, his implies ha µ( i)=⊥ o i∈[1, k]. Le us assume
owa ds con adic ion ha i s maximal p io i y is odd, and wi hou loss o gene ali y i is p1. Applying ou
hypo hesis o each edge o he cycle, we ha e
µ( 1)◁pkµ( k)◁pk−1· · · ◁p2µ( 2)◁p1µ( 1).
The second i em o Lemma 3.6 implies ha µ( 1)◁p1µ( 1), which con adic s he hi d i em since ◁p1
is non- e lexi e gi en ha p1is odd.
Le us now p o e he con e se implica ion. We p o e he ollowing p ope y by induc ion on he numbe o
p io i ies: o all g aphs sa is ying pa i y (wi hou he usual assump ion ha e e y e ex has an ou going
edge), he e exis s a ee and a p og ess measu e µ:V→Y such ha µ( )=⊤ o all e ices ∈V.
Le Gbe a g aph sa is ying pa i y. Wi hou loss o gene ali y, he la ges p io i y din he g aph is
e en. Le us de ine G′as he g aph ob ained om Gby emo ing all edges wi h p io i y d. We conside
17
C.C. Aspec s o Pa h-Fo ming Games
i s decomposi ion in o s ongly connec ed componen s: le G1, ... , Gkdeno e he s ongly connec ed com-
ponen s o G′, numbe ed so ha o any edge u→ ∈E(G′), i u∈V(Gi) hen ∈V(Gj) o j≥i. A
s onge p ope y holds o edges ud−1
−−→ ∈E(G′): i u∈V(Gi) hen ∈V(Gj) o j>i. Indeed, i
∈V(Gi) hen we could o m a cycle in G′whose la ges p io i y is d−1, a con adic ion. Hence each
Gihas p io i ies in [1, d−2], and being a subg aph o Gi sa is ies pa i y. By induc ion hypo hesis, he e
exis s a ee iand a p og ess measu e µi:V(Gi)→Y isuch ha µi( )=⊤ o all e ices ∈V(Gi).
Le us de ine = [ 1, ... , k], and he unc ion µ:V(G)→Y by µ( ) = µi( ) i ∈V(Gi). We
claim ha µis a p og ess measu e: le us conside an edge up
−→ ∈E(G), hen
•i p=d, hen µ( )◁dµ(u) because ◁dis he ull ela ion;
•i p=d−1, hen µ( )◁d−1µ(u) because u∈V(Gi) and ∈V(Gj) o j>i;
•I p<d−1, hen µ( )◁pµ(u). Indeed u∈V(Gi) and ∈V(Gj) o j≥i, so ei he j=iand
his ollows om he ac ha µiis a p og ess measu e, o j>iand we ha e µ( )◁d−1µ(u) so a
o io i µ( )◁pµ(u).
Theo em 3.7 (Fundamen al heo em o p og ess measu es).Le G be a game and a e ex. Then E e
wins om i he e exis s a ee and a p og ess measu e µ:V→Y s. . µ( )=⊤.
P oo . Assume ha E e wins om and le σbe a posi ional s a egy. The pa i y g aph G[σ] sa is ies
pa i y om , so hanks o Lemma 3.6 he e exis s a ee and a unc ion µ:V→Y such ha µ( )=⊤
and o all edges up
−→ ∈Ewe ha e µ( )◁pµ(u). We ema k ha µ:V→Y is ac ually a p og ess
measu e: he condi ion o u∈VE e is ensu ed by he edge σ(u), and he condi ion o ∈VAdam by
assump ion on µ.
Co olla y 3.8 (Fundamen al co olla y o p og ess measu es).Le G be a game wi h n e ices and p io i ies
in [1, d], and a e ex. Le T be a (n,d/2)-uni e sal ee. Then, E e wins om i he e exis s a
p og ess measu e µ:V→YTs. . µ=⊤.
P oo . Assume ha E e wins om , hanks o Theo em 3.7 he e exis s a ee and a p og ess measu e
µ:V→Y such ha µ( )=⊤. Since Tis (n,d/2)-uni e sal and has a mos nlea es, embeds in o
T, which hanks o Fac 14 implies ha he e exis s µ′:Y →YT espec ing he ela ions ◁. We ex end
i o µ′:Y →YTby µ′(⊥) = ⊥. Then he composi ion µ′◦µ:V→YTis a p og ess measu e such ha
(µ′◦µ)( )=⊥. The con e se implica ion is a di ec consequence o Theo em 3.7.
3.3 Quasi-polynomial Algo i hm
Le us ix Tan (n,d/2)-uni e sal ee. I induces bo h a la ice (YT,≤) and a mono onic unc ion
δT:YT×[1, d]→YT, which in u n induces a mono onic ope a o OT:FV→FV. Since Tis ixed we
do no speci y he subsc ip T o all hese objec s.
The las s ep is o cons uc an algo i hm e u ning he minimal p og ess measu e elying on Kleene’s
ixed poin heo em (s a ed as Theo em 2.28 ).
18
We say ha an edge up
−→ is inco ec i ¬(µ( )◁pµ(u)), and a e ex uis inco ec i ei he u∈VE e
and all ou going edges a e inco ec o u∈VAdam and he e exis s an inco ec ou going edge.
The pseudocode o he algo i hm is gi en in Algo i hm 1, whe e we le ℓmin deno e he minimal lea
in T.
Algo i hm 2 The alue i e a ion algo i hm.
1: Da a: A pa i y game wi h n e ices p io i ies in [1, d] and a (n,d/2)-uni e sal ee T.
2: o each ∈Vdo
3: µ( )←ℓmin
4: end o
5: epea
6: µ←O(µ)
7: un il µ=O(µ)
8: e u n µ
Theo em 3.9 (Gene ic alue i e a ion algo i hm).Fo all, (n,d/2)-uni e sal ee T, o all pa i y G wi h
n e ices and p io i ies in [1, d], he alue i e a ion algo i hm o e he ee T e u ns he minimal p og ess
measu e µ o G o e T.
The heo em is ue hanks o he Co olla y 3.8, he minimal p og ess measu e yields o a solu ion o pa i y
games: E e wins om i µ( )=⊤.
19
C.C. Aspec s o Pa h-Fo ming Games
4. Mean Payo Games and Ene gy Games
Mean Payo Games (MPGs) and Ene gy Games a e wo impo an classes o in ini e-du a ion games played
on weigh ed g aphs, whe e wo playe s ake u ns o mo e a oken along he edges o he g aph o p oduce
an in ini e pa h.
Mean Payo Games ocus on he long- e m andom ewa d ha a playe can achie e. In an MPG, each
edge has an associa ed weigh , and he goal o E e is o maximize he mean ( andom) o he weigh s along
he in ini e pa h, while Adam aims o minimize i . The alue o a posi ion in he game is de e mined by
he mean payo ha can be gua an eed om ha posi ion, conside ing op imal s a egies o bo h playe s.
Ene gy Games, on he o he hand, in ol e main aining he sum o he weigh s (o ene gy le el) abo e
a ce ain h eshold h oughou he play. Each mo e changes he ene gy le el by he weigh o he chosen
edge, and he objec i e o E e is o ensu e ha he ene gy le el ne e d ops below ze o, while Adam ies
o cause a de ici . The game is won by he E e i hey can keep he ene gy non-nega i e inde ini ely.
The ela ionship be ween MPGs and Ene gy Games lies in hei use o weigh s and hei goals in ol -
ing he accumula ion o hese weigh s. Speci ically, Ene gy Games can be seen as a special case o MPGs
whe e he ocus is on p e en ing he ene gy le el om becoming nega i e a he han op imizing a andom
alue. Addi ionally, sol ing an MPG can o en in ol e echniques ha a e used in Ene gy Games, such as
analyzing he wo s -case accumula ion o weigh s. This close connec ion allows insigh s and algo i hms
om one ype o game o in o m solu ions o he o he .
Lemma 4.1 (Rela ing mean payo games and ene gy objec i es).Le G be a game. Then G sa is ies
MeanPayo −≥0i sa is ies Ene gy <∞
P oo . Le us say ha a cycle in Gis non-nega i e i he sum o i s weigh s is non-nega i e. We conside
he ollowing p ope ies:
(i) Gsa is ies MeanPayo ≥0.
(ii) All cycles in Ga e non-nega i e.
(iii) Gsa is ies Ene gy <∞.
We p o e he implica ions (i)⇒(ii), hen (ii)⇒(iii), and inally (iii)⇒(i).
(i)⇒(ii) is clea .
(ii)⇒(iii). Le us conside an in ini e pa h, and s ike ou all edges in ol ed in a cycle in i . A mos
nedges a e no s icken ou , incu ing a mos −nW in ene gy d op. Since cycles a e non-nega i e, he
lowes le el in a cycle is also lowe bounded by −nW . Hence he ene gy le el o he in ini e pa h is a
mos 2nW .
(iii)⇒(i). Assume ha Gsa is ies Ene gy <∞, his implies ha all pa ial sums a e g ea e han
o equal o a cons an ℓ. This implies ha he means o he pa ial sums a e lowe bounded by ℓ
k, which
con e ges o 0 when kgoes o in ini y. The e o e Gsa is ies MeanPayo ≥0.
20
5. Simple S ochas ic Games
In his sec ion, we del e in o he ans o ma ion o Mean Payo Games in o Simple S ochas ic Games
[10], a c ucial s ep ha enables us o analyze he di icul y o hese games. This educ ion is no me ely a
heo e ical exe cise; i p o ides a undamen al link ha allows he complexi y o Mean Payo Games o be
unde s ood in he b oade con ex o decision-making unde unce ain y.
We begin by ou lining he p ocedu e o con e ing a Mean Payo Game in o a co esponding Simple
S ochas ic Game [10]. This in ol es mapping he s a egies and payo s o he Mean Payo Game on o
he p obabilis ic ou comes o he Simple S ochas ic Game, he eby embedding he de e minis ic na u e o
he o me in o he s ochas ic amewo k o he la e .
Following he educ ion, we ocus on es ablishing he compu a ional complexi y o sol ing Simple S ochas-
ic Games [4]. This analysis is pi o al, as he complexi y esul s de i ed he e apply also o Mean Payo
Games and Pa i y Games, hanks o he educ ions. We explo e a ious algo i hmic app oaches used o
sol e hese games, assessing hei e iciency and p ac icali y in di e en scena ios.
Finally, he implica ions o his educ ion a e p o ound, ex ending he unde s anding o game complex-
i y o o he ela ed games h ough a chain o educ ions. This in e connec ed unde s anding no only
solidi ies ou g asp o game heo y bu also enhances he applicabili y o hese concep s o eal-wo ld
p oblems whe e s a egic decision-making and unce ain y play a signi ican ole.
5.1 Reduc ion MPG o SSG
In ou explo a ion o he compu a ional complexi y o Mean Payo Games (MPGs), we ini ia e he p ocess
wi h a pi o al educ ion o Discoun ed Mean Payo Games (DMPGs). This s a egic s ep se es as a
ounda ional b idge in ou ul ima e goal o ans o ming MPGs in o Simple S ochas ic Games, he eby
acili a ing a smoo he and mo e manageable educ ion p ocess.
The educ ion om MPGs o DMPGs in ol es adjus ing he o iginal payo model o MPGs o include
a discoun ac o , which modi ies he e alua ion o long- e m ewa ds, making he model sensi i e o he
iming o payo s. This addi ion o a discoun ac o in oduces a empo al dimension o he game’s s a -
egy, closely aligning i wi h he p obabilis ic decision-making amewo k o Simple S ochas ic Games.
By i s mapping MPGs o DMPGs, we simpli y he subsequen educ ion o Simple S ochas ic Games.
This simpli ica ion is achie ed because DMPGs, wi h hei emphasis on discoun ed ewa ds, na u ally ap-
p oxima e he expec ed alue calcula ions inhe en in Simple S ochas ic Games. The p esence o a discoun
ac o helps in app oxima ing he p obabilis ic na u e o s ochas ic games, hus p o iding a clea e pa hway
o he subsequen educ ion.
In his sec ion, we will de ail he echnical s eps in ol ed in his ini ial educ ion, analyze he implica-
ions o in oducing a discoun ac o , and discuss how his p epa a o y s ep enhances he easibili y and
cla i y o educing MPGs di ec ly o Simple S ochas ic Games. Th ough his me hodical app oach, we
aim o p o ide a comp ehensi e amewo k ha elucida es he complexi y o hese game ypes in a uni ied
manne .
27

C.C. Aspec s o Pa h-Fo ming Games
Theo em 5.1 (Pu e posi ional de e minacy o MPG).Mean payo objec i es a e uni o mly posi ionally
de e mined o e ini e a enas. The e exis s posi ional s a egies σ∗ o E e and τ∗ o Adam ha a e
op imal s. .
min
τ σ∗,τ(u) = max
σmin
τ σ,τ(u)
and
max
σ σ,τ∗(u) = min
τmax
σ σ,τ(u)
Theo em 5.2 (Discoun ed payo app oxima ion).Le G be a g aph on n e ices, le c :E→ {−W, ... , 0, ... , W}
be a colo ing unc ion on i s edges and le λbe a eal numbe sa is ying 0< λ < 1. I (λ)Gand Ga e
he alues o he discoun ed and mean payo games played on he g aph G s a ing a a ∈V , hen
G−2n(1 −λ)W≤ (λ)G≤ G+ 2n(1 −λ)W.
P oo . Conside he ou come o a discoun ed game in which E e uses a posi ional op imal s a egy o
he non-discoun ed game and Adam uses a posi ional op imal s a egy o coun e he s a egy o E e.
The ou come o such a game clea ly supplies a lowe bound on he alue (λ)Go he discoun ed game.
The play in such a case consis s o a pa h o leng h k, ollowed by a cycle o leng h ℓwhich is epea ed
inde ini ely, whe e 0 ≤k≤n−1, 1 ≤ℓ≤nand k+ℓ≤n.
Assume o he momen ha all he edge weigh s a e non-nega i e. Le w0, ... , wℓ−1be he weigh s
o he edges in he cycle o med. As E e uses an op imal s a egy o he non-discoun ed game we ge
ha Pℓ−1
i=0 wi≥ℓ . The ou come o he discoun ed game is hen a leas
Pℓ−1
i=0 λiwi
Pℓ−1
i=0 λi=w0+λw1+· · · +λℓ−1wℓ−1
1 + λ+· · · +λℓ−1.
Now, conside ing he gene al case, he weigh ed sum can be w i en as:
(1 −λ)λk ℓ−1
X
i=0
wiλi!

∞
X
j=0
λjℓ
=
(1 −λ)λkPℓ−1
i=0 wiλi
1−λℓ≥
(1 −λ)λk+ℓ−1Pℓ−1
i=0 wi
1−λℓ
As ℓ(1 −λ)/(1 −λℓ)>1 and λk+ℓ−1> λn>1−n(1 −λ), his is a leas (1 −n(1 −λ)) G.
We now e u n o he gene al case in which he edge weigh s a e no assumed o be non-nega i e. By
adding W o each weigh , we can make all he weigh s non-nega i e. The alue and ou come o he game
a e changed by exac ly W. Applying he p e ious inequali y o he esul ing non-nega i e game, we ge
ha
( (λ)G+W)≥(1 −n(1 −λ))( G+W),
o equi alen ly ha
(λ)G≥ G−n(1 −λ)( G+W)≥ G−2n(1 −λ)W.
The opposi e inequali y is p o ed in a simila way.
28
In pa icula , i we choose λ= 1 −1/(4n3W), hen i is easy o e i y ha | (λ)G− G| ≤ 1/(2n(n−1)),
and Gcan be ob ained om (λ)Gby ounding o he nea es a ional wi h a denomina o less han n.
We hus ob ain a educ ion om MPGs o discoun ed payo games (DPGs).
We a e inally in a posi ion o desc ibe a educ ion om Discoun ed Payo Games (DPGs) o Simple
S ochas ic Games (SSGs). Recall ha we ha e al eady desc ibed a educ ion om Mean Payo Games
(MPGs) o DPGs. In ansi ioning om DPGs o SSGs, ou ocus shi s o mapping he dynamics o
discoun ed ewa ds in o he p obabilis ic decision-making p ocesses inhe en in SSGs.
The educ ion p ocess in ol es con e ing he payo s uc u e o DPGs, whe e u u e ewa ds a e dis-
coun ed by a ac o diminishing o e ime, in o he p obabilis ic payou s o SSGs. This en ails embedding
he discoun ed alues in o s a e ansi ions o SSGs ha depend on he s a egies and ac ions o playe s,
e ec i ely ansla ing he de e minis ic elemen s o DPGs in o s ochas ic ou comes. The key challenge
he e is o ensu e ha he s a egic dep h and complexi y o decisions in DPGs a e p ese ed wi hin he
s ochas ic amewo k o SSGs.
Be o e we del e in o he ans o ma ion o Mean Payo Games in o Simple S ochas ic Games, i is essen ial
o es ablish he ollowing lemmas. These lemmas p o ide he necessa y se o equa ions o sol ing bo h
Discoun ed Payo Games and Simple S ochas ic Games.
Le 
op be he n- ec o whose i h componen is G( i). We call 
op he alue ec o o G.
Lemma 5.3. The 
op o he discoun ed games played on he g aph G = (VE e,VAdam,E)is he unique
solu ion o he ollowing se o equa ions:
G( i) = (max(i,j)∈E{(1 −λ)wij +λ G( j)}i i ∈VE e ,
min(i,j)∈E{(1 −λ)wij +λ G( j)}i i ∈VAdam.
Lemma 5.4. Le G = (V,E)be a SSG ha hal s wi h p obabili y 1, and le p(u, )deno e he p obabili y
a ached o an edge (u, ) ha emana es om a Rand e ex u. The alues G(u)o he e ices o G
o m he unique solu ion o he ollowing se o equa ions:
G(u) = 








max(u, )∈E{ G( )}i u is a max e ex,
min(u, )∈E{ G( )}i u is a min e ex,
P
(u, )∈E
{p(u, )· G( )}i u is a Rand e ex,
along wi h he condi ions ha (0-sink)=0and (1-sink)=1.
Le G= (VE e,VAdam,E) be a DPG wi h discoun ing ac o λ. I we add a cons an c o all he weigh s o
he game, he alue o he game is inc eased by c. I we mul iply all he weigh s o he game by a cons an
c>0, he alue o he game is mul iplied by c. We can he e o e scale he weigh s so ha hey will all be
a ional numbe s in he in e al [0, 1]. I he o iginal weigh s we e in he ange {−W, ... , 0, ... , W}, hen
he new weigh s will be a ional numbe s wi h denomina o s and nume a o s in he ange {0, 1, ... , 2W}.
Theo em 5.5 (Reducing DMPG o SSG).Sol ing (non-s ochas ic) discoun ed payo games educes in
polynomial ime o sol ing s ochas ic eachabili y games.
29
C.C. Aspec s o Pa h-Fo ming Games
Figu e 10: Simula ing a ansi ion o a discoun ed payo game
P oo . We cons uc in he ollowing way a SSG G′= (V′,E′), wi h he same alue as he scaled DPG
G= (VE e,VAdam,E) wi h discoun ing ac o λ. Each edge (u, ) wi h weigh win Gis eplaced by
he cons uc shown in 10. We le V′=VMax ∪VMin ∪VRand, whe e VMax =VE e ,VMin =VAdam and
VRand is he se o in e media e e ices added. The simple s ochas ic game G′hal s wi h p obabili y 1,
as in each ansi ion he e is a p obabili y o 1 −λo eaching a sink e ex. The alues o he e ices

op o he discoun ed payo game Gsa is y he se o equa ions gi en in Lemma 5.3. The alues o he
e ices 
′
op o he simple s ochas ic game G′sa is y he se o equa ions gi en in Lemma 5.4. These wo
se s o equa ions become iden ical once he in e media e a iables, ha co espond o he in e media e
e ices in oduced by he ans o ma ion desc ibed in 10, a e elimina ed. The e o e he sys ems is he
same 
op =
′
op As his se o equa ions has a unique solu ion, he alues o he wo games a e equal. The
ans o ma ion o G o G′can clea ly be ca ied ou in polynomial ime. This comple es he desc ip ion o
he educ ion.
5.2 Complexi y o SSG is NP ∩coNP
Simple S ochas ic Games (SSGs) ep esen a undamen al class o decision-making models ha a e pi o al
in he domains o heo e ical compu e science and game heo y. This sec ion del es in o he in ica e
compu a ional complexi y o SSGs [4], emphasizing hei challenging na u e and he signi ican ole hey
play in complexi y heo y. SSGs a e a special case o wo-playe , ze o-sum games in ol ing p obabilis ic
ou comes, whe e playe s al e na e mo es in a di ec ed g aph wi h s ochas ic ansi ions.
Fi s we will need o men ion he posi ional de e minancy heo em. I is going o be ensu e us ha
ega ding any s a egy o Adam, E e will be able o ensu e some p obabili y o alue o each he sink and
ice e sa o Adam.
Theo em 5.6 (Pu e posi ional de e minacy o s ochas ic eachabili y games).S ochas ic eachabili y
games a e uni o mly pu ely posi ionally de e mined. The e exis s posi ional s a egies σ∗ o E e and τ∗
o Adam ha a e op imal s. .
min
τ σ∗,τ(u) = max
σmin
τ σ,τ(u)
and
max
σ σ,τ∗(u) = min
τmax
σ σ,τ(u)
Lemma 5.7. Le G be a simple s ochas ic game wi h n e ices ha hal s wi h p obabili y 1. Then he e
is a s a egy σ′o E e such ha , o some op imal s a egy τ′=τ(σ′)o Adam wi h espec o s a egy
σ′, o all e ices i ∈VMax wi h neighbo s j and k,
σ′,τ′(i) = max[ σ′,τ′(j), σ′,τ′(k)].
30
We comple e his sec ion wi h some obse a ions abou op imal s a egies and he ec o 
op . Fo any
SSG G, le IG: [0, 1]n→[0, 1]n(w i en simply as Ii he e is no ambigui y abou which g aph is mean ),
de ined as IG(
x) = 
y om Lemma 5.4 he se o equa ions o SSG, whe e
y(i) =















max{x(j), x(k)}, i iis a max e ex o Gwi h neighbo s j,k,
min{x(j), x(k)}, i iis a min e ex o Gwi h neighbo s j,k,
1
2(x(j) + x(k)), i iis a Rand e ex o Gwi h neighbo s j,k,
0, i i=n−1,
1, i i=n.
We call he se o ec o s 
z o which 
z=I(
z) he solu ions o G. Then om Lemma 5.7, i is s aigh o -
wa d o show ha i Gis a SSG ha hal s wi h p obabili y 1, hen o any pai o op imal s a egies σ′,τ′,
he ec o 
σ′,τ′= ( σ′,τ′(1), ... , σ′,τ′(n)) is a solu ion o G. F om his i ollows ha i Ghas a unique
solu ion, hen 
op =
σ′,τ′ o any pai o op imal s a egies σ′,τ′.
F om now on he e ices will be numbe ed 1, . . . , nand 1 will be he s a e ex, n−1 will be he
0-sink, and nwill be sink-1.
De ini ion 5.8 (S opping Game).Gi en a SSG Gwe de ine S opping Game G′as ollows: G′con ains all
he e ices o Gand o e e y edge eo G,G′con ains a se o Rand e ices {e1,e2, ..., em} ⊆ VRand.
Fo each edge e= (i,j) o G, he ollowing se is included in G′:{(i,e1), (e1,e2), (e2,e3), ..., (em,n−
1), (e1,j), (e2,j), ..., (em,j)}
Figu e 11: S opping Game G′ om SSG G
F om his se up, i should be no ed ha when ollowing a pa h om e ex i, he i s e ex encoun e ed
om he se {1, ... , n}will ei he be e ex jo e ex n−1 (designa ed as he 0-sink). This e ex is
eached wi hin m+1 s eps o ewe . Consequen ly, he e is a p obabili y o 1/2m ha he 0-sink is eached
be o e jwhen s a ed in e ex i. I his 0-sink e ex is eached du ing a andom walk, he game concludes.
This ype o game is e e ed o as a 1/2m-s opping game because a any gi en poin , om any e ex
among {1, ... , n}, he likelihood o concluding he game be o e a i ing a ano he e ex om he se
{1, ... , n−2}is a leas 1/2m.
Fo ha we a e going o use he ollowing lemma ha has been p o ed in [9]:
Lemma 5.9 (Shapley, 1953).I G′is a 1
2m-s opping game co esponding o G hen G′has a unique
solu ion.
31
C.C. Aspec s o Pa h-Fo ming Games
And now he main lemma in o de o p oo he complexi y o SGG in [4]:
Lemma 5.10. The e is a cons an c >0, such ha i G is a SSG wi h n e ices, he alue o G is ≥1
2i
and only i he alue o he co esponding 1
2cn -s opping game is ≥1
2.
Theo em 5.11. The SSG alue p oblem is in NP ∩coNP
P oo . We i s desc ibe a nonde e minis ic Tu ing machine M ha on inpu a SSG Gwi h n e ices,
accep s i and only i Ghas alue >1
2.Mcons uc s he 1
2c-s opping game G′co esponding o G, whe e
cis he cons an o Lemma 5.10, and hen guesses a ec o z∈[0, 1]n, whe e each componen o zis
a ional. I hen e i ies ha he ec o zis a solu ion o G′. I so and i he alue o he s a e ex is
>1
2 hen Maccep s; else M ejec s. F om Lemma 5.10, Maccep s Gi and only i he alue o Gis >1
2.
A simila cons uc ion shows ha he complemen o he SSG alue p oblem is in NP. A nonde e minis ic
Tu ing machine e
M, gi en a SSG Gas inpu , cons uc s he 1
2c-s opping game G′co esponding o G,
whe e cis he cons an o Lemma 5.10 and hen guesses a ec o ez∈[0, 1]n, whe e each componen o ez
is a ional. I hen e i ies ha he ec o ezis a solu ion o G′. I so and i he alue o he s a e ex is
≤1
2 hen e
Maccep s; else e
M ejec s.
32

6. Conclusions
In his hesis, we ha e explo ed he cu en s a e o he a o Uni e sal T ees and G aphs as applied o
Pa i y Games and Mean Payo Games, as well as he educ ions be ween hese games and Simple S ochas-
ic Games.
Fi s ly, in Sec ion 3, we ha e examined he cons uc ion o Uni e sal T ees speci ically o Pa i y Games.
We de ailed he s ep-by-s ep p ocess o building hese ees and ou lined he me hods used o cons uc
he P og ess Measu e necessa y o implemen ing a Value I e a ion algo i hm. This sec ion also includes a
comp ehensi e analysis o he heo e ical ounda ions unde pinning hese cons uc ions, p o iding a solid
g oundwo k o unde s anding hei p ac ical applica ions in sol ing Pa i y Games.
Secondly, in Sec ion 4, we explo ed he ela ionship be ween Ene gy Games and Mean Payo Games.
This included a de ailed examina ion o he educ ion om Pa i y Games o Mean Payo Games (MPG)
and an analysis o he lowe bound o Uni e sal G aphs. We also discussed why he s uc u e used o Pa i y
Games does no yield a quasi-polynomial algo i hm o Mean Payo Games, highligh ing he limi a ions
and challenges inhe en in ex ending hese me hods.
Nex , we examined ha Simple S ochas ic Games (SSG) a e a leas as di icul as Mean Payo Games
(MPG). We p o ed he complexi y o SSG alls wi hin NP ∩coNP, and how his esul , h ough he e-
duc ions, implies he same complexi y o o he games as well. This connec ion unde sco es he b oade
implica ions o SSG complexi y esul s o ela ed game- heo e ic p oblems.
Se e al open ques ions eme ge om his p ojec . One signi ican ques ion is whe he i is possible o
de elop a polynomial, a he han a quasi-polynomial, algo i hm o Pa i y Games. Addi ionally, i emains
o be de e mined i he e exis s any s uc u e ha could lead o a quasi-polynomial o polynomial algo i hm
o Mean Payo Games (MPG). Un il a mo e e icien algo i hm o MPG is disco e ed, i is p ema u e o
asse he exis ence o such an algo i hm o Simple S ochas ic Games (SSG).
33
C.C. Aspec s o Pa h-Fo ming Games
Re e ences
[1] S. A o a and B. Ba ak. Compu a ional Complexi y: A Mode n App oach. Camb idge Uni e si y P ess,
2006.
[2] C is ian S. Calude, Sanjay Jain, Bakhady Khoussaino , Wei Li, and F ank S ephan. Deciding pa i y
games in quasipolynomial ime. In P oceedings o he 49 h Annual ACM SIGACT Symposium on The-
o y o Compu ing, STOC 2017, page 252–263, New Yo k, NY, USA, 2017. Associa ion o Compu ing
Machine y.
[3] An onio Casa es and Pie e Ohlmann. On he ESL algo i hm o sol ing ene gy games. CoRR,
abs/2110.07346, 2021.
[4] Anne Condon. The complexi y o s ochas ic games. In o ma ion and Compu a ion, 96(2):203–224,
1992.
[5] S ephen Cook. The p e sus np p oblem. The millennium p ize p oblems, 02 2001.
[6] Na hana¨el Fijalkow, Pawe l Gaw ychowski, and Pie e Ohlmann. Value I e a ion Using Uni e sal G aphs
and he Complexi y o Mean Payo Games. In Ja ie Espa za and Daniel K ´al’, edi o s, 45 h In e -
na ional Symposium on Ma hema ical Founda ions o Compu e Science (MFCS 2020), olume 170
o Leibniz In e na ional P oceedings in In o ma ics (LIPIcs), pages 34:1–34:15, Dags uhl, Ge many,
2020. Schloss Dags uhl – Leibniz-Zen um ¨u In o ma ik.
[7] Na hana¨el Fijalkow, Na halie Be and, Pa icia Bouye -Deci e, Romain B enguie , A naud Ca ayol,
John Fea nley, Hugo Gimbe , Flo ian Ho n, Rasmus Ibsen-Jensen, Nicolas Ma key, Benjamin Mon-
mege, Pe No o n´y, Mickael Randou , Ocan Sanku , Syl ain Schmi z, Oli ie Se e, and Ma eusz
Skom a. Games on g aphs, 2023.
[8] Ch is os H. Papadimi iou. On ine icien p oo s o exis ence and complexi y classes. In Ja osla
Neˆse il and Mi osla Fiedle , edi o s, Fou h Czechoslo akian Symposium on Combina o ics, G aphs
and Complexi y, olume 51 o Annals o Disc e e Ma hema ics, pages 245–250. Else ie , 1992.
[9] L. S. Shapley. S ochas ic games*. P oceedings o he Na ional Academy o Sciences, 39(10):1095–
1100, 1953.
[10] U i Zwick and Mike Pa e son. The complexi y o mean payo games on g aphs. Theo . Compu . Sci.,
158(1–2):343–359, may 1996.
34