Nash Equilibrium的定义

在一个给定的$n$人战略式博弈 $G=<\Gamma ;S_1,S_2,\cdots,S_n ;u_1,u_2,\cdots,u_n >$ 中，战略组合 $s^=(s_1^，\cdots，s_i^，\cdots，s_n^)$ 是一个Nash均衡当且仅当 $\forall i \in \Gamma，\forall s_i \in S_i$ ，有：

$u_i(s^*_i,s^*_{-i})\ge u_i(s_i,s_{-i})$

或者 $\forall i \in \Gamma，si^*\in \arg \max \limits{si \in S_i}u_i(s_i,s^*{-i})$

传统博弈论中，一般将Nash均衡作为博弈问题的解。
占优战略均衡一定是Nash均衡。
重复剔除的占优均衡也是Nash均衡。

两人战略式博弈中Nash均衡的求解（划线法和箭头法）

划线法

划线法利用了Nash的一个性质：

在两人博弈的时候，相互构成最优战略的战略组合就是Nash均衡。

具体方法如下：

考察参与人1的最优战略，对于参与人2的每一个战略，找出来参与人1的最优战略，在其支付下划一横线。
用上述方法找出参与人二的最优战略，然后看看哪一个方格中花了两个横线，该战略组合就是就是Nash均衡。

	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均衡。

具体方法如下：

对于每一个战略组合，检查是否会有人因为更高的支付而偏离这个战略组合，如果有，就用一个箭头指向索要偏离的战略组合。
找出来没有人会偏离的战略组合，即找到一个方格，这个方格没有箭头指向其他方格，该战略组合就是Nash均衡。
可以任意选择一个方格，顺着他指向的箭头，找到下一个方格，接着顺着这个方格指向的箭头，直至找到尽头，没有箭头可以继续找到下一个战略组合，即为Nash均衡。

| | 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均衡

定义及相关概念

在一个给定的有限$n$人战略式博弈$G=<\Gamma ;S1,S_2,\cdots,S_n ;u_1,u_2,\cdots,u_n >$中，对任一参与人$i$，设$S_i={s_i^1,\cdots,s_i^{K_i}}$，则参与人$i$的一个混合战略为定义在战略集$S_i$上的一个概率分布$\sigma_i=(\sigma_i^1,\cdots,\sigma_i^{K_i},)$，其中$\sigma_i^j(j=1,\cdots,K_i)$表示参与人$i$选择战略$s_i^j$的概率。$\sigma_i^j$满足$0\leq \sigma_i^j \leq 1$且$\sum \limits{j=1}^{K_i}\sigma_i^j=1$。

当参与人$i$的混合战略$\sigma_i$以概率$1$赋给某一战略$s_i^j$时，即$\sigma_i=(0,\cdots,1,\cdots,0)$，此时，混合战略退化为纯战略(pure strategy).
以后用$\Sigma_i={\sigma_i}$表示参与人$i$的混合战略空间，用$\sigma=(\sigma_1,\sigma_2,\cdots,\sigma_n)$表示混合战略组合。其中$\Sigma_i \in \Sigma_i$，表示博弈中每个参与人$i(i=1,2,\cdots,n)$采用混合战略组合中相应战略$\sigma_i$的一种博弈情形。
用$\Sigma=\prod\limits_{i=1}^{n}\Sigma_i={(\sigma_1,\sigma_2,\cdots,\sigma_n)|\sigma_i \in \Sigma_i,i=1,2,\cdots,n}$表示混合战略组合空间，其中$\sigma \in \Sigma$

期望效益

我们用$\sigma{-i}=(\sigma_1,\cdots,\sigma{i-1},\sigma{i+1},\cdots,\sigma_n,))$表示除了参与人$i$以外的其他参与人的混合战略组合，因此$\sigma=(\sigma_i,\sigma{-i})$,我们用$vi(\sigma)=v_i(\sigma_i,\sigma{-i})$表示参与人$i$在混合战略组合$\sigma=(\sigmai,\sigma{-i})$下的期望效益。

如果用$\pi(s)$表示在混合战略$\sigma$下，纯战略组合$s(s \in S)$出现的概率，那么参与人$i$在混合战略组合$\sigma=(\sigmai,\sigma{-i})$下的期望效益$v_i(\sigma)$可以表示为:

