【博弈论-完全信息静态博弈】 Nash均衡

占优行为

囚徒困境

说明：

1. （抵赖，抵赖）Pareto优于（坦白，坦白），看似对双方来说都是不错的选择（双赢），但是不可能成为一致性预测；
2. 这是因为，对每一方来说都有更好的选择，即牺牲另一方的支付，产生坦白-抵赖的局面。

在囚徒困境问题中，无论其他人选择什么战略，参与人的最优战略（坦白）总是唯一的。这样的最优战略称为“占优战略”。

下面给出他的规范化定义：

定义2.1 在$n$人博弈中，如果对于所有的其他参与人的选择$s_{-i}$，$s_i^{\ast }$都是参与人$i$的最优选择，即$\forall s_i\in S_i(s_i\ne s_i^{\ast })$，$\forall s_{-i}\in {\prod }_{j=1,j\ne i}^n{S}_j$，有$$u_i(s_i^{\ast },s_{-i})>u_i(s_i,s_{-i})$$
则称$s_i^{\ast }$为参与人$i$的占优战略。

简而言之，就是不管别人怎么选，我选这个战略的效用函数都能取到最大。

而我选择这一选择战略的行为称为占优行为。

定义2.2 在$n$人博弈中，如果对所有参与人$i$，都存在占优战略$s_i^{\ast }$，则占优战略组合$s^{\ast }=(s_1^{\ast },s_2^{\ast },...,s_n^{\ast })$称为占优战略均衡。

怎么判断呢？
在每一个其他人的战略组合下，比较一下自己选择不同战略下的效用，如果存在一个战略的效用比其他情况都好，那这个就是占优战略。

重复剔除劣战略行为

定义2.3 在$n$人博弈中，如果对于参与人$i$，存在战略$s_i^{\prime },s^{\prime \prime }\in S_i$，对$\forall s_{-i}\in {\prod }_{j=1,j\ne i}^n{S}_j$，有$$u_i(s_i^{\prime \prime },s_{-i})>u_i(s_i^{\prime },s_{-i})$$则称战略$s_i^{\prime }$为参与人$i$的劣战略，或者说战略$s_i^{\prime \prime }$相对于战略$s_i^{\prime }$占优。

参与人的这种选择行为称为剔除劣战略行为。

重复剔除劣战略后，对战略式博弈$G$的求解问题就可转换为对$G^{\prime }$的求解。遵循这一思路，不断剔除劣战略的行为称为重复剔除劣战略行为。

通过重复剔除劣战略得到的解称为重复剔除的占优均衡。

定义2.4 在$n$人博弈中，如果对于参与人$i$，存在战略$s_i^{\prime },s_i^{\prime \prime }\in S_i$，对$\forall s_{-i}\in {\prod }_{j=1,j\ne i}^n{S}_j$，有$$u_i(s_i^{\prime \prime },s_{-i})\ge u_i(s_i^{\prime },s_{-i})$$且$\exists s_{-i}^{\prime }$，使得$$u_i(s_i^{\prime \prime },s_{-i})>u_i(s_i^{\prime },s_{-i})$$则称战略$s_i^{\prime }$为参与人$i$的弱劣战略，或者说战略$s_i^{\prime \prime }$相对于战略$s_i^{\prime }$弱占优。

所以劣战略可分为严格劣战略和弱劣战略。

如果重复剔除劣战略行为中包含弱劣战略的剔除，那么顺序的不同会造成解的不同。

Nash均衡的定义

定义2.5 在一个给定的$n$人战略式博弈中，战略组合$s^{\ast }$是一个Nash均衡当前仅当$\forall i\in \Gamma ,\forall s_i\in S_i$，有$$u_i(s_i^{\ast },s_{-1}^{\ast })\ge u_i(s_i,s_{-i}^{\ast })$$
或者$\forall i\in \Gamma$，$s_i^{\ast }\in \underset{s_i\in S_i}{\mathrm{argmax}}{u}_i(s_i,s_{-i}^{\ast })$。

求取纯战略Nash均衡的方法：

1. 划线法；
2. 箭头法。

混合战略Nash均衡

混合战略

以一定的概率分布来选择自己战略的行为，在博弈论中称之为混合战略。

定义2.6 在一个给定的有限$n$人战略式博弈中，对任一参与人$i$，设$S_i=\{s_i^1,...,s_i^K\}$，则参与人$i$的一个混合战略定义为在战略集$S_i$上的一个概率分布${\sigma }_i=({\sigma }_i^1,...,{\sigma }_i^{K_i})$。

符号	含义
${\Sigma }_i$	参与人$i$的混合战略空间
$\Sigma$	混合战略组合空间
$\pi (s)$	在混合战略组合$\sigma$下，纯战略组合$s$出现的概率
$v_i(\sigma )$	$={\sum }_{s\in S}\pi (s)u_i(s)$，参与人$i$的期望效用
${\sigma }_j(s_j)$	在混合战略组合$\sigma$下，参与人$j$选择$s_j$的概率

混合战略Nash均衡

定义2.7 在有限$n$人战略式博弈中，混合战略组合${\sigma }^{\ast }$为一个Nash均衡，当且仅当$\forall i\in \Gamma ,\forall {\sigma }_i\in {\Sigma }_i$，有$v_i({\sigma }_i^{\ast },{\sigma }_{-i}^{\ast })\ge v_i({\sigma }_i,{\sigma }_{-i}^{\ast })$。

