Nash Equilibria in Finite-Horizon Multiagent Concurrent Games
Nash Equilibria in Finite-Horizon Multiagent Concurrent Games
复制标题
有限视野多智能体并发博弈中的纳什均衡
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Moshe Y. Vardi
中科院分区：
文献类型：
--
作者：
S. Rajasekaran;Moshe Y. Vardi
在具有有限时间目标的多智能体并发博弈中寻找纯策略纳什均衡的问题最近受到了一些关注。早期的工作通过使用拉宾自动机解决了这个问题。在这项工作中，我们采取了代理人的目标的有限时域性质的概述，并表明，检查和寻找纯策略纳什均衡可以使用安全游戏和套索测试在Büchi自动机的组合来完成。为了将策略推理与时间推理分开，我们通过确定性有限词自动机（DFA）对智能体的目标进行建模，因为LTL f和LDL f等有限时域逻辑是通过转换为等效DFA来推理的。这使我们能够将问题的复杂性描述为PSPACE完全。
The problem of finding pure strategy Nash equilibria in multiagent concurrent games with finite-horizon temporal goals has received some recent attention. Earlier work solved this problem through the use of Rabin automata. In this work, we take advan-tage of the finite-horizon nature of the agents’ goals and show that checking for and finding pure strategy Nash equilibria can be done using a combination of safety games and lasso testing in Büchi automata. To separate strategic reasoning from temporal reasoning, we model agents’ goals by deterministic finite-word automata (DFAs), since finite-horizon logics such as LTL f and LDL f are reasoned about through conversion to equivalent DFAs. This allows us to characterize the complexity of the problem as PSPACE com-plete.
DOI：
10.4204/eptcs.326.1
发表时间：
2020-09
期刊：
--
影响因子：
--
作者：
L. M. Tabajara;Moshe Y. Vardi
通讯作者：
L. M. Tabajara;Moshe Y. Vardi