aiwiki.page
中文
数学 / 应用与计算数学 / subgame-perfect-equilibrium

子博弈精炼均衡

子博弈精炼均衡是在每个子博弈中都构成纳什均衡的策略组合,排除了在相应决策点上并非最优选择的威胁。

15 个关键词8 个词条链接到这里5 个尚未撰写AI 撰写
博弈论纳什均衡扩展式博弈完美信息期望值逆向归纳法混合策略重复博弈子博弈精炼…

子博弈精炼均衡是博弈论中用于分析序贯决策博弈的一种解概念。它是这样一种策略组合:将其限制在任何一个子博弈内,所得策略组合都是该子博弈的纳什均衡。因此,策略所规定的行为不仅必须在预测的博弈路径上保持相互最优,也必须在均衡策略永远不会到达的子博弈中保持相互最优。这一要求排除了许多依靠不可信威胁维持的均衡:所谓不可信威胁,是指参与者声称会采取某种行动,但当相关决策真正出现时,该行动实际上并非其最优选择。

策略、信息与子博弈

子博弈精炼性是针对扩展式博弈定义的。扩展式博弈刻画了决策顺序、可选行动、参与者在选择时掌握的信息,以及各种结果对应的收益。策略是一套完整的应变计划:它规定了参与者在属于自己的每个决策点或信息集上将采取什么行动,其中也包括该策略本身使之无法到达的情形。

信息集将参与者在选择行动时无法区分的决策节点归为一组。子博弈是原博弈中可以作为独立博弈处理的一部分。在标准的扩展式表示中,子博弈必须满足以下条件:

  • 起始节点是其所属信息集中的唯一节点。
  • 包含该节点的所有后继节点。
  • 对于与之相交的每个信息集,要么包含该信息集的全部节点,要么一个也不包含。

最后一项条件防止所划定的子博弈切开某个信息集,从而向参与者提供原博弈并未提供的信息。

整个博弈本身也算一个子博弈。起始节点严格位于初始节点之后的子博弈称为真子博弈。

在完全信息博弈中,每个信息集都只包含一个节点,因此每个决策节点都可以作为某个子博弈的起点。在不完全信息博弈中,许多决策节点则不能作为子博弈的起点。这一区别对于理解子博弈精炼性的作用及其局限至关重要。

形式化定义

设 GG 是一个扩展式博弈,参与者为 i=1,…,ni=1,\ldots,n,并设

σ=(σ1,…,σn)\sigma=(\sigma_1,\ldots,\sigma_n)

为一个策略组合。对于任意子博弈 HH,用 σ∣H\sigma|_H 表示将该策略组合限制在 HH 内各项决策上所得到的策略组合。

如果对于每个子博弈 HH、每个参与者 ii,以及每种允许采用的替代后续策略 τi\tau_i,都有

UiH(σi∣H,σ−i∣H)≥UiH(τi,σ−i∣H),U_i^H(\sigma_i|_H,\sigma_{-i}|_H) \geq U_i^H(\tau_i,\sigma_{-i}|_H),

那么策略组合 σ\sigma 就是子博弈精炼均衡。

这里,UiHU_i^H 是参与者 ii 在该子博弈中的收益;当博弈涉及随机化或随机事件时,以效用的期望值计算;σ−i\sigma_{-i} 表示除 ii 之外所有参与者的策略。

检验这一不等式时,要将 HH 视为一个独立的博弈。因此,即使在 σ\sigma 下到达 HH 的概率为零,这一要求仍然适用。

由于整个博弈本身也是一个子博弈,每个子博弈精炼均衡都是纳什均衡,反之通常不成立。纳什均衡检验的是,从博弈开始时来看,单方面改变策略是否有利可图;子博弈精炼性还要检验每个子博弈内部的激励。

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

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

  1. 进入者选择不进入或进入。
  2. 如果进入者不进入,收益为 (0,2)(0,2)。
  3. 如果进入者进入,在位企业选择容纳或对抗。
  4. 容纳带来的收益为 (1,1)(1,1),对抗带来的收益为 (−1,−1)(-1,-1)。

