完全信息动态博弈_海盗分金博弈问题分析

经典的博弈论分析案例一一“海盗分金”问题5个海盗抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推。

“海盗分金”其实是一个高度简化和抽象的模型，体现了博弈的思想。

在“海盗分金”模型中，任何“分配者”想让自己的方案获得通过的关键是事先考虑清楚“挑战者”的分配方案是什么，并用最小的代价获取最大收益，拉拢“挑战者”分配方案中最不得意的人们。

假设前提假定“每个海盗都是绝顶聪明且很理智”，那么“第一个海盗提出怎样的分配方案才能够使自己的收益最大化？” 推理过程从后向前推，如果1至3号强盗都喂了鲨鱼，只剩4号和5号的话，5号一定投反对票让4号喂鲨鱼，以独吞全部金币。

所以，4号惟有支持3号才能保命。

3号知道这一点，就会提出（100，0，0）的分配方案，对4号、5号一毛不拔而将全部金币归为已有，因为他知道4号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。

不过，2号推知3号的方案，就会提出（98，0，1，1）的方案，即放弃3 号，而给予4号和5号各一枚金币。

由于该方案对于4号和5号来说比在3号分配时更为有利，他们将支持他而不希望他出局而由3号来分配。

这样，2号将拿走98枚金币。

同样，2号的方案也会被1号所洞悉，1号并将提出（97, 0，1, 2, 0）或（97, 0，1, 0，2）的方案，即放弃2号，而给3号一枚金币，同时给4号（或5号）2枚金币。

由于1号的这一方案对于3号和4号（或5号）来说，相比2号分配时更优，他们将投1号的赞成票，再加上1号自己的票，1号的方案可获通过，97枚金币可轻松落入囊中。

这无疑是1号能够获取最大收益的方案了！答案是：1号强盗分给3号1枚金币，分给4号或5号强盗2枚，自己独得97枚。

分配方案可写成（97, 0, 1, 2, 0）或（97, 0, 1, 0, 2）。

分析1号看起来最有可能喂鲨鱼，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还收益最大。

博弈论——完全信息动态博弈2 完全信息的动态博弈2.1完全和完美信息的动态博弈动态博弈(dynamic game)：参与⼈在不同的时间选择⾏动。

完全信息动态博弈指的是各博弈⽅先后⾏动，后⾏动者知道先⾏动者的具体⾏动是什么且各博弈⽅对博弈中各种策略组合下所有参与⼈相应的得益都完全了解的博弈静态博弈习惯⽤战略式(Strategic form representation)表述，动态博弈习惯⽤扩展式（Extensive form representation）表述。

战略式表述的三要素：参与⼈集合、每个参与⼈的战略集合、由战略组合决定的每个参与⼈的⽀付。

扩展式表述的要素包括：参与⼈集合、参与⼈的⾏动顺序、参与⼈的⾏动空间、参与⼈的信息集、参与⼈的⽀付函数、外⽣事件（⾃然的选择）的概率分布。

n⼈有限战略博弈的扩展式表述⽤博弈树来表⽰1(1,2) (0,3)①结：包括决策结和终点结。

决策结是参与⼈采取⾏动的时点，终点结是博弈⾏动路径的终点。

第⼀个⾏动选择对应的决策结为“初始结”，⽤空⼼圆表⽰，其它决策结⽤实⼼圆表⽰。

X表⽰结的集合，x X表⽰某个特定的结。

z表⽰终点结，Z表⽰终点结集合。

表⽰结之间的顺序关系，x x′表⽰x在x′之前。

x之前所有结的集合称为x的前列集，x之后所有结的集合称为x的后续集。

以下两种情况不允许：前者违背了传递性和反对称性；后者违背了前列节必须是全排序的。

在以上两个假设之下，每个终点结都完全决定了博弈树的某个路径。

②枝：博弈树上，枝是从⼀个决策结到其直接后续结的连线，每⼀个枝代表参与⼈的⼀个⾏动选择。

在每⼀个枝旁标注该具体⾏动的代号。

⼀般地，每个决策结下有多个枝，给出每次⾏动时参与⼈的⾏动空间，即此时有哪些⾏动可供选择。

③信息集（information sets）：博弈树中某⼀决策者在某⼀⾏动阶段具有相同信息的所有决策结集合称为⼀个信息集。

博弈树上的所有决策结分割成不同的信息集。

每⼀个信息集是决策结集合的⼀个⼦集(信息集是由决策结构成的集合)，该⼦集包括所有满⾜下列条件的决策结：(1)每⼀个决策结都是同⼀个参与⼈的决策结。

