读书笔记: 博弈论导论 - 总结
读书笔记: 博弈论导论 - 总结
总结
本文是Game Theory An Introduction (by Steven Tadelis) 的学习笔记的总结。
博弈论
博弈论是关于智能理性决策者的协作和冲突的数学模型的研究。
博弈论的目的可以说是研究寻找博弈均衡的方法。
博弈论的直接目标不是找到一个玩家的最佳策略，而是找到所有玩家的最理性策略组合。
我们称最理性策略组合 为均衡 。
博弈论（也叫逆向博弈论）的另外一个作用是机制设计，根据期望的结果，设计一个博弈体系。
博弈论的分类
这本书中将博弈论的只是分为四类：
- 完整信息的静态博弈
- 完整信息的动态博弈
- 不完整信息的静态博弈
- 不完整信息的动态博弈
博弈论的数学模型
-
普通形式博弈(normal-form game)的数学表达
- 一个有限的玩家集合, N = {1, 2, \cdots, n}
- 每个玩家的纯策略集合的组合, {S_1, S_2, \cdots, S_n}
- 一套收益函数, {v_1, v_2, \cdots, v_n}，对于每个玩家，每一种所有玩家选择的策略组合，都有一个收益值。
v_i: S_1 \times S_2 \times \cdots \times S_n \text{ for each } i \in N
-
贝叶斯博弈(Bayesian Game)
用于描述不完整信息博弈。
术语
-
静态博弈(static game) vs 动态博弈(dynamic game)
静态博弈指所有玩家同时、独立做出选择。也叫做同时博弈(Simultaneous game)
动态博弈指所有玩家按照次序做出选择。也叫做序贯博弈(Sequential game)、序列博弈。 -
完整信息博弈(Complete information game) and 不完整信息博弈(Incomplete information game)
完整信息博弈是指所有知识被所有玩家都了解，就是成为了公共知识。
不完整信息博弈是指一个玩家不知道其他玩家的部分信息(actions, outcomes, payoffs)。 -
完美信息博弈(Information perfect game) vs 不完美信息博弈(Information imperfect game)
完美信息博弈指一个玩家知道对手做出了选择，并且知道对手的选择是什么。比如：围棋。
不完美信息博弈指一个玩家知道对手做出了选择，但是不知道对手的选择是什么。比如：德州扑克。 -
普通形式博弈(Normal-Form Game) vs 扩展形式博弈(Extensive-Form Game)
博弈的数学化定义方式。
普通形式博弈比较简单，适用描述信息较少的情况，比如：两个玩家的纯策略的静态博弈。
扩展形式博弈用于形式化描述博弈。无论完美信息还是不完美信息，完整信息还是不完整信息都可以。
针对不完美信息，支持信息集的概念。
针对不完整信息，支持Nature和类型概念。 -
Subgame-perfect equilibrium
这里主要说perfect这个词，这个词和equilibrium用在一起时，常常有精炼(refinement)的意思，表示优化均衡的结果。 -
序贯(sequential)
序贯表示连续的。 -
信念(beliefs)，
玩家i的一个信念就是他的对手们的一个可能的策略组合。 -
最佳反应(Best Response)
当其他玩家策略已知时，玩家i的优势策略就是其最佳反应。
这是博弈论的中心。理性，序贯理性的意味就是最佳反应。均衡的结果也来自于最佳反应。
最佳反应：对于玩家i，给定其对其他玩家的信念，他会选择在这个信念上对自己最好的行为。 -
序贯理性(Sequential Rationality)
在博弈中的每个阶段，玩家都保持理性。 -
信任系统(a system of beliefs)
对每个信息集上一个行动的选择概率。见后面的数学定义。 -
信誉(Reputation)
在博弈论中，玩家为了证明自己的信誉（自己的类型），会选择一种行为，这种行为只会对自己的类型有益，而对其它类型有损失。
经典博弈问题
- 囚徒困境(Prisoner's Dilemma)
两个囚徒选择沉默(mum)和告密(flink)的一个静态博弈问题。
| 玩家2 | |||
|---|---|---|---|
| m | f | ||
| 玩家1 | M | 4, 4 | -1, 5 |
| F | 5, -1 | 1, 1 |
- 报复博弈(Revenge Game)
报复博弈一般和囚徒困境组成一个两阶段博弈。
两个囚徒在玩完囚徒困境后，进入报复博弈，选择单独人(loner)和加入帮派(gang)的一个静态博弈问题。
| 玩家2 | |||
|---|---|---|---|
| l | g | ||
| 玩家1 | L | 0, 0 | -4, -1 |
| G | -1, -4 | 1, 1 |
- 古诺双寡头(The Cournot Duopoly)
- (p-Beauty Contest)
- 两性之争(the Battle of the Sexes)
策略
一个策略是一个玩家在博弈中，根据当时的情况，选择其行动的逻辑。
策略有各种各样的。我们可以想象每个策略都是如果这样，我就选择行动X，等等。
博弈理论中定义了一些策略。
-
纯策略(Pure Strategy)
玩家总是选择一个特定的行动。 -
混合策略(Mixed Strategy)
玩家在选择行动上有一个可能性分布。但是最终会选择一个纯策略。 -
行为策略(Behavioral Strategy)
玩家在选择行动上有一个可能性分布。一般用于动态博弈的自然选择，所以总是使用这个可能性分布来计算（期望收益等）。
正式的说法是：对每个信息集指定一个行动上的独立可能性分布。
-
条件选择策略(Conditional Play)
如果怎样，我会怎样的策略。 -
奖罚策略(Reward-and-punishment Strategy)
好行为被奖励，坏行为被惩罚的策略。用于多阶段博弈。 -
残忍触发策略(Grim-trigger strategy)
在第一阶段上选择一个合作（符合子博弈精炼均衡）的行动；
在以后的阶段里，继续选择这个合作行动，当且仅当对方也一直选择合作的行动；否则选择惩罚性的行动。 -
使用第三方作为信誉机制(Third-Party Institutions as Reputation Mechanisms)
在多阶段博弈中，如何保证协作的一种机制。
玩家1：如果玩家2支付保证金给玩家3（第三方），则信任玩家2，否则不信任。
玩家2：在阶段1，支付保证金给玩家3。在以后的阶段中，如果玩家3一直遵守保证金协议，则继续支付保证金。
如果支付保证金了，则于玩家1合作，否则叛变。
玩家3：（保证金协议）在一个阶段中，如果玩家2合作，则返回保证金给玩家2；否则不返回保证金。 -
不使用第三方的信誉机制(Reputation Transfers without Third Parties)
在多阶段博弈中，如何保证协作的一种机制。
玩家P_1^1：如果玩家P_2^1创建了一个唯一的商标，则信任玩家，否则不信任。
玩家：在阶段1，选择一个唯一的商标，和玩家1合作。然后，把商标以价格p^* > 1卖给下家（玩家P_2^2）。
玩家P_1^t(t>1)：如果1) 玩家P_2^t从玩家P_2^{t-1}手里买了这个唯一的商标，2) 而且这个商标没有被滥用（叛变）过，则信任玩家，否则不信任。
玩家P_2^t(t>1)：如果1) 玩家从玩家P_2^{t-2}以价格p^*手里买了这个唯一的商标，2) 而且这个商标没有被滥用（叛变）过，和玩家合作。然后，把商标以价格卖给下家（玩家P_2^{t+1}）。
方法
-
严格劣势策略(strictly dominated strategy)
一个理性玩家不会选择一个严格劣势策略。 -
优势策略(Dominant Strategy)
如果有的话，玩家一定会选择优势策略。 -
帕累托优势(pareto dominate)
-
重复剔除严格劣势均衡(Iterated elimination of strictly dominated strategies (IESDS))
如果能够找到一个严格劣势策略，将其删除掉，简化了博弈；
然后在简化的博弈中，重复上面的过程，直到有一个优势策略为止。 -
纳什均衡(Nash equilibrium)
纳什均衡的定义是：在一个策略组合中，如果一个玩家i，当其他所有玩家的策略都不变时（是这个策略组合中的玩家策略），玩家i的策略是个最佳反应。
如果这个条件对每个玩家都成立，则这个策略组合是一个纳什均衡。
纳什均衡的概念可以从纯策略组合，推广到混合策略（期望收益）、（动态博弈的）行为策略、（不完整信息）贝叶斯纳什均衡。
纳什证明了每个博弈都至少有一个纳什均衡。
纳什均衡相当于在博弈论中发现了一个新大陆。
一个问题是纳什均衡的解往往很多，因此，有一个精炼 的概念，就是我们常常看到词perfect，其目的是近一步减少纳什均衡的解。
-
子博弈精炼(Subgame perfection)
子博弈精炼是对纳什博弈的一种优化。
要求对于一个行为策略组合\sigma^*，满足在任何一个合适的子博弈中，这个行为策略组合都是一个纳什均衡。 -
逆向归纳法(Backward induction solution)
在扩展形式博弈树中，可以形象的看出：
从底层开始，玩家在每个父节点的子节点集合中，选择出(最佳反应的)其会获得最大收益的行为。每个父节点会对应一个或者几个最佳反应节点。
将这些节点的收益值作为其父节点的收益值。
重复迭代可以找到所有玩家的一个子博弈精炼均衡。 -
贝叶斯纳什均衡(Bayesian Nash equilibrium)
可以说是纳什均衡在不完整信息博弈中的扩展。大概的意思是计算了其他玩家类型的分布概率上的收益期望。
注意：子博弈精炼不适用于不完整信息博弈，主要原因是不知道其他玩家的类型，导致在子博弈上难以确定收益。 -
精炼贝叶斯均衡(perfect Bayesian equilibrium)
在不完整信息博弈中，精炼贝叶斯均衡是一个贝叶斯纳什均衡和一个信任系统的组合，并需要满足下面四个需求：
精炼贝叶斯均衡(perfect Bayesian equilibrium)的四个需求： * 需求 15.1
每个玩家在每个信息集上，都将有一个意义明确的信念（关于他的位置）。也就是说博弈将有一个信念体系。-
需求 15.2
\sigma^* = (\sigma_1^*, \cdots, \sigma_n^*)是一个不完整信息博弈的贝叶斯纳什均衡，我们要求在所有信息集上，在均衡路径上的信念符合贝叶斯规则。 -
需求 15.3
对于不在均衡路径上的信息集，其信念值可以是任何值。 -
需求 15.4
给定玩家的信念，玩家的策略必须是序贯理性。也就是说在每一个信息集上，玩家将选择信念对应的最佳反应。
-
原理
单阶段偏差原理(The One-Stage Deviation Principle)
在理解单阶段偏差原理 之前，我们先回顾一些背景知识：
- 每个博弈都存在至少一个纳什均衡。
- 在有限多阶段博弈中，如果每个阶段博弈都有唯一的纳什均衡，则多阶段博弈的最优结果就是这些纳什均衡的组合（的路径）。
- 在有限多阶段博弈中，如果至少有一个阶段博弈有多个的纳什均衡，则多阶段博弈的最优策略组合可能会偏离阶段博弈的纳什均衡。
那么在多阶段博弈中，在多阶段博弈的扩展形式博弈树(extensive-form game tree)上，一条路径的收益是容易得到的，只要求出每个阶段博弈的收益总和就可以了。
这样，我们也可以比较容易计算两条路径中，哪个更优（一般和折扣率有关）。
问题是：对于玩家i来说，当其他玩家的策略组合\sigma_i给定的时，如何找到玩家i的最佳反应(best response)？
注：这里的策略可以是任何策略，比如纯策略，混合策略，条件策略等。
这里边，一个比较麻烦的问题是路径太多。比如：考虑一下一个有五个阶段的博弈。
幸运的是，上面这个骇人的问题可以被简化- 这就是单阶段偏差原理。
单阶段偏差原理 的含义是，当其他玩家的策略组合给定的时，判断玩家i的一条路径是否最优，只要看这个路径（策略）是不是单点不可改善(one-shot unimprovable)。
因此只要检测和它有一个信息集不同 的那些路径就可以了。
比如：如果一个阶段博弈有A和B两个行动，在一个三阶段的重复博弈中，判断一条玩家的路径（策略）AAA是否是不可改善，只需要对比BAA，ABA和AAB就可以了。
很明显，这个原则只适合于有限多阶段博弈。
其实原书中，对于Prisoner-Revenge Game，计算折扣率，可以看成对单阶段偏差原理 的过程描述，只不过只是比较两个路径。
下面加上书中的定义和定理，以供参考。
单阶段偏差原理表述如下:
一个阶段的不可改善策略必定是最优的。
这意味着，如果在一个阶段博弈中，存在一个单阶段不可改善策略 ，则不会发生偏离，也就是不存在非纳什均衡的最优策略。
反之，则一定会发生偏离的情况。
单阶段不可改善策略 的定义如下：
一个策略是单阶段不可改善的，则:
不存在信息集h_i和行动a \in A_i(h_i)和对应的策略\sigma_i^{a, h_i}（其为除了信息集以外，和都一致的策略），有\sigma_i^{a, h_i} > v_i(\sigma_i, h_i)。
参照见One-shot deviation principle
基本数学符合
\Gamma: 博弈(game)
N: 玩家(player)集合
i: 玩家i, i \in N
X: 结果(outcome)集合。
X_i: 玩家i的结果(outcome)集合。
x_i: 玩家i的一个结果(outcome)。
S: 策略集合(strategy set), S \equiv S_1 \times S_2 \times \cdots \times S_n.
S_i: 玩家i的策略集合(strategy set)
S_{-i}: 除去玩家i的策略集合(strategy set), S_{-i} \equiv S_1 \times S_2 \times \cdots \times \S_{i-1} \times \S_{i+1} \times \cdots \times S_n.
s = (s_1, s_2, \cdots, s_n): 表示所有玩家的一个策略组合。
s_i: 玩家i的一个策略(strategy)，s_i \in S_i。
s_{-i} = (s_1, s_2, \cdots, s_{i-1}, s_{i+1}, \cdots, s_n): 表示除了玩家i，以外的所有玩家的一个策略组合。
A_i: 玩家i的行动集合。
a_i: 玩家i的一个行动，a_i \in A_i。
\mathbb{R}AAAAA: 实数。
u_i: X \to \mathbb{R}: 玩家i的收益函数，基于一个结果组合。
v_i: s \to \mathbb{R}: 玩家i的收益函数，基于一个策略组合。
H_i: 玩家i的信息集的集合
: 玩家i的一个信息集，h_i \in H_i。
A_i(h_i): 玩家i的一个信息集对应的行动集合。
s_i(h_i): 玩家i的一个纯策略。s_i(h_i) \in A_i(h_i)
T: 多阶段博弈的所有时期。
t: 多阶段博弈的一个时期。
p(x_k | a): 采取行动a时，产生结果x_k的概率。
E(u(x) | a): 采取行动a的期望收益。
0 < \delta < 1: （多阶段博弈中的）折扣率。
动态博弈(Dynamic Game)
策略组合\sigma = (\sigma_1, \cdots, \sigma_n): 一个动态博弈的混合策略组合(mixed strategies profile)。
不完整信息博弈
\Theta : 所有玩家的类型空间(type space)集合。
\Theta_i = \{ \theta_{i1}， \cdots， \theta_{ik}\} : 玩家i的类型空间(type space)。
\theta_i : 玩家i的类型(type)。
\theta_{-i} : 除了玩家i以外其他玩家的类型(type)。
\phi_i : 玩家 i 对其他玩家 type 的信任分布概率。
v_i(a; \theta_i) : 当在type 下，依赖于一个行动组合的玩家收益函数，
机制设计
m_i \in \mathbb{R} : 玩家i的资金。
Y : 所有玩家（机制设计的）结果组合集合。
y = (x, m_1, \cdots, m_n) : 所有玩家（机制设计的）一个结果组合。
\Gamma = \langle A_1, \cdots, A_n, g(\cdot) \rangle : 一个机制。
不完整信息的动态博弈
\mu: 信任系统(a system of beliefs)，对每个信息集上一个行动的选择概率。
参照
- Game Theory An Introduction (by Steven Tadelis)
- 读书笔记: 博弈论导论 - 01 - 单人决策问题
- 读书笔记: 博弈论导论 - 02 - 引入不确定性和时间
- 读书笔记: 博弈论导论 - 03 - 完整信息的静态博弈 预备知识
- 读书笔记: 博弈论导论 - 04 - 完整信息的静态博弈 理性和公共知识
- 读书笔记: 博弈论导论 - 05 - 完整信息的静态博弈 纳什均衡
- 读书笔记: 博弈论导论 - 06 - 完整信息的静态博弈 混合的策略
- 读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识
- 读书笔记: 博弈论导论 - 08 - 完整信息的动态博弈 可信性和序贯理性
- 读书笔记: 博弈论导论 - 09 - 完整信息的动态博弈 多阶段博弈
- 读书笔记: 博弈论导论 - 10 - 完整信息的动态博弈 重复的博弈
- 读书笔记: 博弈论导论 - 11 - 完整信息的动态博弈 战略协议
- 读书笔记: 博弈论导论 - 12 - 不完整信息的静态博弈 贝叶斯博弈
- 读书笔记: 博弈论导论 - 13 - 不完整信息的静态博弈 拍卖和竞标
- 读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计
- 读书笔记: 博弈论导论 - 15 - 不完整信息的动态博弈 序贯理性
- 读书笔记: 博弈论导论 - 16 - 不完整信息的动态博弈 信号传递博弈
- 读书笔记: 博弈论导论 - 17 - 不完整信息的动态博弈 建立信誉
- 读书笔记: 博弈论导论 - 18 - 不完整信息的动态博弈 信息传递和廉价谈判
- 读书笔记: 博弈论导论 - 总结
- Nash bargaining solution
- Mechanism design
- Sequential equilibrium
- Perfect Bayesian equilibrium
- Game theory