[数据结构与算法]【博弈论-完全信息动态博弈】 子精炼博弈Nash均衡

子博弈精炼Nash均衡的定义

子博弈精炼Nash均衡的定义

扩展式博弈同样面临Nash均衡的多重性问题，而且有些均衡是明显不合理的。

子博弈

子博弈就是原博弈的一部分，它始于原博弈中一个位于单结信息集中的决策结，并由决策结$x$及后续结共同组成。

子博弈可以作为一个独立的博弈进行分析，并且与原博弈具有相同的信息结构。

定义6.1 扩展式博弈的战略组合$s^{?}$是一个子博弈精炼Nash均衡，当切仅当满足以下条件：

1. 它是原博弈的Nash均衡；
2. 它在每一个子博弈上给出Nash均衡。

说明：一个战略组合的子博弈精炼Nash均衡当且仅当它对所有的子博弈构成Nash均衡。

定理6.1 每个有限的扩展式博弈都存在子博弈精炼Nash均衡。

子博弈精炼Nash均衡的求解——逆向归纳法

有限扩展式博弈的一般步骤：

1. 找出博弈的所有子博弈；
2. 按照博弈进程的“反方向”，逐一求解各个子博弈，即最先求解最底层的子博弈再求解上一层的子博弈；

逆向归纳法对于完美信息的博弈问题尤为适用，所谓完美信息的博弈，是指每个参与人决策时都没有不确定性，也就是说，在博弈树中每个参与人的信息集都是单决策结的。

对于完美信息的博弈，子博弈精炼Nash均衡完全满足动态规划的最优性原理。

子博弈精炼的Nash均衡不仅在均衡路径上给出参与人的最优选择，而且在非均衡路径上也能给出参与人的最优选择。

但是Nash均衡给出的选择可能在非均衡路径上不是最优的，此时，这种战略称为“不可置信的威胁”。

逆向归纳法从本质上讲是一种重复剔除劣战略的过程，但是我们不能直接用重复剔除劣战略的思想来求解。

海盗分金问题

承诺行动和要挟诉讼

承诺行动

(不开发,(开发,开发))由于含有不可置信的威胁而不能成为子博弈精炼Nash均衡。

但是，如果在博弈开始之前，企业2采取某种行动使自己的支付发生改变，那么原来不可置信的威胁就可能变得可信。

企业2先花了1000万购买一手研发设备，那么博弈就成为了：

此时之前的不可置信的威胁就成为了购买设备这条子树的子精炼博弈的Nash均衡。

也就是说，企业2通过提前购买设备，使得自己在随后的博弈过程中无论如何都必须选择“开发”。此时，“企业2无论如何都会选择开发”这种战略，对企业1来说是可信的。

“企业2提前购买设备”这种行为在博弈论中称为“承诺行动”。

从本质上讲，承诺行动就是在博弈开始之前参与人采取的某种改变自己支付或行动空间的行动，该行动可使原本不可信的威胁变得可信。

参与人的承诺行动是有成本的，否则这种承诺就不可信。

由于这个成本在企业2采取承诺行动之后是无法收回的，因此也称为“沉淀成本”。

这一案例展现的是支付空间的改变。接下来给出行动空间的改变的案例。

应用——要挟诉讼

所谓要挟诉讼，指的是原告几乎不可能胜诉而其唯一的目的可能是希望通过私了得到一笔赔偿的诉讼。

下面给出要挟诉讼的模型。

通过逆向归纳法可以求出博弈的子博弈精炼Nash均衡位$$((不指控,要求赔偿,放弃),拒绝)$$

上述模型中，“要挟”之所以没有成功，关键在于原告将会起诉的威胁并不可信。

我们可以采取的承诺行动是，在指控被告的同时，甚至在指控之前就将诉讼费$p$支付给律师，无论以后是否上法庭，这笔费用都不退还。

$s>\gamma x$时，原告才会愿意私了而不是上法庭；
$s<\gamma x+d$时，被告将愿意私了而不是上法庭；

因此存在了一个私了的区域$[\gamma x,\gamma x+d]$。

同时，被告也可以采取自己的承诺行动来避免一些无端指控，即在关于私了的协商未开始前，预先支付律师费，也不能收回。

那么要挟诉讼中的私了区域是$[\gamma x,\gamma x+d?f]$。沉淀成本$f$的存在使得私了的区域变小。

虽然采取承诺行动可以一定程度上减少被告可能遇到的无端状况，但是被告在设置沉淀成本$f$时，还面临两个问题：

1. 被告如何设定$f$的大小。$f$过大，对被告来讲可能得不偿失；$f$过小又可能无法有效阻止各种无端指控的发送；
2. 被告何时设置。如果预先支付了，但指控没有发送，这笔钱就浪费了；好的方法是购买法律保险。

子博弈精炼Nash均衡的特性

子博弈精炼Nash均衡的合理性

子博弈精炼Nash均衡与人们直觉的差异

子博弈精炼Nash均衡的特性是：不仅要求在博弈到达的路径上参与人的选择最优，而且要求在博弈没有达到的路上参与人的选择也要最优。

差异的原因：现实中人们的理性最多能确保在博弈到达的路径上人们的选择最优。

只看到了自己预测到的结果，忽视了自己没预测到的结果，没有综合考虑。

蜈蚣博弈的唯一子博弈精炼Nash均衡是：在博弈的任一阶段，每个参与人都选择终止博弈。

但是实验表明，大部分人会在60～70轮之间进行终止。

逆向归纳法对理性的要求

子博弈精炼Nash均衡不仅要求“参与人完全理性”，而且要求“参与人完全理性”为共同知识，否则无法采用逆向归纳法求解。

同时，有些情况下还要求每个参与人不会“犯错误”，而且要求每个参与人都会预期到其他人不会犯错误。

子博弈精炼Nash均衡的唯一性

提出子博弈精炼Nash均衡的主要目的是克服Nash均衡的多重性。但是我们讨论的博弈问题仍然可能存在多个子博弈精炼Nash均衡。

在完美信息扩展博弈中，如果不存在这样的参与人，该参与人在某一决策结上对自己的选择所导致的结果是无差异的，那么博弈存在唯一的子博弈精炼Nash均衡。

如果有这样的参与人，选择对自己的选择导致的结果无差异，那么博弈会存在多个子博弈精炼Nahs均衡。

上述结论只适用于完美信息的扩展式博弈，对信息完全但是不完美的扩展式博弈不一定适用。

那么关于信息完全但不完美的博弈存在唯一子博弈精炼Nash均衡的条件：如果博弈的每个子博弈都只存在唯一的Nash均衡，那么该博弈只有唯一的子博弈精炼Nash均衡。