一句话：提出视角博弈模型，其中玩家仅观察自己拥有的顶点，并研究其获胜策略判定、ATL*模型检测及策略表达能力。
论文引入视角博弈，建模玩家仅能观察自有顶点的多智能体系统。博弈图顶点由玩家划分，玩家在自有顶点选择后继；视角策略只依赖其自有顶点的访问历史。与基于观察的部分可见性不同，这里的不确定性是横向的：玩家完全观察属于自己的历史顶点。判定玩家是否存在获胜视角策略。纯策略下，确定性/通用奇偶自动机目标为 EXPTIME-完全，LTL 目标为 2EXPTIME-完全，Perspective-ATL* 模型检测同复杂度；对图大小复杂度为多项式，比观察型部分可见博弈指数级容易。概率情形下，几乎获胜随机视角策略不可判定。最后研究 ω-正则目标，比较视角与无记忆策略，并给出允许视角策略的 LTL 片段。
We introduce and study perspective games, which model multi-agent systems in which agents can view only the parts of the system that they own. As in standard multi-player turn-based games, the vertices of the game graph are partitioned among the players. Starting from an initial vertex, the players jointly generate a computation, with each player deciding the successor vertex whenever the generated computation reaches a vertex she owns. A perspective strategy for a player depends only on the history of visits in her vertices. Thus, unlike observation-based models of partial visibility, where uncertainty is longitudinal - players partially observe all vertices in the history, uncertainty in the perspective model is transverse - players fully observe part of the vertices in the history. Perspective games are not determined, and we study the problem of deciding whether a player has a winning perspective strategy. In the pure setting, we show that the problem is EXPTIME-complete for objectives given by a deterministic or universal parity automaton over an alphabet that labels the vertices of the game, and is 2EXPTIME-complete for LTL objectives. Accordingly, so is the model-checking complexity of Perspective-ATL*- an extension of ATL* with path quantification that captures perspective strategies. In all cases, the complexity in the size of the graph is polynomial - exponentially easier than games with observation-based partial visibility. In the probabilistic setting, we show that deciding whether a player has an almost-winning randomized perspective strategy is undecidable. Finally, we study perspective games with objectives given by ω-regular conditions over the set of vertices. In particular, we compare the power of perspective and memoryless strategies and show, for example, that while the generalized-Büchi and the Streett objectives do not admit memoryless strategies, generalized Büehl admits perspective strategies, and Streett does not. We also describe a fragment of LTL that admits perspective strategies.
DOI 原文 ·
@inproceedings{paperbot5002,
title = {Perspective Games},
author = {Orna Kupferman and Gal Vardi},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785662}
}