A Note on the Approximation of Mean-Payoff Games

Abstract

We consider the problem of designing approximation schemes for the values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [ 1; 1] admit additive fully-polynomial approximation schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of designing additive/relative approximation schemes for general mean-payoff games (i.e. with no constraint on their edge-weights) is P-time equivalent to determining their exact solution.

1 Introduction

Two-player mean-payoff games are played on weighted graphs1 with two types of vertices: in player-0 vertices, player 0 chooses the successor vertex from the set of outgoing edges; in player-1 vertices, player 1 chooses the successor vertex from the set of outgoing edges. The game results in an infinite path through the graph. The long-run average of the edge-weights along this path, called the value of the play, is won by player 0 and lost by player 1.

The decision problem for mean-payoff games asks, given a vertex v and a threshold 2 Q, if player 0 has a strategy to win a value at least when the game starts in v. The value problem consists in computing the maximal (rational) value that player 0 can achieve from each vertex v of the game. The associated (optimal) strategy synthesis problem is to construct a strategy for player 0 that secures the maximal value.

Mean-payoff games have been first studied by Ehrenfeucht and Mycielski in [ 1 ], where it is shown that memoryless (or positional) strategies suffice to achieve the optimal value. This result entails that the decision problem for these games lies in NP \ coNP [ 2, 18 ], and it was later shown to belong to2 UP \ coUP [ 10 ]. Despite many efforts [ 19, 18, 13, 5, 6, 20, 9, 12 ], no polynomial-time algorithm for the mean-payoff game problems is known so far.

Beside such a theoretically engaging complexity status, mean-payoff games have plenty of applications, especially in the synthesis, analysis and verification of reactive (non-terminating) systems. Many natural models of such systems include quantitative information, and the corresponding question requires the solution of quantitative games, like mean-payoff games. Concrete examples of applications include various kinds of scheduling, finite-window online string matching, or more generally, analysis of online problems and algorithms, as well as selection with limited storage [ 18 ]. Mean-payoff games can even be used for solving the max-plus algebra Ax = Bx problem, which in 1 in which every edge has a positive/negative (rational) weight 2 The complexity class UP is the class of problems recognizable by unambiguous polynomial time nondeterministic Turing machines [ 14 ]. Obviously P UP \ coUP NP \ coNP. Algorithms [ 12 ] [ 18 ] [ 20 ] [ 9 ]

Decision Problem O(jE j jV j W ) (jE j jV j2

W ) O(jE j jV j 2 jV j)

Value Problem

O(jEj jV j2 W (logjV j + logW ))

(jEj jV j3 W )

O(jEj jV j 2 jV j logW )

Note Deterministic Deterministic Deterministic min(O(jE j jV j2 W ); min(O(jEj jV j3 W (logV + logW )); Randomized 2 O(pjV j logjV j) logW ) 2 O(pjV j logjV j) logW ) turn has further applications [ 6 ]. Beside their applicability to the modeling of quantitative problems, mean-payoff games have tight connections with important problems in game theory and logic. For instance, parity games [ 8 ] and the model-checking problem for the modal mu-calculus [ 11 ] are poly-time reducible to mean-payoff games [ 7 ], and it is a long-standing open question to know whether these problems are in P.

Table 1 summarize the complexity of the main algorithms for solving mean-payoff games in the literature. In particular, all deterministic algorithms for mean-payoff games are either pseudopolynomial (i.e., polynomial in the number of vertices jV j, the number of edges jEj, and the maximal absolute weight W , rather than in the binary representation of W ) or exponential [ 19, 18, 13, 12, 20, 17 ]. The works in [ 9, 3 ] define a randomized algorithm which is both subexponential and pseudopolynomial. Recently, the authors of [ 15, 4 ] show that the pseudopolynomial procedures in [ 18, 13, 12 ] can be used to design (fully) polynomial value approximation schemes for certain classes of meanpayoff games: namely, mean-payoff games with positive (integer) weights or rational weights with absolute value less or equal to 1. In this paper, we consider the problem of extending such positive approximation results for general mean-payoff games, i.e. mean-payoff games with weights arbitrary shifted/scaled on the line of rational numbers. 2

Preliminaries and Definitions

