¹武汉科技大学理学院数学与统计系，湖北 武汉

²武汉科技大学冶金工业过程系统科学湖北省重点实验室，湖北 武汉

收稿日期：2022年10月23日；录用日期：2022年11月18日；发布日期：2022年11月28日

摘要

纳什均衡的近似求解是博弈论中基础且重要的话题，其中基于特征向量的方法提供了一个新的视角，因此对博弈矩阵非方阵情形的探讨是值得期待的。本文以两人零和博弈为例，探讨了纳什均衡求解体系与非方支付矩阵的奇异方向的关系。关于纳什均衡计算的两个定理表明：当支付矩阵存在非负奇异值，且其对应的左奇异向量和右奇异向量元素都非负时，则该奇异向量分别对应博弈双方的纳什均衡解。以局中人的策略选择数目分别为3个和2个的情况为算例，验证了该定理的适用性，并对大规模非方矩阵博弈的纳什均衡的近似求解提供了一个新的方向。

关键词

非方支付矩阵，两人零和博弈，纳什均衡解，奇异向量

Approximate Nash Equilibrium Solution of Two Person Zero Sum Game in Singular Direction

Wenlong Wu¹, Yicheng Gong^1,2*

¹Department of Mathematics and Statistics, College of Science, Wuhan University of Science and Technology, Wuhan Hubei

²Hubei Province Key Laboratory of Systems Science in Metallurgical Process, Wuhan University of Science and Technology, Wuhan Hubei

Received: Oct. 23^rd, 2022; accepted: Nov. 18^th, 2022; published: Nov. 28^th, 2022

ABSTRACT

The approximate solution of Nash equilibrium is a basic and important topic in game theory, in which the method based on the eigenvector provides a new perspective, so it is worth looking forward to the discussion of the non-square matrix of the game. Taking a two-person zero-sum game as an example, this paper discusses the relationship between Nash equilibrium solution system and the singular direction of the non-square payment matrix. Two theorems about Nash equilibrium calculation show that when the payoff matrix has a non-negative singular value, and its corresponding left singular vector and right singular vector elements are all non-negative, then the singular vectors correspond to the Nash equilibrium solutions of both players in the game. Taking the cases where the number of strategy choices of the players in the game is 3 and 2 respectively, the applicability of the theorem is verified, and a new direction is provided for the approximate solution of Nash equilibrium for large-scale non-square matrix games.

Keywords:Non-Square Payoff Matrix, Two-Person Zero-Sum Game, Nash Equilibrium Solution, Singular Vector

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

博弈论作为现代数学的一个新分支，也是运筹学的一个重要学科，在生活的各个方面都有着广泛的应用。而其基础理论纳什均衡则作为桥梁，不仅将经济学与其他社会科学、自然科学相连接，且不论是从深度还是广度上，都推动了经济学研究的发展进程 [1]。

针对博弈中纳什均衡的求解，大量学者对此都有所探讨。从线性或非线性优化的角度出发，2015年安京京等人针对模糊二人零和博弈，提出了一种新的收益排序方法，将博弈的均衡求解转化为带参数的多目标线性规划问题，运用于解决其他的竞争对策问题 [2]。2020年刘豪利用并改进群智能算法，将求解均衡转化成单目标优化问题 [3]。2021年Sadana Utsav等人提供了一个基于非线性优化的方法来求解开环纳什均衡策略，并证明了一类带脉冲控制的线性状态微分对策的开环纳什均衡是唯一的，且最多只能有一个脉冲 [4]。同年，Ganzfried Sam针对连续博弈中的纳什均衡求解问题，通过创建一个混合整数线性公式提出了解决连续情况的第一个算法 [5]。2022年侯剑、李萌萌等人提出一种Nikaido-Isoda算法，将效用函数是强凸的纳什均衡问题转化为一类光滑约束优化问题进行求解 [6]。而从强化学习的角度出发，2022年袁唯淋等人探讨了在大规模智能博弈对抗中博弈论与强化学习的结合，并强调了反事实后悔值最小化(CounterFactual Regret Minimaxzation, CFR)算法在求解近似纳什均衡时能够极大提高模型的泛化能力 [7]。Liu Luping等人也基于强化学习中遗憾最小化算法中的价值函数，对多智能体随机博弈中的纳什均衡进行求解 [8]。

