DeepMind发表Nature论文提出非对称博弈的降维方法

近日,DeepMind 在 Scientific Report 上发表论文《Symmetric Decomposition of Asymmetric Games》,表明一个非对称博弈可以分解为多个对称博弈,从而将博弈降维,并且非对称博弈和对称变体的纳什均衡也有非常简单的对应关系。


随着 AI 系统在现实世界中扮演的角色越来越重要,理解不同系统之间如何交互变得非常关键。


DeepMind 最新在 Scientific Report 上发表了一篇论文《Symmetric Decomposition of Asymmetric Games》,使用了博弈论的一个分支来解决这个问题。具体来说,DeepMind 研究者检验了两个智能系统在非对称博弈游戏(asymmetric game,包括 Leduc 扑克和多种棋牌游戏)的特定类型情景下的行为和反应。非对称博弈还可以自然地对现实世界场景建模,例如自动拍卖,其中买家和卖家以不同的动机行动。研究结果给出了对这些场景的新洞察,揭示了一种非常简单的分析方法。虽然 DeepMind 的兴趣主要在于如何将该理论应用到多个 AI 系统的交互中,但研究者相信这些结果还可以应用到经济学、进化生物学和经验博弈论(empirical game theory)等。


该方法被证明在数学上是很简单的,允许对非对称博弈进行快速、直接的分析。


博弈论是一种数学理论,用于分析竞争环境中决策者使用的策略,可以在多种情景中应用于人类、动物和计算机。博弈论在研究多智能体环境中很常用,多智能体环境中的系统数量超过一个,例如多个家庭机器人协作打扫房子。传统上通常使用简单的对称博弈游戏来分析多智能体系统的演化动态,例如「囚徒困境」,其中每个玩家都有相同的可选动作。虽然这些博弈游戏可以为多智能体系统的工作方式提供有用的洞察,并告诉我们如何让所有玩家取得想要的结果——即纳什均衡,但是它们无法对所有情景建模。


DeepMind 的新技术允许快速、简单地在更加复杂的非对称博弈中发现可用于实现纳什均衡的策略(非对称博弈游戏中每个玩家都有不同的策略、目标和奖励)。可以通过「性别大战」(一个博弈论研究中常用的协调博弈游戏)的例子展示这些博弈和用于分析它们的新技术。


在性别大战中,两个玩家需要在一个晚上协商去看歌剧还是看电影。两个玩家中,一个略微更喜欢歌剧,另一个更喜欢电影。这个博弈是非对称的,因为虽然两个玩家的可选策略是相同的,但是基于玩家偏好,选项所对应的奖励是不同的。为了维持他们的友谊,或者说均衡,两个玩家需要选择相同的选项,如果选择了不同的选项则收益为零。




该游戏有三个均衡:(i) 两个玩家都决定去歌剧院,(ii) 两人都决定去看电影,(iii) 最后的混合选择,其中每个玩家选择自己偏好的活动的比例为五分之三。最后一个「不稳定」选择可以用 DeepMind 的方法,通过将非对称博弈简化或分解成对称博弈而被迅速发现。这些分解出的对称博弈游戏本质上把每个玩家的奖励表作为一个独立的对称双人博弈,其均衡点与原来的非对称博弈一致。


下图为两个分解出的简单对称博弈游戏绘制了纳什均衡,我们可以快速发现非对称博弈 (a) 中的最优策略。也可以反过来操作,使用非对称博弈发现对称博弈中的均衡。



红点表示纳什均衡。我们可以轻松地从两个分解出的对称博弈游戏 (b) 和 (c) 的绘图中得出非对称博弈 (a)。以上所有图中,x 轴对应于玩家 1 选择歌剧的概率,y 轴对应于玩家 2 选择歌剧的概率。


这一方法也适用于其他游戏,包括论文中详述的 Leduc 扑克。在所有这些情景中,该方法被证明在数学上是简单的,可以快速而直接地分析非对称博弈,我们希望这也有助于我们理解不同的动态系统,包括多智能体环境。


论文:Symmetric Decomposition of Asymmetric Games




论文链接:https://www.nature.com/articles/s41598-018-19194-4


我们提出了关于双人非对称博弈游戏的新理论洞察,允许优雅地将非对称博弈游戏分解为两个单人对称博弈游戏。具体来说,我们展示了如何通过预见和研究构成非对称博弈的收益表(A 和 B),将非对称双矩阵博弈 (A,B) 分解为它的对称变体,即两个独立的、单人的对称博弈。我们揭示了双人非对称博弈与其单人对称博弈之间形式上的多种令人惊讶的关系,促进了对原始非对称博弈进行分析的便利性(因为分解可以降维)。主要的研究成果揭示了,如果 (x,y) 是非对称博弈 (A,B) 的纳什均衡,则 y 是由收益表 A 决定的对称博弈游戏的纳什均衡,x 是由收益表 B 决定的对称博弈游戏的纳什均衡,反之亦然。并且两个单人对称博弈的纳什均衡的组合构成了非对称博弈的纳什均衡。通过在多个标准实例中检验更简单的对称博弈游戏的演化动态,我们展示了这些形式关系如何帮助发现和分析非对称博弈的纳什结构。 


原文链接:https://deepmind.com/blog/game-theory-insights-asymmetric-multi-agent-games/

理论
暂无评论
暂无评论~
返回顶部