西安电子科技大学：《智能控制导论》课程教学课件（博弈控制）第七讲 动态博弈分析（下）

历些毛子代枝大学 逆向归纳法 XIDIAN UNIVERSITY 一个例子 D 策略式（收益矩阵）表述 见右下图。 B (2,2） A2 *可见，它有两个纳什均衡： R (3,1)和(2,2)。 (3.1) (0,0) 如果A选择U,B的信息集 B 就不可达，即B的信息集 L R 不在均衡路径上。 U 2,2 2,2 D 3,1 0,0

逆向归纳法  一个例子  策略式(收益矩阵)表述 见右下图。  可见，它有两个纳什均衡: (3, 1) 和 (2, 2)。 如果A选择U, B的信息集 就不可达， 即B的信息集 不在均衡路径上。 L R U 2, 2 2, 2 D 3, 1 0, 0 A B

历安毛子种枚大学 逆向归纳法 XIDIAN UNIVERSITY *逆向归纳法(Backward Induction)是求 解动态博弈纳什均的最简便方法。在求 解动态博弈纳什均斯时，从最后一个子博弈 开始逆推上去，这就是逆向归纳法。所以逆 向归纳法就是从动态博弈的最后一个阶段 或最后一个子博弈开始，逐步向前倒推以求 解动态博弈均的方法

逆向归纳法  逆向归纳法（Backward Induction）是求 解动态博弈纳什均衡的最简便方法。在求 解动态博弈纳什均衡时,从最后一个子博弈 开始逆推上去,这就是逆向归纳法。所以逆 向归纳法就是从动态博弈的最后一个阶段 或最后一个子博弈开始,逐步向前倒推以求 解动态博弈均衡的方法

历安毛子代枚大学 逆向归纳法 XIDIAN UNIVERSITY *从博弈的最后一个阶段开始分析，若B选择L获利 1,选择R获利0，因此B选L。 倒退到第一阶段，A选U获利2，选D获利取决于B 的选择。 *但A知道B是理性的，一旦 到达第二阶段，B肯定选择 D L,从而，A获利3。因此， A应该选择D。 B (2,2) A2 因此，D,L)是纯策略 R 纳什均衡。 (3.1) (0,0)

 从博弈的最后一个阶段开始分析，若B选择L获利 1, 选择R获利0，因此B选L。  倒退到第一阶段，A选U获利2，选D获利取决于B 的选择 。  但A知道B是 理性的，一旦 到达第二阶段，B肯定选择 L，从而，A获利3。因此， A应该选择D。  因此，(D, L)是纯策略 纳什均衡。 逆向归纳法

历安毛子代枚大等 与策略式分析的比较 XIDIAN UNIVERSITY 逆向归纳法实际上是严格 D 下策反复删去法在扩展式 描述的动态博弈中的应用2,2) B A2 *逆向归纳法不适合无限 R 博弈。 *逆向归纳法不适合不 (3,1) (0,0) 完美信息博弈。 B L R 逆向归纳法剔出了非 U 2,2 2,2 理性的均衡策略。 D 3,1 0,0

与策略式分析的比较  逆向归纳法实际上是严格 下策反复删去法在扩展式 描述的动态博弈中的应用。  逆向归纳法不适合无限 博弈。  逆向归纳法不适合不 完美信息博弈。  逆向归纳法剔出了非 理性的均衡策略。 L R U 2, 2 2, 2 D 3, 1 0, 0 A B

历安毛子代枚大学 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 5个海盗抢来100个金币，大家决定分赃的 方式是：由海盗一提出一种分配方案，如果同 意该方案的人数达到半数，则该提议通过并实 施。否则该提议人将被扔进大海，然后由接下 来的海盗重复提议过程。 假定每个人都绝顶聪明，也不相互合作，并 且极度自私，那么第一个海盗该如何提议

