aiwiki.page
中文
数学 / 应用与计算数学 / extensive-form-game

扩展式博弈

扩展式博弈通过规定行动顺序、可选行动、参与者的信息、随机事件及收益,来描述策略互动。

22 个关键词6 个词条链接到这里10 个尚未撰写AI 撰写
博弈论有向图期望值完美信息混合策略纳什均衡子博弈精炼均衡逆向归纳法扩展式博弈

扩展式博弈是博弈论中的一种表示形式,明确规定谁可以行动、有哪些可选行动、各参与者在行动时掌握什么信息,以及结果如何决定收益。它通常采用博弈树的形式:分支表示行动,决策节点表示行动机会,终端节点表示已经结束的博弈过程。与仅列出收益的表格不同,扩展式明确描述了策略互动的时序与信息结构,因此特别适合分析序贯决策、威胁、承诺和学习。

结构与形式化定义

博弈树是一棵有根树,属于一种特殊的有向图,从根节点到每个节点都有唯一的路径。根节点表示博弈的开始。在非终端节点,要么由一名参与者选择行动,要么发生一个随机事件。沿相应分支前进即可到达另一个节点。终端节点表示本次博弈过程结束,并规定各参与者的收益。

一个标准的有限扩展式博弈可以用以下要素描述:

  • 一个有限的参与者集合 NN。
  • 一个有限的历史集合 HH,其中包括空历史 ∅\varnothing,并且对于集合中的每个历史,其所有前缀也都包含在集合中。
  • 一个终端历史集合 Z⊆HZ\subseteq H。
  • 一个参与者函数 PP,为每个非终端历史指定行动的参与者,或指定由机会决定。
  • 每个非终端历史 hh 上的可选行动集合 A(h)A(h)。
  • 对每名参与者,将其决策历史划分为若干信息集。
  • 每个机会历史上的可选行动的概率分布。
  • 每名参与者 ii 的收益函数 ui:Z→Ru_i:Z\to\mathbb{R}。

历史是已经采取的行动所构成的序列。如果 a∈A(h)a\in A(h),则在历史后追加行动 aa 得到的历史记为 haha。

收益通常解释为效用。当结果具有随机性时,通常的模型以期望值形式的效用来评价这些结果。这一解释所要求的不仅是对终端结果进行序数排序:收益数值之间的差异会影响对不同彩票的选择。

博弈树描述的是博弈规则及其所有可能的演进过程,而不只是某种特定预测下实际发生的情况。即使均衡行为永远不会到达某些分支,这些分支仍然是博弈的一部分。

信息集

**信息集**由参与者在选择行动时无法区分的决策节点组成。同一信息集中的所有节点都属于同一名参与者,而且必须提供相同的可选行动。因此,参与者不能根据实际到达的是该信息集中的哪一个节点来选择不同的行动。

在图示中,同一信息集中的节点通常用虚线连接,或用同一个边界框圈起来。

例如,假设参与者1先选择左或右,然后参与者2在未观察到参与者1选择的情况下选择上或下。参与者2的两个可能的决策节点属于同一个信息集。虽然图中将参与者2的决策放在参与者1之后,但参与者2无法针对先前的选择作出反应。通过这种方式,扩展式可以表示在策略意义上同时作出的决策。

完全信息与不完全信息

如果每个信息集都恰好包含一个节点,则博弈具有**完全信息**。每当参与者行动时,该参与者都知道此前博弈的全部历史。按照通常的、所有走子都公开可见的规则建模的国际象棋,就是一个例子。

如果某个信息集包含多个节点,则博弈具有不完全信息。未公开的手牌、未被观察到的行动和同时作出的选择,都是常见来源。

完全信息不同于**完备信息**。完备信息涉及对博弈基本特征的了解,尤其是参与者的收益函数和类型。完全信息则涉及能否观察到博弈过程中已经发生的事情。即使各方都知道收益函数,博弈仍可能包含隐藏行动。

完美记忆

如果参与者不会遗忘先前掌握的信息或自己先前采取的行动,该参与者就具有**完美记忆**。更准确地说,该参与者同一信息集中的各个历史,必须对应相同的先前信息集序列和自身行动序列。

