第三讲完全信息动态博弈

1第三章完全信息动态博弈第一节完全信息动态博弈的扩展式表述动态博弈的根本特征是，参与人的行动有先后顺序，且后行动的参与人在自己行动之前能观测到先行动的参与人的行动，特别是能根据先行动的参与人的行动调整或做出自己的战略选择。运用战略式表述动态博弈的缺陷表现在：1．看不出行动的先后顺序；2．对于描述2人以上的博弈较不方便。因此，扩展式表述extensiveformrepresentation被用于描述动态博弈。一、扩展式表述的要素1．参与人集合：i=1,……,n。此外，用N代表虚拟参与人“自然”。2．参与人的行动顺序theorderofmoves：谁在什么时候行动。3．参与人的行动空间actionset：在每次行动时，参与人有些什么选择。4．参与人的信息集informationset：每次行动时，参与人知道些什么。5．参与人的支付函数：在行动结束之后，每个参与人得到些什么（支付是所有行动的函数）。6．外生事件（即自然的选择）的概率分布。如同两人有限博弈的战略表述可以用支付矩阵表示一样，n人有限博弈的扩展式表述可以用博弈树gametree表示。二、博弈树的基本建筑材料buildingblocks开发不开发ANN大大小小BBBB开发开发开发开发不开发不开发不开发不开发（4，4）（8，0）（-3，-3）（1，0）（0，8）（0，0）（0，1）（0，0）图3-12（一）结nodes1．结的分类（1）决策结decisionnodes：参与人采取行动的时点。包括：起点结——initialnodes非起点结——（2）终点结terminalnodes：博弈行动路径的终点。2．结的顺序关系precedencerelation用X表示所有结的集合，x∈X表示某个特定的结。x≺x表示“x在x之前”≺3．前列集thesetofpredecessors和后续集thesetofsuccessors定义P(x)为在x之前的所有结的集合，简称为x的前列集；定义T(x)为x之后的所有结的集合，简称为x的后续集。如果P(x)=∅，x称为初始结，用O表示，如果T(x)=∅，x称为终点结，用z表示。Z表示终点结集合。除终点结之外所有的结都是决策结，在不引起混乱的情况下，用X表示决策结的集合。除初始结O外，对于所有x∈X，如果存在一个p(x)∈P(x)，使得对于所有的x≺x，x≠p(x)意味着x≺p(x)，那么，p(x)称为x的直接前列结immediatepredecessor。如果，x是x的直接前列结，则x称为x的直接后续结immediatesuccessor。直接后续结集合用t(x)表示。4．结的要求（假设）（1）传递性假设transitive：如果x≺x1，x1≺x2，则x≺x2。（2）反对称性假设asymmetric：如果x≺x，则x≺x不成立。即如果x在x之前，x不能在x之前。传递性和反对称性意味着顺序关系“≺”是半序的partialorder，即有些结之间是不可比较的，如图3-1中B的四个决策结。（3）前列结全排序假设：如果x1≺x，x2≺x，那么，或者x1≺x2，或者x2≺x1，就是说，x的所有前列结必须是全排序的totallyordered。前列结全排序假设意味着，任何一个非初始结的直接前列结是唯一的。保证了从初始结到任何一个结只有唯一的路径。（一个决策结可以有多个直接后续结（依赖于可选择的行动的数量））。传递性和反对称性排除了图3-2a的情形；前列结全排序假设排除了图3-2b的情形。xx´x(a)(b)图3-2博弈论不允许出现的情况35．参与人行动的描述在博弈树中，“谁在什么时候行动”用在决策结旁标注参与人的办法表示。可以引入函数i：X→{N，1，……，n}，即函数i(x)表示，在决策结x，参与人i行动。它给出了博弈中参与人行动顺序的完整描述（博弈扩展式表述的第二个要素）。6．每一个终点结z完全决定了博弈树的路径，因此，可以用函数ui(z)表示对应的博弈树路径导致的第i个参与人的支付函数（博弈扩展式表述的第五个要素）。（二）枝branches枝是从一个决策结到它的直接后续结的连线，每一个枝代表参与人的一个行动选择。对于一个给定的决策结x∈X，在一个有限的行动集合A(x)和一个一一对应的函数a：t(x)→A(x)，该函数意味着，在该结点可选择的行动集合A(x)与该结点的直接后续结集合t(x)之间存在一一对应关系。枝不仅完整地描述了每一个决策结参与人的行动空间（扩展式表述的第三个要素），而且给出了从一个决策结到下一个决策结的路径。（三）信息集informationsets1．所有决策结分属不同的信息集，每一个信息集是决策结集合的一个子集，该子集包括所有满足下列条件的决策结：（1）每一个决策结都是同一参与人的决策结；（2）该参与人知道博弈进入该信息集的某一个决策结，但不知道自己究竟处于哪一个决策结。2．引入信息集的目的在于描述下列情况：一个参与人要做出决策时，他可能并不知道“之前”发生的所有事情（即不完美信息）。3．同一信息集的决策结用虚线连接起来（或用虚线圈起来）。用H代表信息集的集合，h∈H代表一个特定的信息集。特别地，用h(x)表示包含决策结x的信息集。4．信息集的特征一个决策结属于一个，并且只能属于一个信息集。假定x∈h(x)，H应满足下列条件：（1）x∉p(x)且x∉p(x)。即同一个信息集内的一个决策结不能是其他决策结的前列结或后续结。这一条件意味着，参与人在博弈任何时点上记得自己以前的行动。（2）i(x)=i(x)，即同一信息集的所有决策结都是同一参与人的决策结。这一条件意味着，参与人不会将自己的行动于其他人的行动的决策结混淆。（3）A(x)=A(x)，即一个参与人在属于同一信息集的每一个决策结的行动空间应该是相同的。否则，参与人可利用行动空间的不同区分不同的决策结。博弈模型的一个更基本假设：博弈的结构是所有参与人的共同知识，每个参与人都可以看到博弈树。5．完美信息博弈一个信息集可包含一个或多个决策结。只包含一个决策结的信息称为单结信息集single-tons。如果博弈树的所有信息集都是单结的，该博弈称为完美信息博弈gameofperfectinformation。完美信息博弈意味着，博弈中：（1）没有任何两个参与人同时行动；（2）所有后行动者能准确知道前行动者选择了什么行动；（3）所有参与人观测到自然的行动（即自然先行动，且所有参与人都能观测到）（完全信息只要求观测到自然的行动，即没有事先的不确定性；完美信息除了这一要求外，还要求观测到其他参与人以前的行动。）6．自然4自然的信息集总是假定为单结。“自然在参与人决策之后行动”=“自然在参与人决策之前行动，但参与人不能观测到自然的行动”。（因此，在画博弈树时，最好先画自然。）7．博弈树的描绘规则相同的博弈可以用不同的博弈树描绘，但应当遵守两个规则：（1）一个参与人在决策之前知道的事情（可能是其他参与人的行动或自然的行动）必须出现在该参与人的决策结之前。例如，相同博弈可以用决策结顺序A→N→B或N→A→B表示，但是不能用A→B→N或B→A→N等表示。（2）信息集必须准确表达出来，即同一参与人，在表示相同博弈的不同博弈树中，信息集的数量必须相同，自然除外。此外，扩展式表述也可用于静态博弈，博弈树可以从任何一个参与人的决策结开始（由于所有参与人同时行动），每个参与人都只有一个信息集（因为没有参与人在决策时知道其他参与人的选择）。8．完美回忆一般假定博弈满足“完美回忆”的要求。完美回忆是指：没有参与人会忘记自己以前知道的事情，所有参与人都知道自己以前的选择。完美回忆要求，如果：（1）x2∈h(x1)（即x2和x1属于同一信息集）；（2）x∈p(x1)，（即x是x1的前列集）；（3）i(x)=i(x1)，（即x和x1都是参与人i的决策结）。那么，存在一个x（可能是x本身），满足：（1）x∈h(x)，即“同一信息集”假设；（2）x∈p(x2)，x是x2的前列结；（3）在x点为到达x1的行动与在x点为到达x2的行动是一样的。即“同一行动假设”。如图3-3：下面图3-4a和图3-4b（引自Kreps,David,1990,ACourseinMicroeconomics,Chapter12and14）均不成立。1xxUDUDx1x21图3-3完美记忆的要求5UD122LLRR111图3-4a开发不开发N11UUDD22LLRR图3-4b116图3-4a不满足“同一行动”假设。参与人不能区分（D，L)和（D，R）是正常的。但他不应该不能区分（U，R）和（D，R），即他把自己以前的选择忘记了。图3-4b不满足“同一信息集”假设。最初，参与人1是知道自然的选择的，但后来，他就忘了，区别不了（大，D，L）和（小，D，L）。三、扩展式表述的严格表述（一）历史1.全历史全历史（或终端历史）terminalhistory：博弈中所有从开始到结束的行动序列称为全历史。用H表示全历史的集合。2.子历史子历史subhistory：若将全历史表示成一个行动序列(a1,a2,…,aK)，（其中K为博弈从开始到结束依次发生的行动次数，K为自然数，当K时，表示无穷动态博弈。行动序列中的每一个a都为向量），那么(a1,a2,…,am)，其中Km，就称为全历史(a1,a2,…,aK)的子历史。用h表示子历史。3.真子历史真子历史propersubhistory：当Km时，(a1,a2,…,am)就称为全历史(a1,a2,…,aK)的真子历史。4.空历史空历史emptyhistory：博弈开始前的历史是一个空历史，用Ф表示空历史。例如：在图3-1动态囚徒困境中，存在四个全历史：（坦白，坦白），（坦白，抵赖），（抵赖，坦白），（抵赖，抵赖）。其中，全历史（坦白，坦白）有三个子历史：空历史Ф，（坦白），（坦白，坦白）。而前两个子历史，即是空历史Ф，（坦白）真子历史。在图3-2取消管制博弈中，存在五个全历史：（维持），（取消，[进，进]），（取消，[进，退]），（取消，[退，进]），（取消，[退，退]）。其中，全历史（取消，[进，进]）也存在三个子历史：空历史Ф，（取消），（取消，[进，进]）。7（二）参与人函数1.参与人函数的涵义参与人函数描述了“在全历史中，每个时刻（点）行动的参与人”。2.参与人函数的表示HhNiihP},:{)(。其中，P为players。参与人函数的意思为，在子历史h之后，是参与人i行动。例如：在图3-1动态囚徒困境中：P(Ф)=囚徒1，表示博弈从囚徒1行动开始（囚徒1行动前是空历史）；P(坦白)=P(抵赖)=囚徒2，表示在历史（坦白）和（抵赖）之后轮到囚徒2行动。（三）扩展式表述的严格表示1.扩展式表述的四个要素（1）参与人集合（2）全历史集合（3）参与人函数（4）偏好2.扩展式表述的严格表示完全信息动态博弈的扩展式为{,,,}NHPu。其中N为参与者集合；H为博弈的全历史集合，即H={(a1,a2,…,aK)}；P为参与人函数；u为支付函数，表示博弈参与者的偏好。3.行动集合与博弈的基本式相比，扩展式没有直接给出博弈参与者的行动集合，原因在于扩展式已经隐含地定义了各参与者在行动时有些什么样的行动可供选择，根据全历史和参与者函数，能很容易地得到各参与者的行动集合。在历史h之后，参与者P(h)所有可能的行动集合定义为：AP(h)(h)={aP(h):(h,a)是一个子历史，aP(h)是行动向量a的第P(h)个元素}。其含义为，对于一些非全历史h，如果序列(h,a)是历史，那么aP(h)就是在h之后采取行动的第P(h)个参与人可以选择的行动之一。4.完美信息与完全但不完美信息扩展式表述的区别需要注意的是，在完美信息下，扩展式有三个地方与完全但不完美信息不同。（1）历史h由行动向量序列变为行动序列。例如，在取消管制中，历史（取消，[进，8进]）是一个向量序列，因为企业1和企业2是同时行动的，如果改成企业2后行动，那么就变成（取消，进，进），也就是由一个向量序列便成了单值序列，意思也完全不一样了。（