Potential theory for mean payoff games
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part I, Tome 340 (2006), pp. 61-75
Voir la notice de l'article provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {340},
year = {2006},
language = {en},
url = {http://geodesic.mathdoc.fr/item/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/