Game graphs A game graph is a tuple = (V; E; w; hV0; V1i) where G = (V; E; w) is a weighted graph and hV0; V1i is a partition of V into the set V0 of player-0 vertices and the set V1 of player-1 vertices. An infinite game on is played for infinitely many rounds by two players moving a pebble along the edges of the weighted graph G . In the first round, the pebble is on some vertex v 2 V . In each round, if the pebble is on a vertex v 2 Vi (i = 0; 1), then player i chooses an edge (v; v0) 2 E and the next round starts with the pebble on v0. A play in the game graph is an infinite sequence p = v0v1 : : : vn : : : such that (vi; vi+1) 2 E for all i 0. A strategy for player i (i = 0; 1) is a function : V Vi ! V , such that for all finite paths v0v1 : : : vn with vn 2 Vi, we have (vn; (v0v1 : : : vn)) 2 E. A strategy-profile is a pair of strategies h 0; 1i, where 0 (resp. 1) is a strategy for player 0 (resp. player 1). We denote by i (i = 0; 1) the set of strategies for player i. A strategy for player i is memoryless if (p) = (p0) for all sequences p = v0v1 : : : vn and p0 = v00v10 : : : vm0 such that vn = vm0. We denote by iM the set of memoryless strategies of player i. A play v0v1 : : : vn : : : is consistent with a strategy for player i if vj+1 = (v0v1 : : : vj ) for all positions j 0 such that vj 2 Vi. Given an initial vertex v 2 V , the outcome of the strategy profile h 0; 1i in v is the (unique) play outcome (v; 0; 1) that starts in v and is consistent with both 0 and 1. Given a memoryless strategy i for player i in the game , we denote by G ( i) = (V; E i ; w) the weighted graph obtained by removing from G all edges (v; v0) such that v 2 Vi and v0 6= i(v).

Mean-Payoff Games A mean-payoff game (MPG) [ 1 ] is an infinite game played on a game graph where player 0 wins a payoff value defined as the long-run average weights of the play, while player 1 loses that value. Formally, the payoff value of a play v0v1 : : : vn : : : in is

MP(v0v1 : : : vn : : : ) = lim inf n!1 n 1 nX1 w(vi; vi+1): i=0

The value secured by a strategy 0 2

0 in a vertex v is val 0 (v) = inf 12 1

MP(outcome (v; 0; 1)) and the (optimal) value of a vertex v in a mean-payoff game is val (v) = sup inf 02 0 12 1

MP(outcome (v; 0; 1)): We say that 0 is optimal if val 0 (v) = val (v) for all v 2 V . Secured value and optimality are defined analogously for strategies of player 1. Ehrenfeucht and Mycielski [ 1 ] show that mean-payoff games are memoryless determined, i.e., memoryless strategies are sufficient for optimality and the optimal (maximum) value that player 0 can secure is equal to the optimal (minimum) value that player 1 can achieve.

Theorem 1 ([ 1 ]). For all MPG have

= (V; E; w; hV0; V1i) and for all vertices v 2 V , we and there exist two memoryless strategies 0 2 0M and 1 2

1M such that val (v) = val 0 (v) = val 1 (v): Moreover, uniform optimal strategies exist for both players, i.e. there exists a strategy profile h 0; 1i that can be used to secure the optimal value independently of the initial vertex [ 1 ]. Such a strategy profile is said the optimal strategy profile.

The following lemma characterizes the shape of MPG values in a MPG = (V; E; w; hV0; V1i) with integer weights in f W; : : : ; W g. Note that solving MPG with rational weights is P-time reducible to solving MPG with integer weights [ 20, 18 ]. Lemma 1 ([ 1, 20 ]). Let

= (V; E; w; hV0; V1i) be a MPG with integer weights and lreattiWona=l nmu maxb(evr;vnd0)2sEucjwh(thva;tv10)j. For each vertex v 2 V , the optimal value val (v) is a d jV j and jnj d W .

We consider the following three classical problems [ 18, 9 ] for a MPG = (V; E; w; hV0; V1i): 1. Decision Problem. Given a threshold 2 Q and a vertex v 2 V , decide if val (v) . 2. Value Problem. Compute for each vertex v 2 V the value val (v). 3. (Optimal) Strategy Problem . Given an MPG , compute an (optimal) strategy profile for .