海盗分金——博弈论的故事1（一）海盗分金5名海盗分100枚金币。

规则是大家抽签分出1—5号，并按顺序提方案。

1号首先提方案，5人表决，当超半数同意时有效；否则1号将被抛入大海。

然后，2号提方案，4人表决，评判方式同上。

以此类推。

假定每个人都很聪明，1号提出什么方案，能使自己收益最大？答案是：（97、0、1、0、2 ）或（97、0、1、2、0）。

推理：假定1—3号都抛入大海，那末4号也活不了，所以，4号必须保住3号。

据此，3号可提方案（100、0、0）。

2号推知3号方案，可提出（98、0、1、1）方案，来拉拢4号和5号。

1号推知2号方案，可推出上述方案，拉拢住3号，以及4号或5号中的1人。

（二）博弈论与博弈类型博弈（Game），本是游戏、竞赛的意思。

所要解决的核心问题是：参与博弈的其他人员会怎么做？我应采取怎样的对策来取得最佳效果？博弈的例子到处可见：讨价还价、划拳、小孩猜拳、下棋、打牌，以及“三十六计”、“田忌赛马”等。

博弈论作为一种理论，最先是由美国经济学家冯·诺伊曼在1937年提出来的，他与经济学家奥斯卡·摩根斯坦于1944年合著的《博弈论与经济行为》公认为博弈论诞生的标志。

今天，博弈论已为数学的一个较为完善的分支，并在许多领域被运用。

在经济学领域的影响被称为“现代经济学的一次大的革命”。

博弈类型：1.静态博弈与动态博弈。

前者指参与者同时行动、同时出牌或亮招，如招标、考试等；后者指参与者的行动有先后次序，如下棋、战争、商业竞争等。

2.完全信息博弈与不完全信息博弈。

前者指参与者互相都“知己知彼”，否则就是后者。

3.零和博弈与非零和博弈。

前者指“你赢的就是我输的”，如打麻将、下棋等；后者指大家的得失总和不为零，如势均力敌的战争会使两败俱伤，而商业合作会使“双赢”。

4.合作博弈与非合作博弈。

在非零和博弈中，分为这两种。

前者指博弈双方可都获利，如价格联盟；后者指博弈结果会对双方都不利。

2 完全信息的动态博弈2.1完全和完美信息的动态博弈动态博弈(dynamic game)：参与人在不同的时间选择行动。

完全信息动态博弈指的是各博弈方先后行动，后行动者知道先行动者的具体行动是什么且各博弈方对博弈中各种策略组合下所有参与人相应的得益都完全了解的博弈静态博弈习惯用战略式(Strategic form representation)表述，动态博弈习惯用扩展式（Extensive form representation）表述。

战略式表述的三要素：参与人集合、每个参与人的战略集合、由战略组合决定的每个参与人的支付。

扩展式表述的要素包括：参与人集合、参与人的行动顺序、参与人的行动空间、参与人的信息集、参与人的支付函数、外生事件（自然的选择）的概率分布。

n人有限战略博弈的扩展式表述用博弈树来表示1(1,2) (0,3)①结：包括决策结和终点结。

决策结是参与人采取行动的时点，终点结是博弈行动路径的终点。

第一个行动选择对应的决策结为“初始结”，用空心圆表示，其它决策结用实心圆表示。

X表示结的集合，x X表示某个特定的结。

z表示终点结，Z表示终点结集合。

表示结之间的顺序关系，x x´表示x在x´之前。

x之前所有结的集合称为x的前列集，x之后所有结的集合称为x的后续集。

以下两种情况不允许：前者违背了传递性和反对称性；后者违背了前列节必须是全排序的。

在以上两个假设之下，每个终点结都完全决定了博弈树的某个路径。

②枝：博弈树上，枝是从一个决策结到其直接后续结的连线，每一个枝代表参与人的一个行动选择。

在每一个枝旁标注该具体行动的代号。

一般地，每个决策结下有多个枝，给出每次行动时参与人的行动空间，即此时有哪些行动可供选择。

③信息集（information sets）：博弈树中某一决策者在某一行动阶段具有相同信息的所有决策结集合称为一个信息集。

博弈树上的所有决策结分割成不同的信息集。

每一个信息集是决策结集合的一个子集(信息集是由决策结构成的集合)，该子集包括所有满足下列条件的决策结：(1)每一个决策结都是同一个参与人的决策结。

