The Library
A pseudo-quasi-polynomial algorithm for mean-payoff parity games
Tools
Tools
Tools
Daviaud, Laure, Jurdzinski, Marcin and Lazic, Ranko (2018) A pseudo-quasi-polynomial algorithm for mean-payoff parity games. In: 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Oxford, 9–12 Jul 2018. Published in: LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science pp. 325-334. ISBN 9781450355834. doi:10.1145/3209108.3209162
|
PDF
WRAP-pseudo-quasi-polynomial-algorithm-Daviaud-2018%20%281%29.pdf - Accepted Version - Requires a PDF viewer. Download (799Kb) | Preview |
Official URL: https://doi.org/10.1145/3209108.3209162
Abstract
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Algorithms, Two-person zero-sum games, Polynomials | ||||||
| Journal or Publication Title: | LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science | ||||||
| Publisher: | ACM | ||||||
| ISBN: | 9781450355834 | ||||||
| Official Date: | July 2018 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 325-334 | ||||||
| DOI: | 10.1145/3209108.3209162 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 4 May 2018 | ||||||
| Date of first compliant Open Access: | 4 May 2018 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||
| Type of Event: | Other | ||||||
| Location of Event: | Oxford | ||||||
| Date(s) of Event: | 9–12 Jul 2018 | ||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
