一句话：系统研究零/一/二人可达性切换博弈的判定复杂度，并证明其比随机博弈版本更难。
本文研究零人、一人和二人可达性切换博弈（reachability switching games）的胜者判定问题。切换博弈是随机博弈的确定性类比。作者在通常的显式模型与简洁表示模型下开展复杂度分析：零人情形是 NL-难，简洁表示下为 P-难且上界为 NP∩coNP；一人情形是 NP-完全；二人情形是 PSPACE-难且属于 EXPTIME。对于一人和二人情形，结果在两种模型下均成立。研究还表明，同一博弈的切换变体在复杂度意义下难于对应的随机版本，揭示了确定性切换机制带来的计算代价。
We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP $\cap$ coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. Our results show that the switching variant of a game is harder in complexity-theoretic terms than the corresponding stochastic version.
@article{paperbot1318,
title = {Reachability Switching Games},
author = {John Fearnley and Martin Gairing and Matthias Mnich and Rahul Savani},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 2},
year = {2021},
doi = {10.23638/lmcs-17(2:10)2021}
}