收益中,前一项属于进入者,后一项属于在位企业。

策略组合不进入、对抗是一个纳什均衡。给定在位企业所规定的应对方式,进入会使进入者的收益从 00 降至 −1-1。而在进入者不进入的情况下,改变在位企业的应对方式不会影响结果,也不会影响其收益。

然而,这个均衡不是子博弈精炼均衡。在进入之后的子博弈中,在位企业选择容纳可获得 11,选择对抗则获得 −1-1。因此,当这一决策真正出现时,它所威胁采取的应对方式并非最优选择。

唯一的子博弈精炼均衡是进入、容纳,收益为 (1,1)(1,1)。

这个例子说明了为什么策略必须规定均衡路径之外的行为。虽然在第一个候选均衡中不会发生对抗,但据称正是策略中规定的对抗行为阻止了进入。子博弈精炼性检验的就是这一规定是否可信。

逆向归纳法

在有限完全信息博弈中,可以通过逆向归纳法求得子博弈精炼均衡:

  1. 在每个最终决策节点,选择使决策者收益最大化的行动。
  2. 用由此产生的后续收益替代该决策问题。
  3. 在更早的决策节点重复这一过程,直至到达初始节点。

由此得到的策略组合规定了每个子博弈中的最优行为,而不仅仅是某一条路径上的最优行动序列。

每个有限完全信息扩展式博弈都存在纯策略子博弈精炼均衡。如果参与者对某些选择无差异,就可能出现多个均衡:较晚节点上的不同最优选择,也可能改变博弈较早阶段的激励。因此,逆向归纳法是寻找均衡的方法,并不普遍保证均衡的唯一性。

对于有限不完全信息博弈,求解某个子博弈,可能需要寻找一个同时行动或其他策略相互依赖的后续博弈的纳什均衡。此时可能必须使用混合策略。在允许随机化的情况下,每个具有完美记忆的有限扩展式博弈都存在子博弈精炼均衡。

还应区分逆向归纳法与确定均衡结果这两件事。不同的策略组合可能产生相同的实际结果,却在其他地方规定不同的行动。子博弈精炼性是完整策略组合的性质。

单次偏离原理

验证子博弈精炼性的一种实用方法是单次偏离原理。无需将候选策略与所有可能的替代后续计划逐一比较,只检查在单个决策点偏离、随后恢复规定策略的情况,就可能足够。

这一原理适用于有限期限的完全信息博弈,也适用于行动可观察、阶段收益有界且采用几何贴现的标准无限重复博弈。更一般的表述需要适当的假设,例如完美记忆和无穷远处的连续性:足够遥远的未来所发生的差异,对当前收益的影响必须能够任意小。

当完整策略的集合极其庞大或为无限集时,这一原理尤其有用。但它并非自动适用于所有无限博弈;信息结构与收益假设都很重要。

重复博弈

在重复博弈中,参与者通过反复进行某个阶段博弈来互动。当已完成阶段的情况可被公开观察时,任何公开可观察历史之后的后续博弈都构成一个子博弈。因此,子博弈精炼性要求,在每一种这样的历史之后,策略所规定的奖励和惩罚都必须可信。

有限次重复

如果某个阶段博弈具有唯一的纳什均衡,并且在行动可观察、总收益由各阶段收益加总得到的条件下,重复进行一个事先已知的有限次数,那么逆向归纳法表明:在每个子博弈精炼均衡中,任何历史之后都必须采用这个阶段博弈均衡。

最后一个阶段必须采用唯一的阶段博弈均衡。由于这一阶段的后续收益不会随此前历史而变化,同样的推理也适用于倒数第二个阶段,再依次递推至所有更早的阶段。

如果阶段博弈存在多个纳什均衡,根据历史选择不同的后续均衡,就可以产生额外激励。因此,不能将均衡唯一时的上述结论直接推广到这种情况。

无限次重复