第七章完全信息动态博弈博弈中的得益，是各参与人追求的根本目标，关于得益的信息是博弈中最重要的信息之一。

在一些博弈中参与人对自己的得益情况完全清楚，对其他参与人的得益也都很清楚，如前面介绍过的囚徒困境，猜硬币等；还有一些博弈中，参与人对其他参与人的得益情况并不了解，例如投标、拍卖活动中，各参与人对其他参与人的标的的估价很难了解，即使最后的成交价是明确的，但各参与人仍然无法知道其他参与人中标、拍得标的的真正得益是多少。

一般地，参与人完全了解所有参与人的得益情况的博弈称为“完全信息博弈”，不完全了解其他参与人的得益情况的博弈称为“不完全信息博弈”。

博弈中的过程，是博弈结构的重要部分，根据博弈过程的不同，可以将博弈分为：“静态博弈”、“动态博弈”和“重复博弈”。

如果参与人选择战略时是同时或可以看作同时的博弈称为“静态博弈”；若各参与人战略的选择和行动不仅有先后顺序，后选择、后行动的参与人在自己选择行动之前，可以看到前面的过程，这种博弈称为“动态博弈”（也称为“多阶段博弈”）。

动态博弈中在轮到行为时对博弈的进程完全了解的参与人，称为具有“完美信息”的参与人，如果动态博弈的所有参与人都有完美信息，称为“完美信息的动态博弈”。

相应的轮到行为时对博弈的进程不完全了解的参与人，称为具有“不完美信息”，这样的动态博弈称为“不完美信息的动态博弈”。

7.1 完全且完美信息动态博弈动态博弈中一个参与人的一次行为称为一个“阶段”。

由于每个参与人在动态博弈中可能不止一次行为，因此，每个参与人在一个动态博弈中就可能有数个甚至许多个博弈阶段。

动态博弈一般用扩展形表示，括弧中前一个数字代表乙的得益，后一个数字代表甲的得益。

动态博弈的一个中心问题是“可信性”问题。

所谓可信性是指动态博弈中先行为的参与人是否该相信后行为的参与人会采取对自己有利的或不利的行为。

因为后行为方将来会采取对先行为方有利的行为相当于一种“许诺”，而将来会采取对先行为方不利的行为相当于一种“威胁”，因此我们可将可信性分为“许诺的可信性”和“威胁的可信性”。

《博弈论：原理、模型与教程》第二部分完全信息动态博弈第7章子博弈精炼Nash均衡7.2 子博弈精炼Nash均衡的求解（重点！）（已精细订正！）定义7－1虽然给出了子博弈精炼Nash的定义，但没有说明如何求解子博弈精炼均Nash衡。

下面以图6－8 中扩展式博弈为例，介绍一种最常用的求解子博弈精炼Nash均衡的方法—逆向归纳法。

（讲！）考察图6－8中的博弈。

参与人1在博弈开始时（即在信息集}{)(11x I 上面临两种选择—行动A 和行动B 。

参与人1此时选择哪种行动呢？对于理性的参与人1来讲，只会选择使自己支付最大化的行动。

从图6－8很容易知道参与人1选择行动B 时所得到的支付为2；但是，如果参与人1选择行动A ，则所得支付就要取决于参与人2在信息集}{)(22x I 上的选择，以及博弈达到决策结3x 时参与人1在信息集}{)(31x I 上的选择。

也就是说，参与人1选择行动A 所得支付，取决于子博弈)(2x Γ的结果。

因此，为了确定参与人1在博弈开始时的选择，就必须确定参与人1选择行动A 的所得支付，而为了确定参与人1选择行动A 的所得支付，就必须先求解子博弈)(2x Γ。

如何求解博弈)(2x Γ呢？可以采用同样的方法来求解子博弈)(2x Γ，即在求解子博弈)(3x Γ的基础上，确定参与人2在信息集}{)(22x I 上的选择，从而求解子博弈)(2x Γ。

由以上分析可以得到图6－8中博弈的求解过程：首先求解博弈树中最底层的子博弈)(3x Γ得到子博弈)(3x Γ的结果为(3,0)（即参与人1选择E ）； 再求解博弈)(2x Γ，容易得到博弈的结果(1,1)（即参与人2选择D ）； 最后求解原博弈，即子博弈)(1x Γ，得到博弈的结果为(2,1)（即参与人1选择B ）。

（讲！）考察更一般的情形。

对于图7－6中的博弈树，参与人i 在信息集})({i i x I 选择行动L 还是行动R ，取决于选择行动L 和行动R 所带来的后果。