Abstract:
We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).

Abstract:
We consider 2-player games played on a finite state space for infinite rounds. The games are concurrent: in each round, the two players choose their moves simultaneously; the current state and the moves determine the successor. We consider omega-regular winning conditions given as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory and infinite-precision. We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n^{2d+3}) time, where n is the size of the game and 2d is the number of priorities, and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP cap coNP. While this complexity is the same as for the simpler class of turn-based games, where in each state only one of the players has a choice of moves, our algorithms, that are obtained by characterization of the winning sets as mu-calculus formulas, are considerably more involved.

Abstract:
We consider games played on graphs with the winning conditions for the players specified as weak-parity conditions. In weak-parity conditions the winner of a play is decided by looking into the set of states appearing in the play, rather than the set of states appearing infinitely often in the play. A naive analysis of the classical algorithm for weak-parity games yields a quadratic time algorithm. We present a linear time algorithm for solving weak-parity games.

Abstract:
We introduce two-level discounted games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted game and the lower level game is an undiscounted reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. We show the existence of pure memoryless optimal strategies for both players and an ordered field property for such games. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted games can be decided in NP intersected coNP. We also give an alternate strategy improvement algorithm to compute the value.

Abstract:
Computing the winning set for B{\"u}chi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is $\tilde{O}(n \cdot m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. We are the first to break the $\tilde{O}(n\cdot m)$ bound by presenting a new technique that reduces the running time to $O(n^2)$. This bound also leads to an $O(n^2)$ algorithm time for computing the set of almost-sure winning vertices in alternating games with probabilistic transitions (improving an earlier bound of $\tilde{O}(n\cdot m)$) and in concurrent graph games with constant actions (improving an earlier bound of $O(n^3)$). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time $O(n^2)$. Finally, we show how to maintain the winning set for B{\"u}chi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.

Abstract:
Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objective. Our main results are as follows: (a) exponential memory is necessary and sufficient for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP \cap coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is polynomially equivalent to the problem of deciding the winner in mean-payoff parity games, while optimal strategies may require infinite memory in mean-payoff parity games. As a consequence we obtain a conceptually simple algorithm to solve mean-payoff parity games.

Abstract:
We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode \omega-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition requires that the resource level never drops below 0, and the mean-payoff condition requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP \cap coNP, while for mean-payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.

Abstract:
In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. We consider reachability objectives where player 1 tries to ensure a target state to be visited almost-surely or positively. On the basis of information, the game can be one-sided with either (a)player 1 or (b)player 2 having partial observation, or two-sided with both players having partial observation. On the basis of randomization (a)players may not be allowed to use randomization (pure strategies), or (b)may choose a probability distribution over actions but the actual random choice is not visible (actions invisible), or (c)may use full randomization. Our results for pure strategies are as follows: (1)For one-sided games with player 2 perfect observation we show that belief-based strategies are not sufficient, and present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2)For one-sided games with player 1 perfect observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3)We show that for the two-sided case finite memory strategies are sufficient for both positive and almost-sure winning. We establish the equivalence of the almost-sure winning problem for pure strategies with randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results in the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was claimed.

Abstract:
We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every epsilon > 0 there is a word that is accepted with probability at least 1 - epsilon. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.

Abstract:
We consider both finite-state game graphs and recursive game graphs (or pushdown game graphs), that can model the control flow of sequential programs with recursion, with multi-dimensional mean-payoff objectives. In pushdown games two types of strategies are relevant: global strategies, that depend on the entire global history; and modular strategies, that have only local memory and thus do not depend on the context of invocation. We present solutions to several fundamental algorithmic questions and our main contributions are as follows: (1) We show that finite-state multi-dimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weight is fixed; whereas if the number of dimensions is arbitrary, then problem is already known to be coNP-complete. (2) We show that pushdown graphs with multi-dimensional mean-payoff objectives can be solved in polynomial time. (3) For pushdown games under global strategies both single and multi-dimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multi-dimensional problem is also undecidable (whereas under modular strategies the single dimensional problem is NP-complete). We show that if the number of modules, the number of exits, and the maximal absolute value of the weight is fixed, then pushdown games under modular strategies with single dimensional mean-payoff objectives can be solved in polynomial time, and if either of the number of exits or the number of modules is not bounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multi-dimensional mean-payoff games or pushdown games under modular strategies with single-dimensional mean-payoff objectives would imply the solution of the long-standing open problem of fixed parameter tractability of parity games.