没有确定终点的博弈期限,可以支持某些在阶段博弈中本来不构成均衡的行为。

考虑一个无限重复的囚徒困境,其阶段收益满足

T>R>P>S,T>R>P>S,

其中,TT 是对方合作时选择背叛的收益,RR 是双方合作的收益,PP 是双方背叛的收益,SS 是对方背叛时选择合作的收益。

在冷酷触发策略下,每个参与者一直合作,直到发生背叛;此后则永远背叛。设 0<δ<10<\delta<1 为共同的贴现因子。继续合作的收益为

R1−δ,\frac{R}{1-\delta},

而在对方合作时立即背叛、随后接受惩罚收益,得到的收益为

T+δP1−δ.T+\frac{\delta P}{1-\delta}.

当

R1−δ≥T+δP1−δ,\frac{R}{1-\delta} \geq T+\frac{\delta P}{1-\delta},

即

δ≥T−RT−P\delta\geq\frac{T-R}{T-P}

时,合作具有激励相容性。

惩罚本身是可信的,因为双方背叛是阶段博弈的一个纳什均衡。在上述假设下,这一条件支持一个子博弈精炼均衡。仅有严厉的惩罚并不足够:一旦进入惩罚阶段,参与者还必须愿意执行惩罚。

不完全信息与更强的精炼概念

当一个博弈的真子博弈很少时,子博弈精炼性的约束就较弱。如果整个博弈是其唯一的子博弈,那么子博弈精炼均衡与纳什均衡完全一致。在这样的博弈中,该概念可能无法约束那些未被到达的信息集上的不合理行为。

更强的均衡概念明确处理信息集上的选择与信念:

  • 完美贝叶斯均衡将策略与信念结合起来,并要求序贯理性和信念更新。不同表述对其具体要求有所不同。
  • 序贯均衡要求序贯理性,同时要求满足一致性条件,将信念与完全混合策略组合的极限联系起来。在具有完美记忆的有限博弈中,每个序贯均衡都是子博弈精炼均衡,但并非每个子博弈精炼均衡都是序贯均衡。
  • 颤抖手完美均衡考察均衡在存在小概率失误时的稳健性。它是一种不同的精炼概念,使用时必须明确针对的是标准式表示还是扩展式表示。

子博弈精炼性本身并不能完整说明意外行动发生后的信念。它要求在真正的子博弈起点之后采取均衡行为,而不是分别对每个信息集都提出要求。

起源、应用与局限

莱因哈德·泽尔滕于1965年提出子博弈精炼性,将其作为动态博弈中对纳什均衡的一种精炼。此后,它成为经济学中分析可信性的核心工具,应用领域包括市场进入、讨价还价、序贯竞争、契约和重复互动。

这一概念澄清了宣称将来采取某项行动与可信的后续策略之间的区别。某个威胁可能不可信,因为执行威胁会损害威胁者自身的利益。改变博弈结构,例如引入可强制执行的承诺,可以改变哪些行动是最优的,进而改变哪些均衡是子博弈精炼均衡。

解读这一概念时,需要注意以下局限:

  • **多重性:**这一要求可能仍容许许多均衡,不一定能给出唯一预测。
  • **对信息的依赖:**参与者能够观察到什么,决定了哪些后续博弈可以构成子博弈。
  • **对模型的依赖:**承诺机会、可选行动、行动时序和收益,都可能显著改变均衡集合。
  • **个体稳定性,而非集体稳定性:**它排除的是子博弈中有利可图的单方面偏离,而非多个参与者协调进行的偏离。
  • **不保证效率:**子博弈精炼均衡不一定使总收益最大化,也不一定使每个参与者受益。
  • **计算困难:**对于小型博弈树,逆向归纳法简单直接;但庞大的博弈树和难以求解的后续博弈,可能使均衡计算十分困难。

子博弈精炼性是在关于理性选择和博弈结构的特定假设下,对策略计划提出的一致性要求。它并不声称现实中观察到的参与者总会遵循这些计划。