[博弈论--完全信息静态博弈] 纳什均衡--求解混合策略纳什均衡

支撑求解法

什么是支撑？

对于给定的混合战略组合$\sigma$，$\sigma$的支撑是指参与人按照$\sigma$选择战略时，所有参与人的支集 S i ( σ i ) = { s i ∈ S i ∣ σ i ( s i ) > 0 } S_i(\sigma_i)=\{s_i\in S_i|\sigma_i(s_i)\gt0\} Si​(σi​)={si​∈Si​∣σi​(si​)>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。