博弈论
任课教师：
南京航空航天大学 经管学院
李帮义 教授
博弈论与信息经济学
第二章 完全信息动态博弈
博弈的扩展式表述
博弈的扩展式表述包括以下要素：
1.参与人的集合：i=1,…,n. N—虚拟参与人“自然”。
2.参与人的行动顺序：谁在什么时候行动。
3.参与人的行动空间：在每次行动时，参与人有些什么选择。
4.参与人的信息集：每次行动时，参与人知道些什么。
5.参与人的支付函数：在行动结束之后，每个参与人得到些什么（支付是所有行动的函数）。
6.外生事件（即自然的选择）的概率分布。
博弈树
博弈树的基本建筑材料包括结、枝、信息集。
1.结
结{
决策结：参与人采取行动的时点。
终点结：博弈行动路径的终点。
所有结的结合，
表示某个特定的结。
用
表示定义在X上的顺序关系：
意味着
在
之前。
假定
满足传递性和反对称性，从而意味着顺序关系
是半序的，即有些结之间是不可比较的。
用
博弈树
1.结
定义
为在 之前的所有结的集合，简称为 的前列集。
定义
为在 之后的所有结的集合，简称为 的后续集。
如果 ， 称为初始结。
如果 ， 称为终点结。
除了终点结之外的所有结都是决策结。
在图示中，用空心圆代表初始结，实心圆代表其他决策结。
博弈树
2.枝
在博弈树上，枝是从一个决策结到它的直接后续结的连线，每一个枝代表参与人的一个行动选择，博弈树的枝不仅完整地描述了每一个决策结参与人的行动空间，而且给出了从一个决策结到下一个决策结的路径。正因为如此，每一个终点结才完全决定了博弈树的路径。
博弈树
3.信息集
博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策结集合的一个子集，该子集包括所有满足下列条件的决策结：
①每一个决策结都是同一参与人的决策结。
②该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟处于哪一个决策结。
一个信息集可能包含多个决策结，也可能只包含一个决策结。只包含一个决策结的信息集称为单结信息集。如果博弈树的所有信息集都是单结的，该博弈称为完美信息博弈。
博弈树
注：习惯上，博弈树的终点结的支付向量的第一个数字总是“第一个”参与人的支付，第二个数字总是“第二个”参与人的支付。
完美回忆：指没有参与人会忘记自己以前知道的事情，所有参与人都知道自己以前的选择。
扩展式表达博弈的纳什均衡
为了说明如何从扩展式表达构造战略式表达，让我们考虑房地产开发博弈的例子。假定在博弈开始之前自然就选择了“低需求”，并且已成为参与人的共同信息；再假定开发商A先决策，开发商B在观测到A的选择后决策。那么，博弈的扩展式表述如图所示。
A
B
B
开发
不开发
开发
不开发
开发
不开发
（-3，-3）
（1，0）
（0，1）
（0，0）
这是一个完美信息博弈（每个人的信息集都是单结的）。
扩展式表达博弈的纳什均衡
为了构造出这个博弈的战略式表述，首先注意到，A只有一个信息集，两个可选择的行动，因而A的行动空间也即战略空间：SA=(开发，不开发)。但B有两个信息集，每个信息集上有两个可选择的行动，因而B有四个纯战略，分别为：
1.不论A开发还是不开发，我开发—威胁战略S1=(开发,不开发).
开发我开发，A不开发我不开发—跟随战略S2=(开发,不开发).
开发我不开发，A不开发我开发—差异化战略S3=(不开发,开发).
4.不论A开发还是不开发，我不开发—放弃战略S4=(不开发,不开发).
扩展式表达博弈的纳什均衡
这个博弈的战略式表达为：
0，0
0，1
0，0
0，1
1，0
1，0
-3，-3
-3，-3
开发商B
S1
S2
S3
S4
开发商B
开发
不开发
从战略式表达中，我们发现这个博弈有三个纯战略纳什均衡： （不开发，S1）,（开发，S3），（开发，S4）
扩展式表达博弈的纳什均衡
在扩展式表述博弈中，所有n个参与人的一个纯战略组合s=（si,…,sn）决定了博弈树上的一个路径。每一个战略组合（即博弈树的路径）决定了一个支付向量u=（u1,…,un）。战略组合si*是扩展式博弈的一个纳什均衡，如果对于所有的i，si*最大化
，即
扩展式表达博弈的纳什均衡
在扩展式表述博弈中，混合战略被称为“行为战略”以区别于战略式表述博弈的混合战略概念。行为战略是指参与人在每一个信息集上随机地选择行动。一个行为战略规定了对应每一个信息集的行动集合上的概率分布，且不同信息集上的概率分布是独立的。每一个行为战略组合b=（b1，…，bn）给出一个支付空间上的概率分布。b*=（b1*，…，bn*）是一个行为战略纳什均衡，如果没有任何参与人可以通过选择其他行为战略增加自己的期望效用。
扩展式表达博弈的纳什均衡
例：
A
B
B
开发
不开发
开发
不开发
开发
不开发
（1，0）
（0，1）
（0，0）
（-3，-3）
假定行为战略
混合战略
{开发，开发}—威胁战略
{开发，不开发}—跟随战略
{不开发，开发}—差异化战略
{不开发，不开发}—放弃战略
扩展式表达博弈的纳什均衡
则：
上例说明：一个行为战略可能对应多个混合战略；但逆定理不成立，即一个混合战略只对应一个行为战略。
库恩（Kuhn，1953）证明，在完美回忆博弈中，混合战略和行为战略是等价的。
子博弈精炼纳什均衡
例：
A
B
B
开发
不开发
开发
不开发
开发
不开发
（1，0）
（0，1）
（0，0）
（-3，-3）
从上一节讨论中，可得三个纳什均衡：
（不开发，{开发，开发}）—不可置信的威胁；
（开发，{不开发，开发}）—唯一的子博弈精炼纳什均衡；
（开发，{不开发，不开发}）—不可置信的承诺
子博弈精炼纳什均衡
子博弈的定义：
一个扩展式表述博弈的子博弈G由一个决策结x和所有该决策结的后续结组成，它满足下列条件：①x是一个单结信息集；②子博弈的信息集和支付向量都直接继承自原博弈。
子博弈精炼纳什均衡定义：
扩展式表述博弈的战略组合s*=（s1*，…，si*，…，sn*）是一个子博弈精炼纳什均衡，如果： ①它是原博弈的纳什均衡； ②它在每一个子博弈上给出纳什均衡。
子博弈精炼纳什均衡
现在以上例进行说明：
A
B
B
开发
不开发
开发
不开发
开发
不开发
（1，0）
（0，1）
（0，0）
（-3，-3）
这个博弈有三个子博弈，除原博弈外，子博弈(b)和(c)实际上是两个单人博弈（即在每个博弈中，只有开发商B在决策）。
x
x’
x
x’
开发
不开发
开发
不开发
（-3，-3）
（1，0）
（0，1）
（0，0）
(b)子博弈Ⅰ
(c)子博弈Ⅱ
如前所述，这个博弈有三个纳什均衡：（不开发，{开发，开发}）； （开发，{不开发，开发}）； （开发，{不开发，不开发}）
子博弈精炼纳什均衡
检验这三个纳什均衡是否满足子博弈精炼纳什均衡的要求。
x
开发
不开发
（1，0）
（-3，-3）
子博弈(b)
x’
开发
不开发
（0，0）
（0，1）
子博弈(c)
在子博弈(b)，B的最优选择是不开发；在子博弈(c)，B的最优选择是开发。
纳什均衡（不开发，{开发，开发}）中B的均衡战略{开发，开发}在子博弈(c)上构成纳什均衡，但在子博弈(b)上不构成纳什均衡，因此，（不开发，{开发，开发}）不是一个子博弈精炼纳什均衡；
同理，纳什均衡（开发，{不开发，不开发}）中B的均衡战略{不开发，不开发}在子博弈(b)上构成纳什均衡，但在子博弈(c)上不构成纳什均衡，因此， （开发，{不开发，不开发}）也不是一个子博弈精炼纳什均衡。
子博弈精炼纳什均衡
与上述两个纳什均衡不同，纳什均衡（开发，{不开发，开发}）中B的均衡战略{不开发，开发}无论在子博弈(b)上还是在子博弈(c)上都构成纳什均衡（即如果A开发，B不开发；如果A不开发，B开发），因此（开发，{不开发，开发}）是这个博弈的唯一的子博弈精炼纳什均衡。
子博弈精炼纳什均衡
用逆向归纳法求解子博弈精炼纳什均衡：
假定博弈有两个阶段，第一阶段参与人1行动，第二阶段参与人2行动，并且2在行动前观测到1的选择。
令A1是参与人1的行动空间，A2是参与人2的行动空间。
参与人1：
参与人2：
Step1：
Step2：
子博弈精炼纳什均衡
例：
A
B
B
开发
不开发
开发
不开发
开发
不开发
（1，0）
（0，1）
（0，0）
（-3，-3）
Step1：B的最优行动规则——差异化战略S3={不开发，开发}
Step2：A——开发
所以，精炼均衡是（开发，{不开发，开发}）
子博弈精炼纳什均衡
例：
1
2
1
U
D
L
R
U’
D’
(2,0)
(1,1)
(3,0)
(0,2)
Step1：参与人1（第二次行动）——U’
Step2：参与人2——L
Step3：参与人1——U
所以，精炼均衡（{U,U’}，L）
用逆向归纳法求解子博弈精炼纳什均衡的过程，实质是重复剔除劣战略过程在扩展式表述博弈上的扩展：从最后一个决策结开始依次剔除掉每一个子博弈的劣战略，最后生存下来的战略构成精炼纳什均衡。
承诺行动与子博弈精炼纳什均衡
有些纳什均衡之所以不是精炼均衡，是因为他们包含了不可置信的威胁战略。这一点意味着，如果参与人能在博弈之前采取某种措施改变自己的行动空间或支付函数，原来不可置信的威胁就可能变得可置信，博弈的精炼均衡就会相应改变。我们将这些为改变博弈结果而采取的措施称为“承诺行动”。
有些情况下，一个参与人可以通过减少自己的选择机会使自己受益，原因在于保证自己不选择某些行动可以改变对手的最优选择。这样的承诺是完全承诺。
如果一个承诺只是增加某个行动的成本而不是使该行动完全没有可能，这样的承诺是不完全承诺。
承诺行动与子博弈精炼纳什均衡
例：
A
B
B
开发
不开发
开发
不开发
开发
不开发
（1，0）
（0，1）
（0，0）
（-3，-3）
如果在A决策之前，B与某个客户签订一个合同，规定B在一个特定的时刻交付客户若干面积的写字楼办公室，如果B不能履约，将赔偿客户3500万。
这个合同就是一个承诺行动。
此时，B的{开发，开发}就不再是一个不可置信的威胁。因为不论A是否开发，开发是B的最优选择。
子博弈精炼纳什均衡应用举例
1.斯坦科尔伯格寡头竞争模型
例： 市场上有两家企业，企业 1 首先选择产量
假定函数为：
两个企业有相同的单位成本
子博弈精炼纳什均衡应用举例
逆向归纳法：
Step1：
Step2：
得：
子博弈精炼纳什均衡应用举例
库诺特模型的纳什均衡是
斯坦科尔伯格均衡的总产量
大于库诺特均衡的总产量
企业1的斯坦科尔伯格均衡产量
>库诺特均衡的产量
企业2的斯坦科尔伯格均衡产量
>库诺特均衡的产量
这就是“先动优势”。
子博弈精炼纳什均衡应用举例
2.供应链的协调
考虑由一个制造商和一个零售商组成的供应链。制造商的单位生产成本为一个常数 。零售商以固定价格 销售，其中 。设需求函数为
其中， 是零售商的促销投资； 是零售商不进行促销投资时的市场规模， ； 是投资敏感系数， ； 是增量需求投资弹性。一般地，促销投资越多，需求越高，而投资的边际需求递减，即成立 。
子博弈精炼纳什均衡应用举例
如果供应链集中管理，那么，集中决策者选择投资 最大化下面的渠道利润
其中，第一项表示销售利润。很明显， 是 的一个严格凹函数，即二阶条件成立。因此，满足一阶条件的投资 是集中化决策者的最优解，解集中化决策者的一阶条件得
即集中决策者将投资 。在开区间 中的增量需求投资弹性 越大，最优投资 越大。
子博弈精炼纳什均衡应用举例
下面，考虑一个分散系统——制造商通过契约 安排批发产品给零售商，其中， 是一个单位批发价格， ，是补贴率， 。这样，零售商将从制造商处获得补贴 ，它的实际投资为 。零售商选择投资 最大化下面的利润函数
分散化决策时，零售商的最优投资为
很显然，批发价格 越高，零售商的最优投资越低；补贴越高，零售商的最优投资越高。现在，回答是否存在契约安排 协调制造商和零售商组成的供应链。为了回答这个问题，需要看这一契约是否诱导零售商选择集中决策时的最优投资。
子博弈精炼纳什均衡应用举例
定理 满足 的契约安排 能够协调供应链。
证明： 根据前面的描述可知，制造商的利润函数为
这样，在分散决策时渠道利润为
即当 时，供应链被协调。这样，最优补贴 。 ■
从定理可知，当供应链被协调时，零售商的利润为
子博弈精炼纳什均衡应用举例
由于 且 ，所以零售商的利润为正。但是，制造商通过增加批发价格 可以分配任意小的正利润给零售商。换句话说，通过增加 ，制造商能够获得总渠道利润的任意大的配置，但不能获得总的渠道利润。
重复博弈
“重复博弈”是指同样结构的博弈重复多次，其中的每次博弈被称为“阶段博弈”。
以囚徒困境为例，如果每次判刑不是很重，那么，两个囚徒在刑满释放之后再作案，作案之后再判刑，释放之后再作案，如此等等，他们直接进行的就是重复博弈，其中每次作案是一个阶段博弈。
重复博弈
重复博弈的基本特征：
①重复性
②博弈的历史（所有的参与人都观测到博弈过去的历史，如在每一个新的阶段博弈，两个囚徒都知道同伙在过去的每次博弈中选择了抵赖还是坦白）
③支付之和（博弈方考虑的不仅仅是一个环节，而是整个阶段；参与人的总支付是所有阶段博弈支付的贴现值之和或加权平均值）
④战略空间明显复杂化（参与人在重复博弈中的战略空间远远大于且复杂于再每一个阶段博弈中的战略空间）
重复博弈
影响重复博弈均衡的因素：
①单阶段的均衡
②博弈重复的次数
1.有限次重复博弈
例：
0，300
0，300
-10，0
40，50
在位者
默许
斗争
进入者
进入
不进入
在一次博弈中，如果进入者先行动，这个博弈的唯一的子博弈精炼纳什均衡结果是进入者进入，在位者默许。
先假定有20个同样的市场，通过一直倒推分析，得到这个博弈的唯一子博弈精炼均衡是在位者在每一个市场上都选择默许，进入者在每一个市场上选择进入。
重复博弈
上述结果可以一般化为下述定理：
定理：令G是阶段博弈，G(n)是G重复n次的重复博弈（n<∞）.
那么，如果G有唯一的纳什均衡，重复博弈G(n)的唯一子博弈精炼纳什均衡结果是阶段博弈G的纳什均衡重复n次（即每个阶段博弈出现的都是一次性博弈的均衡结果）。
重复博弈
2.无限次重复博弈
例1：
-1，-1
-10，0
0，-10
-8，-8
乙
坦白
抵抗
甲
坦白
抵抗
假定：①博弈重复无穷次。折现率
②严酷战略：首先双方合作；只要对方没有背叛，就一直合作；一方看到对方一次背叛，则永远背叛下去。以囚徒困境为例，开始选择抵抗；选择抵抗知道有一方选择了坦白，然后永远选择坦白。
重复博弈
甲：严酷战略
乙：抵抗，抵抗…坦白…
收益: -1 ， -1 ， 0 ， -8 ， -8 ，...
总收益1=
如果乙很守信用，一直抵抗下去。
总收益2=（-1）+（-1）+（-1）+…
比较总收益1和总收益2得出：
若 ，乙就不会选择背叛。
其实折现率 反映了一个人重视短期（ 小）/长期（ 大）行为。
重复博弈
例2：库诺特博弈的无限次重复
已知：如前的库诺特博弈
若两人合作，则：
重复博弈
甲：严酷战略
①合作产量
②若没有背叛，则维持产量
③
若看到背叛，则选择产量
乙：合作， …， 投机， …
收益：
重复博弈
乙的收益：
投机的总收益：
一直合作的总收益：
∴当 ，乙会选择合作。
重复博弈
无名氏定理 (Friedman 1971) 令G为一个 人阶段博弈，
为以G为阶段博弈的无限期重复博弈， 是G的一个纳什均衡（纯策略或混合策略）， 是 决定的支付向量， 是一个任意可行的支付向量， 是可行支付向量集合。那么，对于任何满足 的 （ ），存在一个贴现因子 使得对于所有的 ， 是一个特定的子博弈完美纳什均衡结果。
重复博弈
例：参与人不固定
0，0
0，0
-1，2
1，1
生产商
高质量
低质量
消费者
买
不买
生产商：首先生产高质量；继续生产高质量，除非曾经生产过低质量；如果上
一次生产了低质量的产品，之后永远生产低质量产品。
消费者：购买，一直购买；如果厂商曾经生产过低质量，不在购买。
生产商的收益：
若 ，生产商将一直生产高质量。