另一方面，从博弈矩阵出发的纳什均衡求解体系在此前也存在相关研究。早先Weil等人提出博弈理论和特征系统之间存在着紧密的联系，并针对两人零和矩阵博弈论证了两者之间的关系 [9]。而后Thompson G L等人又将博弈论与特征系统的研究延拓到复数领域 [10]。Wernick R J等人则是针对参数化博弈矩阵，将其研究进一步深化 [11]。近些年，Liu H等人从不同类型的矩阵出发，更加具体地研究了特征值、特征向量与矩阵博弈之间的关系 [12]。2019年王照琨根据非合作博弈的纳什均衡与复制方程的饱和驻点的等价性，计算了符合矩阵博弈的纳什均衡 [13]。2020年DeepMind团队Gemp I等人提出将主成分分析作为一种特征博弈的新观点，令矩阵中的特征向量由博弈的局中人控制，并论证了主成分分析解是严格且唯一的纳什均衡 [14]。2021年Szabó György等人在矩阵分解的框架下讨论了不同类型的相互作用及其组合的可能纳什均衡，并建立了无限多个混合策略纳什均衡与支付矩阵的零特征值特征向量之间的关系 [15]。2022年刘昊天等人对于多无人机协同空战博弈决策问题，利用矩阵对策法建立敌我双方对抗支付博弈模型，求解空战博弈混合策略纳什均衡，为解决多无人机空战策略问题提供了有价值的参考 [16]。

参考国内外的文献，从相关定义到应用推广，对纳什均衡的求解方法的先行研究由浅入深，非常丰富，但基于支付矩阵的特征方向对博弈矩阵的研究较少，且大部分都以支付矩阵为方阵的两人零和博弈为研究对象。而在现实生活中，博弈双方的策略数目也时常存在不对等的情况，由此本文从非方支付矩阵的奇异方向出发，探求两人零和博弈的混合策略纳什均衡与支付矩阵的奇异向量之间的关系及其普遍性，为纳什均衡的求解提供一种新的思路。

2. 博弈中的纳什均衡

博弈是指在一定的规则约束下，基于相互作用的环境，不同的局中人根据各自掌握的信息，从利益最大化的角度出发，选择不同的应对策略的过程。博弈有多种分类方式：一次博弈和重复博弈；静态博弈和动态博弈；完全信息博弈与不完全信息博弈；有限博弈和无限博弈；非合作博弈和合作博弈；一般均衡和博弈均衡。而从博弈的重要属性——效用来分析零和博弈、常和博弈和变和博弈，既有一定的学术价值，又有一定的理念创新 [17]。

我们称博弈中的参与主体为“局中人”，而各局中人的收益或损失为各自的“支付”或“效用”，则当且仅当所有局中人的支付之和在博弈进行过程中及博弈结束时恒为零或某一固定常数时，博弈被称为“零和博弈”。由于在一定的规则下，一方的收益必然意味着另一方的损失，且博弈各方的收益和损失加和永远为零或某一固定常数，故零和博弈也属于非合作博弈。在金融市场、公司治理和各类博弈游戏等领域零和博弈都被广泛应用。

每个博弈者根据条件做出的决策称为策略，而博弈者可以选择的全部策略组成的集合叫做策略集合。策略作为博弈的三要素之一，可以分为纯策略和混合策略。纯策略是给局中人如何进行博弈给出确定的选择，而混合策略是对每个纯策略分配一个概率而形成的策略，其允许玩家随机选择一个纯策略。

1950年，美国数学家小约翰·福布斯·纳什首次用精准的数学语言定义了纳什均衡，并且在包含混合策略的情况下，用严密的逻辑证明了纳什均衡在n人有限博弈中的普遍存在性，从而开创了与诺依曼和摩根思特恩框架路线均完全不同的非合作博弈理论 [18]。所以纳什均衡也称为非合作博弈均衡，其可以分为纯策略纳什均衡和混合策略纳什均衡。前者是指参与之中的所有局中人都使用纯策略，而后者是指至少有一个局中人使用混合策略。

