论文标题
并发游戏带有多个拓扑
Concurrent Games with Multiple Topologies
论文作者
论文摘要
与$ω$ regarbular目标的并发多游戏游戏是由几个相互作用组件组成的系统的标准模型，每个组件都有自己的目标。此类游戏的标准解决方案概念是NASH平衡，这是玩家的“稳定”策略概况。 在许多设置中，由于内部变量，相互作用的组件（例如，由于相互作用的组件）无法完全观察到系统。然后，互动由部分信息游戏建模。不幸的是，众所周知，部分信息游戏是否具有NE是可决定的。当系统分配过程ID时，自然会出现部分信息的特定设置，但是这些ID在流程中不知道。然后，这些过程具有有关系统状态的完整信息，但不确定其行动对过渡的影响。 我们概括了上面的设置，并引入了多人游戏游戏（MTGS） - 并发游戏具有几种可能的拓扑结构，玩家不知道实际使用了哪种拓扑。我们表明，将NE的概念扩展到这些游戏可以采用几种形式。为此，我们提出了两个NE：保守的NE概念，如果玩家可以严格地在获胜的场景中添加拓扑，以及贪婪的NE，如果她能够在以前失去的拓扑中获胜，她会偏离她的痛苦。我们研究了这些NE的特性，并表明游戏是否承认它们的问题是可决定的。
Concurrent multi-player games with $ω$-regular objectives are a standard model for systems that consist of several interacting components, each with its own objective. The standard solution concept for such games is Nash Equilibrium, which is a "stable" strategy profile for the players. In many settings, the system is not fully observable by the interacting components, e.g., due to internal variables. Then, the interaction is modelled by a partial information game. Unfortunately, the problem of whether a partial information game has an NE is not known to be decidable. A particular setting of partial information arises naturally when processes are assigned IDs by the system, but these IDs are not known to the processes. Then, the processes have full information about the state of the system, but are uncertain of the effect of their actions on the transitions. We generalize the setting above and introduce Multi-Topology Games (MTGs) -- concurrent games with several possible topologies, where the players do not know which topology is actually used. We show that extending the concept of NE to these games can take several forms. To this end, we propose two notions of NE: Conservative NE, in which a player deviates if she can strictly add topologies to her winning set, and Greedy NE, where she deviates if she can win in a previously-losing topology. We study the properties of these NE, and show that the problem of whether a game admits them is decidable.
