The complexity of solving infinite games, including parity, mean payoff, and simple stochastic, is an important open problem in verification, automata, and complexity theory. In this paper, we develop an abstract sett...
详细信息
The complexity of solving infinite games, including parity, mean payoff, and simple stochastic, is an important open problem in verification, automata, and complexity theory. In this paper, we develop an abstract setting for studying and solving such games, based on function optimization over certain discrete structures. We introduce new classes of recursively local-global (RLG) and partial recursively local-global (PRLG) functions, and show that strategy evaluation functions for simple stochastic, mean payoff, and parity games belong to these classes. In this setting, we suggest randomized subexponential algorithms appropriate for RLG- and PRLG-function optimization. We show that the subexponential algorithms for combinatorial linear programming, due to Kalai and Matousek, Sharir, Welzl, can be adapted for optimizing the RLG- and PRLG-functions. (c) 2005 Elsevier B.V. All rights reserved.
We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cy...
详细信息
We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph. We identify a new "controlled" version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP boolean AND coNP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shot-test paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity min(poly(.)W, 2(O(root nlogn))), which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights). (c) 2006 Elsevier B.V. All rights reserved.
作者：
Vorobyov, SergeiTech Univ Wien
Inst Informat Syst Abteilung Datenbanken & Artificial Intelligence A-1040 Vienna Austria
New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem in NP boolean AND CONP, based on linearprogramming (LP), LP-representations, combinatorial LP, linear comple...
详细信息
New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem in NP boolean AND CONP, based on linearprogramming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are surveyed. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论