3. 矩阵博弈中的基础定义

定义1：在完全信息静态博弈下，设有N个有限局中人，每个局中人i可选择的策略的集合为 $S_i$，对应的效用函数为 $u_i$。则博弈结果是由一组策略构成的元组 $s=\left(s_1,s_2,\cdots ,s_N\right),s\in S$，其中S表示博弈结果空间， $S=S_1\times S_2\times \cdots \times S_N$。对于局中人i来说，对手的策略表示为 $s_{-i}=\left(s_1,\cdots ,s_{i-1},s_{i+1}\cdots ,s_N\right)$，则 $s=\left(s_i,s_{-i}\right)$。

定义2：设集合 $G=\left\{N,S_1,\cdots ,S_n,u_1,\cdots ,u_N\right\}$ 为一个具有完全信息的博弈模型，当对于每个局中人i都有 $u_i\left(s_i^{*},s_{-i}^{*}\right)\ge u_i\left(s_i,s_{-i}^{*}\right)$ 时，则称策略组合 $\left\{s^{*}=\left(s_i^{*},s_{-i}^{*}\right)|s_i^{*}\in s_i,s_{-i}^{*}\in s/s_i\right\}$ 为G的一个纳什均衡。

对于每个局中人而言，当对手策略选定时，选择使得自己效用最大的策略，这时的策略称为“最优反应”，同时满足所有局中人的最优反应的博弈结果就是纳什均衡。

定义3：如果存在一个策略组 $s=\left(s_i^{*},s_{-i}^{*}\right)$，其使得任何局中人i单方面偏离自己的策略 $s_i^{*}$ 都将无利可图时，该策略组称为纯策略纳什均衡。其中每个局中人可选的策略 $s_i^{*}$ 也称纯策略。

在纯策略纳什均衡中，每个局中人的纯策略 $s_i^{*}$ 都是对手均衡策略 $s_{-i}^{*}$ 的最优反应。

以二人有限博弈为例，设局中人1和局中人2分别有m和n个可选择的策略 $\alpha ,\beta$。则其可选择的策略的集合分别为 $S_1,S_2$，其中 $S_1=\left\{{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_m\right\},S_2=\left\{{\beta }_1,{\beta }_2,\cdots ,{\beta }_n\right\}$。

定义4：设 $S_i$ 上的一个概率分布为局中人i (i = 1, 2)的一个混合策略，用 ${\Delta }_i$ 分别表示两个局中人的混合策略集合，如下式所示：

${\Delta }_1=\left\{X=\left(x_1,x_2,\cdots ,x_m\right)|{\displaystyle {\sum }_{i=1}^m{x}_i}=1,x_i\ge 0,i=1,\cdots ,m\right\}$ (1)

${\Delta }_2=\left\{Y=\left(y_1,y_2,\cdots ,y_n\right)|{\displaystyle {\sum }_{j=1}^n{y}_j}=1,y_j\ge 0,j=1,2,\cdots ,n\right\}$ (2)

其中 $X=\left(x_1,x_2,\cdots ,x_m\right)\in {\Delta }_1$ 为局中人1的混合策略， $x_i\left(i=1,2,\cdots ,m\right)$ 表示局中人1以概率 $x_i$ 随机选择纯策略 ${\alpha }_i$。 $Y=\left(y_1,y_2,\cdots ,y_n\right)\in {\Delta }_2$ 为局中人2的混合策略， $y_j\left(j=1,2,\cdots ,n\right)$ 表示局中人2以概率 $y_j$ 随机选择纯策略 ${\beta }_j$。

定义5：混合策略的博弈模型 $G=\left\{N=2,{\Delta }_1\left(S_1\right),{\Delta }_2\left(S_2\right),U_1,U_2\right\}$，其中 $\left\{\left(X,Y\right)|X\in {\Delta }_1,Y\in {\Delta }_2\right\}$ 称为混合策略组合， $U_1,U_2$ 分别为局中人1、2的期望效用，如下式所示。

$U_1=E_1\left(X,Y\right)={\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{j=1}^n{u}_1\left({\alpha }_i,{\beta }_j\right)x_i{y}_j}}$ (3)

