Potential theory for mean payoff games |
| |
Authors: | Y M Lifshits D S Pavlov |
| |
Institution: | (1) St. Petersburg Department of the Steklov Mathematical Institute, St. Petersburg, Russia;(2) Department of Mathematics, Institute of Fine Mechanics and Optics, St. Petersburg, Russia |
| |
Abstract: | The paper presents an O(mn2n
log Z) deterministic algorithm for solving the mean payoff game problem, m and n being the numbers of arcs and vertices, respectively,
in the game graph, and Z being the maximum weight (the weights are assumed to be integers). The theoretical basis for the
algorithm is the potential theory for mean payoff games. This theory allows one to restate the problem in terms of solving
systems of algebraic equations with minima and maxima. Also, in order to solve the mean payoff game problem, the arc reweighting
technique is used. To this end, simple modifications, which do not change the set of winning strategies, are applied to the
game graph; in the end, a trivial instance of the problem is obtained. It is shown that any game graph can be simplified by
n reweightings. Bibliography: 16 titles.
__________
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 61–75. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|