paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Perfect half space games

完美半空间博弈
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文属于逻辑、自动机与博弈论方向的形式化方法研究,讨论能量奇偶博弈的求解复杂度,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向;仅与形式化验证的理论基础有间接关联。引用 19 inbox
Thomas Colcombet, Marcin Jurdziński, Ranko Lazić, Sylvain Schmitz
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:引入完美半空间博弈并证明其位置确定性,进而以伪多项式时间求解多维能量奇偶博弈。

论文研究多维能量奇偶博弈的求解与复杂度问题,特别是在能量维数和优先级数固定时,无论初始信用作为输入的一部分还是存在量化。作者引入完美半空间博弈,其中玩家2动态选择一列完美半空间,目标是使遇到的多维权重和沿一致方向发散。论文证明 Jurdziński 等人的 bounding games 可归约到完美半空间博弈,后者又可翻译为 Colcombet 与 Niwiński 的字典序能量博弈,并具有强位置确定性:玩家2无需知道当前完美半空间即可行动。作为应用,这些博弈被用于在固定能量维数和优先级数时以伪多项式时间求解多维能量奇偶博弈;在给定初始信用时得到最优 2-EXPTIME 复杂度,而此前最好上界为非初等。

问题
如何求解多维能量奇偶博弈并刻画其复杂度,尤其是初始信用给定或存在量化时。
方法
引入完美半空间博弈,建立从 bounding games 到完美半空间博弈、再到字典序能量博弈的归约,并证明强位置确定性。
评估
通过理论归约与复杂度分析进行评估:给出固定维数和优先级数下的伪多项式时间算法,以及给定初始信用时的最优 2-EXPTIME 上界。
原文摘要(Abstract)

We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a chosen sequence of perfect half spaces (chosen dynamically by Player 2). We establish that the bounding games of Jurdziński et al. (ICALP 2015) can be reduced to perfect half space games, which in turn can be translated to the lexicographic energy games of Colcombet and Niwiński, and are positionally determined in a strong sense (Player 2 can play without knowing the current perfect half space). We finally show how perfect half space games and bounding games can be employed to solve multi-dimensional energy parity games in pseudo-polynomial time when both the numbers of energy dimensions and of priorities are fixed, regardless of whether the initial credit is given as part of the input or existentially quantified. This also yields an optimal 2-EXPTIME complexity with given initial credit, where the best known upper bound was non-elementary.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{ColcombetJLS17,
  title = {Perfect half space games},
  author = {Thomas Colcombet and Marcin Jurdziński and Ranko Lazić and Sylvain Schmitz},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005105}
}