$U_2=E_2\left(X,Y\right)={\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{j=1}^n{u}_2\left({\alpha }_i,{\beta }_j\right)x_i{y}_j}}$ (4)

不妨令上式中 $u_1\left({\alpha }_i,{\beta }_j\right)=a_{ij}$，$u_2\left({\alpha }_i,{\beta }_j\right)=b_{ij}$，$i=1,2,\cdots ,m$，$j=1,2,\cdots ,n$。则局中人1、2的支付矩阵可以表示为 $A={\left(a_{ij}\right)}_{m\times n},B={\left(b_{ij}\right)}_{m\times n}$。令X，Y分别表示局中人1、2的混合策略列向量，再结合支付矩阵，局中人1、2的期望效用可以写成如下矩阵形式。

$E_1\left(X,Y\right)=X^{\text{T}}AY$ (5)

$E_2\left(X,Y\right)=X^{\text{T}}BY$ (6)

定义6：如果每个局中人都选择在对手不改变的情况下的最好的策略分布，即对于局中人1、2都满足：

$E_1\left(X^{*},Y\right)\ge E_1\left(X,Y\right)\forall X\in {\Delta }_1\left(S_1\right)$ (7)

$E_2\left(X,Y^{*}\right)\ge E_2\left(X,Y\right)\forall Y\in {\Delta }_2\left(S_2\right)$ (8)

则称混合策略组合 $\left(X^{*},Y^{*}\right)$ 为博弈模型G的混合策略纳什均衡 [19]。

4. 零和矩阵博弈

博弈双方得益总是为零的博弈称为零和博弈。在两人零和博弈中，若局中人1的支付矩阵为A，则局中人2的支付矩阵B = −A，即一方的收益等于另一方的损失。所以出于简洁性我们只考虑局中人1何时收益最大，由此得到的混合策略也会使得局中人2的损失最小。

当博弈双方有着相同的策略选择个数时，支付矩阵此时为方阵。若局中人可选的策略有限且固定，两人零和博弈的模型完全由支付矩阵A决定。为了探究矩阵博弈与特征系统之间的关系，先前的研究从求解特征值对应特征向量的公式 $\left(A-\lambda I\right)X=0$ 出发，定义了由标量 $\theta$ 和支付矩阵A构成的博弈矩阵 $S_{\left(A,\theta \right)}=A-\theta I$，得到了两人零和博弈下混合策略纳什均衡和特征值/特征向量的关系。而本文将考虑在两人零和博弈中，当双方博弈策略个数不同，支付矩阵为非方时，是否能得到适用性更广更加普遍的结论。

根据冯诺依曼的极大极小定理可知，对于任意的支付矩阵A，都存在混合策略纳什均衡 $\left(X^{*},Y^{*}\right)$ 使得公式 ${\max }_X{X}^{\text{T}}A{Y}^{*}={\min }_Y{\left(X^{*}\right)}^{\text{T}}AY$ 成立。由此可以推出极小极大值等于极大极小值，即 ${\max }_X{\min }_Y{X}^{\text{T}}AY={\min }_Y{\max }_X{X}^{\text{T}}AY$，不妨定义其值为v(A)。易知v(A)也是两人零和博弈中当双方都采用混合策略组 $\left(X^{*},Y^{*}\right)$ 时局中人1的收益。则当 $X^{\text{T}}AY=v\left(A\right)$ 时， $\left(X,Y\right)$ 可以称为达到纳什均衡的最优策略。

定义7：若局中人1存在混合策略X使得 $X^{\text{T}}A\ge 0$ 有解，则称X为局中人1的经济优解，若 $X^{\text{T}}A>0$，则称其为严格经济优解；若局中人2存在混合策略Y使得 $BY\ge 0$ 有解，则称Y为局中人2的经济优解，若 $BY>0$ 有解，则称 为局中人2的严格经济优解。

当局中人1存在混合策略 $X^{\prime }$ 使得 ${\left(X^{\prime }\right)}^{\text{T}}A\ge 0$ 有解，则对局中人2任意的策略，局中人1都将获得非负收益，即 $\forall Y,U_1={\left(X^{\prime }\right)}^{\text{T}}AY\ge 0$，故称为经济优解 [20] [21]。

