Skip to main content
SpringerLink
Log in

Polynomial-Time Algorithms for Energy Games with Special Weight Structures

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time.

In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Algorithm 2
Algorithm 3
Fig. 5

Similar content being viewed by others

Notes

  1. Both reductions were originally shown for mean-payoff games.

  2. More precisely, the auxiliary algorithm of Gurvich et al. [18] solves a decision version of mean-payoff games. It has to output, for every node v, whether the mean-payoff at v is at least zero or not. If it is, the potential of v computed by this algorithm is equal to what we call the minimal sufficient energy of v. If not, we know that the minimal sufficient energy of v is ∞.

  3. The randomized subexponential algorithm of Björklund and Vorobyov [2] uses the same randomization scheme as the random facet algorithm.

  4. We formally define the concept of penalty in Sect. 2.

  5. A worst-case instance for the first two algorithms has been developed by Lebedev and is mentioned by Gurvich et al. [18] and shown by Beffara and Vorobyov [1] (for the second algorithm, we exploit the fact that it is deterministic and there exists a bad ordering in which the nodes are processed). Worst-case instances for the third and the fourth algorithm have been given by Zwick and Paterson [33] and Friedmann et al. [15], respectively. We note that the instances shown by Beffara and Vorobyov [1] and Friedmann et al. [15] contain one cycle of small negative weight. One can change the value of this cycle to −W to make these examples belong to the desired class of graphs without changing the worst-case behaviors of the mentioned algorithms.

  6. (G,w) is usually called a “game graph” in the literature. We will simply say “graph”.

  7. If some node v has a self-loop (v,v) of weight w(v,v), we can replace the self-loop as follows: we add an artificial node v′ and two edges (v,v′) and (v′,v). The edges (v,v′) and (v′,v) both get the weight w(v,v). This does not change the energy values nor the average weight of any cycle.

  8. Positional strategies are both pure and memoryless, i.e., they are deterministic and do not depend on the history of the game. The existence of optimal positional strategies in energy games follows immediately from the existence of optimal positional strategies in mean-payoff games [13] and the reduction of energy games to mean-payoff games [6].

  9. We need to take the supremum here to include the case that s has penalty of at least D for every real D. In this case, P G,w (s)=∞ (P G,w (s) will not be well-defined if we use maximum instead of supremum).

  10. Remember that we assume that there are no self-loops and therefore v≠u.

  11. At this point we remark that energy games are not as resistant to perturbations of weights as mean-payoff games. In particular, if w(u,v)≤w′(u,v)≤w(u,v)+x for every edge (u,v) and some positive constant x, then also \(\operatorname{val}(v) \leq\operatorname{val}' (v) \leq\operatorname {val}(v) + x \), where \(\operatorname{val}(v) \) and \(\operatorname {val}' (v) \) are the values of the mean-payoff games for v in (G,w) and (G,w′), respectively. A similar inequality is not true for the minimal energies. Consider a cycle of total weight 0. By adding −1 to each edge weight, the weight of this cycle changes from non-negative to negative. Thus, the minimal energy might change from 0 to ∞.

  12. The third property we mentioned above follows from property 2 and the approximation guarantee of the energy function e.

  13. There are many notions of ergodicity [5, 24]. Strong ergodicity is the strongest one as it implies other ergodicity conditions.

  14. We formally define the notion of clique-width and the class of strongly ergodic graphs in Sect. 6.2.

  15. The reduction of Bouyer et al. [6] adds nodes and edges such that, after every edge that is taken, Bob has the possibility to return to the starting node s by an edge of weight t, for a finite t≥0. In this way we have \(e ^{*}_{G, w} (s) \leq t \) if and only if Alice wins at s. It is now possible to find \(e ^{*}_{G, w} (s) \) by binary search because the maximum finite energy is limited to nW.

  16. Readers that are familiar with parity games might wonder why the same idea does not work for parity games. In parity games every node has a priority. This corresponds to the case where all outgoing edges of a node have the same weight. Under this restriction we are not allowed to add edges of weight −∞ wherever we want to.

  17. We use Lebedev’s definitions [24].

  18. To be precise: Alice has to play σ ∗ for nodes already present in (G,w) and for the other nodes the edge that does not go back to s has to be chosen.

  19. Because of its special structure such a path P is also known as a “lasso” in the literature.

