暨南大学博弈论课程笔记

发表于 2024-03-08 分类于课程笔记，博弈论本文字数： 6.7k

Game Theory

研究问题：决策主体的行为**发生直接相互作用（区别于决策论）的决策及其均衡**问题。

基本假设:

完全理性的参与人

参与人的行为和目标有一致性，为了目标的最大化前后一致的努力：
- 参与人决策的偏好具有一致性，对具体的决策问题保持稳定；
- 参与人完全理解决策问题，可以对决策问题中的不确定性进行建模分析；
- 参与人具有强大的接近无限的逻辑计算推理能力；
- 猜数问题：多个参与人同时报数，将报数之和x0.7后取整= $R$ ，谁最接近这个数谁赢。
  - 2 人：报 0 >= 平局
  - 3 人： $R \leq 70$ ，故若报数 $> 70$ 必输，我完全理性，不报 $> 70$ 。我知道其他人也完全理性，进而大家都 $\leq 70$ ，进而又使得 $R \leq 49$ 。每个人都觉得其他人是完全理性的，进而依次递推又使 $R \leq 0$ ，推出报 $> 0$ 必输。但 (0, 10, 50) 中，10 又赢了，若不加入黑斜体的假设，则与前面的结论相悖，加入假设后，这个结果将不可能在该博弈问题中存在，故不与前面的结论矛盾。
  - 故只下关于参与人的假设，并不能解决博弈论问题。
共同知识（博弈论特有的假设）
- 完全理性的参与人是共同知识；
- 博弈问题的结构是共同知识；
- 以上两点都构成无穷尽的相互知识（我知道每个人都知道，每个人都知道每个人都知道）；
- 有了共同知识，每个人都知道自己的结果会如何影响其他人的结果。

分析方法：内省式思维（Put yourself to others truth）

合作博弈：博弈之前制定协议，遵守协议进行博弈，约束参与方行为；

非合作博弈：不约束参与方行为，每个人都仅为了自己的利益进行决策，允许存在博弈过程中的合作行为，但目标都是使自己利益最大化。是当今博弈论问题主要讨论的问题。

分类方法 1：完全信息博弈、不完全信息博弈；博弈信息是否存在不确定的随机因素；
分类方法 2：静态博弈、动态博弈；参与人的最终决策是否同时做出；
课程主讲：完全信息静态博弈、完全信息动态博弈；

博弈问题的解：所有的参与人对博弈结果的一致性预测。

基本元素及符号

参与人 Player： $Γ = {1, 2, 3, \dots, n}$
行动 Action：参与人在某个时间点的决策变量
- $a$ 参与人的行动
- $A$ 参与人的行动集， $A = {a, b, . . .}$ ,
- $a = (a_{1}, a_{2}, . . ., a_{n})$ 有序集合表示 $n$ 个参与人的行动组合（也就是每个参与人采用的决策的组合）
战略 Strategy：参与人的行动规则（在每一种轮到自己行动的情形下应该采取的行动）。也就是针对其它参与人的决策情况，自己做出的进一步行动。在静态博弈问题中，战略和行动是一回事，所以行动没有战略重要。

在 $n$ 人博弈中，用 $s_{i}$ 表示参与人 $i$ 的战略， $X_{i}$ 表示参与人 $i$ 在博弈中可能面临的所有决策情形的集合（观测集）。即 $s_{i} : X_{i} \to A_{i}$ (e.g. $s_{1}^{1} (x_{1}) = a$ )
- $s = (s_{1}, s_{2}, \dots, s_{n})$ 所有参与人的战略组合
- $s_{i}^{j}$ 表示第 $i$ 个参与人的第 $j$ 个战略
- $S = {s}$ 所有战略组合构成的集合
支付 Payoff / 效用函数 utility function：参与人在博弈中的所得。在一种特定的博弈情形（i.e. 行动组合/战略组合）下，参与人得到的确定或期望（i.e. 可以是确定值也可以是统计值）的效用水平。
- $u_{i} = u_{i} (s_{1}, s_{2}, \dots, s_{n})$ 强调效用函数和战略组合有关
- $s_{- i} = (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{n})$ 表示除 $i$ 参与人外的战略组合。 $u_{i} = u_{i} (s_{i}, s_{- i})$ 强调效用函数不止和 $i$ 的战略有关，也和其他人的战略有关。

静态博弈问题 / 战略式博弈

描述博弈