另一方面，在两人零和博弈中，因为一方的收益等于另一方的损失， $U_1=-U_2$，所以混合策略纳什均衡 $\left(X^{*},Y^{*}\right)$ 不可能同时由双方的严格经济优解构成。当双方经济优解 $\left(X^{\prime },Y^{\prime }\right)$ 都存在时，则 $\left(X^{*},Y^{*}\right)=\left(X^{\prime },Y^{\prime }\right)$，且此时 $v\left(A\right)=0$。

引理1：设 $\theta$ 为标量，当博弈支付矩阵A固定时，构造函数 $R_{\left(A,\theta \right)}=A{A}^{\text{T}}A-\theta A=\left(A{A}^{\text{T}}-\theta I\right)A$。可知当矩阵A中元素都非负时， $v\left(R_{\left(A,\theta \right)}\right)$ 是关于 $\theta$ 的非增函数。

证明：不妨设 ${\theta }_1>{\theta }_2$，设 $X_{{\theta }_1},Y_{{\theta }_1}$ 是支付矩阵为 $R_{\left(A,{\theta }_1\right)}$ 时两人零和博弈的最优策略； $X_{{\theta }_2},Y_{{\theta }_2}$ 是支付矩阵为 $R_{\left(A,{\theta }_2\right)}$ 时的最优策略。则有如下推导：

$v\left(R_{\left(A,\theta \right)}\right)=\underset{X}{\max }\underset{Y}{\min }{X}^{\text{T}}{R}_{\left(A,\theta \right)}Y=\underset{Y}{\min }\underset{X}{\max }{X}^{\text{T}}{R}_{\left(A,\theta \right)}Y$ (9)

$\begin{array}{c}v\left(R_{\left(A,{\theta }_1\right)}\right)\le X_{{\theta }_1}^{\text{T}}{R}_{\left(A,{\theta }_1\right)}{Y}_{{\theta }_2}=X_{{\theta }_1}^{\text{T}}\left(A{A}^{\text{T}}A-{\theta }_{1}A\right)Y_{{\theta }_2}\\ =X_{{\theta }_1}^{\text{T}}\left(A{A}^{\text{T}}A-{\theta }_{2}A+{\theta }_{2}A-{\theta }_{1}A\right)Y_{{\theta }_2}\\ =X_{{\theta }_1}^{\text{T}}\left(A{A}^{\text{T}}A-{\theta }_{2}A\right)Y_{{\theta }_2}+\left({\theta }_2-{\theta }_1\right)X_{{\theta }_1}^{\text{T}}A{Y}_{{\theta }_2}\\ \le v\left(R_{\left(A,{\theta }_2\right)}\right)-\left({\theta }_1-{\theta }_2\right)X_{{\theta }_1}^{\text{T}}A{Y}_{{\theta }_2}\end{array}$ (10)

考虑当收益矩阵A非负时，此时 $X_{{\theta }_1}^{\text{T}}A{Y}_{{\theta }_2}\ge 0$，又因为 ${\theta }_1>{\theta }_2$，可得 $v\left(R_{\left(A,{\theta }_1\right)}\right)\le v\left(R_{\left(A,{\theta }_2\right)}\right)$，即 $v\left(R_{\left(A,\theta \right)}\right)$ 是关于 $\theta$ 的非增函数得证。

引理2：存在 $\theta \in R$，使得 $v\left(R_{\left(A,\theta \right)}\right)>0$ ；且存在 ${\theta }^{\prime }\in R,{\theta }^{\prime }>\theta$，使得 $v\left(R_{\left(A,{\theta }^{\prime }\right)}\right)<0$。

证明：

$v\left(R_{\left(A,\theta \right)}\right)\ge X^{\text{T}}{R}_{\left(A,\theta \right)}{Y}_{\theta }=X^{\text{T}}\left(A{A}^{\text{T}}A-\theta A\right)Y_{\theta }=X^{\text{T}}A{A}^{\text{T}}A{Y}_{\theta }-\theta X^{\text{T}}A{Y}_{\theta }$ (11)