References

  1. Beffara, E., Vorobyov, S.: Is randomized Gurvich-Karzanov-Khachiyan’s algorithm for parity games polynomial? Tech. Rep. 2001-025, Department of Information Technology, Uppsala University (2001)

  2. Björklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Appl. Math. 155(2), 210–229 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bloem, R., Chatterjee, K., Henzinger, T.A., Jobstmann, B.: Better quality in synthesis through quantitative objectives. In: CAV, pp. 140–156 (2009)

    Google Scholar 

  4. Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On canonical forms for zero-sum stochastic mean payoff games. Dyn. Games Appl. (2013, to appear)

  5. Boros, E., Elbassioni, K.M., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic mean payoff games: smoothed analysis and approximation schemes. In: ICALP, pp. 147–158 (2011)

    Google Scholar 

  6. Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: FORMATS, pp. 33–47 (2008)

    Google Scholar 

  7. Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.F.: Faster algorithms for mean-payoff games. Form. Methods Syst. Des. 38(2), 97–118 (2011)

    Article  MATH  Google Scholar 

  8. Cerný, P., Chatterjee, K., Henzinger, T.A., Radhakrishna, A., Singh, R.: Quantitative synthesis for concurrent programs. In: CAV, pp. 243–259 (2011)

    Google Scholar 

  9. Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource interfaces. In: EMSOFT, pp. 117–133 (2003)

    Google Scholar 

  10. Condon, A.: The complexity of stochastic games. Inf. Comput. 96(2), 203–224 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  11. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1–3), 77–114 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. Daskalakis, C., Papadimitriou, C.H.: Continuous local search. In: SODA, pp. 790–804 (2011)

    Google Scholar 

  13. Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8(2), 109–113 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  14. Friedmann, O.: A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In: IPCO, pp. 192–206 (2011)

    Google Scholar 

  15. Friedmann, O., Hansen, T.D., Zwick, U.: A subexponential lower bound for the random facet algorithm for parity games. In: SODA, pp. 202–216 (2011)

    Google Scholar 

  16. Friedmann, O., Hansen, T.D., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC, pp. 283–292 (2011)

    Google Scholar 

  17. Gentilini, R.: A note on the approximation of mean-payoff games. In: CILC (2011)

    Google Scholar 

  18. Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28(5), 85–91 (1990)

    Article  MathSciNet  Google Scholar 

  19. Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica 49(1), 37–50 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  20. Jurdzinski, M.: Deciding the winner in parity games is in UP∩co-UP. Inf. Process. Lett. 68(3), 119–124 (1998)

    Article  MathSciNet  Google Scholar 

  21. Kalai, G.: A subexponential randomized simplex algorithm. In: STOC, pp. 475–482 (1992)

    Google Scholar 

  22. Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Math. Program. 79(1–3), 217–233 (1997)

    MATH  MathSciNet  Google Scholar 

  23. Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23(3), 309–311 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  24. Lebedev, V.N.: Effectively solvable classes of cyclical games. J. Comput. Syst. Sci. Int. 44(4), 525–530 (2005)

    MATH  Google Scholar 

  25. Lifshits, Y.M., Pavlov, D.S.: Potential theory for mean payoff games. J. Math. Sci. 145(3), 4967–4974 (2007)

    Article  MathSciNet  Google Scholar 

  26. Martin, D.A.: Borel determinacy. Ann. Math. 102(2), 363–371 (1975)

    MATH  Google Scholar 

  27. Matoušek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4–5), 498–516 (1996)

    MATH  MathSciNet  Google Scholar 

  28. Obdrzálek, J.: Clique-width and parity games. In: CSL, pp. 54–68 (2007)

    Google Scholar 

  29. Pisaruk, N.N.: Mean cost cyclical games. Math. Oper. Res. 24(4), 817–828 (1999)

    MATH  MathSciNet  Google Scholar 

  30. Roth, A., Balcan, M.F., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: SODA, pp. 805–816 (2010)

    Google Scholar 

  31. Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: STACS, pp. 569–579 (1992)

    Google Scholar 

  32. Vorobyov, S.: Cyclic games and linear programming. Discrete Appl. Math. 156(11), 2195–2231 (2008)

    MATH  MathSciNet  Google Scholar 

  33. Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1–2), 343–359 (1996)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Science and Technology, Klosterneuburg, Austria

    Krishnendu Chatterjee

  2. University of Vienna, Faculty of Computer Science, Vienna, Austria

    Monika Henzinger & Sebastian Krinninger

  3. Nanyang Technological University, Singapore, Singapore

    Danupon Nanongkai

Authors
  1. Krishnendu Chatterjee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Monika Henzinger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sebastian Krinninger
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Danupon Nanongkai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sebastian Krinninger.

Additional information

K. Chatterjee supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award.

M. Henzinger and S. Krinninger supported by the Austrian Science Fund (FWF): P23499-N23, the Vienna Science and Technology Fund (WWTF) grant ICT10-002, the University of Vienna (IK I049-N), and a Google Faculty Research Award.

D. Nanongkai’s work partially done while at University of Vienna, Austria.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chatterjee, K., Henzinger, M., Krinninger, S. et al. Polynomial-Time Algorithms for Energy Games with Special Weight Structures. Algorithmica 70, 457–492 (2014). https://doi.org/10.1007/s00453-013-9843-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9843-7

Keywords

Search

Navigation