定义2.8 在有限$n$人战略式博弈中，混合战略组合${\sigma }^{\ast }$为一个Nash均衡，当且仅当$\forall i\in \Gamma ,\forall {\sigma }_i\in {\Sigma }_i$，有$v_i({\sigma }_i^{\ast },{\sigma }_{-i}^{\ast })\ge v_i(s_i,{\sigma }_{-i}^{\ast })$。

命题2.1 在参与人$i$的最优混合战略${\sigma }_i^{\ast }$中，对$\forall {\sigma }_i^{j^{\ast }}>0$，有$$v_i(s_j^i,{\sigma }_{-i})=v_i({\sigma }_i^{\ast },{\sigma }_{-i})$$

说明：

1. 选择战略$j$的概率一定得大于0；
2. 在战略指定的情况下，求得的期望应该是相等的。

定理2.1（最优反应引理） 在有限$n$人战略式博弈中，混合战略组合${\sigma }^{\ast }$是一个Nash均衡，当切仅当$\forall i\in \Gamma$，${\sigma }^{\ast }$的支集$S_i({\sigma }_i^{\ast })$（大于0的概率出现的所有纯战略的集合）中的每一个纯战略都是给定${\sigma }_{-i}^{\ast }$下的最优反应。

混合战略Nash均衡的求解

支撑求解法

什么是支撑？

对于给定的混合战略组合$\sigma$，$\sigma$的支撑是指参与人按照$\sigma$选择战略时，所有参与人的支集$S_i({\sigma }_i)=\{s_i\in S_i|{\sigma }_i(s_i)>0\}$的直积。表示的是，当参与人按照$\sigma$选择战略时，纯战略组合集$S$中以大于0的概率出现的所有纯战略组合的集合。

于支撑求解法的思路就是：

1. 构造出所有的混合战略均衡的支撑；
2. 对于每个给定的支撑，求解上述式子所确定的方程。

等值法是支撑求解法的一种特例。

在求解方程组的过程中可能会出现下述三种情形：

1. 方程组的解不存在。Nash均衡的解总是存在的，所以导致无解的原因在于所构造的支撑有问题，需要构造新的支撑；
2. 解不满足非负性条件，即方程组的解虽然存在，但是解中存在小于0的情形；
3. 方程的解都存在，并且解都大于0，但是对于给定的解，存在这样的情形：对于某个参与人$i$，存在一个不属于支集$S_i({\sigma }_i^{\ast })$的战略$s_i^h$，对于给定的其他参与人的战略${\sigma }_{-i}^{\ast }$，参与人$i$采用这个战略的期望效用更大一些。

求解小tips：

1. 不存在纯战略Nash均衡，因此不存在支撑中只包含参与人一个战略的Nash均衡；
2. 解不存在或者不满足非负性很好看出来，这时候直接就是不成立；
3. 把没考虑在内的战略带进去算算，看看这个期望是不是大一些，如果是，那么这个解也是无效的。
4. 给定战略组合，如果能剔除严格劣战略，那么说明这么选择的战略组合是有问题的，可以直接删除，以减小计算量。

规划求解法

相对于支撑求解法，规划求解法对两人有限博弈问题的Nash均衡求解十分有效。

零和博弈

所谓零和博弈是指在任何博弈情形下两个参与人的支付之和为0。

在零和博弈中，如果给出了支付矩阵U，就意味着给出了所有参与人的支付。

a先选，b后选对应着极小极大；b先选，a后选对应着极大极小。

定义2.9 对于给定的零和博弈的支付矩阵$U$，如果存在某个$i^{\ast },j^{\ast }$，使得$$a_{i^{\ast }{j}^{\ast }}=\underset{i}{\max }\underset{j}{\min }{a}_{ij}=\underset{j}{\min }\underset{i}{\max }{a}_{ij}$$
那么称第$i^{\ast },j^{\ast }$对应的点为支付矩阵U的鞍点。

定理2.2 在零和博弈中，如果支付矩阵U存在鞍点，那么鞍点对应的战略组合就是博弈的Nash均衡。

接下来，我们引入混合战略意义下的Nash均衡。

定义2.10 对于给定的零和博弈的支付矩阵U，如果存在参与人1的某个混合战略${\sigma }_1^{\ast }$和参与人2的某个混合战略${\sigma }_2^{\ast }$，使得$$v_1({\sigma }_1^{\ast },{\sigma }_2^{\ast })=\underset{{\sigma }_1}{\max }\underset{{\sigma }_2}{\min }{v}_1({\sigma }_1,{\sigma }_2)=\underset{{\sigma }_2}{\min }\underset{{\sigma }_1}{\max }{v}_1({\sigma }_1,{\sigma }_2)$$那么称该战略组合为支付矩阵U的鞍点。

定理2.3 同定理2.2。

定理2.4

命题2.2 如果支付矩阵U的每个元素都大于0，那么博弈的值大于0。

命题2.3 支付矩阵U’是U的每个元素都加上了一个c，那么支付矩阵对应的零和博弈的Nash均衡战略相同，博弈的值相差c。