一句话：研究不完全信息下多玩家非零和游戏的理性合成，证明二人奇偶目标为 ExpTime 完全，三人以上不可判定。
论文研究有限图上回合制多玩家非零和博弈的理性合成，目标为 omega-regular 性质，理性由 Nash 均衡（NE）形式化。与完全信息不同，不完全信息下 NE 未必存在，故作者研究 NE 存在性。结果表明：二人奇偶目标的 NE 存在性问题是 ExpTime 完全的（即使双方均不完全信息），超过二人不可判定；理性合成在二人不完全信息玩家时也是 ExpTime 完全的，超过三人不可判定。对于系统（Player 0）对抗由 k 个玩家组成的理性环境且仅 Player 0 不完全信息的情形，当 k 任意但固定时结果为 ExpTime 完全；作者还分析了 k 作为输入一部分时的复杂度。
In this paper, we study the rational synthesis problem for turn-based multiplayer non zero-sum games played on finite graphs for omega-regular objectives. Rationality is formalized by the concept of Nash equilibrium (NE). Contrary to previous works, we consider here the more general and more practically relevant case where players are imperfectly informed. In sharp contrast with the perfect information case, NE are not guaranteed to exist in this more general setting. This motivates the study of the NE existence problem. We show that this problem is ExpTime-C for parity objectives in the two-player case (even if both players are imperfectly informed) and undecidable for more than 2 players. We then study the rational synthesis problem and show that the problem is also ExpTime-C for two imperfectly informed players and undecidable for more than 3 players. As the rational synthesis problem considers a system (Player 0) playing against a rational environment (composed of k players), we also consider the natural case where only Player 0 is imperfectly informed about the state of the environment (and the environment is considered as perfectly informed). In this case, we show that the ExpTime-C result holds when k is arbitrary but fixed. We also analyse the complexity when k is part of the input.
DOI 原文 ·
@inproceedings{paperbot4356,
title = {Rational Synthesis Under Imperfect Information},
author = {Emmanuel Filiot and Raffaella Gentilini and Jean-François Raskin},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209164}
}