Geodesic
Potential theory for mean payoff games
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part I, Tome 340 (2006), pp. 61-75 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We present an $O(mn2^n\log Z)$ deterministic algorithm for solving the mean payoff game problem, $m$ and $n$ being respectively the number of arcs and vertices in the game graph and $Z$ being the maximum weight (we assume that the weights are integer numbers). The theoretical basis for the algorithm is the potential theory for mean payoff games. This theory allows to restate the problem in terms of solving systems of algebraic equations with minima and maxima. Also we use arc reweighting technique to solve the mean payoff game problem by applying simple modifications to the game graph that do not change the set of winning strategies, obtaining at the end a trivial instance of the problem. We show that any game graph can be simplified by $n$ reweightings. 
@article{ZNSL_2006_340_a3,
     author = {Yu. M. Lifshits and D. S. Pavlov},
     title = {Potential theory for mean payoff games},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {61--75},
     year = {2006},
     volume = {340},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a3/}
}
TY  - JOUR
AU  - Yu. M. Lifshits
AU  - D. S. Pavlov
TI  - Potential theory for mean payoff games
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2006
SP  - 61
EP  - 75
VL  - 340
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a3/
LA  - en
ID  - ZNSL_2006_340_a3
ER  - 
%0 Journal Article
%A Yu. M. Lifshits
%A D. S. Pavlov
%T Potential theory for mean payoff games
%J Zapiski Nauchnykh Seminarov POMI
%D 2006
%P 61-75
%V 340
%U http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a3/
%G en
%F ZNSL_2006_340_a3
Yu. M. Lifshits; D. S. Pavlov. Potential theory for mean payoff games. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part I, Tome 340 (2006), pp. 61-75. http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a3/

[1] Henrik Björklund, Sven Sandberg, and Sergei Vorobyov, “Memoryless determinacy of parity and mean payoff games: a simple proof”, Theoretical Computer Science, 310 (2004), 365–378 | DOI | MR | Zbl

[2] Henrik Björklund, Sven Sandberg, and Sergei Vorobyov, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, DIMACS Technical Report No 5, 2004 | MR

[3] Y. J. Chu and T. H. Liu, “On the shortest arborescence of a directed graph”, Science Sinica, 14 (1965), 1396–1400 | MR | Zbl

[4] A. Ehrenfeucht and J. Mycielski, “Positional strategies for mean payoff games”, International Journal of Game Theory, 8 (1979), 109–113 | DOI | MR | Zbl

[5] V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, “Cyclic games and an algorithm to find minimax cycle means in directed graphs”, USSR Computational Mathematics and Mathematical Physics, 28 (1988), 85–91 | DOI | MR | Zbl

[6] T. Gallai, “Maximum-Minimum Sätze über Graphen”, Acta Mathematica Academiae Scientiarum Hungaricae, 9 (1958), 395–434 | DOI | MR | Zbl

[7] Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003

[8] Donald B. Johnson, “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM, 24 (1977), 1–13 | DOI | MR | Zbl

[9] Marcin Jurdziński, “Small progress measures for solving parity games”, Proceedings of 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 1770, eds. Hotst Reichel and Sophie Tison, Springer, 2000, 290–301 | MR | Zbl

[10] Marcin Jurdziński, Mike Paterson, and Uri Zwick, “A Deterministic Subexponential Algorithm for Solving Parity Games” (to appear)

[11] Hartmut Klauck, “Algorithms for Parity Games”, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science, 2500, eds. E. Grädel et al., Springer-Verlag, 2002, 107–129 | MR | Zbl

[12] Dexter Kozen, “Results on the propositional $\mu$-calculus”, Theoretical Computer Science, 27 (1983), 333–354 | DOI | MR | Zbl

[13] H. W. Kuhn, “The hungarian method for the assignment problem”, Naval Research Logistics Quarterly, 2 (1955), 83–97 | DOI | MR | Zbl

[14] Stephen Kwek and Kurt Mehlhorn, “Optimal Search for Rationals”, Information Processing Letters, 86 (2003), 23–26 | DOI | MR | Zbl

[15] N. Pisaruk, “Mean cost cyclical games”, Mathematics of Operations Research, 24 (1999), 817–828 | DOI | MR | Zbl

[16] Uri Zwick and Mike Paterson, “The complexity of mean payoff games on graphs”, Theoretical Computer Science, 158 (1996), 343–359 | DOI | MR | Zbl