Approximate Solutions for MPG Dealing with approximate MPG solutions, we can take into consideration either absolute or relative error measures, and define the notions of additive and relative MPG approximate value.

Definition 1 (MPG additive "-value). Let v 2 V and consider " only if: = (V; E; w; hV0; V1i) be a MPG, let 0. The value vfal 2 Q is said an additive "-value on v if and Definition 2 (MPG relative "-value). Let V and consider " = (V; E; w; hV0; V1i) be a MPG, let v 2 0. The value vfal 2 Q is said a relative "-value on v if and only if: jvfal Note that additive MPG "-values are shift-invariant. More precisely, if vfal is an additive approximate "-value on the vertex v in = (V; E; w; hV0; V1i), then vfal + k is an additive approximate "-value in the MPG 0 = (V; E; w + k; hV0; V1i), where all the weights are shifted by k. On the contrary, additive MPG "-values are not scale-invariant. In fact, if vfal is a relative "-value for v in the MPG = (V; E; w; hV0; V1i), then k vfal is a relative " k-value for v in the MPG 0 = (V; E; w k; hV0; V1i), where all the weights are multiplied by k. In other words, the additive error on is amplified by a factor k in the scaled version of the game, 0. Conversely, relative MPG "-values are scale invariant but not shift invariant.

The notions of (fully) polynomial approximation schemes w.r.t relative and additive errors are formally defined below.

Definition 3 (MPG Fully Polynomial Time Approximation Scheme (FPTAS)). An additive (resp. relative) fully polynomial approximation scheme for the MPG = (V; E; w; hV0; V1i) is an algorithm A such that for all " > 0, A computes an additive (resp. relative) "-value in time polynomial w.r.t. the size3 of and 1" .

Definition 4 (MPG Polynomial Time Approximation Scheme (PTAS)). An additive (resp. relative) polynomial approximation scheme for the MPG = (V; E; w; hV0; V1i) is an algorithm A such that for all " > 0, A computes an additive (resp. relative) "value in time polynomial w.r.t. the size of . 3 Given = (V; E; w; hV0; V1i), size( ) = jEj + jV j + log(W ), where W is the maximum (absolute value) of a weight in .

Mean-Payoff Games and Additive Approximation Schemes

Recently, [ 15 ] provides an additive fully polynomial scheme for the MPG value problem on graphs with rational weights in the interval [ 1; +1]. A natural question is whether we could efficiently approximate the value in MPG with no restrictions on the weights. The next theorem shows that a generalization of the positive approximation result in [ 15 ] on MPG with arbitrary (rational) weights would indeed provide a polynomial time exact solution to the MPG value problem.

Theorem 2. The MPG value problem does not admit an additive FPTAS, unless it is in P.

Proof. We start to consider the MPG problem on graphs with integer weights. Assume that the MPG value problem on graphs with integer weights admits an additive FPTAS. Given a MPG = (V; E; w; hV0; V1i) and a vertex v 2 V , let jV j = n and " = 1 2n(n 1) . Then, our FPTAS computes an additive "-value vfal on v in time polynomial w.r.t. n. By Lemma 1, val (v) is a rational number with denominator d such that 1 d n. Two rationals with denominator d for which 1 d n have distance at least n(n1 1) . Hence, there is a unique rational with denominator d, 1 d n, within the interval I = fq 2 Q j vfal " q

1 vfal + "g, where " = 2n(n 1) . Such unique rational is val (v) and can be easily found in time logarithmic w.r.t. n [ 16 ]. Thus, we have an algorithm A to solve the value problem on in time polynomial w.r.t. n. The MPG problem on graphs with rational weights can be reduced in polynomial time (w.r.t. the size of ) to the MPG on graphs with integer weights by simply resizing the weights in the original graph [ 20, 12 ]. tu In view of the proof of the above theorem, we could still hope to obtain some positive approximation results for general (i.e. arbitrarly scaled) MPG by considering weaker notion of approximations with respect to FPTAS. Unfortunately, the next lemma shows that the following is sufficient to show that the MPG value problem is in P: determining in time polynomial w.r.t. the size of a given MPG a k-approximate value of v, where v 2 V and k is an arbitrary constant.

Theorem 3. For any constant k: If the problem of computing an additive k-approximate MPG value can be solved in polynomial time (w.r.t. the size of the input MPG), then the MPG value problem belongs to P.

