一句话：本文证明带成本奇偶博弈中求最小成本界的最优策略问题 PSPACE 完全，且指数记忆必要且充分。
带成本的奇偶博弈在奇色出现与随后更大的偶色之间施加任意但固定的成本界，是对奇偶博弈的定量扩展。已有结果表明判定胜负仍在 NP∩co-NP，且一方有位置策略。本文研究实现最小成本界的最优策略：求解问题变为 PSPACE 完全，指数记忆一般必要且总是充分；内存大小与实现界之间存在渐进权衡。结果对一元和二进制成本编码均成立。对带成本的 Streett 博弈，最优博弈在复杂度和记忆需求上与取胜同样困难。
The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the cost incurred 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, solving and 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. All these results hold true for both a unary and binary encoding of costs. Moreover, we investigate Streett games with costs. Here, playing optimally is as hard as winning, both in terms of complexity and memory.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{Weinert016,
title = {Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs},
author = {Alexander Weinert and Martin Zimmermann},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 3},
year = {2017},
doi = {10.23638/lmcs-13(3:29)2017}
}