当A固定时，可知不等式的前半部分有界。若局中人1存在严格经济优解，即 $X^{\text{T}}A>0$ 时，则当 $\theta$ 趋于无穷小时， $v\left(R_{\left(A,\theta \right)}\right)$ 趋于无穷大，则存在 $\theta \in R$，使得 $v\left(R_{\left(A,\theta \right)}\right)>0$。

$v\left(R_{\left(A,{\theta }^{\prime }\right)}\right)\le X_{{\theta }^{\prime }}^{\text{T}}{R}_{\left(A,{\theta }^{\prime }\right)}Y=X_{{\theta }^{\prime }}^{\text{T}}\left(A{A}^{\text{T}}A-{\theta }^{\prime }A\right)Y=X_{{\theta }^{\prime }}^{\text{T}}A{A}^{\text{T}}AY-{\theta }^{\prime }{X}_{{\theta }^{\prime }}^{\text{T}}AY$ (12)

同理可知，当局中人2存在严格经济优解， ${\theta }^{\prime }$ 趋于无穷大时， $v\left(R_{\left(A,{\theta }^{\prime }\right)}\right)$ 趋于无穷小，则存在 ${\theta }^{\prime }\in R,{\theta }^{\prime }>\theta$，使得 $v\left(R_{\left(A,{\theta }^{\prime }\right)}\right)<0$。

定理1： $v\left(R_{\left(A,\theta \right)}\right)$ 是关于 $\theta$ 的连续函数，且存在 ${\theta }_0$，使得 $v\left(R_{\left(A,{\theta }_0\right)}\right)=0$。

对于任意的矩阵 $G,H$，在文献 [9] 中对 $v\left(G+\theta H\right)$ 关于 $\theta$ 的连续性已有证明，所以 $v\left(R_{\left(A,\theta \right)}\right)=v\left(A{A}^{\text{T}}A-\theta A\right)$ )也是关于 $\theta$ 的连续函数。

由引理1和引理2可知，当博弈支付矩阵为非负矩阵时，函数 $v\left(R_{\left(A,\theta \right)}\right)$ 能够趋于正负无穷，且为连续单调非增函数，则自然存在 ${\theta }_0\in \left[\theta ,{\theta }^{\prime }\right]$，使得 $v\left(R_{\left(A,{\theta }_0\right)}\right)=0$。而当A不为非负矩阵时，若博弈双方存在严格经济优解，则根据函数的介值定理也知其存在零解。

定理2：当存在A的非负奇异值 $\sigma$，且其对应的左奇异向量X_L和右奇异向量Y_R元素都非负时，则有 $v\left(R_{\left(A,{\sigma }^2\right)}\right)=0$，且X_L，Y_R分别为局中人1和局中人2在博弈支付矩阵 $R_{\left(A,{\sigma }^2\right)}$ 下的最优策略，即纳什均衡解。

证明：由假设可知，当存在A的非负奇异值 $\sigma$ 时， ${\sigma }^2$ 为矩阵 $A{A}^{\text{T}}$ 和 $A^{\text{T}}A$ 的特征值，且相应的左右奇异向量X_L，Y_R分别是 $A{A}^{\text{T}}$ 和 $A^{\text{T}}A$ 关于特征值 ${\sigma }^2$ 的特征向量。则有如下推导：

${\left(X_L\right)}^{\text{T}}A{A}^{\text{T}}={\sigma }^2{\left(X_L\right)}^{\text{T}};A^{\text{T}}A{Y}_R={\sigma }^2{Y}_R$

${\left(X_L\right)}^{\text{T}}\left(A{A}^{\text{T}}-{\sigma }^2{I}_{m\times m}\right)=0;\left(A^{\text{T}}A-{\sigma }^2{I}_{n\times n}\right)Y_R=0$ (13)

${\left(X_L\right)}^{\text{T}}{R}_{\left(A,{\sigma }^2\right)}={\left(X_L\right)}^{\text{T}}\left(A{A}^{\text{T}}-{\sigma }^2{I}_{m\times m}\right)A=0$

$R_{\left(A,{\sigma }^2\right)}{Y}_R=A\left(A^{\text{T}}A-{\sigma }^2{I}_{n\times n}\right)Y_R=0$ (14)

又因为

