说明：

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

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

定义2.1 在 n n n人博弈中，如果对于所有的其他参与人的选择 s − i s_{-i} s−i​， s i ∗ s_i^* si∗​都是参与人 i i i的最优选择，即 ∀ s i ∈ S i ( s i ≠ s i ∗ ) \forall s_i\in S_i(s_i\not =s_i^*) ∀si​∈Si​(si​​=si∗​)， ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in \prod_{j=1,j\not=i}^nS_j ∀s−i​∈∏j=1,j​=in​Sj​，有 u i ( s i ∗ , s − i ) > u i ( s i , s − i ) u_i(s_i^*,s_{-i})\gt u_i(s_i,s_{-i}) ui​(si∗​,s−i​)>ui​(si​,s−i​) 则称 s i ∗ s^*_i si∗​为参与人 i i i的占优战略。

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

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

定义2.2 在 n n n人博弈中，如果对所有参与人 i i i，都存在占优战略 s i ∗ s_i^* si∗​，则占优战略组合 s ∗ = ( s 1 ∗ , s 2 ∗ , . . . , s n ∗ ) s^*=(s_1^*,s_2^*,...,s_n^*) s∗=(s1∗​,s2∗​,...,sn∗​)称为占优战略均衡。

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

定义2.3 在 n n n人博弈中，如果对于参与人 i i i，存在战略 s i ′ , s ′ ′ ∈ S i s_i',s''\in S_i si′​,s′′∈Si​，对 ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in\prod_{j=1,j\not=i}^nS_j ∀s−i​∈∏j=1,j​=in​Sj​，有 u i ( s i ′ ′ , s − i ) > u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\gt u_i(s_i',s_{-i}) ui​(si′′​,s−i​)>ui​(si′​,s−i​)则称战略 s i ′ s_i' si′​为参与人 i i i的劣战略，或者说战略 s i ′ ′ s_i'' si′′​相对于战略 s i ′ s_i' si′​占优。

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

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

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

定义2.4 在 n n n人博弈中，如果对于参与人 i i i，存在战略 s i ′ , s i ′ ′ ∈ S i s_i',s_i''\in S_i si′​,si′′​∈Si​，对 ∀ s − i ∈ ∏ j = 1 , j ≠ i n S j \forall s_{-i}\in\prod_{j=1,j\not=i}^nS_j ∀s−i​∈∏j=1,j​=in​Sj​，有 u i ( s i ′ ′ , s − i ) ≥ u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\ge u_i(s_i',s_{-i}) ui​(si′′​,s−i​)≥ui​(si′​,s−i​)且 ∃ s − i ′ \exist s_{-i}' ∃s−i′​，使得 u i ( s i ′ ′ , s − i ) > u i ( s i ′ , s − i ) u_i(s_i'',s_{-i})\gt u_i(s_i',s_{-i}) ui​(si′′​,s−i​)>ui​(si′​,s−i​)则称战略 s i ′ s_i' si′​为参与人 i i i的弱劣战略，或者说战略 s i ′ ′ s_i'' si′′​相对于战略 s i ′ s_i' si′​弱占优。

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

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

定义2.5 在一个给定的 n n n人战略式博弈中，战略组合 s ∗ s^* s∗是一个Nash均衡当前仅当 ∀ i ∈ Γ , ∀ s i ∈ S i \forall i\in\Gamma,\forall s_i\in S_i ∀i∈Γ,∀si​∈Si​，有 u i ( s i ∗ , s − 1 ∗ ) ≥ u i ( s i , s − i ∗ ) u_i(s_i^*,s_{-1}^*)\ge u_i(s_i,s_{-i}^*) ui​(si∗​,s−1∗​)≥ui​(si​,s−i∗​) 或者 ∀ i ∈ Γ \forall i\in\Gamma ∀i∈Γ， s i ∗ ∈ arg max ⁡ s i ∈ S i u i ( s i , s − i ∗ ) s_i^*\in \argmax_{s_i\in S_i}u_i(s_i,s_{-i}^*) si∗​∈si​∈Si​argmax​ui​(si​,s−i∗​)。

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

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