Proof. We start to consider MPG with integer weights. Let v be a vertex in the MPG = (V; E; w : E 7! [ W; W ]; hV0; V1i) and denote jV j = n. If 2k + 1 > (n 2)!, then the problem of determining val (v) can be solved in time O(kk) = O(1) by simply enumerating all the strategies available to the players.

Otherwise, assume 2k +1 (n 2)!. Consider the game 0 = (V; E; w0; hV0; V1i), where 8e 2 E : w0(e) = w(e) n!. By hypothesis, there is an algorithm A that computes a k-approximate value vfal for v on 0 in time T polynomial w.r.t. the size of 0. Since log(W n!) = O(n log(n) + log(W )), T is also polynomial w.r.t. the size of . By construction, val 0 (v) is an integer. There are at most 2k + 1 integers in the interval [vfal

k; vfal + k], thus we have at most 2k + 1 candidates f bvfanl ! kc ; : : : ; bgvanl +!kc g for val (v). Moreover, those candidates lie in an interval of length L 2kn+! 1 (nn!2)! = n (n1 1) . The minimum distance between two possible candidates for val (v) is n (n1 1) .

The exact value val (v) is thus the unique rational number with denominator of size at most n that lies in the interval [ bvfal kc ; bgval+kc ] and can be easily found in time n! n! logarithmic w.r.t. n [ 16 ].

The MPG problem on graphs with rational weights can be reduced in polynomial time (w.r.t. the size of ) to the MPG on graphs with integer weights by simply resizing the weights in the original graph [ 20, 12 ]. tu A direct consequence of Theorem 3 is that the MPG value problem does not admit a PTAS, unless it is in P. More precisely, Theorem 2 and Theorem 3 entail a result of P-time equivalence between the exact MPG value problem and the three classes of approximations listed in Corollary 1.

Corollary 1. The following problems are P-time equivalent: 1. Solving the MPG value problem. 2. Determining an additive FPTAS for the MPG value problem. 3. Determining an additive PTAS for the MPG value problem. 4. Computing an additive k-approximate MPG value in polynomial time, for any constant k. 4

Mean-Payoff Games and Relative Approximation Schemes

In the recent work in [ 4 ], the authors consider the design approximation schemes for the MPG value problem based on the relative–rather than absolute–error. In particular, they provide a relative FPTAS for the MPG value problem on graphs with nonnegative weights. Note that negative weights are necessary to encode parity games and the calculus model checking into MPG games [ 10 ]. The following theorem considers the problem of designing (fully) polynomial approximation schemes for the MPG value problem on graphs with arbitrary (positive and negative) rational weights. It shows that solving such a problem would indeed provide an exact solution to the MPG value problem, computable in time polynomial w.r.t. the size of the MPG.

Theorem 4. The MPG value problem does not admit a relative PTAS, unless it is in P. Proof. Let = (V; E; p; hV0; V1i) be a MPG, let v 2 V . Assume that MPG admit a relative PTAS and consider " = 21 . Our assumption entails that we have an algorithm A that computes a relative 12 -value vfal for v in time polynomial w.r.t. the size of . We show that vfal 0 if and only if val (v) 0. In other words, we show that the MPG decision problem is PTIME reducible to the computation of a relative 12 -value. By definition of relative "-value, for " = 12 , we have: jvfal jval (v)j val (v)j 1 2 (1)

We have four cases to consider: 1. In the first case, assume that vfal val (v) 0 and vfal suppose val (v) < 0. Then, Disequation implies: 0. By contradiction, vfal vfal val (v) 1 2 jval (v)j val (v) + 12 jval (v)j < 0 ) that contradicts our hypothesis. 2. In the second case, assume that vfal val (v)

val (v). that contradicts our hypothesis. 3. In the third case, assume that vfal val (v) < 0 and vfal < 0. By contradiction, suppose val (v) > 0. Then, Disequation implies: 0 and vfal < 0. Then, 0 > vfal val (v) vfal

vfal val (v) 1 2 jval (v)j 1 2 jval (v)j 0 ) that contradicts our hypothesis. vfal

0.

4. The last case to consider is: vfal