逆推归纳法：海盗分赃 5个海盗抢来100个金币，大家决定分赃的 方式是：由海盗一提出一种分配方案，如果同 意该方案的人数达到半数，则该提议通过并实 施。否则该提议人将被扔进大海，然后由接下 来的海盗重复提议过程。 假定每个人都绝顶聪明，也不相互合作，并 且极度自私，那么第一个海盗该如何提议

历安毛子种枚大兽 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 逆推归纳法的求解思路如下： 。首先考虑只剩下最后一个海盗：海盗5，其他四个海盗 己经被扔进大海，显然，他会分给自己100金币，自己 同意并通过。 逆推到只剩下海盗4和海盗5的情况，海盗4会分给自己 100金币，不给海盗5分。海盗4自己同意并通过，海盗5 反对但无用。 。再回到海盗3，海盗3会给海盗5一枚金币以获取他的支 持，给自己99枚，海盗3和海盗5同意并通过

逆推归纳法的求解思路如下：  首先考虑只剩下最后一个海盗：海盗5，其他四个海盗 已经被扔进大海，显然，他会分给自己100金币，自己 同意并通过。  逆推到只剩下海盗4和海盗5的情况，海盗4会分给自己 100金币，不给海盗5分。海盗4自己同意并通过，海盗5 反对但无用。  再回到海盗3，海盗3会给海盗5一枚金币以获取他的支 持，给自己99枚，海盗 3和海盗5同意并通过。 逆推归纳法：海盗分赃

历零毛子代找大学 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 逆推归纳法的求解思路如下： 。回到海盗2，他分给海盗4一枚金币，以获 取海盗4的支持，分给海盗3和海盗5零枚 金币，海盗2和海盗4同意并通过，海盗3和 海盗5反对但无用

逆推归纳法的求解思路如下：  回到海盗2，他分给海盗4一枚 金币，以获 取海盗4的支持，分给 海盗3和海盗5零枚 金币，海盗2和海盗4同意并通过，海盗3和 海盗5 反对但无用。 逆推归纳法：海盗分赃

历安毛子代枚大等 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 逆推归纳法的求解思路如下： 。再回到海盗1，他分给海盗3和海盗5各一枚金 币以获取他的支持，给自己98枚，不分给海盗 2和海盗4，海盗1,3，和5同意并通过，海盗2 和海盗4反对但无用。 。因此，海盗分赃问题的答案是： (98,0,1,0,1),海盗1得98，海盗2和4得0，海 盗3和5各得1

逆推归纳法的求解思路如下：  再回到海盗1，他分给海盗3和海盗5各一枚金 币以获取他的支持，给自己98枚，不分给海盗 2和海盗4，海盗1，3，和5同意并通过，海盗2 和海盗4反对但无用。  因此，海盗分赃问题的答案是: (98,0,1,0,1), 海盗1得98，海盗2和4得0，海 盗3和5各得1。 逆推归纳法：海盗分赃

历安毛子代枚大学 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 海盗分赃的全过程表格表示如下： (全部海盗半数同意即可通过) 海盗1海盗2 海盗3海盗4 海盗5 海盗5 100 海盗4 100 海盗3 99 1 海盗2 99 1 海盗1 98

海盗分赃的全过程表格表示如下： （全部海盗半数同意即可通过） 海盗1 海盗2 海盗3 海盗4 海盗5 海盗5 100 海盗4 100 海盗3 99 1 海盗2 99 1 海盗1 98 1 1 逆推归纳法：海盗分赃

历安毛子代枚大等 逆推归纳法：海盗分赃 XIDIAN UNIVERSITY 。练习： 1、如果将规则改为超过半数通过，结果又 会怎样。 2、如果将规则改为除提议人之外的海盗， 超过半数通过，结果又会怎样

 练习： 1、如果将规则改为超过半数通过，结果又 会怎样。 2、如果将规则改为除提议人之外的海盗， 超过半数通过，结果又会怎样。 逆推归纳法：海盗分赃