一句话：研究带任意整数权重的奇偶博弈，证明求解属于 NP ∩ coNP，给出策略内存与质量的紧界，并证明阈值问题 EXPTIME 完全。
本文研究带任意整数权重的奇偶博弈，它放松了带费用奇偶博弈中每条迁移权重非负的限制。这类博弈把无限博弈的定性与定量方面原生结合：定量部分以回答奇偶颜色的延迟上确界作为定性目标的质量度量。作者分析求解复杂度、主角制胜策略的内存需求与策略质量，并研究阈值判定问题。关键结果包括：求解属于 NP ∩ coNP；主角有有限状态制胜策略，内存有紧的伪多项式界；对手可能需无限内存；制胜策略质量有紧界；判定主角是否存在质量至多 b 的策略是 EXPTIME 完全的，且主角需要指数内存。结果推广了 finitary parity games 并继承其下界。
Quantitative extensions of parity games have recently attracted significant interest. These extensions include parity games with energy and payoff conditions as well as finitary parity games and their generalization to parity games with costs. Finitary parity games enjoy a special status among these extensions, as they offer a native combination of the qualitative and quantitative aspects in infinite games: The quantitative aspect of finitary parity games is a quality measure for the qualitative aspect, as it measures the limit superior of the time it takes to answer an odd color by a larger even one. Finitary parity games have been extended to parity games with costs, where each transition is labeled with a nonnegative weight that reflects the costs incurred by taking it. We lift this restriction and consider parity games with costs with arbitrary integer weights. We show that solving such games is in NP $\cap$ coNP, the signature complexity for games of this type. We also show that the protagonist has finite-state winning strategies, and provide tight pseudo-polynomial bounds for the memory he needs to win the game. Naturally, the antagonist may need infinite memory to win. Moreover, we present tight bounds on the quality of winning strategies for the protagonist. Furthermore, we investigate the problem of determining, for a given threshold $b$, whether the protagonist has a strategy of quality at most $b$ and show this problem to be EXPTIME-complete. The protagonist inherits the necessity of exponential memory for implementing such strategies from the special case of finitary parity games.