CMSC 5728 Decision Analysis & Game Theory - Lecture 03
- Game Trees (Extensive form)
- The Cournot Duopoly Model
- The Stackelberg Duopoly Model
Game Trees (Extensive form)
- 顺序游玩
- 玩家轮流做出选择
- 玩家可以选择之前的选择
- 游戏被表示成一棵树
- 每个非叶子节点代表一些玩家的决策
- 边缘代表可用选择
- 可以被转换为矩阵 matrix game （Normal form）
- 每个飞叶子节点代表一些玩家的决策点
- 边缘代表可用的选择（可能是无限的）
- 完美信息 Perfect information
- 没有任何两个参与人同时行动，并且所有后行动者能确切知道前行动者选择了什么行动
例子：房地产开发博弈
假设
- 由于规模经济的限定，在一个特定地区只能容纳一个开发商去进行房地产开发
- A 和 B 两个开发商决定是否对该地区的房地产进行开发
- A 具有优先行动的权力，B在观察到A的 行动后决定自己的下一步行动
支付向量
- 如果 A 和 B 同时选择开发，激烈的竞争将导致两败俱伤，每家仅获得 -3 的支付
- 如果 A 和 B 两家中的一家选择开发，另外一家选择不开发，则开发的一家将获得 1 的支付，而不开发的一家获得 0 的支付
- 如果两家都不开发，则其支付分别为 0
房地产开发博弈的扩展式表述（博弈树）
含义
- A 选择开发，B 在观察到 A 选择开发后仍然选择开发，则 A 和 B 的支付分别为 -3，-3
- A 选择开发，B 在观察到 A 选择开发后选择不开发，则 A 获得 1 的支付，而 B 获得 0的支付
- A 选择不开发，B 在观察到 A 选择不开发后，选择开发，则 A 的支付为 0，B 的支付为 1
- A 选择不开发，B 在观察到 A 选择不开发后，仍然选择不开发，则 A 和 B 的支付分别为 0 和 0
问题：如何求解上述博弈（完美信息动态）的 NE ?
把扩展式转化为标准式，然后利用 NE 的定义寻找 NE
B 的纯战略
- 不论 A 开发还是不开发，B 开发，记为（开发，开发）。含义：不论博弈到达 B 的哪一个信息集，B 都选择开发
- A 开发，B 开发；A 不开发，B 不开发，记为（开发，不开发）。含义：博弈到达左信息集（A开发），B 选择开发；博弈到达右信息集（A 不开发)，B 选择不开发
- A 开发，B 不开发；A 不开发，B 开发，记为（不开发，开发）。含义：博弈到达左信息集（A 开发），B 选择不开发；博弈到达右信息集（A 不开发），B 选择开发
- 不论 A 开发还是不开发，B 都不开发，记为（不开发，不开发）。含义：不论博弈到达 B 的哪一个信息集，B 都选择不开发
| B | |||||
|---|---|---|---|---|---|
| （开，开） | （开，不开） | （不开，开） | （不开，不开） | ||
| A | 开发 | -3, -3 | -3, -3 | 1, 0 | 1, 0 |
| 不开发 | 0, 1 | 0, 0 | 0, 1 | 0, 0 | |
不可置信战略 Incredible threat
- B 在决策前可以清楚地看到 A 的选择
- 如果 A 选择开发，B 的最优选择是不开发
- 如果 A 选择不开发，B 的最优选择是开发，而不是不开发
- 因此（不开发，不开发）是 B 的不可置信战略，该 NE 不合理
剔除完美信息博弈不合理 NE 的逻辑：只有当一个站略规定的行动规则在所有可能的情况下都是最优时，它才是一个合理的战略
在完美信息动态博弈中，会有部分 NE 包含不可置信的战略，精练 NE 的思路就是利用扩展式表述剔除包含不可置信战略 NE
子博弈精练 Subgame perfect（SPNE）
- （完美信息博弈中），每一个决策结及其后续结构成一个子博弈
- 博弈本身构成自身的一个子博弈
房地产开发博弈中的三个子博弈
- 自身
- 两个只有开发商 B 决策的单人博弈
SPNE：一个战略组合
它是整个博弈的 NE
其相关行动规则在每一子博弈上都是 NE
在所有可能的路径上到达均衡，不仅包括均衡路径（equilibrium path，一个特
定的NE决定的原博弈树上唯一的一条路径），还包括所有其他在不同子博弈中
的分支路径（非均衡路径）
求解 SPNE 思路
- 寻找整个博弈的可能NE(可以通过把扩展式转化为标准式表述实现)
- 在每一个子博弈(博弈的分支路径)验证可能的NE是否达到均衡
- 剔除只在某些分支路径达到均衡，而在另一些分支路径无法达到均衡的NE
案例分析
(不开发，(开发，开发))：
- 在子博弈B1中，B的最优战略是不开发
- 在子博弈B2中，B的最优战略是开发
- NE (不开发，(开发，开发))中B的 均衡战略(开发，开发)在子博弈B2上构成NE，但在子博弈B1上不构成NE
- 上述NE不是一个SPNE
(开发，(不开发，开发))：
- B的均衡战略(不开发，开发)(如果A 开发，B不开发；如果A不开发，B开发) 无论在子博弈B1还是子博弈B2上都构成 NE
- 上述NE构成开发博弈唯一的SPNE
- “A开发，B不开发”成为开发博弈唯一合理的均衡结果
小结：SPNE 与 NE 的关系
- SPNE是NE在完美信息博弈中的精练(refinement)解概念(引入参与人行动的先后顺序)
- SPNE一定是NE
- 但NE不一定都是SPNE
逆向归纳法 backward induction
一种求解 SPNE 的简便方法
以开发博弈为例
- 首先在从最后一个决策结开始的子博弈 中寻找该博弈中的NE
- 只有B决策的单人博弈B1和B2
- B1:已知A选择开发，B的最优选择是不 开发(开发的支付-3低于不开发的支付 0)
- 剔除不可置信的战略开发
- B2:已知A选择不开发，B的最优选择是 开发(开发的支付1高于不开发的支付0)
- 剔除不可置信的战略不开发
- 在博弈进入B的决策阶段，B的最优行动 规则: (不开发，开发)
- 含义:如果A在第一阶段选择开发，B在 第二阶段选择不开发;如果A在第一阶段 选择不开发，B在第二阶段选择开发
- 一个新的博弈:第二阶段单人博弈的均 衡战略和初始结A的行动共同构成
- 只有开发商A在决策
- A在第一阶段的最优战略:开发(A选择开发的支付1高于选择不开发的支付0)
- A在第一阶段理性预期到B在第二阶段的 最优战略，A第一阶段的最优选择是开发
开发博弈的扩展式表述及其SPNE结果
