Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Recursive Approach to Solving Parity Games in Quasipolynomial Time
363
0
0.0
(
0
)
Added by
Pawe{\\l} Parys
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Zielonkas classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of Zielonkas classic algorithm that brings its complexity down to $n^{mathcal{O}left(logleft(1+frac{d}{log n}right)right)}$, for parity games of size $n$ with $d$ priorities, in line with previous quasipolynomial-time solutions.
rate research
Read More
2.5 player parity games combine the challenges posed by 2.5 player reachability games and the qualitative analysis of parity games. These two types of problems are best approached with different types of algorithms: strategy improvement algorithms for 2.5 player reachability games and recursive algorithms for the qualitative analysis of parity games. We present a method that - in contrast to existing techniques - tackles both aspects with the best suited approach and works exclusively on the 2.5 player game itself. The resulting technique is powerful enough to handle games with several million states.
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.
The window mechanism was introduced by Chatterjee et al. to reinforce mean-payoff and total-payoff objectives with time bounds in two-player turn-based games on graphs. It has since proved useful in a variety of settings, including parity objectives in games and both mean-payoff and parity objectives in Markov decision processes. We study window parity objectives in timed automata and timed games: given a bound on the window size, a path satisfies such an objective if, in all states along the path, we see a sufficiently small window in which the smallest priority is even. We show that checking that all time-divergent paths of a timed automaton satisfy such a window parity objective can be done in polynomial space, and that the corresponding timed games can be solved in exponential time. This matches the complexity class of timed parity games, while adding the ability to reason about time bounds. We also consider multi-dimensional objectives and show that the complexity class does not increase. To the best of our knowledge, this is the first study of the window mechanism in a real-time setting.
Strategic interactions often take place in an environment rife with uncertainty. As a result, the equilibrium of a game is intimately related to the information available to its players. The emph{signaling problem} abstracts the task faced by an informed market maker, who must choose how to reveal information in order to effect a desirable equilibrium. In this paper, we consider two fundamental signaling problems: one for abstract normal form games, and the other for single item auctions. For the former, we consider an abstract class of objective functions which includes the social welfare and weighted combinations of players utilities, and for the latter we restrict our attention to the social welfare objective and to signaling schemes which are constrained in the number of signals used. For both problems, we design approximation algorithms for the signaling problem which run in quasi-polynomial time under various conditions, extending and complementing the results of various recent works on the topic. Underlying each of our results is a meshing scheme which effectively overcomes the curse of dimensionality and discretizes the space of essentially different posterior beliefs -- in the sense of inducing essentially different equilibria. This is combined with an algorithm for optimally assembling a signaling scheme as a convex combination of such beliefs. For the normal form game setting, the meshing scheme leads to a convex partition of the space of posterior beliefs and this assembly procedure is reduced to a linear program, and in the auction setting the assembly procedure is reduced to submodular function maximization.
In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to either foil the parity objective or to maximize the mean payoff. Our main technical result is a pseudo-quasi-polynomial algorithm for solving mean-payoff parity games. All algorithms for the problem that have been developed for over a decade have a pseudo-polynomial and an exponential factors in their running times; in the running time of our algorithm the latter is replaced with a quasi-polynomial one. By the results of Chatterjee and Doyen (2012) and of Schewe, Weinert, and Zimmermann (2018), our main technical result implies that there are pseudo-quasi-polynomial algorithms for solving parity energy games and for solving parity games with weights. Our main conceptual contributions are the definitions of strategy decompositions for both players, and a notion of progress measures for mean-payoff parity games that generalizes both parity and energy progress measures. The former provides normal forms for and succinct representations of winning strategies, and the latter enables the application to mean-payoff parity games of the order-theoretic machinery that underpins a recent quasi-polynomial algorithm for solving parity games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