战略式博弈，要求：

所有参与人只行动一次
所有参与人行动同时进行

非常适合用于描述静态博弈问题。

参与人 $Γ$
每个参与人的非空战略集 $S_{i}$
每个参与人定义在所有战略组合 $\prod_{i = 1}^{n} S_{i}$ 上的偏好关系，用效用函数表示

若 $n < \infin$ , $| S_{i} | < \infin$ 称为有限博弈，用 $G = ⟨ Γ; (S_{i}), (u_{i}) ⟩$

囚徒困境

两名犯罪嫌疑人被审讯时，彼此坦白或抵赖都会影响到最终对方的支付。

分析结果是在非合作博弈中，双方都应该坦白。若事先制定了同盟，则都应抵赖。

	坦白	抵赖
坦白	-4, -4	0, -6
抵赖	-6, 0	-1, -1

在非合作博弈中，完全理性的参与人，一定会偏离 $s_{i} = (抵赖，抵赖)$ 这个战略组合，而选择坦白。这便是“困境”的含义。

占优战略/严格占优战略

Strictly Dominent Strategy

在这种战略中，无需理会对方的选择而做出的决策。在囚徒困境中，选择坦白就属于占优战略。在解决博弈问题中是非常优越的性质。

Definition: 在 $n$ 人博弈中，如果对于所有其它参与人的选择 $s_{- i}$ ， $s_{i}^{*}$ 都是参与人 $i$ 的最优选择。i.e.

\begin{aligned} \forall s_{i} \in S_{i} \and s_{i} \neq s_{i}^{*} \\ \forall s_{- i} \in \prod_{j = 1, j \neq i}^{n} S_{j}, u_{i} (s_{i}^{*}, s_{- i}) > u_{i} (s_{i}, s_{- i}) \end{aligned}

则称 $s_{i}^{*}$ 是参与人 $i$ 的严格占优战略。 $>$ 强调“严格”，但一般没有人会在此处变成 $\geq$ 。

$\prod_{j = 1, j \neq i}^{n} S_{i}$ 表示除了 $i$ 之外的所有参与人的战略组合的集合。

若参与人存在占优战略，那他肯定会选择占优战略。此称为参与人的占优行为。

占优战略均衡：在 $n$ 人博弈中，如果对所有参与人 $i$ ，都存在占优战略 $s_{i}^{*}$ ，则占优战略组合 $s^{*} = (s_{1}^{*}, s_{2}^{*}, \dots, s_{n}^{*})$ 称为占优战略均衡。

严格劣战略

Strictly Dominated Strategy

在劣战略中，严格二字比较重要，不可省略（用于区分弱战略）。存在一个战略永远好于另一个战略。

