Expressiveness and Complexity Results for Strategic Reasoning

Expressiveness and Complexity Results for Strategic Reasoning
复制标题

策略推理的表现力和复杂性结果

DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Wooldridge
M. Wooldridge
中科院分区：
--
文献类型：
--
作者：
Julian Gutierrez;Paul Harrenstein;M. Wooldridge

文献摘要

被引文献

相似文献

本文提出了多人非零和并发游戏中纳什均衡的规范、计算和验证的一系列表现力和复杂性结果，其中玩家的目标表示为时间逻辑公式。我们的结果基于一种描述此类游戏中均衡的新颖方法：基于获胜策略和记忆推理的语义表征。这种表征使我们能够获得与时态逻辑中的平衡特性分析相关的许多其他结果。我们证明，直到相似性，多人非零和并发博弈中纳什均衡的推理可以在 ATL* 中完成，并且在此类博弈中构建均衡策略配置文件可以使用有限内存策略在 2EXPTIME 中完成。我们还研究了两种更简单的情况，即两人博弈和顺序博弈，并表明后一种情况下的均衡规范可以通过比 ATL* 弱的时序逻辑来获得。基于这些结果，我们解决了一些悬而未决的问题，提出了新的均衡逻辑特征，并为许多问题提供了改进的答案和替代解决方案。 1998 ACM 学科分类 F.4.1 数学逻辑 - 时间逻辑，F.3.1 程序的指定、验证和推理，I.2.11 分布式人工智能 - 多智能体系统
This paper presents a range of expressiveness and complexity results for the specification, computation, and verification of Nash equilibria in multi-player non-zero-sum concurrent games in which players have goals expressed as temporal logic formulae. Our results are based on a novel approach to the characterisation of equilibria in such games: a semantic characterisation based on winning strategies and memoryful reasoning . This characterisation allows us to obtain a number of other results relating to the analysis of equilibrium properties in temporal logic. We show that, up to bisimilarity, reasoning about Nash equilibria in multi-player non-zero-sum concurrent games can be done in ATL ∗ and that constructing equilibrium strategy profiles in such games can be done in 2EXPTIME using finite-memory strategies. We also study two simpler cases, two-player games and sequential games, and show that the specification of equilibria in the latter setting can be obtained in a temporal logic that is weaker than ATL ∗ . Based on these results, we settle a few open problems, put forward new logical characterisations of equilibria, and provide improved answers and alternative solutions to a number of questions. 1998 ACM Subject Classification F.4.1 Mathematical logic – Temporal logic, F.3.1 Specifying and Verifying and Reasoning about Programs, I.2.11 Distributed Artificial Intelligence – Multia-gent systems