2026-07-21T18:41:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6571 2024-03-06T10:38:44Z ddc:004 open_access

Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs Weinert, Alexander Zimmermann, Martin Parity Games with Costs Optimal Strategies Memory Requirements Tradeoffs The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the distance between occurrences of odd colors and the next occurrence of a larger even one. Such games quantitatively extend parity games while retaining most of their attractive properties, i.e, determining the winner is in NP and co-NP and one player has positional winning strategies. We show that the characteristics of parity games with costs are vastly different when asking for strategies realizing the minimal such bound: the solution problem becomes PSPACE-complete and exponential memory is both necessary in general and always sufficient. Thus, playing parity games with costs optimally is harder than just winning them. Moreover, we show that the tradeoff between the memory size and the realized bound is gradual in general. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Weinert and Martin Zimmermann 2016 Is Part Of LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2016.31 urn:nbn:de:0030-drops-65714 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.31 eng https://creativecommons.org/licenses/by/3.0/legalcode