Definition: 在 $n$ 人博弈中，如果对于参与人 $i$ 存在战略 $s_{i}^{'}, s_{i}^{″} \in S_{i}$ 使得

\forall s_{- i} \in \prod_{j = 1, j \neq i}^{n} S_{j}, u_{i} (s_{i}^{″}, s_{- i}) > u_{i} (s_{i}^{'}, s_{- i})

则称战略 $s_{i}^{'}$ 为参与人 $i$ 的严格劣战略，或称战略 $s_{i}^{″}$ 相对于 $s_{i}^{'}$ 占优。

参与人不一定会选择 $s_{i}^{″}$ ，但一定不会选择 $s_{i}^{'}$ 。此称为参与人的剔除劣战略行为。

剔除劣战略行为：对于战略式博弈 $G = ⟨ Γ; S_{1}, S_{2},, \dots, S_{n}; u_{1}, u_{2}, \dots, u_{n} ⟩$ ，如果 $s_{i}^{'}$ 是参与人 i 的严格劣战略，那么实际上是构造一个新的战略界 $S_{i}^{'} = S i ∖ s_{i}^{'}$ ， $G$ 转化为

G^{'} = ⟨ Γ; S_{1}, S_{2}, \dots, S_{i}^{'}, \dots, S_{n}; u_{1}, u_{2}, \dots, u_{n} ⟩

重复剔除劣战略可解

重复剔除劣战略: 可以反复剔除掉一些严格劣战略，就是在排除一个战略后，又可以继续排除另一个战略（可以不是同一个参与人的战略）；
重复剔除的占优均衡：所有参与人都可以剔除劣战略直到只剩一个战略；
重复剔除劣战略可解的：如果上面满足，则该博弈问题是重复剔除劣战略可解的。

🔦Example:

b1: a1=1 a2=3 a3=2 --> a2

b2: a1=3 a2=2 a3=1 --> a1

b3: a1=1 a2=2 a3=3 --> a3

a1: b1=0 b2=3 b3=1 --> b2

a2: b1=1 b2=2 b3=0 --> b2

a3: b1=4 b2=3 b3=2 --> b1

依次剔除劣战略 b3 --> a3 --> b1 --> a2

所以只剩下 a1 和 b2，这是重复剔除劣战略可解的

在解题过程中，要看清表格，分清行列，分清单元格内的数字分别是谁的支付。

弱劣战略

Definition: 在 $n$ 人博弈中，如果对于参与人 $i$ 存在战略 $s_{i}^{'}, s_{i}^{″} \in S_{i}$ 使得

\begin{aligned} \forall s_{- i} \in \prod_{j = 1, j \neq i}^{n} S_{j}, u_{i} (s_{i}^{″}, s_{- i}) \geq u_{i} (s_{i}^{'}, s_{- i}) \\ \exists s_{- i}^{'} \in \prod_{j = 1, j \neq i}^{n} S_{j}, u_{i} (s_{i}^{″}, s_{- i}^{'}) > u_{i} (s_{i}, s_{- i}^{'}) \end{aligned}

则称战略 $s_{i}^{'}$ 为参与人 $i$ 的严格若劣战略，或称战略 $s_{i}^{″}$ 相对于 $s_{i}^{'}$ 弱占优。

条件中，不止把 $>$ 都改成 $\geq$ ，还要排除两个战略的支付完全一样的情况。

⚠️ 在重复剔除劣战略的过程中，如果每次可以剔除的劣战略（严格劣战略、弱劣战略）不止一个，那么各个劣战略剔除的顺序不同，得到的博弈结果就可能不同（也就是说，可能只是真实结果的一部分。貌似有点像拓扑排序？）。除非每次剔除的都是严格劣战略。

Nash 均衡

纯战略 Nash 均衡

Pure Strategy

参与人确定地选择一种战略。

一个战略组合 $(s_{1}^{*}, s_{2}^{*}, \dots, s_{n}^{*})$ 能够成为博弈的结果，就必须对于所有参与人，当其他参与人选定了上述战略后，该参与人选择上述战略得到的支付不小于选择其它战略组合的支付。

Definition [Nash 均衡]：在一个给定的 $n$ 人战略式博弈 $G = ⟨ Γ, (S_{i}), (u_{i})_{n} ⟩$ 中，战略组合 $(s_{1}^{*}, s_{2}^{*}, \dots, s_{n}^{*})$ 是一个 Nash 均衡，当且仅当 $\forall i \in Γ, \forall s_{i} \in S_{i}$ ，都有 $u_{i} (s_{i}^{*}, s_{- i}^{*}) \geq u_{i} (s_{i}, s_{- i}^{*})$ 或写作

\forall i \in Γ, s_{i}^{*} \in {argmax}_{s_{i} \in S_{i}} u_{i} (s_{i}, s_{- i}^{*})

Nash 均衡是完全信息静态博弈问题的解。其指出了面对完全信息静态博弈问题的时候，已经存在了解决它的方法，但本质上一种枚举法，仍然存在着问题。

推论：

一个战略组合 S’ 不是 Nash 均衡，就一定不是博弈问题的解；
占优战略均衡一定是 Nash 均衡。重复剔除的占优均衡一定是 Nash 均衡

解法：有没有严格占优战略 > 有没有严格劣战略 > Nash 均衡

划线法

两个参与人，每个参与人战略有限

记得第一列表示参与人 1，第一行表示参与人 2，支付按照参与人的顺序编写

	→ 2的战略
↓ 1的战略	b1	b2	b3
a1	3,2	1,3	2,5
a2	2,4	4,5	3,4
a3	4,2	3,1	2,3

考察 (a1, b1)，若 1 选择 a1，2可以选择 b3 来获得更大的支付，所以 (a1,b1) 不是Nash 均衡。

考察 (a2, b2)，若 1 选择 a2，2 选择 b2 最优。若 2 选择 b2，1 选择 a2 最优。也就是他们相互构成了最优战略的战略组合。此时是 Nash 均衡。

若参与人 2 先选择战略，则参与人 1 的最优战略划线表示出来。反过来，若参与人 1 先选择战略，则参与人 2 的最优战略划线表示出来。得到：

	→ 2的战略
↓ 1的战略	b1	b2	b3
a1	3,2	1,3	2,5
a2	2,4	4,5	3,4
a3	4,2	3,1	2,3

可看到 (a2, b2) 中存在着两个划线，此战略组合为 Nash 均衡。

箭头法

两个参与人，每个参与人战略有限

	→ 2的战略
↓ 1的战略	b1	b2	b3
a1	↓ 3,2 →	1,3	2,5
a2	2,4	4,5	3,4
a3	4,2	3,1	2,3

如果有人想偏离这个战略组合，则这个战略组合一定不是 Nash 均衡。

用箭头表示参与人想偏离这个战略组合，对每个战略组合都进行一次计算。

如果有某个战略组合不存在箭头，则该组合是 Nash 均衡。和划线法相比，更像排除法。

猎兔博弈

只有双方同时选择狩猎鹿的时候，才能狩猎成功。狩猎兔则不需要。

	鹿	兔
鹿	5,5	0,2
兔	2,0	2,2

存在两个 Nash 均衡 (5, 5) (2, 2)

如果一个问题存在多个 Nash 均衡，则需要根据具体的情形来判断哪个均衡更好。但其实没有一个规定的方法来判断哪个更好，属于开放性问题。

协调博弈：两个参与人选择一致的行为时获得最高的支付。

对称博弈：参与人 1 和 2 没有区别，怎么变换都可以，偏好和支付都一样。

性别博弈

夫妇决定出去玩，只有同时选到同一个才能出去玩。

↓丈夫→妻子	足球	芭蕾
足球	4,2	0,0
芭蕾	0,0	2,4

存在两个 Nash 均衡 (4, 2) (2, 4)

属于协调博弈。

鹰鸽博弈

两只鸟争夺领地，可以选择把自己表现为鹰或鸽。如果都是鸽，则平分；如果都是鹰，则两败俱伤；如果一只为鹰，一只为鸽，则由鹰独占。

	鹰	鸽
鹰	-2,-2	2,0
鸽	0,2	1,1

反协调博弈：必须选择不同的战略才能达到 Nash 均衡。

混合战略 Nash 均衡

参与人对战略的选择不再具有确定性，而是根据以一定的概率选择某个战略。

在给定的 $n$ 人战略式博弈 $G = ⟨ Γ, (S_{i})_{n}, (u_{i})_{n} ⟩$ 中，对任意参与人 $i$ ，设 $S_{i} = s_{i}^{1}, s_{i}^{2}, \dots, s_{i}^{k_{i}}$ ，则参与人 $i$ 的一个混合战略为定义在 $S_{i}$ 上的一个概率分布 $σ_{i} = (σ_{i}^{1}, σ_{i}^{2}, \dots, σ_{i}^{k_{i}})$ ， $σ_{i}^{j}$ 表示参与人 $i$ 选择战略 $s_{i}^{j}$ 的概率。即满足 $0 \leq σ_{i}^{j} \leq 1, \sum_{j = 1}^{j = k_{i}} = 1$ 。

如抛硬币问题中， $σ_{1} = (0.5, 0.5)$

➗ 符号定义：

$Σ_{i} = {σ_{i}}$ 表示参与人 i 的混合战略空间（对应于 $S_{i}$ 和 $s_{i}$ ）
$σ = (σ_{1}, σ_{2}, \dots, σ_{n})$ 表示混合战略组合。 $σ_{i} \in Σ_{i}$ 。（对应于 $s = (s_{i})_{n}$ ）
$Σ$ 表示混合战略组合空间。 $Σ = \prod_{i = 1}^{n} Σ_{i}$
$σ = (σ_{i}, σ_{- i})$
$u_{i} (s_{i}, s_{- i}) = v_{i} (σ_{i}, σ_{- i})$ 表示支付的期望


概率		q	1-q
	战略	b1	b2
p	a1	x1, y1	x2,y2
1-p	a2	x3,y3	x4,y4

若决策时独立的，则可以分别计算每一个战略组合出现的概率，用这些概率乘以对应的支付得到支付的期望。

Definition [混合战略 Nash 均衡]：在有限 $n$ 人战略式博弈 $G = ⟨ Γ; S_{1}, \dots, S_{n}; u_{1}, \dots, u_{n} ⟩$ 中，混合战略组合 $σ^{*} = (σ_{1}^{*}, σ_{2}^{*}, \dots, σ_{n}^{*})$ 为一个 Nash 均衡，当且仅当 $\forall i \in Γ, \forall σ_{i} \in Σ_{i},$ ，都有 $v_{i} (σ_{i}^{*}, σ_{- i}^{*}) \geq v_{i} (σ_{i}, σ_{- i}^{*})$

求解方法

在参与人 $i$ 的最优混合战略中 $σ_{i}^{j *} = (σ_{i}^{1 *}, \dots, σ_{i}^{n *})$ ， $\forall σ_{i}^{j *} > 0, v_{i} (s_{i}^{j}, σ_{- i}) = v_{i} (σ_{i}^{k}, σ_{- i})$ 。

因为可能在最优混合战略中出现的战略，一定是因为它在其他人选择了最优混合战略的最优纯战略，否则，它就不会出现在这个混合战略中。注意用概率的角度来理解此时的“最优”是指“期望最优”。

引理：在有限 $n$ 人战略是博弈 $G = ⟨ Γ; S_{1}, \dots, S_{n}; u_{1}, \dots, u_{n} ⟩$ 中，混合战略组合 $σ^{*} = (σ_{1}^{*}, σ_{2}^{*}, \dots, σ_{n}^{*})$ 为一个 Nash 均衡，当且仅当 $\forall i \in Γ, σ_{i}^{*}$ 的支集 $S_{i} (σ_{i}^{*})$ 的每个纯战略都是给定 $σ_{- i}^{*}$ 下的最优反应。

所谓“支集”就是以正概率出现在 $σ_{i}$ 中的纯战略。

😆 也就是说，在达到最优混合战略的 Nash 均衡时候，当且仅当对于任意一个参与人，他选择他的混合战略中可能出现的（正概率）的任何一个纯战略时，都是最优的，没有任何偏好的。


概率		q	1-q
	战略	b1	b2
p	a1	x1, y1	x2,y2
1-p	a2	x3,y3	x4,y4

\begin{array}{r} V 1 (a 1, σ_{2}) = q (x 1) + (1 - q) x 2 \\ V 1 (a 2, σ_{2}) = q (x 3) + (1 - q) x 4 \\ V 2 (σ_{1}, b 1) = p (y 1) + (1 - p) y 3 \\ V 2 (σ_{1}, b 2) = p (y 2) + (1 - p) y 4 \end{array}

列方程

\begin{array}{r} V 1 (a 1, σ_{2}) = V 1 (a 2, σ_{2}) \\ V 2 (σ_{1}, b 1) = V 2 (σ_{1}, b 2) \end{array}

就可以用 $x i, y i$ 来表示 $p, q$ ，进而表示 $σ_{1}$ 和 $σ_{2}$

↓丈夫→妻子	足球	芭蕾
足球	4,2	0,0
芭蕾	0,0	2,4

V 1 (F, σ_{2}) = 4 q V 1 (B, σ_{2}) = 2 (1 - q) V 2 (F, σ_{2}) = 2 p V 2 (B, σ_{2}) = 4 (1 - p) 4 q = 2 (1 - q) q = 1 / 3 2 p = 4 (1 - p) p = 2 / 3 σ = ((2 / 3, 1 / 3), (1 / 3, 2 / 3))

考试注意事项：

注明 p, q 分别是什么，注意其分别是属于哪个参与人的，不要因为其出现在 V1 还是 V2 而判断其属于参与人 1 还是参与人 2
注意参与人顺序
给出 $σ = ((., .), (., .))$

Nash 均衡的存在

存在性定理1：每一个有限的战略式博弈至少存在一个 Nash 均衡（也就是至少有纯战略和混合战略 Nash 均衡之一）。

Nash 均衡的多重性

多个 Nash 均衡的存在，弱化了 Nash 均衡的意义，所以需要在多个 Nash 均衡中，选择若干个 Nash 均衡。

均衡精炼（规范式方法）：

子博弈精炼 Nash 均衡
精炼贝叶斯 Nash 均衡（不讲）

非规范式的方法：

焦点效应：可以把所有参与人的注意力都集中在一个特定的 Nash 均衡上的事情，称为一个焦点。

廉价磋商（cheap talk）。在博弈开始前，双方达成一个不具约束力、不需要任何成本的协议，来指导当出现多重 Nash 均衡的时候，如何处理多重 Nash 均衡。来把大家的注意力从多个 Nash 均衡聚焦在其中一个 Nash 均衡上。存在有效和无效的区分。
相关均衡：根据某个共同观测到的信号选择战略。

完全信息动态博弈 / 扩展式博弈

描述博弈：扩展式博弈

参与人的集合
参与人的行动顺序
每个参与人行动时面临的决策问题
1. 可供选择的行动方案
2. 行动时所了解的信息（知不知道其他人做了什么决策，这种信息往往非常复杂）
支付函数

2 3 相当于战略式博弈的战略

博弈树：描述了行动顺序、描述了行动方案

树的叶子中，支付的排序是按照决策的顺序来决定的，也就是谁先决策谁排在前面

graph TB
21(2)
22(2)
1 -- L --> 21
1 -- R --> 22
31(3)
32(3)
33(3)
34(3)
21 -- L' --> 31
21 -- R' --> 32
22 -- L' --> 33
22 -- R' --> 34
22 -.- 21
L1(100, 200, 300)
L2( )
L3( )
L4( )
L5( )
L6( )
L7( )
L8( )
31 -- L'' --> L1
31 -- R'' --> L2
32 -- L'' --> L3
32 -- R'' --> L4
33 -- L'' --> L5
33 -- R'' --> L6
34 -- L'' --> L7
34 -- R'' --> L8

信息集：参与人 i 的信息集 $I_{i}$ 是参与人 $i$ 的决策节点的一个集合（不一定是全集），且满足：

$I_{i}$ 中的每个节点都是参与人 i 的决策节点；
当博弈到达 $I_{i}$ 中的某个决策节点时，参与人 $i$ 知道自己在 $I_{i}$ 中的决策节点上；

但是，不知道自己究竟在哪一个具体决策节点上。

信息集描述了参与人 $i$ 所知道的信息，这些信息可以在博弈树上找到，但往往是找到一堆节点，并不知道自己是在具体的哪个节点。比如知道自己在左子树，但不知道究竟在左子树的哪个节点。

博弈树中同属一个信息集的节点用虚线连接。图中为 参与人 2 不知道参与人 1 的决策时的信息集。

完美记忆：每个参与人都记得之前做过的任何行动

扩展式博弈的战略：参与人在每个信息集上的行动规则。

$H_{i}$ 参与人 i 的信息集的集合 $H_{i} = I_{i}$ 。
$A_{i} (I_{i})$ 参与人 i 在所有信息集上的行动集。
$A_{i} (H_{i})$ 参与人 i 在所有信息集上的行动集 $A_{i} (H_{i}) = \cup_{I_{i} \in H_{i}} A_{i} (I_{i})$
战略： $s_{i} : H_{i} \rarr A_{i} (H_{i})$ 也就是讲清在所有信息集上的行动，才是一个完整的战略。

graph TD
21(2)
11(1)
12(1)
L1(2, 1)
L2(1, 1)
L3(1, 2)
L4(3, 0)
11 ==A==> 21
11 --B--> L1
21 ==C==> 12
21 --D--> L2
12 ==E==> L4
12 --F--> L3

参与人 2： $I_{2} ({x_{2}}), S_{2} = {C, D}$

参与人 1： $I_{1} ({x_{1}}), I_{1} ({x_{3}}), S_{1} = {A, B} \times {E, F} = {(A, E), (A, F), (B, E), (B, F)}$

即便 (B, E) (B,F) 不会出现，但依然应该出现在参与人 1 的战略中，这才是完整的战略

特点：

扩展式博弈中可能发生的每个事件序列都可以用博弈论中的一条路径来表示。如 1 选 A，2 选 C，1 再选 E，可以由上图的博弈树中的加粗的路径表示；
扩展式博弈中，参与人的每个战略组合，也是与博弈树中的路径对应的；比如上文的例子，可以表示为战略组合 ((A, E), C)，也就是博弈树中加粗的路径（谁先做决策，谁先写前面）。多个不同的战略组合可能对应同一条路径，如 ((A, F), D), ((A, E), D)；
1 + 2 = 战略组合实际上描述的就是事件序列。

扩展式博弈的转换

如何从扩展式博弈转换为战略式博弈。根据博弈树（上面最近的哪个），可以得到不同的战略组合，各个的参与人可以得到的支付。

参与人 1 ↓ 参与人 2 →	C	D
(A, E)	3, 0	1, 1
(A, F)	1, 2	1, 1
(B, E)	2, 1	2, 1
(B, F)	2, 1	2, 1

根据划线法，可以得到两个 Nash 均衡：((B, E), D)，((B, F), D)。

扩展式博弈的问题一定可以一一对应地转换为一个战略式博弈的问题

graph TD
1(企业1)
21(企业2)
22(企业2)

1 -- 开发 --> 21
1 -- 不开发 --> 22
21 -- 开发 --> -400,-400
21 -- 不开发--> 200,0
22 -- 开发 --> 0,200
22 -- 不开发--> 0,0

由于扩展式博弈转换为战略式博弈丢失了很多信息，所以并不一定得到的每个 Nash 均衡都是扩展式博弈的最终的 Nash 均衡。转换为战略式博弈问题后，可以得到多个 Nash 均衡:

(不, (开, 开)) ：(开，开) 分别对应企业 2 两个决策节点的决策。也就是 A 开发与否， B 都选择开发。不合理。
(开, (不, 开)) ：也就是 A 开发 B 就不开发，反之就开发。合理。
(开, (不, 不)) ：也就是 A 开发与否，B 都不开发。不合理。

除此之外，还有(不开, (开, 不)) 这个不是战略式博弈的 Nash 均衡的战略组合也合理。

综上，我们可以用这种方法解决 Nash 均衡的多重性问题，此即为 精炼法。

子博弈精炼 Nash 均衡

通过定义更加精炼的博弈解来剔除不合理的 Nash 均衡。也叫 子博弈 (Subgame) 精炼 (Perfect) Nash 均衡 (SPNE)。

子博弈：

原博弈的一部分
始于原博弈一个位于单点信息集（也就是只有一个决策点组成的信息集）的决策节点 x，并由 x 及其后续节点组成
具有与原博弈相同的信息结构（每个参与人在做决策的时候知道什么）

可以形象地理解为树中的某个节点及其所有子节点（但要保证满足第 3 条要求，即在存在虚线，也就是标明信息集的时候，会存在信息结构，不能够切断信息集改变其信息结构）。根据其节点的不同，称呼为 $Γ (x_{i})$

逆向归纳法：在原博弈有限（等价于子博弈个数有限），则可以通过逆向归纳法得到 SPNE

逆向归纳法的特点：

是一种动态规划的方法；
尤其适用于完美信息问题（Perfect info）（每个参与人的决策节点都是单点信息集）；
用逆向归纳法求出的 Nash 均衡不仅在均衡路径上给出了参与人的选择，在非均衡路径上也给出了参与人的选择。不包括那些不可置信（不合理）的行为（威胁）；
本质是重复剔除劣战略

海盗分赃问题：五个海盗分一百枚金币，由海盗 1 开始提出方案，若提出方案有半数或半数以上赞成，则通过方案；反之，则将海盗 1 丢入海里，剩下的海盗继续分赃，由海盗 2 提出方案，以此类推。

海盗 5：(0, 0, 0, 0, 100)
海盗 4：(0, 0, 0, 100, 0) 无论提出什么方案，都可以半数通过
海盗 3：(0, 0, 99, 0, 1) 海盗 5 一定会赞成，不然海盗 4 一定不会给海盗 5 留金币
海盗 2：(0, 99, 0, 1, 0) 海盗 4 一定会赞成，不然海盗 3 一定不会给海盗 4 留金币
海盗 1：(98, 0, 1, 0, 1) 海盗 3 和 5 一定会赞成，不然海盗 4 一定不会给他们留金币

由此，就可以知道，从海盗 4 开始就可以动态规划，即海盗i 在海盗i+1 的基础上，海盗i 给海盗i+1 不分金币且活着的海盗分给一个金币。虽然海盗 1 面临着被丢入水中的威胁，但这种威胁是不可置信的，所谓的子博弈精炼法，便是去除了多重 Nash 均衡中的不可置信的威胁。

海盗 1 优势最大，如此不平衡的方案最终仍然会通过，这说明完全理性的博弈问题并不适用于现实问题，完全理性的参与人并不能代表现实中的人。

承诺行动

在博弈开始前，参与人采取的某种改变自己支付或行动空间的行动，称之为承诺行动。使得原本不可置信的威胁变为可信的。

对参与人本身有利；
承诺行动是有成本的（如果是没有成本的，那可以退回则退化成了承诺行动不存在的情况）；