博弈论的五个入门结论(博弈论速成指南)

选自TowardsDataScience

作者:Jesus Rodriguez

机器之心编译

参与:魔王、杜伟

随着人工智能的发展,博弈论迎来了复兴。关于博弈论,数据科学家需要了解哪些经典思想和新思路呢?本文作者就这些问题一一展开了分析。通过此文,相信读者会对博弈论的概念和分类有更清晰的理解。

博弈论的五个入门结论(博弈论速成指南)(1)

博弈论是最让人着迷的数学领域之一,它影响了多个不同领域,如经济学、社会科学、生物学,显然还有计算机科学。博弈论的定义有很多,但我认为以下这个定义非常有帮助,尽管它过分简洁:

博弈论是具备激励机制的概率。

游戏在人工智能发展过程中起到关键作用。对于初学者而言,游戏环境在强化学习或模仿学习等领域中逐渐成为流行的训练机制。理论上,任何多智能体 AI 系统都要经历玩家之间的游戏化交互。构建游戏原则的数学分支正是博弈论。在人工智能语境和深度学习系统语境下,要想使多智能体环境具备一些必备的重要能力,博弈论必不可少。在多智能体环境中,不同的 AI 程序需要交互或竞争才能达成目标。

博弈论的历史与计算机科学史密不可分。目前博弈论领域中的许多研究可以追溯至阿兰·图灵、冯·诺伊曼这些计算机科学先驱的工作。因电影《美丽心灵》而闻名于世的纳什均衡(Nash equilibrium)是现代系统中很多 AI 交互的基础。但是,利用博弈论原则多次建模 AI 宇宙超出了纳什均衡的范畴。想理解如何利用博弈论构建 AI 系统,最好先理解我们在社会或经济互动中常遇到的博弈类型

我们每天参与数百种基于游戏动态(game dynamics)的交互。但是,游戏化环境的架构与此完全不同,其激励和参与者目的也不相同。如何将这些原则应用到 AI 智能体建模中呢?这个难题推动 AI 研究某些领域的发展,如多智能体强化学习。

显然,游戏是博弈论最具可见性的实体,但它远远不是应用博弈论概念的唯一空间。也就是说,还有很多其他领域也受到博弈论和 AI 的共同影响。大多数需要多个「参与者」合作或竞争才能完成任务的场景都可以利用 AI 技术进行游戏化和改进。尽管之前的陈述是一种泛化,但我认为它传达出了一个信息:博弈论和 AI 是一种思考和建模软件系统的方式,而不只是一种技术。

利用博弈论的 AI 场景应包含不止一个参与者。例如,Salesforce Einstein 这类销售预测优化 AI 系统就不是应用博弈论原则的完美场景。但是,在多智能体环境中,博弈论又有明显不同。

在 AI 系统中建构游戏动态需要两步:

博弈论的五个入门结论(博弈论速成指南)(2)

  • 参与者设计:博弈论可用来优化参与者的决策,以获得最大效用;
  • 机制设计:逆博弈论(inverse game theory)主要为一组智能参与者设计游戏。拍卖就是机制设计的经典案例。

那么 AI 时代的数据科学家又需要了解哪些博弈呢?这些博弈彼此之间是否存在着联系呢?本文作者、Invector Labs 首席科学家兼执行合伙人 Jesus Rodriguez 对此发表了自己的看法。

博弈论的五个入门结论(博弈论速成指南)(3)

本文作者 Jesus Rodriguez。

数据科学家应该知道的 5 种博弈

假设我们正在构建一个需要多个智能体互相合作竞争才能完成特定目标的 AI 系统,即博弈论的经典场景。自 20 世纪 40 年代诞生以来,博弈论专注于建模最常见的交互模式,现在我们每天在多智能体 AI 系统中看到的就是它们。理解环境中不同类型的游戏动态是设计高效游戏化 AI 系统的关键元素。从较高层次来看,五元素标准有助于理解 AI 环境中的游戏动态,即对称 vs 非对称、完美信息 vs 非完美信息、合作 vs 非合作、同时 vs 序列和零和 vs 非零和。下面将一一展开介绍。