$\begin{equation} v_i(\sigma)=v_i(\sigma_i,\sigma_{-i})=\sum_{s\in S}\pi(s)u_i(s)\tag{1} \end{equation}$

我们假设每个参与人对于战略的随机选择是相互独立的，故有:

$\pi(s)=\prod_{j=1}^n \sigma_j(s_j)\tag{2}$

把(2)代入(1)，可得:

$\begin{align} v_i(\sigma) & =v_i(\sigma_i,\sigma_{-i}) \\ & =\sum_{s\in S}\pi(s)u_i(s)\\ & =\sum_{s\in S}[\prod_{j=1}^n \sigma_j(s_j)]u_i(s)\tag{3}\\ \end{align}$

如果参与人$i$选择了纯战略$si^k(j=1,\cdots,K_i)$，其中$K_i$表示参与人$i$拥有的战略数目，即其战略集的大小。这算是$\sigma$的一个特例，此时可以认为$\sigma=(s_i^k,\sigma{-i})$。进一步，我们用$vi(s_i^k,\sigma{-i})$表示在其他参与人选择混合战略$\sigma_{-i}$的情况下，参与人$i$选择纯战略$s_i^k$的期望支付。则(3)式可以写成:

$\begin{align} v_i(\sigma) & =v_i(\sigma_i,\sigma_{-i}) \\ &=v_i(s_i^k,\sigma_{-i})\\ & =\sum_{s\in S}[\prod_{j=1}^n \sigma_j(s_j)]u_i(s)\tag{3}\\ & =\sum_{s_{-i}\in S_{-i}}[\prod_{j=1 j\neq i}^n \sigma_j(s_j)]u_i(s_i^k,s_{-i})\tag{4}\\ \end{align}$

（4）式中$\prod \limits{j=1 j\neq i}^n \sigma_j(s_j)$表示在混合战略$\sigma=(s_i^k,\sigma{-i})$下，其他参与人的纯战略组合$s_{-i}$出现的概率。

此处关于$j\neq i$的理解如下:

既然我们假定了参与人$i$选择战略$si^k$，那么相当于所有战略组合的集合由于参与人$i$选择纯战略$s_i^k$而从$S={s}$缩小为$S{-i}={s_{-i}}$,所以求和符号下标中战略组合的集合是除去参与人$i$的战略组合的集合。

上述四式描述了参与人$i$选择一个纯战略的情形，为了获得他混合战略的期望，我们需要对于这些混合战略的每一个分量重复上述步骤，求和，就可以得到这个参与人$i$的期望效用。

继续上述步骤:(注意下式中的$v_i(\sigma)$和上一个推导公式中的不一样，下面的指的是所有战略的期望效应)

$\begin{align} v_i(\sigma) & =v_i(\sigma_i,\sigma_{-i}) \\ &=\sum \limits _{k=1}^{K_i}\sigma_i^k v_i(s_i^k,\sigma_{-i})\\ &=\sum \limits _{k=1}^{K_i}\sigma_i^k\{\sum_{s_{-i}\in S_{-i}}[\prod_{j=1 j\neq i}^n \sigma_j(s_j)]u_i(s_i^k,s_{-i})\} \tag{5}\\ \end{align}$

混合战略Nash均衡

定义2.7
在有限n人战略式博弈 $G=<\Gamma ;S1,S_2,\cdots,S_n ;u_1,u_2,\cdots,u_n >$ 中，混合战略组合 $\sigma^=(\sigma_1^,\sigma_2^,\cdots,\sigma_n^)$为一个Nash均衡，当且仅当$\forall i \in \Gamma ,\forall \sigma_i \in \Sigma_i$ ,有$v_i(\sigma_i^*,\sigma{-i}^)\ge vi(\sigma_i,\sigma{-i}^)$

定义2.8
在有限n人战略式博弈 $G=<\Gamma ;S1,S_2,\cdots,S_n ;u_1,u_2,\cdots,u_n >$ 中，混合战略组合 $\sigma^=(\sigma_1^,\sigma_2^,\cdots,\sigma_n^)$为一个Nash均衡，当且仅当$\forall i \in \Gamma ,\forall \sigma_i \in \Sigma_i$ ,有$v_i(\sigma_i^*,\sigma{-i}^)\ge vi(s_i,\sigma{-i}^)$