25 博弈论¶

约 2256 个字预计阅读时间 11 分钟

博弈论的基本概念¶

博弈论研究由一些带有相互竞争性质的主体所构成的体系的理论。它能以数字表示人的行为或为人的行为建立模式，研究对抗局势中最优的对抗策略和稳定局势，以及如何追求各方的最优策略和决定对策的结果，协助人们在一定规则范围内寻求最合理的行为方式

博弈 vs 优化

博弈是多主体，优化是单主体

博弈的要素¶

参与者（player）：参与博弈的决策主体
策略（strategy）：参与者可以采取的行动方案
策略组合（strategy profile）：所有参与者选择的策略的集合
收益（payoff）：参与者在某一策略组合下的收益
- 费用（cost）：参与者在某一策略组合下需付出的代价

博弈论的假设¶

参与者是理性的，以最大化他的收益或最小化他的费用作为选择策略的准则

博弈的分类¶

合作博弈(cooperative game)：局中人之间可以结成联盟，协调彼此的策略，并对获得的收益进行再分配

静态博弈(static game)：所有参与者同时选择策略并行动，且只能行动一次，参与者选择策略时不知道其他参与者的选择。

完全信息(complete information)：参与者掌握其他参与者的可选策略和收益等信息

完美信息(perfect information)：在动态博弈中，参与者掌握其他参与者已选择的策略

简单例子¶

囚徒困境（Prisoner's Dilemma）¶

甲、乙两人共同犯罪，警方掌握了一部分犯罪事实，将他们带到警局分别讯问

若两人均承认所有罪行，则各被判处6个月徒刑
若一人认罪，一人不认罪，前者被轻判1个月徒刑，后者被重判9个月徒刑
若两人均不认罪，则以部分罪行各被判处2个月徒刑

	乙认罪	乙不认罪
甲认罪	甲6个月，乙6个月	甲1个月，乙9个月
甲不认罪	甲9个月，乙1个月	甲2个月，乙2个月

Nash 均衡¶

Nash 均衡（Nash equilibrium）

（完全信息静态）博弈的某个局势，每一个理性的参与者都不会单独偏离它
- 对每一个参与者，在其他参与者策略不变情况下，单独采取其他策略，收益不会增加

纯策略与混合策略¶

纯策略（pure strategy）：参与者每次行动都选择某个确定的策略

混合策略（mixed strategy）：参与者可以以一定的概率分布选择若干个不同的策略

Nash 定理¶

若参与者有限，每位参与者的策略集均有限，收益函数均为实值函数，则博弈必存在混合策略意义下的 Nash 均衡

最优反应函数¶

Alt text

对其他参与者的任一策略组合，参与者的最优反应函数为可使其收益达到最大的策略集合，记为 \(B_i(a_{-i})\)，即 \(B_i(a_{-i})=\{a_i^*|u_i(a_i^*,a_{-i})\geq u_i(a_i^*,a_{-i}), \forall a_i\in A_i\}\)

Alt text

则充要条件可写为 \(\mathbf{a}^*\in \mathscr{B}(\mathbf{a}^*)\)

如果只有一个的话，那就是 \(\mathbf{a}^* = \mathscr{B}(\mathbf{a}^*)\)，我们可以由此想到不动点定理

不动点定理¶

Alt text

Nash 均衡的例子¶

Battle of Sexes¶

♂️：一起看球赛，收益为3；一起逛街，收益为1；各自行动，收益为0

♀️：一起看球赛，收益为1；一起逛街，收益为3；各自行动，收益为0

(♂️,♀️)	♂️ 看球赛	♂️ 逛街
♀️ 看球赛	(3,1)	(0,0)
♀️ 逛街	(0,0)	(1,3)

可见，双方看球或双方逛街都是均衡状态

鸽鹰博弈（Hawk-Dove Game）¶

(A,B)	B:鸽子	B:鹰
A:鸽子	(0,0)	(-1,1)
A:鹰	(1,-1)	(-5,-5)

可见，一方鹰，另一方鸽子是均衡状态

在这里，第一个分量列最大，第二个分量行最大。

石头剪刀布¶

Alt text

不存在 Nash 均衡

让座¶

Alt text

Braess 悖论¶

Alt text

这体现出了 低效的均衡（inefficient of Equilibrium）

网络设计博弈¶

Alt text

从单个使用者的利益来看，使用者 \(i\) 选择道路 \(s_i-t\) 是唯一的一个 Nash 均衡，总费用为 \(\sum\limits_{i=1}^k \frac1i=O(\ln k)\)

矩阵博弈¶

二人零和（zero-sum）有限博弈（完全信息静态博弈）

每人的可行策略集为有限集，设甲、乙的策略集分别为 \(\{X_1,X_2,\cdots,X_m\}\) 和 \(\{Y_1,Y_2,\cdots,Y_n\}\)，所有的局势形如 \((X_i,Y_j)\)
零和：甲的收益为 \(a_{ij}\)，乙的收益为 \(-a_{ij}\)

矩阵 \(\mathbf{A}=(a_{ij})_{m\times n}\) 称为博弈的收益矩阵

极小极大原则¶

若甲选择策略 \(X_i\)，不论乙如何选择，其收益至少为 \(\min\limits_{1\leq j\leq n}a_{ij}\)。

甲的最佳策略是 \(\max\limits_{1\leq i\leq m}\min\limits_{1\leq j\leq n}a_{ij}\)（每行最小值的最大值）

乙的最佳策略是 \(\min\limits_{1\leq j\leq n}\max\limits_{1\leq i\leq m}a_{ij}\)（每列最大值的最小值）

可以证明 \(\max\limits_{1\leq i\leq m}\min\limits_{1\leq j\leq n}a_{ij}\leq\min\limits_{1\leq j\leq n}\max\limits_{1\leq i\leq m}a_{ij}\)

Alt text

如果 \(\max\limits_{1\leq i\leq m}\min\limits_{1\leq j\leq n}a_{ij}=\min\limits_{1\leq j\leq n}\max\limits_{1\leq i\leq m}a_{ij}\)，其为鞍点（saddle point）

若 \(a_{st}\) 为鞍点，则 \((X_s,Y_t)\) 是博弈的 Nash 均衡
若鞍点不存在，则博弈不存在纯策略 Nash 均衡
- 例如石头剪刀布：\(\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}\) 不存在鞍点，所以不存在纯策略 Nash 均衡