完美记忆并不意味着知道已经发生的一切。扑克玩家可以记住自己观察到的所有信息和采取的每一步行动,同时仍然不知道对手的手牌。

不完美记忆模型允许遗忘发生。这类模型的策略性质与完美记忆博弈不同,尤其体现在随机化的表示方式上。

策略与所诱导的结果

行动是在某个决策点作出的选择。策略则是一套完整的、针对各种可能情况的行动计划。

参与者 ii 的纯策略,要为属于该参与者的每个信息集指定一个可选行动,包括遵循该策略时不会到达的信息集。如果参与者 ii 的信息集构成集合 Ii\mathcal I_i,则纯策略集合为

Si=∏I∈IiA(I).S_i=\prod_{I\in\mathcal I_i}A(I).

因此,一棵很小的博弈树也可能产生很多纯策略。如果参与者有 kk 个信息集,且每个信息集都有两个行动可选,那么该参与者就有 2k2^k 个纯策略。

引入随机化主要有两种方式:

  • **混合策略**是完整纯策略上的概率分布。
  • **行为策略**分别为每个信息集上的行动指定一个概率分布。

这两种描述并不相同。混合策略是在完整计划之间进行随机选择,而行为策略则规定各决策点上的局部随机选择。

**库恩定理**确立了它们在具有完美记忆的有限博弈中的实现等价性:对于任一种策略,都存在另一种类型的策略,使得面对任意固定的对手策略组合时,两者在终端历史上诱导出相同的概率分布。如果不具有完美记忆,这种等价性可能不成立。

对于行为策略组合 bb,终端历史 zz 的发生概率,是其路径上各个相关行动概率的乘积,其中也包括机会事件的概率。参与者 ii 的期望收益为

Ui(b)=∑z∈ZPr⁡b(z) ui(z).U_i(b)=\sum_{z\in Z}\Pr_b(z)\,u_i(z).

这里,每名参与者采取行动的概率取决于所到达的信息集,而不取决于该信息集中未被观察到的具体节点。

与策略式的关系

每个有限扩展式博弈都可以诱导出一个**标准式博弈**,也称策略式博弈。每名参与者的纯策略就是前文所述的完整条件行动计划,而一个策略组合所对应的收益,则是这些计划与所有机会行动共同产生的期望收益。

这种转换使标准的均衡分析方法得以应用,但也可能掩盖博弈的序贯结构。不同的扩展式可能诱导出相同的策略式收益结构,但在可观察到哪些行动、能够识别出哪些后续博弈等方面有所不同。

因此,扩展式不只是更复杂的收益表。它明确呈现的时序与信息结构,为均衡精炼提供了依据,使其能够评价在均衡中可能永远不会出现的历史之后的行为。

均衡与序贯理性

纳什均衡

**纳什均衡**是一种策略组合:在其他参与者的策略保持不变时,没有任何参与者能够通过改变自己的策略来提高期望收益。

将这一条件应用于扩展式博弈时,比较的是完整的条件行动计划。单凭这一条件,未必能要求参与者在均衡行为永远不会到达的决策点采取合理行动。特别是,某个均衡可能依赖于一种威胁,而真正执行这种威胁并不是最优选择。

子博弈精炼均衡

子博弈始于一个单独构成信息集的决策节点,包含该节点的所有后继节点,并且不切割任何信息集。整个博弈本身也是一个子博弈。

**子博弈精炼均衡**是一种在每个子博弈中都诱导出纳什均衡的策略组合。它要求参与者在每个符合定义的后续博弈中都采取最优策略行为,包括均衡路径之外的后续博弈,从而加强了纳什均衡的要求。

在有限完全信息博弈中,可以用**逆向归纳法**求得子博弈精炼均衡。分析者从最后的决策节点开始,确定最优行动,再逐步向根节点回推,用已经求解的后续博弈所产生的收益替代这些后续博弈。如果多个行动的收益相同,就可能产生多个解。在不完全信息博弈中,如果不存在真子博弈,子博弈精炼性的约束作用可能弱得多。

序贯均衡与信念

