一句话：将 Perspective 博弈扩展到多玩家、联盟与非零和，证明不可判定边界，并给出两人非零和可判定与理性合成结果。
Perspective 博弈建模多智能体系统，其中每个智能体只能观察系统中属于自己的部分。与基于观察的部分可见性不同，这里的不确定性是横向的：智能体完整观察部分历史，而非部分观察完整历史。已有工作仅研究零和两人 Perspective 博弈。本文研究更丰富的多玩家设定，区分零和、联盟零和以及非零和博弈；在非零和情形关注 Nash 均衡等稳定结果。作者证明，横向不确定性与纵向不确定性类似，当玩家数至少为三且包含联盟或非零和目标时问题不可判定。随后聚焦两人非零和 Perspective 博弈，证明寻找和推理稳定结果可判定，且与完全可视博弈具有相同复杂度。文章还研究 Perspective 下的 rational synthesis，即生成与理性环境交互时满足规约的系统，覆盖自动机或 LTL 表示的布尔目标，以及取值在 [0,1] 的 LTL[F] 多值目标，智能体在此类多值设定中最大化满足值。
Perspective games model multi-agent systems in which agents can view only the parts of the system that they own. Unlike the observation-based model of partial visibility, where uncertainty is longitudinal – agents partially observe the full history, uncertainty in perspective games is transverse – agents fully observe parts of the history. So far, researchers studied zero-sum two-player perspective games. There, the objective of one agent (the system) is to satisfy a given specification, and the objective of the second agent (the environment) is to fail the specification.We study richer and more realistic settings of perspective games. We consider games with more than two players, and distinguish between zero-sum games, where the objectives of the players form a partition of all possible behaviors, zero-sum games among coalitions, where agents in a coalition share their objectives but do not share their visibility, and non-zero-sum games, where each agent has her own objectives and is assumed to be rational rather than hostile. In the non-zero-sum setting, we are interested in stable outcomes of the game; in particular, Nash equilibria.We show that, as is the case with longitudinal uncertainty, transverse uncertainty leads to undecidability in settings with three or more players that include coalitions or non-zero-sum objectives. We then focus on two-player non-zero-sum perspective games. There, finding and reasoning about stable outcomes is decidable, and in fact, unlike the case with longitudinal uncertainty, can be done in the same complexity as in games with full visibility. In particular, we study rational synthesis in the perspective setting, where the goal is to generate systems that satisfy their specification when interacting with rational environments. Our study includes Boolean objectives given by automata or LTL formulas, as well as a multi-valued setting, where the objectives are ${\text{LTL}}\left[ {\mathcal{F}} \right]$ formulas with satisfaction values in [0, 1], and the agents aim to maximize the satisfaction value of their objectives.
DOI 原文 ·
@inproceedings{paperbot6238,
title = {Perspective Multi-Player Games},
author = {Orna Kupferman and Noam Shenwald},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470616}
}