博弈论的五个入门结论(博弈论速成指南)(4)

作者提出的五元素标准。

对称 vs 非对称

最简单的一种博弈分类方式是根据对称性进行分类。在对称博弈环境里,每个玩家具备同样的目标,结果仅取决于策略。国际象棋就是一种经典的对称博弈。我们在现实世界中遇到的很多场景缺少对称的数学优雅性,因为参与者通常目标不同,甚至还存在冲突。商务谈判则属于非对称博弈,参与各方目标不同,并从不同的角度来评估结果(例如,赢得合同 vs 最小化投资)。

完美信息 vs 不完美信息

另一种重要的博弈分类方式基于可获取信息类型。完美信息博弈指每个玩家都能够看到其他玩家的行动,例如国际象棋。在很多现代交互的环境中,每个玩家的行动是对别人隐藏的,博弈论将这些场景归类为不完美信息博弈。从扑克等纸牌游戏到自动驾驶汽车,不完美游戏博弈就在我们身边。

合作 vs 非合作

在合作博弈环境中,不同的参与者可以通过结盟来最大化最终结果。合同谈判通常被认为是合作博弈。在非合作博弈环境中,参与者禁止结盟。战争是非合作博弈的终极案例。

同时 vs 序列

在序列博弈环境中,每个玩家了解对手之前的动作。棋盘游戏本质上最具序列博弈属性。在同时博弈场景中,双方可以同时行动,例如证券交易。

零和 vs 非零和

零和游戏指一方有得其他方必有失,例如棋盘游戏。非零和游戏中,多个玩家可以从其他玩家的动作中获益。经济交互中多个参与者合作扩大市场规模就是非零和博弈。

纳什均衡

对称博弈统治 AI 世界,其中大多数基于 20 世纪最著名的数学理论之一:纳什均衡。纳什均衡以美国数学家 John Forbes Nash 命名。本质上,纳什均衡描述了这样的场景:每个玩家选择一个策略,当一个玩家不改变策略时,没有玩家能从改变策略中获益。

博弈论的五个入门结论(博弈论速成指南)(5)

已故美国数学家、经济学家 John Nash。

纳什均衡是一个优美且强大的数学模型,它可以解决很多博弈论问题,但在一些对称博弈环境中捉襟见肘。对于初学者而言,纳什方法假设玩家具备无限的计算能力,而现实环境中几乎不存在这种情况。

此外,很多纳什均衡模型无法解释风险概念(常见于大多数非对称博弈场景,如经济市场)。因此,很多非对称博弈场景很难利用纳什均衡实现。在多智能体 AI 系统中这一点尤为重要,这需要在解决方案的数学优雅性和实现的可行性中找到合适的平衡。

博弈论中正在影响机器学习的新想法

多智能体 AI 系统是 AI 生态系统中最让人着迷的领域之一。多智能体系统等领域的近期进展扩展了博弈论的边界,它依赖该领域中最复杂的思想。作者在下文又列举了出现在现代机器学习中的博弈论子领域的示例。

平均场博弈

平均场博弈(Mean Field-Games,MFG)是博弈论中比较新的领域。MFG 理论诞生于 2006 年,是 Minyi Huang、Roland Malhamé、Peter Caines、Jean-Michel Lasry 和菲尔兹奖得主 Pierre-Louis Lions 发表的一系列独立论文中的一篇。

从概念上看,MFG 包含的方法和技术用于研究由「理性博弈方」组成的大群体下的微分博弈。这些智能体不光对自己的状态(如财富、资产)有偏好,对群体中其他智能体的分布也存在偏好。MFG 理论为这些系统研究泛化纳什均衡。

