博弈3-完全信息动态博弈
一、博弈的扩展型
1.要素
博弈的参与者
对于参与人可能采取行动的一个完整描述(即它们的可行行动集)
博弈的先后顺序，即谁在什么时候行动
对于参与人采取行动时所知信息的描述(即信息集)
针对所有参与者可能选择的策略组合，每一个参与者获得的收益
2.博弈树
博弈树由结点(node)和边(edge)组成，对应博弈参与人、行动和收益。
- 非叶子节点：代表参与人，表示在该节点处哪个参与人做出行动。每个非叶子节点仅代表一个参与人。
- 边：代表行动。
- 策略：一条由根节点到叶子节点的路径中，某一个参与人的所有行动按顺序排列，即得到该参与人的一个策略。
- 叶子节点：代表由根节点到该叶子节点的路径中所得到的每一个参与人的策略共同作用下得到的收益。收益只存在于叶子节点。
3.博弈树的规则
- 每一个节点都是初始点的后续节点，同时，初始点是唯一具有这一特性的节点。
- 除初始点之外的任一节点都只有一个直接前置节点。初始点没有前置点。
- 从同一个节点引出的多个分支具有不同的行动标签。
- 每一个信息集只包含一个参与人的决策点。
- 某个信息集中的所有节点必须具有相同数量的直接后继点，而且其中所有节点是通过具有相同集合行动标签的分支而达到这些后继点的。
对扩展式信息集的解释：
上述规则4,5描述了信息集的构成规则，在博弈树中，相同信息集的节点使用虚线连接。如果一个信息集中有超过1个节点，则在该信息集的参与人不能区分自己在信息集的哪个节点上，即该参与人不能知道前一参与人做出了什么行动，使自己达到了该信息集的哪一节点，即可以认为该参与人与其前一参与人做出行为是同时或逻辑同时的。
如果扩展型的每一个信息集都是单独的一个节点，即如果图中没有虚线，称之为完美信息博弈，反之则称为不完美信息博弈。
例1
A,B两家公司，A决定是否进入B的行业，B可以观察A的决定。若A进入B的行业(I)，则两公司同时决定是否打广告；若A不进入B的行业(O)，则B独自决定是否打广告。如果两家公司都打广告，则两家公司均获利300(万元)；如果一家打广告一家不打，则打广告公司获利600，不打广告获利100；如果两家公司都不打广告，则均获利500；如果该行业只有一家公司，则打广告获得700，不打获得600。
- 如图，A进入行业后，两公司是同时做是否打广告的决定的，故
是B的一个信息集， 是A的一个信息集， 要用虚线连接。A不知道自己是在 节点还是在 节点，因为A不知道B在 节点做了什么行动。 到 中，A的策略为(进入，打广告)，B的策略为(打广告)，该策略对的收益为 。
4.扩展型与标准型的相互转换
将扩展型转换为标准型：即对于每个从根节点到叶子节点的路径，得到博弈双方的策略，该策略对对应的收益即为叶子节点所标收益。转换为收益矩阵形式即可。收益矩阵无法体现博弈行动的先后顺序。
将标准型转换为扩展型：如果决策是连续而非离散的，无法对每一种行动画出一个分支，则画出一个扇形代表决策范围。
例2
有A,B两家公司，A决定是否进入B的行业，B可以观察A的决定。若A不进入B的行业(O)，则A的收益是0，B独占全部市场份额，收益是4。若A进入B的行业(I)，B可以选择合作(C)或打价格战(F)，若二者合作则平分市场份额收益分别是2,2；若打价格战两败俱伤收益分别是-1,-1。
| A/B | 合作 | 打价格战 |
|---|---|---|
| 进入 | 2,2 | -1,-1 |
| 不进入 | 0,4 | 0,4 |
例3
将如图扩展型转换为标准型。
| A/B | 打广告 | 不打广告 |
|---|---|---|
| 进入,打广告 | 300，300 | 600,100 |
| 进入,不打广告 | 100,600 | 500,500 |
| 不进入,打广告 | 0,700 | 0,600 |
| 不进入,不打广告 | 0,700 | 0,600 |
虽然A选择不进入后无打广告/不打广告的行动，但在转换成标准型收益矩阵时要将两种行动——进入/不进入、打广告/不打广告的组合形成的策略都写出。
例4
| A/B | q2 |
|---|---|
| q1 | q1(a-c-(q1+q2)),q2(a-c-(q1+q2)) |
将古诺博弈转换为扩展型。
由于古诺模型两企业是同时做出决策的，故是不完美信息博弈，要画虚线。
5.逆向归纳法
- 序贯理性：参与人
所采取的策略应该定义出他的每个信息集的最优化行动，包括参与人 (事前)并不相信在博弈中会到达的那些信息集。 - 条件劣策略：对于参与人
的某个策略 来说，如果在到达参与人 的某信息集的情况下，存在另一个策略 严格占优于它，那么策略 是条件劣策略。 - 逆向归纳法：一种从后往前(从博弈树末端的信息集推到博弈开始时的信息集)分析博弈的方法。在可以到达终止点的假定之下，依次地删去每个信息集中作为劣策略的行动。
例5
| A/B | 合作 | 打价格战 |
|---|---|---|
| 进入 | 2,2 | -1,-1 |
| 不进入 | 0,4 | 0,4 |
- 对收益矩阵求解纳什均衡，纳什均衡(0,4)是无意义的，因为若A不进入行业，则B选择打价格战是没有意义的。
- 对博弈树使用逆向归纳法求解纳什均衡。对于
节点，B会选择对使自己收益最大的行动，即(2,2)，这时 节点的收益便表示为(2,2)。对于 节点，A会选择使自己收益最大的行动，即(2,2)。故该博弈的纳什均衡为(2,2)。
二、完全完美信息动态博弈
1.斯塔克伯格双头垄断模型
博弈要素：
- 参与人：企业1，企业2
- 行动集：产量
- 行动顺序：企业1选择产量
，企业2观测到 ，然后选择产量 - 信息集：完美信息
- 收益：
求解，采用逆向归纳法：
- 对于企业2，要选择使其收益
最大的 ，求导得极大值点 - 但由于
是观测 所得，所以 是 的函数，即 - 有企业1收益
，要选择使其收益最大的 ，求导得极大值点 ，则 - 该博弈的逆向归纳纳什均衡为
与古诺模型的比较：
- 与古诺模型的纳什均衡
相比，该模型中企业1(领导者)利润的增加必定意味着企业2(追随者)福利的恶化。了解更多信息可以让一个参与人受损。
2.有工会企业的工资和就业
博弈要素：
- 参与人：工会，企业
- 行动集：工资水平
，就业人数 - 行动顺序：工会给出工资水平
，企业观测到 ，选择就业人数 - 信息集：完美信息
- 收益：
- 其他信息：工会收益
是 的增函数，企业收益 ， 是增凹函数(斜率逐渐变小)
求解，采用逆向归纳法：
- 对于企业，要选择使收益
最大的 ，对 求导得 ，极大值点满足 。即企业要选择其 曲线上斜率为 处对应的 作为最佳 ，可以认为 是关于 的函数 。
- 在企业的等利润曲线上，给定
，只要寻找水平线 的与某一等利润线切点对应的 即为企业要选择的 (直观理解：企业的等利润线是越低越好，给定 水平线相切表示已经最低了，再低就没有等利润线相交了)，同时，这一系列 连线即为 曲线。那么可以认为，企业选择的 一定在这条曲线上。 - 由逆向，接下来分析工会的选择，工会会选择使其收益
最大的 ，由上述分析已知企业选择的 一定在 曲线上，且工会无差异曲线是越往上越好，那么只需取 与某条无差异曲线的切点即可，因为再往上也不会再有相交。该切点即为该问题的均衡点。
- 实际上，这其中还有一块更优区间，使企业利润更好，工会收益更好，但均衡点不在其中。
3.序贯谈判
博弈要素：
- 参与人：参与人1，参与人2
- 行动、顺序、信息及收益：
- 第一阶段：参与人1提出其收益
，留给参与人2收益 ，参与人2若同意则按此分配，不同意则进入第二阶段 - 第二阶段：参与人2提出参与人1收益
，留给自己收益 ，参与人1若同意则按此分配，不同意则进入第三阶段 - 第三阶段：参与人1获得
，参与人2获得
- 第一阶段：参与人1提出其收益
其他信息：本博弈考虑贴现，贴现因子为
， 为第三阶段价值，第二阶段价值为 贴现因子反映了货币的时间价值，若存入银行
元，利率为 ，则下一阶段的钱为 ，即现值为下一阶段价值的 ， 即为贴现因子。
求解，采用逆向归纳法：
- 在第二阶段，参与人1要选择使其收益最大的行动，
的现值只有 ，只有 ，参与人1才会接受 。参与人2在第二阶段会提出 ，若大于此值，参与人1可能会拒绝，参与人2得不到更好的收益，因此参与人2提出的条件是 。 - 接下来倒推第一阶段，参与人2要选择使其收益最大的行动，若拒绝则可获得收益
，同意则得到 。同样的， 的现值只有 ，只有 ，参与人2才会接受 。参与人1在第一阶段会提出 ，即 。因此，在第一阶段参与人1提出 ，参与人2接受此方案。
无限期讨价还价情况：
- 假设该博弈存在逆向归纳解，此时参与人1和2分别得到
，设参与人1在第一阶段提出 参与人2就会接受此方案。则认为有 ，即第一阶段就接受得到的收益同拒绝的收益以及再拒绝得到的收益相同。则解得 。 - 即第一阶段，参与人1提出
，参与人2会接受此方案。
三、完全非完美信息两阶段博弈
1.子博弈精炼
- 完全非完美信息两阶段博弈的表述：
- 参与人1和2同时从各自的可行集
和 中选择行动 和 - 参与人3和4观察到第一阶段的结果
，然后同时从各自的可行集 和 中选择行动 和 - 收益为
。在实际情况中，可以认为参与人3和4与参与人1和2相同，即二者进行了两个阶段的博弈。
- 参与人1和2同时从各自的可行集
- 化简：已知
，则可推出第二阶段博弈的唯一纳什均衡 ，即如果进入第二阶段，博弈应该会达到该纳什均衡，所以已知 就可以求解该博弈，化简博弈有： - 参与人1和2同时从各自的可行集
和 中选择行动 和 - 收益情况为
- 参与人1和2同时从各自的可行集
- 子博弈精炼解：假定
为第一阶段的唯一纳什均衡，则 为两阶段博弈的子博弈精炼解。
2.对银行的挤提
博弈要素：
- 参与人：投资者1，投资者2
- 行动、顺序及信息：日期1(提款，不提)，日期2(提款，不提)
- 收益：(其中D>r>D/2，R>D)
| (日期1)投资者1/投资者2 | 提款 | 不提 |
|---|---|---|
| 提款 | r,r | D,2r-D |
| 不提 | 2r-D,D | 下一阶段(R,R) |
| (日期2)投资者1/投资者2 | 提款 | 不提 |
|---|---|---|
| 提款 | R,R | 2R-D,D |
| 不提 | D,2R-D | D,D |
从后往前分析：
- 先分析第二阶段(日期2)，其纳什均衡为(R,R)，故在第一阶段的“下一阶段”处的收益为(R,R)
- 再分析第一阶段(日期1)，其有两个纳什均衡(r,r)和(R,R)，即两投资者都在日期1提款或都不提款而在日期2提款。该博弈有两个子博弈精炼解。
3.关税和国际市场的不完全竞争
博弈要素：
参与人：政府1，政府2，企业1，企业2
行动、顺序及信息：政府1和2同时选择制定关税税率
和 ；企业1和2同时观察到关税税率，并同时选择提供国内消费和出口的产量 和 收益：
企业1和2收益其利润：国内收益+国外收益-成本-关税
政府1和2收益其国家总福利：消费者剩余+该国企业利润+关税收入
从前往后分析：
假定政府已经制定关税
，求解企业间博弈的纳什均衡(这是一个完全信息静态博弈)，分解其收益表示为只与 有关和只与 有关的两部分，固定 ，以 为变量，求导求极值： 得
，得 则得到
于是有
解得
解下来求关税制定博弈，化简：
(这个是相等的，只不过化简起来非常麻烦) 固定
对 求导，得极值点 ，即 ，即 该博弈的子博弈精炼解为
。
四、重复博弈
1.两阶段重复博弈
定义：对给定的阶段博弈
，令 表示 重复进行 次的有限重复博弈，并且在下一次博弈开始前，所有以前博弈的进行都可被观测到， 的收益为 次阶段博弈的简单相加。 注意：重复博弈中，最后一次博弈一定要归于一个纳什均衡，但在之前的博弈可能不会归于均衡。
唯一纳什均衡情况：如果阶段博弈
有唯一纳什均衡，则对任意有限的 ，重复博弈 有唯一的子博弈精炼解：即纳什均衡结果在每一阶段重复进行。
例6
考虑两阶段囚徒困境的重复博弈：
- 用子博弈精炼的思想倒推，第二阶段是第一阶段的子博弈，其纳什均衡为
：
| (第二阶段) 参与人1/2 | L2 | R2 |
|---|---|---|
| L1 | 1,1 | 5,0 |
| R1 | 0,5 | 4,4 |
- 因此第一阶段，总收益(第一阶段+第二阶段)如下：纳什均衡任然为
：
| (第一阶段) 参与人1/2 | L2 | R2 |
|---|---|---|
| L1 | 2,2 | 6,1 |
| R1 | 1,6 | 5,5 |
- 实际上，无论第一阶段选择什么，都不影响第二阶段的纳什均衡：
| 参与人1/2 | L2 | R2 |
|---|---|---|
| L1 | 1+x,1+y | 5+x,0+y |
| R1 | 0+x,5+y | 4+x,4+y |
(实际上可以这样理解，参与人在进行第一阶段博弈时，会先预测第二阶段的结果，因为无论第一阶段选择什么，都不影响第二阶段的纳什均衡，所以他们会预测第二阶段的纳什均衡，进而做出第一阶段的选择)
多纳什均衡情况：假定第一阶段参与者预测第二阶段的结果将会是下一阶段博弈的一个纳什均衡。由于这里阶段博弈有不止一个纳什均衡，因而参与者可能会预测根据第一阶段的不同结果，在第二阶段博弈中将会出现不同的纳什均衡。
对将来行动所作的可信的威胁或承诺可以影响到当前的行动，子博弈精炼的概念对可信性的要求并不严格。
多纳什均衡情况下的人为设计：在该情况下，博弈双方会制定协议，确保对方不会背叛，并且自己在此情况下能获得最大利益。该协议的一般思路是，如果在第一阶段双方合作愉快，则在第二阶段双方会归于更好的纳什均衡；如果双方在第一阶段某一方表现出来背叛，则第二阶段另一方将作出惩罚，迫使双方归于不好的纳什均衡。
例7
考虑如下的两阶段重复博弈：
| 参与人1/2 | L2 | M2 | R2 |
|---|---|---|---|
| L1 | 1,1 | 5,0 | 0,0 |
| M1 | 0,5 | 4,4 | 0,0 |
| R1 | 0,0 | 0,0 | 3,3 |
如上博弈有两个纳什均衡
，显然在第二阶段博弈一定要归于其中一个纳什均衡。 的纳什均衡对双方而言是利益更大的。 人为规定，如果第一阶段双方选择了
，则在第二阶段双方会选择 ；如果第一阶段出现了其他8个结果的任何一个，则第二阶段双方会选择 。 可以这样理解，第一阶段的
双方得到了最大利益，合作愉快，在第二阶段自然愿意继续合作，故选择 。第一阶段的其他结果出现，意味着一方做出了背叛，如果参与人1背叛，则参与人2会选择 作为惩罚，参与人1别无选择，只能也选 ，如果参与人2背叛同理。至于为什么如果第一阶段合作愉快，第二阶段为什么不继续选择 ，这是因为第二阶段还可能出现背叛，在最后阶段选择一个纳什均衡使双方都没有理由偏离。
| 参与人1/2 | L2 | M2 | R2 |
|---|---|---|---|
| L1 | 2,2 | 6,1 | 1,1 |
| M1 | 1,6 | 7,7 | 1,1 |
| R1 | 1,1 | 1,1 | 4,4 |
- 根据上述制定规则，第一阶段总收益矩阵如上，即
加上 ，其余加上 。于是该博弈有三个纳什均衡，对应着3个子博弈精炼解： ， ， 。
例8
考虑如下的两阶段重复博弈：
| 参与人1/2 | L2 | M2 | R2 | P2 | Q1 |
|---|---|---|---|---|---|
| L1 | 1,1 | 5,0 | 0,0 | 0,0 | 0,0 |
| M1 | 0,5 | 4,4 | 0,0 | 0,0 | 0,0 |
| R1 | 0,0 | 0,0 | 3,3 | 0,0 | 0,0 |
| P1 | 0,0 | 0,0 | 0,0 | 4,1/2 | 0,0 |
| Q1 | 0,0 | 0,0 | 0,0 | 0,0 | 1/2,4 |
- 如上博弈有4个纳什均衡
，显然第二阶段的博弈一定要归于其中一个纳什均衡。 - 定义
帕累托优于 当且仅当 且 ，定义 与 处于同一帕累托边界上如果二者没有帕累托优于的关系，即二者没有可比性，如 且 。 - 可以发现，
帕累托优于 ，但 与 同一帕累托边界上( 与 也同处帕累托边界，但 与 不同处帕累托边界，帕累托边界没有传递性)。 - 制定协议：如果第一阶段选择
，第二阶段将是 ；第一阶段 ， 为 以外任意策略，第二阶段 ；第一阶段 ， 为 以外任意策略，第二阶段 ；第一阶段 ，第二阶段 。 - 即合作愉快，第二阶段就选择最优纳什均衡；一方想合作，但另一方不配合(背叛)，则会受到惩罚，即想合作一方在第二阶段会选择利于其自身但不利于对方的纳什均衡；大家都不想合作，第二阶段选择最优纳什均衡(这是设计的，如果选择最劣
呢)。
| 参与人1/2 | L2 | M2 | R2 | P2 | Q1 |
|---|---|---|---|---|---|
| L1 | 4,4 | 5.5,4 | 3,3 | 3,3 | 3,3 |
| M1 | 4,5.5 | 7,7 | 4,0.5 | 4,0.5 | 4,0.5 |
| R1 | 3,3 | 0.5,4 | 6,6 | 3,3 | 3,3 |
| P1 | 3,3 | 0.5,4 | 3,3 | 7,3.5 | 3,3 |
| Q1 | 3,3 | 0.5,4 | 3,3 | 3,3 | 3.5,7 |
(上表应该是没有问题的，因为按照协议，任意其他情况
- 最终得到总收益矩阵如上所示，有三个纳什均衡，分别对应子博弈精炼解。
2.无限重复博弈
- 概念辨析：逆向归纳解、子博弈精炼解、子博弈、子博弈精炼、子博弈精炼纳什均衡的概念与关系
- 子博弈：子博弈必须始于单个节点；子博弈包含上述节点之后所有后续节点；子博弈的信息集明确，不破坏任何信息集的完整性，即信息集必须是完整的。
- 子博弈精炼：如果参与者的战略在每一个子博弈中都构成了纳什均衡，则称纳什均衡是子博弈精炼的。
- 逆向归纳解：完全且完美信息两阶段博弈中，逆向归纳解为
- 子博弈精炼解：完全非完美信息的两阶段博弈中，子博弈精炼解为
- 子博弈精炼纳什均衡：完全且完美信息两阶段博弈中，子博弈精炼纳什均衡为
；完全非完美信息的两阶段博弈中，子博弈精炼纳什均衡为 - 逆向归纳解与子博弈精炼解的区别：逆向归纳解是由逆向归纳法得出的解，适用于完全且完美信息博弈，逆向归纳解一定是子博弈精炼解，但逆向归纳法不适用于无限博弈情况，因而子博弈精炼解不一定是逆向归纳解。
- 子博弈精炼解和子博弈精炼纳什均衡的区别：子博弈精炼解只要求均衡战略在均衡路径上是最优的，子博弈精炼纳什均衡要求在每一个子博弈上给出纳什均衡，也就是说，构成子博弈精炼纳什均衡的策略不仅在均衡路径上是最优的，而且在非均衡路径上也是最优的。如果整个博弈是唯一的子博弈，子博弈精炼解与子博弈精炼纳什均衡是相同的。
- 战略：参与人的一个战略是关于行动的一个完整计划，它明确了参与人可能会遇到的每一种情况下对可行行动的选择。
例9
考虑如上的博弈树：
- 通过逆向归纳法，求得其逆向归纳解为
，但其子博弈精炼纳什均衡为 。 - 注意：
中的 指参与人A的策略选择， 指参与人2的策略选择，其中 代表如果参与人A选择 ，则参与人B选择 ， 代表如果参与人A选择 ，则参与人B选择 。 - 一个解和一个均衡的区别，在于解特指始于博弈的第一个决策节点并终于终节点的唯一路径，而均衡同时还包含了另外的始自A选择
后B决策点的路径，这也就是说，均衡包含了参与人B的一个完整战略。
例10
考虑三人博弈，参与人C有两个信息集，如果参与人A选择
- 其中节点d及之后的节点可以认为是一个子博弈，但节点e及之后节点不是一个子博弈，因为其破坏了信息集的完整性。
无限重复博弈的相关定义：
贴现因子：给定贴现因子
，无限收益序列 现值为：
平均收益为：
将博弈将要结束的可能性考虑在内，定义
这样既包含了货币的时间价值，又包含了博弈将要结束的可能性。在无限重复博弈中，即使阶段博弈有唯一的的纳什均衡，无限重复博弈中也可以存在子博弈精炼，其中没有一个阶段的结果是
的纳什均衡。 触发战略：如果没有人选择不合作，合作将一直进行下去；一旦有人选择不合作，就会触发其后所有阶段都不再相互合作。如果
距1足够接近，则采取这种战略，对双方都是无限重复博弈的纳什均衡，且这一纳什均衡是子博弈精炼的。
例11
考虑无限重复囚徒困境，贴现因子为
| 参与人1/2 | L2 | R2 |
|---|---|---|
| L1 | 1,1 | 5,0 |
| R1 | 0,5 | 4,4 |
即要么参与人要么永远选
对于某一参与人，若其选择
，则今后收益都是4，即： ；若其选择 则当阶段获益5，今后收益都是1，即 当且仅当
，即 时选择 最优。
3.古诺双头垄断下的共谋
博弈要素：
- 参与人：企业1，企业2
- 策略：产量
- 收益：
- 协定触发战略：在第一阶段生产垄断产量
的一半， 。第 阶段，如果前面 个阶段两个企业的产量都为 ，则生产 ；否则，生产古诺产量 。
假设贴现因子为
- 一直选择垄断产量的一半，收益为：
如果有一方偏离，偏离的一方先选择另一方选择
的情况下最利于自己的产量，之后一直选择古诺产量：
解得，即该方先选择 ，之后一直选择古诺产量，收益为： 要使触发战略成为纳什均衡，有：
解得。
接下来，固定贴现因子
协定：第一阶段生产
。在第 阶段，如果在此之前的 个阶段两企业的产量都是 ，生产 ；否则，生产古诺产出 。 如果一直生产
，收益为： 如果有一方偏离，情况如上述分析一样，收益为：
则有：
则触发战略成为子博弈精炼纳什均衡的
：
当时， ，当 时， 。
接下来使用第二类威胁的方法：
- 协定：在第一阶段生产垄断产量的一半
。第 阶段，如果两个企业在第 阶段都生产 ，则生产 ；如果两个企业在 阶段的产量都是 ，则生产 ；其他情况下生产 。 - 协定解释：这一战略为参与者提供了两种手段，其一是单阶段的惩罚，这时企业生产
；其二是潜在无限阶段的合作，这时企业生产 。如果任何一个企业偏离了合作，则惩罚开始，如果任何一个企业背离了惩罚，则会使博弈进入又一轮惩罚。如果两个企业都不背离惩罚，则在下一阶段又回到合作。
参考文献
[1] 博弈论基础，罗伯特·吉本斯
- Title: 博弈3-完全信息动态博弈
- Author: OwwO99
- Created at: 2023-09-05 21:22:06
- Updated at: 2023-09-09 20:25:03
- Link: https://redefine.ohevan.com/2023/09/05/2023-9-05-博弈3-完全信息动态博弈/
- License: This work is licensed under CC BY-NC-SA 4.0.