定义2.6 在一个给定的有限 n n n人战略式博弈中，对任一参与人 i i i，设 S i = { s i 1 , . . . , s i K } S_i=\{s_i^1,...,s_i^K\} Si​={si1​,...,siK​}，则参与人 i i i的一个混合战略定义为在战略集 S i S_i Si​上的一个概率分布 σ i = ( σ i 1 , . . . , σ i K i ) \sigma_i=(\sigma_i^1,...,\sigma_i^{K_i}) σi​=(σi1​,...,σiKi​​)。

定义2.7 在有限 n n n人战略式博弈中，混合战略组合 σ ∗ \sigma^* σ∗为一个Nash均衡，当且仅当 ∀ i ∈ Γ , ∀ σ i ∈ Σ i \forall i\in\Gamma,\forall\sigma_i\in\Sigma_i ∀i∈Γ,∀σi​∈Σi​，有 v i ( σ i ∗ , σ − i ∗ ) ≥ v i ( σ i , σ − i ∗ ) v_i(\sigma_i^*,\sigma_{-i}^*)\ge v_i(\sigma_i,\sigma_{-i}^*) vi​(σi∗​,σ−i∗​)≥vi​(σi​,σ−i∗​)。

定义2.8 在有限 n n n人战略式博弈中，混合战略组合 σ ∗ \sigma^* σ∗为一个Nash均衡，当且仅当 ∀ i ∈ Γ , ∀ σ i ∈ Σ i \forall i\in\Gamma,\forall\sigma_i\in\Sigma_i ∀i∈Γ,∀σi​∈Σi​，有 v i ( σ i ∗ , σ − i ∗ ) ≥ v i ( s i , σ − i ∗ ) v_i(\sigma_i^*,\sigma_{-i}^*)\ge v_i(s_i,\sigma_{-i}^*) vi​(σi∗​,σ−i∗​)≥vi​(si​,σ−i∗​)。

命题2.1 在参与人 i i i的最优混合战略 σ i ∗ \sigma_i^* σi∗​中，对 ∀ σ i j ∗ > 0 \forall\sigma_i^{j^*}\gt0 ∀σij∗​>0，有 v i ( s j i , σ − i ) = v i ( σ i ∗ , σ − i ) v_i(s_j^i,\sigma_{-i})=v_i(\sigma_i^*,\sigma_{-i}) vi​(sji​,σ−i​)=vi​(σi∗​,σ−i​)

说明：

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

什么是支撑？

对于给定的混合战略组合 σ \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 S S中以大于0的概率出现的所有纯战略组合的集合。

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

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

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

求解小tips：

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

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

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

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

定义2.9 对于给定的零和博弈的支付矩阵 U U U，如果存在某个 i ∗ , j ∗ i^*,j^* i∗,j∗，使得 a i ∗ j ∗ = max ⁡ i min ⁡ j a i j = min ⁡ j max ⁡ i a i j a_{i^*j^*}=\max_i\min_ja_{ij}=\min_j\max_i a_{ij} ai∗j∗​=imax​jmin​aij​=jmin​imax​aij​ 那么称第 i ∗ , j ∗ i^*,j^* i∗,j∗对应的点为支付矩阵U的鞍点。

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

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

定义2.10 对于给定的零和博弈的支付矩阵U，如果存在参与人1的某个混合战略 σ 1 ∗ \sigma_1^* σ1∗​和参与人2的某个混合战略 σ 2 ∗ \sigma_2^* σ2∗​，使得 v 1 ( σ 1 ∗ , σ 2 ∗ ) = max ⁡ σ 1 min ⁡ σ 2 v 1 ( σ 1 , σ 2 ) = min ⁡ σ 2 max ⁡ σ 1 v 1 ( σ 1 , σ 2 ) v_1(\sigma_1^*,\sigma_2^*)=\max_{\sigma_1}\min_{\sigma_2} v_1(\sigma_1,\sigma_2)=\min_{\sigma_2}\max_{\sigma_1} v_1(\sigma_1,\sigma_2) v1​(σ1∗​,σ2∗​)=σ1​max​σ2​min​v1​(σ1​,σ2​)=σ2​min​σ1​max​v1​(σ1​,σ2​)那么称该战略组合为支付矩阵U的鞍点。

定理2.3 同定理2.2。

定理2.4

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

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