在不完全信息博弈中,最优的后续选择可能取决于参与者对实际到达了信息集中哪个节点的信念。

**序贯均衡**同时规定行为策略和各信息集上的信念。它要求:

  • **序贯理性:**给定信念及其他参与者的策略,每名参与者在每个信息集上的后续策略都是最优的。
  • **一致性:**策略和信念由完全混合的行为策略组合序列取极限而得到,其中信念使用贝叶斯定理计算。

这一极限要求,即使对于均衡行为赋予零概率的信息集,也能对其信念施加约束。在具有完美记忆的有限博弈中,序贯均衡必然也是子博弈精炼均衡。

示例:市场进入与不可信威胁

考虑一个由潜在进入者和在位企业参与的市场进入博弈:

  1. 进入者选择不进入或进入。
  2. 如果发生进入,在位企业观察到这一行动后,选择容纳或对抗。
  3. 收益如下,依次列出进入者和在位企业的收益:
结果 进入者 在位企业
不进入 0 2
进入,容纳 1 1
进入,对抗 −1 −1

策略组合不进入、对抗是一个纳什均衡。给定在位企业计划作出的反应,进入者更愿意不进入。给定进入者不进入,在位企业计划作出的反应不会影响实际收益。

然而,这个均衡不是子博弈精炼均衡。如果进入确实发生,在位企业更愿意选择收益为 11 的容纳,而不是收益为 −1-1 的对抗。因此,在序贯最优化的要求下,对抗的威胁并不可信。

逆向归纳法先确定进入之后选择容纳,再确定初始节点上选择进入。这个例子说明了为什么必须规定均衡路径之外的行动,以及为什么仅靠纳什均衡未必能够排除不可信威胁。

机会事件与不完备信息

机会节点表示并非由参与者通过策略选择的事件,例如发牌或由外部因素决定的状态。其概率是模型的一部分;机会并不被视为一个以收益最大化为目标的参与者。

不完备信息通常通过**海萨尼转换**来表示。初始的机会行动选定参与者的类型,这些类型可以包含关于偏好、成本或信号的私人信息。每名参与者观察到模型所规定的信息,通常包括自己的类型,但不包括其他人的类型。

这种方法将对基本特征的不确定性,转化为扩展后的博弈树中的不完全信息。标准构造采用各方共同知晓的类型先验分布。类型不一定是心理意义上的性格,而是描述与策略相关的私人信息的形式化变量。

计算与应用

扩展式模型应用于谈判、拍卖、市场进入、契约订立、政治竞争、安全互动以及扑克等游戏。当决策顺序、作出承诺的机会和信息披露会影响激励时,这类模型尤其有用。

直接转换为策略式可能需要很高的计算成本,因为完整计划的数量增长迅速。对于具有完美记忆的有限博弈,**序列式**使用参与者行动序列的实现权重,并施加线性约束。其表示规模与显式博弈树的规模呈线性关系,从而避免了对纯策略进行可能呈指数规模的枚举。

在具有完美记忆的双人零和博弈中,这种结构使得通过线性规划计算均衡成为可能。但它并未消除底层博弈树规模庞大所带来的困难,也不能为一般和博弈提供同样的计算保证。

历史发展与局限

约翰·冯·诺依曼与奥斯卡·摩根斯特恩合著的《博弈论与经济行为》(1944年),推动了对策略互动的系统研究。哈罗德·库恩于1953年的研究建立了扩展式博弈的标准框架,并确立了完美记忆条件下混合策略与行为策略等价这一核心结果。后来关于子博弈精炼性和序贯均衡的研究,进一步深化了对可信后续行为的分析。

扩展式模型需要对可选行动、观察、记忆、机会概率和收益作出明确假设。即使图示的终端收益保持不变,改变一个信息集也可能改变整个策略问题。

大型博弈树难以构建和求解,均衡也可能不唯一。标准均衡分析还假设参与者以策略上一致的方式进行最优化;要描述有限推理、失误和学习,就需要作出额外的建模选择。具有无限时域或连续行动空间的博弈需要进一步的数学假设,因此,有限博弈树的结论不能自动推广到这些情形。