Nash Equilibrium and Bisimulation Invariance
Nash Equilibrium and Bisimulation Invariance
复制标题
纳什均衡和互模拟不变性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Wooldridge
中科院分区：
文献类型：
--
作者：
Julian Gutierrez;Paul Harrenstein;Giuseppe Perelli;M. Wooldridge
博弈论为分析并发和多智能体系统提供了一个完善的框架。基本思想是并发进程（代理）可以理解为对应于游戏中的玩家； play 代表系统可能的计算运行；策略定义了代理的行为。通常，策略被建模为从系统状态序列到玩家动作的函数。以这种方式分析系统涉及计算博弈中的（纳什）均衡集。然而，我们表明，对于上述策略模型（文献中的标准模型），双相似性并不能保持纳什均衡的存在。因此，从语义的角度来看，两个并发游戏在行为上是等效的，并且从逻辑的角度来看，满足相同的时间公式，但从博弈论的角度来看，它们具有根本不同的属性。在本文中，我们探讨了这一发现所提出的问题，并研究了在双相似性下保留纳什均衡存在的三种策略模型。我们还使用其中一些策略模型为策略推理逻辑提供新的语义基础，并研究限制场景，在这些场景中，相对于文献中的传统策略模型，可以显示出双相似性以保持纳什均衡的存在。
Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies---the standard model in the literature---bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.