Rational verification is the problem of determining which temporal logic properties will hold in a multi-agent system, under the assumption that agents in the system act rationally, by choosing strategies that collectively form a game-theoretic equilibrium. Previous work in this area has largely focussed on deterministic systems. In this paper, we develop the theory and algorithms for rational verification in probabilistic systems. We focus on concurrent stochastic games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments. We study the rational verification problem for both non-cooperative games and cooperative games in the qualitative probabilistic setting. In the former case, we consider LTL properties satisfied by the Nash equilibria of the game and in the latter case LTL properties satisfied by the core. In both cases, we show that the problem is 2EXPTIME-complete, thus not harder than the much simpler verification problem of model checking LTL properties of systems modelled as Markov decision processes (MDPs).


翻译:合理核查是确定多试剂系统中的时间逻辑属性将维持在多试剂系统中的问题,其假设是,系统中的代理商通过选择集体形成游戏理论平衡的战略来理性地行事。这一领域的以往工作主要侧重于确定性系统。在本文中,我们开发了理论和算法,以便在概率系统中进行合理核查。我们侧重于并行的随机游戏(CSGs),可用于模拟复杂多试剂环境中的不确定性和随机性。我们研究了在定性概率环境下不合作游戏和合作游戏的合理核查问题。在前一种情况下,我们考虑了Nash对游戏的平衡性满意的LTL特性,而在后一种情况下,我们考虑了核心满足的LTL特性。在这两种情况下,我们都表明问题已经完成了2EXPTIME,因此不比以Markov(MDPs)为模型的系统对LTL特性进行示范检查的简单核查问题要难得多。

0
下载
关闭预览

相关内容

专知会员服务
91+阅读 · 2021年8月28日
专知会员服务
28+阅读 · 2021年8月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
168+阅读 · 2019年10月11日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
0+阅读 · 2021年9月23日
Arxiv
7+阅读 · 2018年3月21日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员