经典的案例是如何让几个鱼群以比较协调的方式沿相同方向游动。理论上,这种现象很难解释,不过它基于这一事实:鱼对最邻近鱼群的行为有反应。具体而言,每条鱼并不关心其他鱼,但是它关心附近作为一个整体统一移动的鱼群。如果我们用数学术语表述的话,鱼对鱼群的反应是哈密顿-雅可比-贝尔曼方程(Hamilton-Jacobi-Bellman equation,简称 HJB 方程)。而整个鱼群的行动是所有鱼的动作集合,这对应了福克-普朗克方程(Fokker-Planck-Kolmogorov equation)。平均场博弈理论是这两个公式的结合体。

博弈论的五个入门结论(博弈论速成指南)(6)

平均场博弈中的鱼群统一游动经典案例。

随机博弈

随机博弈可以追溯至 1950 年代,由诺贝尔经济学奖获得者 Lloyd Shapley 提出。从概念上来看,随机博弈由有限数量的玩家在有限状态空间中执行,在每个状态中,每个玩家从有限多的动作中选择一个;最终动作组合决定了每个玩家的奖励和下一个状态的概率分布。

博弈论的五个入门结论(博弈论速成指南)(7)

已故数学家、随机博弈概念提出者 Lloyd Shapley。

随机博弈的经典形式是哲学家晚餐问题:有 n 1 位哲学家 (n ≥ 1) 坐在圆桌旁,圆桌中间有一碗米饭,任意两位相邻的哲学家之间有一根筷子,筷子在两人可及范围内。由于桌子是圆的,因此筷子的数量与哲学家人数一样。为了吃到碗中的米饭,每位哲学家需要拿到可及范围内的两根筷子。如果一位科学家吃到了,那么他的两位邻座就不能同时吃到。哲学家的生活很简单,只有思考和吃饭,为了生存,哲学家必须一次次地思考和吃饭。该任务就是设计一个使所有哲学家生存下去的机制。

博弈论的五个入门结论(博弈论速成指南)(8)

随机博弈中的哲学家晚餐经典案例。

演化博弈

演化博弈论(Evolutionary Game Theory,EGT)从达尔文进化论中获得灵感。EGT 的起源可以追溯至 1973 年的 John Maynard Smith 和 George R. Price,也可以作为策略来分析,该数学标准可用于预测竞争策略的结果。

从概念上看,EGT 是博弈论概念在如下场景中的应用:通过选择和复制的进化过程,随着时间的变化,智能体群体使用不同策略来创建稳定的解决方案。EGT 的主要思想是很多行为涉及群体中多个智能体的交互,任意一个智能体的成果都离不开其策略与其他智能体策略之间的交互。经典博弈论专注于静态策略(即策略不随时间变化),而演化博弈论专注于策略随时间的变化,以及在进化过程中最成功的动态策略。

EGT 的经典案例是鹰鸽博弈,即让鹰和鸽子围绕可共用资源竞赛。在该游戏中,每位选手严格遵循以下策略中的一个或全部:

  • 鹰:发起攻击行为,在受伤或对手后退之前绝不停下。
  • 鸽:如果对手发起攻击行为,直接撤退。

如果我们假设存在如下情况:1)当两个个体都发起攻击行为时,战斗最终走向结束,二者具备同等受伤概率;2)战斗成本将个体的健康度降低了某个常量 C;3)当鹰鸽相遇时,鸽子直接逃跑,鹰获取资源;4)两只鸽子遇到资源并平分资源,则鹰鸽博弈的健康情况如下所示:

博弈论的五个入门结论(博弈论速成指南)(9)

逆博弈论

很多案例不需要优化参与者的策略,而是围绕理智参与者的行为设计游戏,这就是逆博弈论。拍卖被认为是逆博弈论中的主要案例。

总之,随着人工智能的发展,博弈论正在复兴。阿兰·图灵或冯·诺伊曼等计算机科学界传奇人物提出的博弈论原则现在已经是全球某些最智能系统的核心,人工智能近期进展也有助于推动博弈论研究的发展。随着 AI 继续进化,我们将看到更多博弈论新想法找到融入主流深度学习系统的方式。

原文链接:towardsdatascience/a-crash-course-in-game-theory-for-machine-learning-classic-and-new-ideas-50e33ba2636d

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页