Computational complexity aspects of path-forming games

Title: Computational Complexity Aspects of Path-Forming Games Author: Oriol Saguillo Gonzalez Advisor: Albert Atserias Peri Department: Computer Science Department Academic year: 2024 Master of Science in Advanced Mathematics and Mathematical Engineering Universitat Polit`ecnica de Catalunya Facultat de Matem`atiques i Estad´ıstica Master in Advanced Mathematics and Mathematical Engineering Master’s thesis Computational Complexity Aspects of Path-Forming Games Oriol Saguillo Gonzalez Supervised by Albert Atserias Peri June, 2024 I would like to express my deepest gratitude to my family and friends for their unwavering support and encouragement throughout this journey. A special thanks to my tutor, Albert Atserias, for his invaluable guidance, mentorship and showing me the beauty of Computational Complexity. I am also grateful to Juanjo Rue for his insightful advice during my master’s program, and to my friends at EPFL for their constant support and companionship. Abstract This thesis explores the current State of the Art regarding the computational complexity of various twoplayer infinite games, focusing on Parity Games, Mean Payoff Games, and Simple Stochastic Games. Initially, we delve into the application of universal trees in the realm of Parity Games, that simplified the groundbreaking quasi-polynomial time algorithm developed by Calude, Jain, Khousainov, Li, and Stephan in 2017. This approach has since been a catalyst for the development of similar complexity algorithms in this domain. We overview the work of Fijalkow et al. in 2020 who built on this foundational concept to extend the use of universal objects to design algorithms for Mean Payoff Games. Here, we analyze a family of value iteration algorithms that demonstrate the utility of universal graphs, an appropriate generalization of the universal trees, in optimizing strategies for Mean Payoff Games. Furthermore, we assess the overarching complexity of Simple Stochastic Games, aiming to draw parallels and distinctions in strategies across these game types. Through this study, we aim to enhance the understanding of algorithmic solutions in game theory and provide a consolidated view of the complexity landscape across different game frameworks. Keywords Game Theory, Computational Complexity, Economics and Computation, Algorithmic Game Theory, Intelligent Agents, Graphs, Combinatorics 1 Contents 1 Introduction 3 2 Preliminaries 5 2.1 Basic Definitions ........................................ 5 2.2 Games Definition ....................................... 8 2.3 Value Iteration Algorithms .................................. 11 3 Parity Games 13 3.1 Universal Trees ........................................ 13 3.2 Progress Measure ....................................... 17 3.3 Quasi-polynomial Algorithm .................................. 18 4 Mean Payoff Games and Energy Games 20 4.1 Reduction Parity Games to MPG ............................... 21 4.2 Universal Graphs ........................................ 21 4.3 Upper and Lower Bounds on Universal Graphs ........................ 23 5 Simple Stochastic Games 27 5.1 Reduction MPG to SSG .................................... 27 5.2 Complexity of SSG is NP ∩coNP .............................. 30 6 Conclusions 33 2 1. Introduction The NP vs P problem [5] is one of the most important open questions in computer science and mathematics, dealing with the efficiency of solving problems and the relationship between two classes of problems: P and NP. P (Polynomial Time) represents problems that can be solved quickly by an algorithm. ”Quickly” means in polynomial time, which is a way to measure how the time to solve the problem increases with the size of the input. Examples of problems in P include sorting numbers and finding the shortest path in a graph. NP (Nondeterministic Polynomial Time) represents problems for which a solution can be checked quickly, given the solution. Examples of problems in NP include checking if some subset of a given set of numbers adds up to a target number (Subset Sum) and determining if a Boolean formula can be satisfied (SAT). The main question in the NP vs P problem is whether every problem whose solution can be checked quickly can also be solved quickly. Formally, this asks if P=NP. If P=NP, it would mean that every problem for which a solution can be verified quickly can also be solved quickly. This would have a huge impact on fields like cryptography, optimization, and artificial intelligence, as many currently difficult problems would become easy to solve. On the other hand, if P=NP, it means there are problems in NP that cannot be solved quickly, even though their solutions can be checked quickly. This aligns with our current experience, where many important problems seem to lack efficient solutions. Problems that lie in the intersection of NP and coNP, denoted as NP ∩coNP, are particularly intriguing. These problems can be both verified and refuted in polynomial time, depending on the given answer. One reason these problems are of significant interest is that they provide insight into the structure of NP and coNP. If a problem in NP ∩coNP is also proven to be NP-complete, it would imply that NP equals coNP, a major unresolved question in computational complexity theory. Such a result would have profound implications, suggesting that every problem for which a solution can be verified quickly can also have its negation verified quickly. On the other hand, Game Theory studies the strategic interactions between rational agents, where the decisions of each participant influence the outcomes for all involved. It aims to predict the outcomes of these interactions and to find optimal strategies for each player. The fundamental concepts of Game Theory include players, strategies, payoffs, and games. Players are the decision-makers, strategies are the possible actions they can take, and payoffs are the rewards or outcomes resulting from the chosen strategies. A central concept is the Nash equilibrium, a state where no player can improve their payoff by unilaterally changing their strategy. The intersection of Game Theory and Computational Complexity forms a crucial theoretical foundation with vast implications for various fields, including economics, computer science, and operations research. One of the most remarkable results in this area is the characterization of the complexity class PPAD (Polynomial Parity Arguments on Directed graphs) introduced by Christos Papadimitriou [8]. This class captures the complexity of finding Nash equilibria in games, showing that this problem is PPAD-complete. This means that while Nash equilibria are guaranteed to exist, finding them can be as computationally challenging as the hardest problems in PPAD. The ongoing research at the confluence of these fields continues to provide deep insights and practical tools for tackling complex, strategic decision-making problems. Simple Stochastic Games (SSGs) are a class of two-player games that involve both deterministic and 3 C.C. Aspects of Path-Forming Games probabilistic transitions. These games are played on a finite directed graph, where the players aim to reach designated target states with the highest probability. SSGs are particularly interesting due to their applications in areas such as verification, synthesis, and probabilistic algorithms. The seminal work by Anne Condon [4] established the foundational complexity results for SSGs, showing that the problem of deciding the winner in these games lies in NP ∩coNP. This result indicates that while it is computationally challenging to determine the winner, the problem is both verifiable and refutable in polynomial time, given a correct solution. In our study, we will explore a major breakthrough in the realm of Parity Games [2], which are simpler than Simple Stochastic Games (SSGs) and also belong to the complexity class NP ∩coNP. A breakthrough in this area is the recent development of a quasi-polynomial algorithm for Parity Games. This algorithm, detailed in [7], has significantly advanced our understanding and sparked renewed interest in the field. The existence of such an algorithm raises the intriguing possibility that NP ∩coNP could equal P for these games. Value iteration is the strategy used to obtain this quasi-polynomial algorithm, thanks to the reliance on Universal Trees, a structure that has a quasi-polynomial space. Value iteration algorithms play a pivotal role in solving these games. For energy games, Casares and Ohlmann [3] discussed the ESL algorithm, which highlights the efficiency improvements possible with value iteration techniques. Similarly, Fijalkow et al. [6] investigated value iteration using universal graphs for Mean-Payoff Games (MPGs), demonstrating its impact on the complexity of these games. We will further explore how these structures work for Mean-Payoff Games (MPG) and assess their potential to yield a quasi-polynomial time algorithm, making further progress towards determining whether NP ∩coNP is indeed in P. The complexity of MPGs has been a topic of significant research, with foundational results provided by Zwick and Paterson [10]. Their work laid the groundwork for understanding the computational challenges associated with MPGs, and subsequent research has built on these insights to develop more efficient algorithms. This breakthrough has profound implications for computational complexity, suggesting that efficient algorithms may exist for some class of problems previously thought to be intractable. The development of the quasi-polynomial algorithm for Parity Games has therefore become a focal point in the unlikely quest for most of the scientific community to determine if the problems in the complexity class NP ∩coNP are in P, inspiring further research and exploration in this exciting area of study in the biggest conjecture of the Theoretical Computer Science. 4 Definition 2.24 (Value problem vG(u)).For each of the games described we face the following computational questions, for each of them assume Gbe a Game and for some vertex u∈G: •PG: vG(u) = 1? •MPG: vG(u)>0? •DMPG: vG(u)>0? •SSG: vG(u)>1/2? 2.3 Value Iteration Algorithms Value Iteration algorithms are critical computational tools used to solve a variety of game theory problems, such as Parity Games, Mean Payoff Games, and Simple Stochastic Games, etc. These algorithms are essential because they offer a systematic way to determine optimal strategies in games with complex and infinite states, which are common in these types of games. Theorem 2.25 (Kleene fixed point theorem).Let (X,≤)be a lattice and O:X→X a monotonic operator, then Ohas a least fixed point which is also the least pre-fixed point. Furthermore: •if X is finite the sequence by u0=⊥and uk+1 =O(uk)is stationary and its limit is the least fixed point of O. •if Opreserves suprema then the least fixed point of Ois sup{Ok(⊥) : k∈N}. Let us consider a lattice(X,≤): the binary relation ≤is a partial order, and every pair of elements has a least upper bound and a greatest lower bound. ⊥for the last element in Xand ⊤for the greatest element. An operator O:X→Xis montonic if for all x,y∈Xs.t. x≤ywe have O(x)≤O(y), and preserves suprema if O(supnxn) = supnO(xn) for all increasing sequences (xn)n∈N.xis a pre-fixed point if O(x)≤x and post-fixed if O(x)≥x. Let us consider a game G. We let FVdenote the set of functions V→Y, it is a lattice when equipped with the componentwise (partial) order induced by Y: we say that µ≤µ′if for all vertices vwe have µ(v)≤µ′(v). The main ingredient is an operator OG:FV→FV. The intent is to obtain the function vGas a fixed point of the operator OG, using the two different approaches for fixed points we introduced above. Whenever Gis clear from the context, we simply write Oinstead of OG. Property 2 (Fixed point through monotonicity): For all games G, the operator OGis monotonic, and vGis the least fixed point of OG. Remark 5 (Greatest versus least fixed point). Whenever technically convenient or more intuitive, we will obtain the value function as the greatest fixed point of OG. For value iteration algorithms, only small adjustments are necessary. This will be different for strategy improvement algorithms, in the next section. Theorem 4 further states that vGis the limit of the sequence (OG(⊥))k k∈N. The pseudocode is given in 1. 11 C.C. Aspects of Path-Forming Games Algorithm 1 A generic value iteration algorithm based on fixed point through monotonicity – naive version. 1: for v∈Vdo 2: µ(v)←⊥ 3: end for 4: repeat 5: µ←OG(µ) 6: until µ=OG(µ) 7: return µ Theorem 2.26 (Generic value iteration algorithm through monotonicity).Assume Property 2 (fixed point through monotonicity) and that Y is finite. Then the generic value iteration algorithm outputs vGwithin at most n · |Y|iterations. Proof. If Yis a finite lattice then so is FV. For each v, the sequence (Ok(µ)(v))k∈Nis non-decreasing, so it can be strictly decreased at most |Y|times. At each iteration the value of at least one vertex is strictly decreased. Hence there are at most n· |Y|iterations. If Yis not finite then the sequence (OG(µ)k)k∈Nconverges towards vGbut further analysis is required to evaluate the convergence speed. 12 3. Parity Games To solve parity games using a quasi-polynomial algorithm, we must utilize a value iteration algorithm. However, before delving into the algorithm, it is essential to introduce some key concepts that will help us establish the process and correctness of the algorithm. To understand the quasi-polynomial algorithm proposed in [2], we need to first define some fundamental data structures, namely Universal Trees and Progress Measures. These concepts are crucial for quantifying the player’s progress towards achieving parity. The main reference for this chapter can be found in [7]. 3.1 Universal Trees The trees we consider have three properties: they are rooted, every leaf has the same depth, and the children of a node are totally ordered. Formally, a tree of height 0 is a leaf, and a tree tof height h+ 1 is an ordered list [t1, ... , tk] of subtrees each of height h. We consider two parameters for trees: the height, and the size which is defined to be the number of leaves. We say that a tree tembeds into another tree Tif: •either both are leaves, •or let t= [t1, ... , tk] and T= [T1, ... , Tk], there exist i1<· · · <iksuch that for all j∈[1, k], we have that tjembeds into Tij. Another possible definition and perspective for this embedding is to consider it as an isomorphism of a smaller tree within a larger tree. Formally, let Tand T′be trees, with Tbeing the smaller tree and T′the larger tree. We say that Tis embedded in T′if there exists an injective homomorphism ϕ:T→T′such that for every vertex v∈T,ϕ(v) and its corresponding edges in Tpreserve the adjacency relationships in T′. This embedding maintains the structural properties of Twithin T′, effectively mapping Tinto T′. Definition 3.1. A tree is (n, h)-universal tree if it embeds all trees of size n and height h. Figure 5: On the left, a tree of height h= 2, which is the smallest (5, 2)-universal tree: it has size 11 (meaning it has 11 leaves). On the right, a tree of size 5 and one possible embedding to the universal tree. [7] An important aspect of these trees is their construction, which is crucial for demonstrating how to model a parity game using the lattice from the first level of the universal tree. Additionally, it is essential to 13 C.C. Aspects of Path-Forming Games note that a quasi-polynomial algorithm can be achieved through the construction of the Universal Tree for Parity Games. The complexity of Value Iteration algorithms depends on the structure being iterated over and its size for the number of possible states during the algorithm’s execution. Theorem 3.2. There exists an (n,h)-universal tree with size f (n,h)satisfying the following: •f(n,h) = f(n,h−1) + f(⌊n/2⌋,h) + f(n−1− ⌊n/2⌋,h) •f(n, 0) = 1 •f(0, h) = 0 An upper bound is given by f(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 general, and polynomial if h =O(log2(n)). Proof. In order to prove that we can generate an (n,h)-universal tree with size f(n,h) we are going to build the tree with the following construction: •Tleft be a (⌊n/2⌋,h)-universal tree. •Tmiddle be a (n,h−1)-universal tree. •Tright be a (n−1− ⌊n/2⌋,h)-universal tree. We are going to merge with the same root Tleft and Tright and insert between them a child, which is Tmiddle . Let Tbe the (n,h)-tree constructed this way. We prove that Tis (n,h)-universal by induction on h: •For the base case h= 0, Tis a single leaf and n= 1, which is clearly (1, 0)-universal. •For the inductive case, assume a h>0 and fix an (n,h)-tree t= [t1, ... , tk]. We want to show that Tembeds t. The main question is how can we cut this tree tand have the maps to Tright,Tmiddle and Tleft. We know that the sum is at most n, if not we cannot embed that tree tiin the universal one. Therefore, there exists a unique p∈[1, k] s. t. the sum of the leafs from t1to tp−1≤ ⌊n/2⌋ and the rest is <⌊n/2⌋. Because we know that Tmiddle has a size of n, then for the pselected we have that the total leafs of tp+1 to tkis ≤n−1− ⌊n/2⌋. To embed t into T we proceed as follows: –the tree [t1, ... , tp−1] has at most ⌊n/2⌋leaves, so it embeds into Tleft by induction hypothesis; –the tree tphas height h−1 and at most nleaves, so it embeds into Tmiddle by induction hypothesis; –the tree [tp+1, ... , tk] has at most n− ⌊n/2⌋leaves, so it embeds into Tright by induction hypothesis. 14 Ordering the leaves Now we will need to define an order to the leafs in order to have a lattice to compare different leafs in the tree. The main idea or concept that we need to extract is how can we say if we are in a post-fixed or pre-fixed point. This is going to be a key step towards the Value Iteration algorithm. Let’s consider a tree tof height h, and define d= 2h. A leaf of tis given by a list of directions indexed by odd numbers p∈[1, d] downwards (e.g. d= 10 a leaf is given by (D9,D7,D5,D3,D1)). We write Ytfor the set of internal nodes and leaves of tand ≤for the lexicographic order on Yt. The interpretation is that if l≤l′, two nodes, if and only if lis to the left of l′. The set of relations ◁pover Ytfor each p∈[1, d]. For a leaf l= (Dd−1, ..., D1) we write l≥pfor the tuple (Dd−1, ..., Dp) for odd pand (Dd−1, ..., Dp+1) for even numbers, which we call the p-truncated branch of l. •For podd, we say that l◁pl′if l≥p<l′ ≥p •For peven, we say that l◁pl′if l≥p≤l′ ≥p Figure 6: Illustration of the relations ◁p. In red, we see that ℓ2◁1ℓ3;ℓ2◁2ℓ3;ℓ3◁2ℓ2;ℓ1◁3ℓ2; ℓ1◁2ℓ2. Lemma 3.3. The relations ◁pfor [1, d]induced by a tree t satisfies the following properties: •◁dis the full relation, i.e. ∀b,b′(b◁db′) •l◁pl′∧l′◁ql′′ ⇒l◁max(p,q)l′′ •◁pis non-reflexive if p is odd. •◁1is total. •for d <p even we have l ◁pl′⇐⇒ ¬(l′◁p+1 l) With the order properties we have from the universal trees we can rephrase the notion of embedding between trees with the ordering of leaves as follows: 15 C.C. Aspects of Path-Forming Games Lemma 3.4. (Equivalence between embedding and orders). Let t,T be two trees of heights h and d = 2h. Then t embeds into T if and only if ∃µ:Yt→YTs.t. for all leaves l,l′∈t, and all p ∈[1, d]: l◁t pl′⇒µ(l)◁T pµ(l′) This lemma is going to be the most important one, the main usage is how can we model from a Parity Game Graph the structure of a Universal Tree. Therefore, we will be able to obtain a Universal Graph for all the Parity Games and the graph structure they are underlined. In order to prove the previous lemma we can use induction on the following lemma for every leaf in the tree. Lemma 3.5. Supose that for every intern node u of t, exists an intern node u′of T such that depth(u) = depth(u′). Let L be the set of leafs under u in t. Then, µ(L)are leaves under u′in T. Proof. We proceed by induction on the height of the subtree rooted at each internal node uin t. Base Case: For the leaves of t, the lemma holds trivially since each leaf lin tmaps directly to a corresponding leaf µ(l) in Tby definition of the embedding function µ. This satisfies the condition that the depth of a leaf in tis equal to the depth of its image in T. Inductive Step: Assume that for all internal nodes vof tat depth k<h, there exists a corresponding internal node v′in Tsuch that: 1. depth(v) = depth(v′), 2. The set of leaves Lvunder vin tmaps to the set of leaves under v′in Tvia µ. Now consider an internal node uin tat depth k+ 1. By the inductive hypothesis, for each child vof u (which is at depth k), there exists a corresponding node v′in Tsuch that: 1. depth(v) = depth(v′), 2. The set of leaves under vmaps to the set of leaves under v′. Since uis the parent of nodes like vat depth k+ 1, and uaggregates the leaves under its children v, we need to find a node u′in Tthat: 1. Is at the same depth as u(depth(u) = k+ 1), 2. Aggregates the leaves under its corresponding children v′. Such a node u′exists because tembeds into T, implying there is a structural preservation of parent-child relationships and leaf aggregations under these relationships. By definition of embedding, the internal node u′in Twill also respect the hierarchical structure such that µmaps the leaves under uto the leaves under u′. Hence, µ(Lu)⊂Lu′, satisfying the lemma’s requirements. 16 3.2 Progress Measure In order to quantify from a tree twhich states are better than other to achieve the parity, we will need a lattice (Yt,≤) and a monotonic function δt:Yt×[1, d]→Yt. The set Ytis going to be the leaves of twith an extra element ⊤defined as ℓ∈Yt, and ≤is the lexicographic order on leaves with ⊤as the greatest element. δt(ℓ,p) = min ≤{ℓ′∈Yt|ℓ < ℓ′≤p}. This in turn induces a monotonic operator Ot:FV→FVdefined by: OT(µ)(u) = (min{δt(µ(u), p)|up −→ v∈E}if u∈VEve, max{δt(µ(u), p)|up −→ v∈E}if u∈VAdam, where VEve and VAdam are vertex sets in the parity game. Let Gbe a parity game, a progress measure is a function µ:V→Yt, which is a pre-fixed point: O(µ)≤µ. Unfolding the definitions, this means that for all vertices u, we have: ∃up −→ v∈E:δt(µ(u), p)≤µ(u) if u∈VEve, ∀up −→ v∈E,δt(µ(u), p)≤µ(u) if u∈VAdam. Lemma 3.6 (Fundamental Lemma for progress measures over graphs).Let G be a game and v a vertex. Then G satisfies parity from v iff there exists a tree t and a progress measure µ:V→Yts.t. µ(v)=⊤. Proof. Let us assume that there exists a tree tand a progress measure µ:V→Ytsuch that µ(v)=⊤ and for all edges up −→ v∈Ewe have µ(v)◁pµ(u). To show that Gsatisfies parity from v, we show that any cycle reachable from vis even. Let us consider such a cycle: v1 p1 −→ v2 p2 −→ v3· · · vk pk −→ v1. Since the cycle is reachable from vand µ(v)=⊤, this implies that µ(vi)=⊥for i∈[1, k]. Let us assume towards contradiction that its maximal priority is odd, and without loss of generality it is p1. Applying our hypothesis to each edge of the cycle, we have µ(v1)◁pkµ(vk)◁pk−1· · · ◁p2µ(v2)◁p1µ(v1). The second item of Lemma 3.6 implies that µ(v1)◁p1µ(v1), which contradicts the third item since ◁p1 is non-reflexive given that p1is odd. Let us now prove the converse implication. We prove the following property by induction on the number of priorities: for all graphs satisfying parity (without the usual assumption that every vertex has an outgoing edge), there exists a tree tand a progress measure µ:V→Ytsuch that µ(v)=⊤for all vertices v∈V. Let Gbe a graph satisfying parity. Without loss of generality, the largest priority din the graph is even. Let us define G′as the graph obtained from Gby removing all edges with priority d. We consider 17 C.C. Aspects of Path-Forming Games its decomposition into strongly connected components: let G1, ... , Gkdenote the strongly connected components of G′, numbered so that for any edge u→v∈E(G′), if u∈V(Gi) then v∈V(Gj) for j≥i. A stronger property holds for edges ud−1 −−→ v∈E(G′): if u∈V(Gi) then v∈V(Gj) for j>i. Indeed, if v∈V(Gi) then we could form a cycle in G′whose largest priority is d−1, a contradiction. Hence each Gihas priorities in [1, d−2], and being a subgraph of Git satisfies parity. By induction hypothesis, there exists a tree tiand a progress measure µi:V(Gi)→Ytisuch that µi(v)=⊤for all vertices v∈V(Gi). Let us define t= [t1, ... , tk], and the function µ:V(G)→Ytby µ(v) = µi(v) if v∈V(Gi). We claim that µis a progress measure: let us consider an edge up −→ v∈E(G), then •if p=d, then µ(v)◁dµ(u) because ◁dis the full relation; •if p=d−1, then µ(v)◁d−1µ(u) because u∈V(Gi) and v∈V(Gj) for j>i; •If p<d−1, then µ(v)◁pµ(u). Indeed u∈V(Gi) and v∈V(Gj) for j≥i, so either j=iand this follows from the fact that µiis a progress measure, or j>iand we have µ(v)◁d−1µ(u) so a fortiori µ(v)◁pµ(u). Theorem 3.7 (Fundamental theorem for progress measures).Let G be a game and v a vertex. Then Eve wins from v iff there exists a tree t and a progress measure µ:V→Yts.t. µ(v)=⊤. Proof. Assume that Eve wins from vand let σbe a positional strategy. The parity graph G[σ] satisfies parity from v, so thanks to Lemma 3.6 there exists a tree tand a function µ:V→Ytsuch that µ(v)=⊤ and for all edges up −→ v∈Ewe have µ(v)◁pµ(u). We remark that µ:V→Ytis actually a progress measure: the condition for u∈VEve is ensured by the edge σ(u), and the condition for v∈VAdam by assumption on µ. Corollary 3.8 (Fundamental corollary for progress measures).Let G be a game with n vertices and priorities in [1, d], and v a vertex. Let T be a (n,d/2)-universal tree. Then, Eve wins from v iff there exists a progress measure µ:V→YTs.t. µ=⊤. Proof. Assume that Eve wins from v, thanks to Theorem 3.7 there exists a tree tand a progress measure µ:V→Ytsuch that µ(v)=⊤. Since Tis (n,d/2)-universal and thas at most nleaves, tembeds into T, which thanks to Fact 14 implies that there exists µ′:Yt→YTrespecting the relations ◁. We extend it to µ′:Yt→YTby µ′(⊥) = ⊥. Then the composition µ′◦µ:V→YTis a progress measure such that (µ′◦µ)(v)=⊥. The converse implication is a direct consequence of Theorem 3.7. 3.3 Quasi-polynomial Algorithm Let us fix Tan (n,d/2)-universal tree. It induces both a lattice (YT,≤) and a monotonic function δT:YT×[1, d]→YT, which in turn induces a monotonic operator OT:FV→FV. Since Tis fixed we do not specify the subscript Tfor all these objects. The last step is to construct an algorithm returning the minimal progress measure relying on Kleene’s fixed point theorem (stated as Theorem 2.28 ). 18 We say that an edge up −→ vis incorrect if ¬(µ(v)◁pµ(u)), and a vertex uis incorrect if either u∈VEve and all outgoing edges are incorrect or u∈VAdam and there exists an incorrect outgoing edge. The pseudocode for the algorithm is given in Algorithm 1, where we let ℓmin denote the minimal leaf in T. Algorithm 2 The value iteration algorithm. 1: Data: A parity game with nvertices priorities in [1, d] and a (n,d/2)-universal tree T. 2: for each v∈Vdo 3: µ(v)←ℓmin 4: end for 5: repeat 6: µ←O(µ) 7: until µ=O(µ) 8: return µ Theorem 3.9 (Generic value iteration algorithm).For all, (n,d/2)-universal tree T, for all parity G with n vertices and priorities in [1, d], the value iteration algorithm over the tree T returns the minimal progress measure µfor G over T. The theorem is true thanks to the Corollary 3.8, the minimal progress measure yields to a solution for parity games: Eve wins from viff µ(v)=⊤. 19 C.C. Aspects of Path-Forming Games 4. Mean Payoff Games and Energy Games Mean Payoff Games (MPGs) and Energy Games are two important classes of infinite-duration games played on weighted graphs, where two players take turns to move a token along the edges of the graph to produce an infinite path. Mean Payoff Games focus on the long-term random reward that a player can achieve. In an MPG, each edge has an associated weight, and the goal of Eve is to maximize the mean (random) of the weights along the infinite path, while Adam aims to minimize it. The value of a position in the game is determined by the mean payoff that can be guaranteed from that position, considering optimal strategies for both players. Energy Games, on the other hand, involve maintaining the sum of the weights (or energy level) above a certain threshold throughout the play. Each move changes the energy level by the weight of the chosen edge, and the objective of Eve is to ensure that the energy level never drops below zero, while Adam tries to cause a deficit. The game is won by the Eve if they can keep the energy non-negative indefinitely. The relationship between MPGs and Energy Games lies in their use of weights and their goals involving the accumulation of these weights. Specifically, Energy Games can be seen as a special case of MPGs where the focus is on preventing the energy level from becoming negative rather than optimizing a random value. Additionally, solving an MPG can often involve techniques that are used in Energy Games, such as analyzing the worst-case accumulation of weights. This close connection allows insights and algorithms from one type of game to inform solutions for the other. Lemma 4.1 (Relating mean payoff games and energy objectives).Let G be a game. Then G satisfies MeanPayoff −≥0iff satisfies Energy <∞ Proof. Let us say that a cycle in Gis non-negative if the sum of its weights is non-negative. We consider the following properties: (i) Gsatisfies MeanPayoff ≥0. (ii) All cycles in Gare non-negative. (iii) Gsatisfies Energy <∞. We prove the implications (i)⇒(ii), then (ii)⇒(iii), and finally (iii)⇒(i). (i)⇒(ii) is clear. (ii)⇒(iii). Let us consider an infinite path, and strike out all edges involved in a cycle in it. At most nedges are not stricken out, incurring at most −nW in energy drop. Since cycles are non-negative, the lowest level in a cycle is also lower bounded by −nW . Hence the energy level of the infinite path is at most 2nW . (iii)⇒(i). Assume that Gsatisfies Energy <∞, this implies that all partial sums are greater than or equal to a constant ℓ. This implies that the means of the partial sums are lower bounded by ℓ k, which converges to 0 when kgoes to infinity. Therefore Gsatisfies MeanPayoff ≥0. 20 5. Simple Stochastic Games In this section, we delve into the transformation of Mean Payoff Games into Simple Stochastic Games [10], a crucial step that enables us to analyze the difficulty of these games. This reduction is not merely a theoretical exercise; it provides a fundamental link that allows the complexity of Mean Payoff Games to be understood in the broader context of decision-making under uncertainty. We begin by outlining the procedure for converting a Mean Payoff Game into a corresponding Simple Stochastic Game [10]. This involves mapping the strategies and payoffs of the Mean Payoff Game onto the probabilistic outcomes of the Simple Stochastic Game, thereby embedding the deterministic nature of the former into the stochastic framework of the latter. Following the reduction, we focus on establishing the computational complexity of solving Simple Stochastic Games [4]. This analysis is pivotal, as the complexity results derived here apply also to Mean Payoff Games and Parity Games, thanks to the reductions. We explore various algorithmic approaches used to solve these games, assessing their efficiency and practicality in different scenarios. Finally, the implications of this reduction are profound, extending the understanding of game complexity to other related games through a chain of reductions. This interconnected understanding not only solidifies our grasp of game theory but also enhances the applicability of these concepts to real-world problems where strategic decision-making and uncertainty play a significant role. 5.1 Reduction MPG to SSG In our exploration of the computational complexity of Mean Payoff Games (MPGs), we initiate the process with a pivotal reduction to Discounted Mean Payoff Games (DMPGs). This strategic step serves as a foundational bridge in our ultimate goal of transforming MPGs into Simple Stochastic Games, thereby facilitating a smoother and more manageable reduction process. The reduction from MPGs to DMPGs involves adjusting the original payoff model of MPGs to include a discount factor, which modifies the evaluation of long-term rewards, making the model sensitive to the timing of payoffs. This addition of a discount factor introduces a temporal dimension to the game’s strategy, closely aligning it with the probabilistic decision-making framework of Simple Stochastic Games. By first mapping MPGs to DMPGs, we simplify the subsequent reduction to Simple Stochastic Games. This simplification is achieved because DMPGs, with their emphasis on discounted rewards, naturally approximate the expected value calculations inherent in Simple Stochastic Games. The presence of a discount factor helps in approximating the probabilistic nature of stochastic games, thus providing a clearer pathway for the subsequent reduction. In this section, we will detail the technical steps involved in this initial reduction, analyze the implications of introducing a discount factor, and discuss how this preparatory step enhances the feasibility and clarity of reducing MPGs directly to Simple Stochastic Games. Through this methodical approach, we aim to provide a comprehensive framework that elucidates the complexity of these game types in a unified manner. 27 C.C. Aspects of Path-Forming Games Theorem 5.1 (Pure positional determinacy for MPG).Mean payoff objectives are uniformly positionally determined over finite arenas. There exists positional strategies σ∗for Eve and τ∗for Adam that are optimal s.t. min τvσ∗,τ(u) = max σmin τvσ,τ(u) and max σvσ,τ∗(u) = min τmax σvσ,τ(u) Theorem 5.2 (Discounted payoff approximation).Let G be a graph on n vertices, let c :E→ {−W, ... , 0, ... , W} be a coloring function on its edges and let λbe a real number satisfying 0< λ < 1. If v(λ)Gand vGare the values of the discounted and mean payoff games played on the graph G starting at a ∈V , then vG−2n(1 −λ)W≤v(λ)G≤vG+ 2n(1 −λ)W. Proof. Consider the outcome of a discounted game in which Eve uses a positional optimal strategy for the non-discounted game and Adam uses a positional optimal strategy to counter the strategy of Eve. The outcome of such a game clearly supplies a lower bound on the value v(λ)Gof the discounted game. The play in such a case consists of a path of length k, followed by a cycle of length ℓwhich is repeated indefinitely, where 0 ≤k≤n−1, 1 ≤ℓ≤nand k+ℓ≤n. Assume for the moment that all the edge weights are non-negative. Let w0, ... , wℓ−1be the weights of the edges in the cycle formed. As Eve uses an optimal strategy for the non-discounted game we get that Pℓ−1 i=0 wi≥ℓv. The outcome of the discounted game is then at least Pℓ−1 i=0 λiwi Pℓ−1 i=0 λi=w0+λw1+· · · +λℓ−1wℓ−1 1 + λ+· · · +λℓ−1. Now, considering the general case, the weighted sum can be written 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 −λ), this is at least (1 −n(1 −λ))vG. We now return to the general case in which the edge weights are not assumed to be non-negative. By adding Wto each weight, we can make all the weights non-negative. The value and outcome of the game are changed by exactly W. Applying the previous inequality to the resulting non-negative game, we get that (v(λ)G+W)≥(1 −n(1 −λ))(vG+W), or equivalently that v(λ)G≥vG−n(1 −λ)(vG+W)≥vG−2n(1 −λ)W. The opposite inequality is proved in a similar way. 28 In particular, if we choose λ= 1 −1/(4n3W), then it is easy to verify that |v(λ)G−vG| ≤ 1/(2n(n−1)), and vGcan be obtained from v(λ)Gby rounding to the nearest rational with a denominator less than n. We thus obtain a reduction from MPGs to discounted payoff games (DPGs). We are finally in a position to describe a reduction from Discounted Payoff Games (DPGs) to Simple Stochastic Games (SSGs). Recall that we have already described a reduction from Mean Payoff Games (MPGs) to DPGs. In transitioning from DPGs to SSGs, our focus shifts to mapping the dynamics of discounted rewards into the probabilistic decision-making processes inherent in SSGs. The reduction process involves converting the payoff structure of DPGs, where future rewards are discounted by a factor diminishing over time, into the probabilistic payouts of SSGs. This entails embedding the discounted values into state transitions of SSGs that depend on the strategies and actions of players, effectively translating the deterministic elements of DPGs into stochastic outcomes. The key challenge here is to ensure that the strategic depth and complexity of decisions in DPGs are preserved within the stochastic framework of SSGs. Before we delve into the transformation of Mean Payoff Games into Simple Stochastic Games, it is essential to establish the following lemmas. These lemmas provide the necessary set of equations for solving both Discounted Payoff Games and Simple Stochastic Games. Let  vopt be the n-vector whose ith component is vG(vi). We call  vopt the value vector of G. Lemma 5.3. The  vopt of the discounted games played on the graph G = (VEve,VAdam,E)is the unique solution of the following set of equations: vG(vi) = (max(i,j)∈E{(1 −λ)wij +λvG(vj)}if i ∈VEve , min(i,j)∈E{(1 −λ)wij +λvG(vj)}if i ∈VAdam. Lemma 5.4. Let G = (V,E)be a SSG that halts with probability 1, and let p(u,v)denote the probability attached to an edge (u,v)that emanates from a Rand vertex u. The values vG(u)of the vertices of G form the unique solution to the following set of equations: vG(u) =          max(u,v)∈E{vG(v)}if u is a max vertex, min(u,v)∈E{vG(v)}if u is a min vertex, P (u,v)∈E {p(u,v)·vG(v)}if u is a Rand vertex, along with the conditions that v(0-sink)=0and v(1-sink)=1. Let G= (VEve,VAdam,E) be a DPG with discounting factor λ. If we add a constant cto all the weights of the game, the value of the game is increased by c. If we multiply all the weights of the game by a constant c>0, the value of the game is multiplied by c. We can therefore scale the weights so that they will all be rational numbers in the interval [0, 1]. If the original weights were in the range {−W, ... , 0, ... , W}, then the new weights will be rational numbers with denominators and numerators in the range {0, 1, ... , 2W}. Theorem 5.5 (Reducing DMPG to SSG).Solving (non-stochastic) discounted payoff games reduces in polynomial time to solving stochastic reachability games. 29 C.C. Aspects of Path-Forming Games Figure 10: Simulating a transition of a discounted payoff game Proof. We construct in the following way a SSG G′= (V′,E′), with the same value as the scaled DPG G= (VEve,VAdam,E) with discounting factor λ. Each edge (u,v) with weight win Gis replaced by the construct shown in 10. We let V′=VMax ∪VMin ∪VRand, where VMax =VEve ,VMin =VAdam and VRand is the set of intermediate vertices added. The simple stochastic game G′halts with probability 1, as in each transition there is a probability of 1 −λof reaching a sink vertex. The values of the vertices  vopt of the discounted payoff game Gsatisfy the set of equations given in Lemma 5.3. The values of the vertices  v′ opt of the simple stochastic game G′satisfy the set of equations given in Lemma 5.4. These two sets of equations become identical once the intermediate variables, that correspond to the intermediate vertices introduced by the transformation described in 10, are eliminated. Therefore the systems is the same  vopt = v′ opt As this set of equations has a unique solution, the values of the two games are equal. The transformation of Gto G′can clearly be carried out in polynomial time. This completes the description of the reduction. 5.2 Complexity of SSG is NP ∩coNP Simple Stochastic Games (SSGs) represent a fundamental class of decision-making models that are pivotal in the domains of theoretical computer science and game theory. This section delves into the intricate computational complexity of SSGs [4], emphasizing their challenging nature and the significant role they play in complexity theory. SSGs are a special case of two-player, zero-sum games involving probabilistic outcomes, where players alternate moves in a directed graph with stochastic transitions. First we will need to mention the positional determinancy theorem. It is going to be ensure us that regarding any strategy of Adam, Eve will be able to ensure some probability or value to reach the sink and vice versa for Adam. Theorem 5.6 (Pure positional determinacy for stochastic reachability games).Stochastic reachability games are uniformly purely positionally determined. There exists positional strategies σ∗for Eve and τ∗ for Adam that are optimal s.t. min τvσ∗,τ(u) = max σmin τvσ,τ(u) and max σvσ,τ∗(u) = min τmax σvσ,τ(u) Lemma 5.7. Let G be a simple stochastic game with n vertices that halts with probability 1. Then there is a strategy σ′of Eve such that, for some optimal strategy τ′=τ(σ′)of Adam with respect to strategy σ′, for all vertices i ∈VMax with neighbors j and k, vσ′,τ′(i) = max[vσ′,τ′(j), vσ′,τ′(k)]. 30 We complete this section with some observations about optimal strategies and the vector  vopt. For any SSG G, let IG: [0, 1]n→[0, 1]n(written simply as Iif there is no ambiguity about which graph is meant), defined as IG( x) =  yfrom Lemma 5.4 the set of equations for SSG, where y(i) =                max{x(j), x(k)}, if iis a max vertex of Gwith neighbors j,k, min{x(j), x(k)}, if iis a min vertex of Gwith neighbors j,k, 1 2(x(j) + x(k)), if iis a Rand vertex of Gwith neighbors j,k, 0, if i=n−1, 1, if i=n. We call the set of vectors  zfor which  z=I( z) the solutions of G. Then from Lemma 5.7, it is straightforward to show that if Gis a SSG that halts with probability 1, then for any pair of optimal strategies σ′,τ′, the vector  vσ′,τ′= (vσ′,τ′(1), ... , vσ′,τ′(n)) is a solution of G. From this it follows that if Ghas a unique solution, then  vopt = vσ′,τ′for any pair of optimal strategies σ′,τ′. From now on the vertices will be numbered 1, . . . , nand 1 will be the start vertex, n−1 will be the 0-sink, and nwill be sink-1. Definition 5.8 (Stopping Game).Given a SSG Gwe define Stopping Game G′as follows: G′contains all the vertices of Gand for every edge eof G,G′contains a set of Rand vertices {e1,e2, ..., em} ⊆ VRand. For each edge e= (i,j) of G, the following set is included in G′:{(i,e1), (e1,e2), (e2,e3), ..., (em,n− 1), (e1,j), (e2,j), ..., (em,j)} Figure 11: Stopping Game G′from SSG G From this setup, it should be noted that when following a path from vertex i, the first vertex encountered from the set {1, ... , n}will either be vertex jor vertex n−1 (designated as the 0-sink). This vertex is reached within m+1 steps or fewer. Consequently, there is a probability of 1/2mthat the 0-sink is reached before jwhen started in vertex i. If this 0-sink vertex is reached during a random walk, the game concludes. This type of game is referred to as a 1/2m-stopping game because at any given point, from any vertex among {1, ... , n}, the likelihood of concluding the game before arriving at another vertex from the set {1, ... , n−2}is at least 1/2m. For that we are going to use the following lemma that has been proved in [9]: Lemma 5.9 (Shapley, 1953).If G′is a 1 2m-stopping game corresponding to G then G′has a unique solution. 31 C.C. Aspects of Path-Forming Games And now the main lemma in order to proof the complexity of SGG in [4]: Lemma 5.10. There is a constant c >0, such that if G is a SSG with n vertices, the value of G is ≥1 2if and only if the value of the corresponding 1 2cn -stopping game is ≥1 2. Theorem 5.11. The SSG value problem is in NP ∩coNP Proof. We first describe a nondeterministic Turing machine Mthat on input a SSG Gwith nvertices, accepts if and only if Ghas value >1 2.Mconstructs the 1 2c-stopping game G′corresponding to G, where cis the constant of Lemma 5.10, and then guesses a vector z∈[0, 1]n, where each component of zis rational. It then verifies that the vector zis a solution of G′. If so and if the value of the start vertex is >1 2then Maccepts; else Mrejects. From Lemma 5.10, Maccepts Gif and only if the value of Gis >1 2. A similar construction shows that the complement of the SSG value problem is in NP. A nondeterministic Turing machine e M, given a SSG Gas input, constructs the 1 2c-stopping game G′corresponding to G, where cis the constant of Lemma 5.10 and then guesses a vector ez∈[0, 1]n, where each component of ez is rational. It then verifies that the vector ezis a solution of G′. If so and if the value of the start vertex is ≤1 2then e Maccepts; else e Mrejects. 32 6. Conclusions In this thesis, we have explored the current state of the art for Universal Trees and Graphs as applied to Parity Games and Mean Payoff Games, as well as the reductions between these games and Simple Stochastic Games. Firstly, in Section 3, we have examined the construction of Universal Trees specifically for Parity Games. We detailed the step-by-step process of building these trees and outlined the methods used to construct the Progress Measure necessary for implementing a Value Iteration algorithm. This section also includes a comprehensive analysis of the theoretical foundations underpinning these constructions, providing a solid groundwork for understanding their practical applications in solving Parity Games. Secondly, in Section 4, we explored the relationship between Energy Games and Mean Payoff Games. This included a detailed examination of the reduction from Parity Games to Mean Payoff Games (MPG) and an analysis of the lower bound of Universal Graphs. We also discussed why the structure used for Parity Games does not yield a quasi-polynomial algorithm for Mean Payoff Games, highlighting the limitations and challenges inherent in extending these methods. Next, we examined that Simple Stochastic Games (SSG) are at least as difficult as Mean Payoff Games (MPG). We proved the complexity of SSG falls within NP ∩coNP, and how this result, through the reductions, implies the same complexity for other games as well. This connection underscores the broader implications of SSG complexity results for related game-theoretic problems. Several open questions emerge from this project. One significant question is whether it is possible to develop a polynomial, rather than a quasi-polynomial, algorithm for Parity Games. Additionally, it remains to be determined if there exists any structure that could lead to a quasi-polynomial or polynomial algorithm for Mean Payoff Games (MPG). Until a more efficient algorithm for MPG is discovered, it is premature to assert the existence of such an algorithm for Simple Stochastic Games (SSG). 33 C.C. Aspects of Path-Forming Games References [1] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2006. [2] Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 252–263, New York, NY, USA, 2017. Association for Computing Machinery. [3] Antonio Casares and Pierre Ohlmann. On the ESL algorithm for solving energy games. CoRR, abs/2110.07346, 2021. [4] Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203–224, 1992. [5] Stephen Cook. The p versus np problem. The millennium prize problems, 02 2001. [6] Nathana¨el Fijalkow, Pawe l Gawrychowski, and Pierre Ohlmann. Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. In Javier Esparza and Daniel Kr´al’, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik. [7] Nathana¨el Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotn´y, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, and Mateusz Skomra. Games on graphs, 2023. [8] Christos H. Papadimitriou. On inefficient proofs of existence and complexity classes. In Jaroslav Neˆsetril and Miroslav Fiedler, editors, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, volume 51 of Annals of Discrete Mathematics, pages 245–250. Elsevier, 1992. [9] L. S. Shapley. Stochastic games*. Proceedings of the National Academy of Sciences, 39(10):1095– 1100, 1953. [10] Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theor. Comput. Sci., 158(1–2):343–359, may 1996. 34