Potential theory for mean payoff games

Рассматривается детерминированный алгоритм для решения задачи об игре средней оплаты со временем работы $O(mn2^n\log Z)$ в худшем случае, где $m$ и $n$ обозначают количество дуг и вершин в игровом графе, а $Z$ обозначает максимальный вес (веса дуг – целые числа). Теоретической основой алгоритма является теория потенциалов для игры средней оплаты, которая позволяет переформулировать задачу в терминах решения систем алгбраических уравнений с минимумами и максимумами. Также вводится техника перевзвешивания дуг, позволяющая решить задачу об игре средней оплаты при помощи последовательности простых операций, не меняющих множества выигрышных стратегий, после которых задача становится тривиальной. Доказывается, что любой граф может быть упрощён за линейное число перевзвешиваний. Библ. – 16 назв.