广延型博弈与反向归纳策略
张涵
广延型博弈的定义与形式
广延型博弈的定义
广延型博弈（extensive form）由下列要素构成：
（1）决策点与决策分枝的结构，在初始决策点与最终结局点之间不存在任何闭环（closed loops）；
（2）清楚地指明什么决策点属于哪一个游戏者；
（3）在宇宙（自然）决策点上选择的概率；
（4）游戏者作决策时所依据的信息集；信息集把游戏者在某一时刻的所有决策点分成若干类。
广延型博弈的定义与形式
（5）在博弈的终极点上每一个游戏者的收益（payoffs）
信息完美的广延型博弈是指每一个游戏者在其作决策时，对于以前所发生的事件具有信息完美（perfect information）。
本章仅分析这一类型的博弈。
广延型博弈的定义与形式
广延型博弈的形式
通常以“决策树”或“博弈树”（tree of the game）的形式来表达。
例1： 例2：
广延型博弈的定义与形式
这个例子与例1只有一点不同：游戏者2的信息集。
例2为“静态博弈”（static game），例1为“动态博弈”（dynamic game）。
广延型博弈的规则
在用图描述广延型博弈时，有两个规则是不能违反的：
第一，对初始点，没有一条箭头指向它；对其他所有箭头，都只有一条箭头指向它。
第二，如果我们从某一点向初始点返回，我们就不可能再通过迂回的途径回到这一点。
这两条规则保证了广延型博弈形式象决策树。
广延型博弈与策略型博弈
定理：对于每一个广延型博弈，都存在一个对应的策略型博弈，我们可以把此策略型博弈视为游戏者同时（simultaneously）选择策略的结果。但是，给出了一个策略型博弈，一般地，总存在着若干个与此相对应的广延型博弈。
从广延型博弈到策略型博弈
例4（讲真话博弈）：假定自然在硬币的正面（H）与背面（T）之间做出了选择，这个选择结果只有游戏者S 知道。
由于对于S 来说，自然选择的结果的信息是完美的，因此，从N（自然）到S 的两个决策点，用实线表示。
已知自然选择H 的概率为,自然选择T 的概率为。但是，S 对R 可以讲真话，也可以讲假话。
从广延型博弈到策略型博弈
如果自然选了H，S对R 报了“H”（讲了真话），然后轮到游戏者R 去选择“h”与“t”。若R 选了“h”，则S 得30，R 得10（左上方的上项）；若R 选了“t”，则S 得10，R 得10。
但是，由于S在自然了T 之后，可以对R 报“H”，然后R选择，R如选择“h”，则结果是（20，0）；R若选择“t”，则结果是（0，10）（即R 挫败了S 的谎言，R 得的多，S 得的少）。
从广延型博弈到策略型博弈
由于R在面临S 报“H”时，不能确定这个“H”是真还是假，所以连结R 的两个决策点的是一条虚线，这里，虚线代表R 的信息集。
同样，R 在面临S 报“T”时，同样无法断定S究竟是讲了真话还是讲了假话，所以，连结R的两个决策点仍是虚线。
从广延型博弈到策略型博弈
从广延型博弈到策略型博弈
现实中，S 可以代表国有企业经理，R 可以指国有企业的所有者——政府，政府看不见实际利润水平是高还是低，H、T分别可代替利润水平高低。
把上述广延型博弈转化为策略型博弈，关键是把S与R的对策写出来。S 的策略是在自然选择的结果自然之后，选择报的变量。由于自然有2 个选择的结果T 与H，对每一个结果，S可以报真与假，所以，S 实际上有4 个对策：
从广延型博弈到策略型博弈
S1：如自然选择H，报“H”；如自然选择T，报“H”；
S2：如自然选择H，报“H”；如自然选择T，报“T”；
S3：如自然选择H，报“T”，如自然选择T，报“H”；
S4：如自然选择H，报“T”，如自然选择T，报“T”。
R 的策略集是对应于S 报的结果所采取的对策。由于S 可能会报“H”与“T”，而对应于S 所报的每一个结果，R可以采取两种不同的策略，所以，R 实际上有4 个对策：
从广延型博弈到策略型博弈
r1：如S 报“H”，实行“h”；如S 报“T”，实行“h”；
r2；如S 报“H”，实行“h”；如S 报“T”，实行“t”；
r3：如S 报“H”，实行“t”；如S 报“T”，实行“h”；
r4：如S 报“H”，实行“t”；如S 报“T”，实行“t”。
根据图，我们可以找出每一组Si与rj（i=1,2,3,4；j=1,2,3,4）所对应的收益。比如，如S 选择S2，R选择r3，由于自然选择H 的概率为，所以，S 的收益为×10+×30=14；而R 的收益为×0+×0=0。类似地，可以写出收益短阵的每个结果。
从广延型博弈到策略型博弈
从策略型博弈到广延性博弈
从策略型博弈到广延性博弈的转化，可以有多种形式。策略型博弈是同时博弈，因此 ，在转化成广延型博弈时要注意的是信息集，要把一个游戏者对另一个游戏者所采取的策略的不确切性用虚线或用椭圆形表达出来。
从策略型博弈到广延性博弈
例5：考虑“囚犯的困境”
将它转化为广延型博弈有两种形式：
从策略型博弈到广延性博弈
反向归纳——信息完美条件下
广延型博弈解的方式
反向归纳法与举例
定义：反向归纳（backward induction）是指从博弈的最终结局出发，游戏者总是选择对自己最有利的结果；一旦知道博弈的最终结果是什么,然后转向次结局的那个决策点，以同样的方法找出该点上的决策者会选择什么决策；……如此反复，直到博弈的初始点，在初始点上决策的那个游戏者决定博弈的最终结果。
通常，反向归纳的解法是采用递退的方法
反向归纳——信息完美条件下
广延型博弈解的方式
例6：请看下图
反向归纳——信息完美条件下
广延型博弈解的方式
运用“反向归纳法”，当决策者“1”最终决策时，其只会选R′或L″，于是回到以“2”决策点，博弈的广延型就递退为(b)
反向归纳——信息完美条件下
广延型博弈解的方式
同理可得
反向归纳——信息完美条件下
广延型博弈解的方式
显然，A只会选“R”，最终结果两人收益都为零。
按“反向归纳”，在每一个信息完美的广延型博弈里，一定可以得到一个策略组合，这个策略组合称为“反向归纳策略组合”。该例的反向归纳策略组合便是（R，l′）。
不可信的威胁（incredible threat）
贝恩（Bain）1956年提出的《对于新的竞争的障碍》（barriers to new competition）提出的垄断者和潜在的进入者之间的博弈。
农村一个姑娘爱上一个小伙子，她父亲坚决不同意，威胁说，如果女儿不与小伙子断绝恋爱关系，他就与女儿断绝父女关系。一般来说，父亲这种威胁是不可置信的威胁。