val (v) < 0 and vfal 0. Then, val (v) > Provided a P-time algorithm for deciding whether val (v) 0, a dichotomic search can be used to determine val (v) in time polynomial w.r.t. the size of [ 12, 20 ]. tu As a direct consequence of Theorem 4 we obtain the following result of P-time equivalence involving the computation of MPG exact and approximate solutions. Corollary 2. The following problems are P-time equivalent: 1. Solving the MPG value problem. 2. Determining a relative FPTAS for the MPG value problem. 3. Determining a relative PTAS for the MPG value problem.

References

1. A. Ehrenfeucht and J. Mycielski . International journal of game theory. Positional Strategies for Mean-Payoff Games , 8 : 109 - 113 , 1979 .

2. A. V. Karzanov and V. N. Lebedev . Cyclical games with proibitions . Mathematical Programing , 60 : 277 - 293 , 1993 .

3. D. Andersson and S. Vorobyov . Fast algorithms for monotonic discounted linear programs with two variables per inequality . Technical Report Preprint NI06019-LAA, Isaac Newton Institute for Mathematical Sciences , Cambridge, UK, 2006 .

4. Y. Boros , K. Elbassioni , M. Fouz , V. Gurvich , K. Makino , and B. Manthey . Stochastic mean-payoff games: Smoothed analysis and approximation schemes . In Proc. of ICALP: Colloquium on Automata, Languages and Programming , 2011 .

5. A. Condon . On algorithms for simple stochastic games . In Advances in Computational Complexity Theory , volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 51 - 73 . American Mathematical Society, 1993 .

6. V. Dhingra and S. Gaubert . How to solve large scale deterministic games with mean payoff by policy iteration . In Proc. Performance evaluation methodolgies and tools, article no. 12. ACM , 2006 .

7. E. A. Emerson , C. Jutla , and A. P. Sistal . On model checking for fragments of the -calculus . In Proc. of CAV: Computer Aided Verification, LNCS 697 , pages 385 - 396 . Springer, 1993 .

8. Y. Gurevich and L. Harrington . Trees, automata, and games . In Proc. of STOC: Symposium on Theory of Computing , pages 60 - 65 . ACM, 1982 .

9. H. Bjorklund and S. Vorobyov . A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games . Discrete Applied Mathematics , 155 : 210 - 229 , 2007 .

10. M. Jurdzinski . Deciding the winner in parity games is in UP \ coUP . Inf. Process. Lett., 68 ( 3 ): 119 - 124 , 1998 .

11. D. Kozen . Results on the propositional mu-calculus . Theor. Comput. Sci. , 27 : 333 - 354 , 1983 .

12. L. Brim , J. Chaloupka , L. Doyen , R. Gentilini , and J-F. Raskin . Faster algorithms for mean payoff games . Formal Methods in System Design , 38 ( 2 ): 97 - 118 , 2011 .

13. N. Pisaruk. Mathematics of operations research. Mean Cost Cyclical Games , 4 ( 24 ): 817 - 828 , 1999 .

14. C. M. Papadimitriou . Computational complexity . Addison-Wesley , Reading, Massachusetts, 1994 .

15. A. Roth , M. Balcan , A. Kalai , and Y. Mansour . On the equilibria of alternating move games . In Proc. of SODA: Symposium on Discrete Algorithms , pages 805 - 816 . ACM, 2010 .

16. S. Kwek and K. Mehlhorn . Optimal search for rationals . Information Processing Letters , 86 : 23 - 26 , 2003 .

17. S. Schewe . From parity and payoff games to linear programming . In Proceedings of MFCS: Mathematical Foundations of Computer Science, LNCS 5734 , pages 675 - 686 . Springer, 2009 .

18. U. Zwick and M. Paterson . The complexity of mean payoff games on graphs . Theoretical Computer Science , 158 : 343 - 359 , 1996 .

19. V. A. Gurvich , A. V. Karzanov , and L. G. Kachiyan . Ussr computational mathematics and mathematical physics. Cyclic Games and an Algorithm to Find Minmax Cycle Means in Directed Graphs , 5 ( 28 ): 85 - 91 , 1988 .

20. Y. Lifshits and D. Pavlov . Potential theory for mean payoff games . Journal of Mathematical Sciences , 145 ( 3 ): 4967 - 4974 , 2007 .