$v\left(R_{\left(A,{\sigma }^2\right)}\right)=\underset{X_L}{\max }\underset{Y_R}{\min }{\left(X_L\right)}^{\text{T}}{R}_{\left(A,{\sigma }^2\right)}{Y}_R=\underset{Y_R}{\min }\underset{X_L}{\max }{\left(X_L\right)}^{\text{T}}{R}_{\left(A,{\sigma }^2\right)}{Y}_R$ (15)

所以可以得到 $v\left(R_{\left(A,{\sigma }^2\right)}\right)=0$，且满足该式的策略(X_L, Y_R)为博弈双方的最优策略，即纳什均衡解。

算例：在两人零和博弈中，设局中人1的支付矩阵为 $A=\left[\begin{array}{cc}1& -1\\ -2& 2\\ 2& -2\end{array}\right]$，则局中人2的支付矩阵为−A，设局中人1、2的混合策略分别为 $\left(x_1,x_2,x_3\right)$ 、 $\left(y_1,y_2\right)$，用期望效用相等建立方程，如公式(15)所示。

$y_1+\left(-1\right)y_2=-2y_1+2y_2=2y_1+\left(-2\right)y_2$

$-x_1+2x_2-2x_3=x_1-2x_2+2x_3$ (16)

可得 $y_1=y_2=\frac{1}{2}$，$x_1=2x_2-2x_3$，即局中人1的混合策略纳什均衡 $\left(y_1,y_2\right)$ 为 $\left(\frac{1}{2},\frac{1}{2}\right)$ ；而当 ${\displaystyle {\sum }_{i=1}^3{x}_i}=1$ 且 $x_i$ 非负时，满足约束 $x_1=2x_2-2x_3$ 的解都为局中人2的混合策略纳什均衡。

根据定理2，博弈支付矩阵为A时，存在奇异值 $\sigma =0$，其对应的左奇异向量 $X_L={\left(u_1,u_2,u_3\right)}^{\text{T}}$，其中 $u_1=2u_2-2u_3$，当满足 $u_i$ 非负且 ${\displaystyle {\sum }_{i=1}^3{u}_i}=1$ 时，该左奇异向量与局中人1的混合策略纳什均衡一致；同样的，奇异值 $\sigma =0$ 对应的右奇异向量 $Y_R={\left(v_1,v_2\right)}^{\text{T}}={\left(\frac{1}{2},\frac{1}{2}\right)}^{\text{T}}$，即为局中人2的混合策略纳什均衡。

5. 小结

对于特殊的静态矩阵博弈，其纯策略纳什均衡可以利用画线、流形图等方法获得，而其混合策略纳什均衡常常利用期望效用相等建立方程求解。除了建立方程外，本文从支付矩阵的特征方向出发，探究了纳什均衡解与矩阵本身的关系。由于特征系统是方阵中十分重要的一环，且相关学者对博弈矩阵与特征值、特征向量的关系已有深入探讨。而针对两人博弈中许多策略选择数目不平衡的情况，我们考虑非方博弈矩阵的奇异方向，以两人零和博弈为例，探求了近似纳什均衡求解体系与非方支付矩阵的奇异方向之间的关系，该研究表明当支付矩阵存在非负奇异值，且其对应的左奇异向量和右奇异向量元素都非负时，则该奇异向量分别对应博弈双方的纳什均衡解。

近似纳什均衡体系的求解一直都是研究博弈的热门话题，粒子群算法及其他结合神经网络和强化学习的先进算法确实有效的降低了纳什均衡求解的复杂度和提高了计算效率。本文从支付矩阵奇异方向的讨论，不仅从理论上对博弈矩阵中纳什均衡的求解进行了更深一步的研究，也在各种数据较多的复杂系统中，为求解大规模非方矩阵博弈均衡提供了新的角度。

基金项目

冶金工业过程系统科学湖北省重点实验室(Y202105)；武汉科技大学教学研究项目(2022X002)。

文章引用

龚谊承,吴雯珑. 奇异方向上两人零和博弈的近似纳什均衡求解
Approximate Nash Equilibrium Solution of Two Person Zero Sum Game in Singular Direction[J]. 应用数学进展, 2022, 11(11): 8183-8190. https://doi.org/10.12677/AAM.2022.1111866

参考文献