NASH均衡存在性证明

纳什均衡的存在性证明 - 知乎

由于最近需要学习一些经济学内容，所以偶尔会看一些相关话题下的回答，发现很多人对“纳什均衡”这个概念存在误用和夸大的情况。

知乎上关于纳什均衡的几篇高赞文章和回答写得都不算好，这些文章单纯通过简单案例解释纳什均衡，这会遗漏一些重要的限制条件，而且完全无法看出这一概念与数学尤其是拓扑学之间的紧密联系。（不过一些赞数不多的回答倒是写得很精彩。）

这里简单介绍一下约翰·纳什最早给出的关于n人非合作博弈在混合策略意义下的均衡点存在性证明。[1]

这个证明不需要花哨的技巧和复杂的数学工具，数学专业本科生可以很容易掌握。

关于博弈论的准备工作

纳什均衡是现代系统博弈理论的重要内容，下面首先介绍对策行为的基本要素：

• 局中人(players)，用N表示包含n个局中人的集合，局中人个体用i表示；
• 行为集(actions)，用Ai表示局中人i全部可行行为的集合，若ai是局中人i的一个行为，则向量a=(a1,a2,⋯,an)是n个局中人形成的行为局势. 行为也被称作纯策略(pure strategy)，向量A=(A1,A2,⋯,An)，a∈A；
• 效用函数(utility functions)，对于任一局势，每个局中人都能得到一个效用值，称Hi:a→R是局中人i的效用函数，向量H=(H1,H2,⋯,Hn).

需要注意的是，效用是局势（而非行为或策略）的实值函数，是局中人衡量局势是否对自己有利的重要指标.

举例来说，假设局中人i有m个纯策略α1,⋯,αm，局中人j有n个纯策略β1,⋯,βn，则局中人i,j的纯策略集分别为
Ai={α1,α2,⋯,αm},Aj={β1,β2,⋯,βn}.
两个局中人总共可以形成m⋅n个局势(αk,βl)，局中人对应不同的效用值Hi(a), Hj(a).

对于一个局中人，如果他的每次决策只能选择某个特定的行为，则称这种情形为纯策略(pure strategy)；如果局中人可以依据某种概率分布在每次决策中选定不同的行为，则称之为混合策略(mixed strategy).

定义1（混合策略）(N,{Ai},{Hi})是一个标准形式的博弈，设Π(X)是X上所有概率分布的集合，则称局中人i的混合策略集为Si=Π(Ai). 全体混合策略局势的集合S可表示为各局中人混合策略集的笛卡尔积，S=S1×S2×⋯×Sn.

混合策略的定义表明，对于策略si，局中人i会依照特定的概率分布选择不同的行为. 显然，纯策略是混合策略的一种特殊形式. 我们记si(aj)为混合策略si下进行行为aj的概率. 由此可以引出一个重要概念：

定义2（混合策略的效用期望）给定一个标准形式博弈G=(N,{Ai},{Hi})，对于混合策略局势s=(s1,s2,⋯,sn)，局中人i的效用期望ui记作
ui(s)=∑a∈AHi(a)∏j=1nsj(aj).

显然，混合策略的效用期望是行为的效用值乘以对应概率的累加. 在下面的一些叙述中，会用策略集S替代纯策略集A.

一个n人非合作对策可以用元组G=(N,S,H)表示，并引入记号
s||si∗=(s1,,⋯,si−1,si∗,si+1,⋯,sn)
表示在局势s=(s1,s2,⋯,sn)中局中人i将策略si换成si∗且其他局中人策略不变而得到的一个新局势.

定义3（平衡局势）如果局势s对全部局中人都有利，即对于任意i∈N, si∗∈Si，有
Hi(s)≥Hi(s||si∗) ,
则称局势s为n人非合作对策G的一个平衡局势（或均衡点）.

平衡局势定义中Hi(s)≥Hi(s||si∗)意味着，无论局中人i将自己的策略如何置换，都不会得到比在局势s下更多的效用值.

需要注意，平衡局势的定义中是根据效用值进行判断，而不是效用期望，所以既可以针对纯策略，也可以针对混合策略. 虽然也有纯策略纳什均衡，但根据矩阵对策的结果，纯策略意义下的平衡局势可能不存在. 下面只在混合策略意义下讨论纳什均衡.

定义4（纳什均衡）给定一个博弈G=(N,S,u)，对于混合策略局势s=(s1,s2,⋯,sn)，若任一局中人i∈N，任一策略si∗∈Si，均满足
ui(s)≥ui(s||si∗) ,
则称局势s是n人非合作博弈G的纳什均衡. 需要明确，纳什均衡是一个特殊的局势.

也就是说，如果一个非合作博弈的局势达到了纳什均衡，则无论哪个局中人更改自己的策略，自己的效用期望都只会持平或下降，而不可能上升. 再次强调，相比定义3，纳什均衡只针对混合策略.

关于拓扑学的准备工作

为了完成纳什定理的证明，下面需要简单介绍一些拓扑学方面的知识. 详细内容可以参考任意一本拓扑学教材.

凸性(Convexity) 对于一个集合C∈Rm，若任取x,y∈C, λ∈[0,1]，满足λx+(1−λ)y∈C，则称集合C是凸的. 若非负标量λi满足∑i=0nλi=1，我们称∑i=0nλixi是向量x0,⋯,xn的凸组合.
举例来说，三维欧氏空间中，一个立方体是凸的，而甜甜圈或碗状结构则是非凸的.

仿射无关性(Affine independence) 对于欧氏空间中的一个向量集{x0,⋯,xn}，若∑i=0nλixi=0和∑i=0nλi=0足够推导出λ0=⋯=λn=0，则称向量x0,⋯,xn是仿射无关的.

n维单纯形(n-simplex) n维单纯形表示为x0⋯xn，是仿射无关向量集{x0,⋯,xn}的全部凸组合的集合，即
x0⋯xn={∑i=0nλixi:∀i∈{0,⋯,n},λi≥0;∑i=0nλi=1}.

标准n维单纯形(Standard n-simplex) 标准n维单纯形记作Δn，其中
Δn={y∈Rn+1:∑i=0nyi=1;yi≥0,∀i∈{0,⋯,n}}.
也就是说，Δn是n+1个单位向量e0,⋯,en的凸组合的集合.

紧性(Compactness) 如果n维欧氏空间Rn中的集合是一个有界闭集，则我们称这个集合是紧的.
我们可以很直观地注意到，标准n维单纯形Δn是一个紧集.

定理5（Brouwer不动点定理）若f:Δm→Δm是连续的，则f有一个不动点，即存在某个z∈Δm使得f(z)=z.
证明从略. 证明过程中所需要的Sperner引理可以参看我之前的一篇文章，正方形可以被划分成五个面积相等的三角形吗——关于Monsky定理的证明.

需要注意的是，Brouwer不动点定理中f:Δm→Δm的条件也通常记作连续f可以将一个紧凸集映射到自身. （之所以写作Δm→Δm的形式，是为了方便Sperner引理的证明.）

双射函数(Bijective function) f是从A到B的映射，任取x,y∈A,x≠y，有f(x)≠f(y)，则称f由A到B单射(injection)；任取y∈B，存在x∈A，使得f(x)=y，则称f由A到B满射(surjection). 若f既单射又满射，则称f是双射函数，也叫1-1对应(one-to-one).

同胚(Homeomorphism) 如果存在一个连续双射函数h:A→B使得h−1也是连续的，则我们称集合A和集合B是同胚的，函数h:A→B称为同胚.
也就是说，同胚是两个拓扑空间之间的双连续函数.

推论6（Brouwer不动点定理的推论）令K=∏j=1kΔmj，K与Δm同胚，若f:K→K连续，则f存在一个不动点.

关于纳什定理的证明

最后，我们来解决著名的有限非合作博弈条件下纳什均衡的存在性问题.

引理7. 对于n人有限非合作博弈G=(N;{Si},i∈N;{ui(s)},i∈N)，s是平衡局势的充分必要条件是
ui(s)≥ui(s||ai), ai∈Ai,i∈N.
证明. 必要性是显然的，我们主要证明充分性.
局中人i任取一个混合策略si=(si(a1),si(a2),⋯,si(ami))，其中mi代表混合策略si对应局中人i的mi种行为，si(aj)表示进行相应行为aj的概率，
ui(s||si)=∑j=1miui(s||aj)si(aj)≤∑j=1miui(s)si(aj)=ui(s).  ◻

引理7的作用在于，可以将纳什均衡的判别条件进行适当放宽. 对于混合策略条件下的博弈，如果局势偏向纯策略而非混合策略，也可以判定局势s是否为纳什均衡. 这为接下来纳什存在定理的证明提供了方便.

Nash定理. 任何有限非合作博弈在混合策略意义下，一定至少存在一个纳什均衡.

证明. 给定一个混合策略局势s∈S，对于任意i∈N, ai∈Ai，我们定义
φi,ai(s)=max{0,ui(s||ai)−ui(s)}.
这个式子表明局中人i更换行为或策略的倾向.
下面定义从S映射到S的映射，f(s)=s′，其中
si′(ai)=si(ai)+φi,ai(s)∑bi∈Ai(si(bi)+φi,bi(s))=si(ai)+φi,ai(s)1+∑bi∈Aiφi,bi(s).
直观来说，f将局势s映射到一个新的局势s′，若新局势中的行为对每个局中人更有利，那么它对应的概率也会增加.
因为每个φi,ai(s)是连续的，所以f连续；因为S是凸的、紧的，f:S→S，所以根据Brouwer不动点定理的推论，f至少存在一个不动点s使得f(s)=s. 下面证明f的不动点s是博弈的纳什均衡点(Nash equilibria).
首先容易验证，若局势s是一个纳什均衡，全部φ都为0，则s是f的不动点.
反过来，考虑f的任意一个不动点s，根据期望的线性性，混合策略局势s中一定至少存在一个行为ai′满足ui,ai′(s)≤ui(s)，根据φ的定义可知，φi,ai′(s)=0.
因为s是f的一个不动点，所以有si′(ai′)=si(ai′). 考虑si′(ai′)的表达式，
si′(ai′)=si(ai′)+φi,ai′(s)1+∑bi∈Aiφi,bi(s)=si′(ai′)1+∑bi∈Aiφi,bi(s),
左右两侧分子相同且均不为0，意味着分母一定是1. 因此对于任意的i和bi∈Ai，有φi,bi(s)=0. 根据φ的定义，意味着没有玩家可以通过改换纯策略来提高自己的效用期望.
由引理7的判别条件可知，局势s是一个纳什均衡(Nash equilibrium). ◼

所以我们通常所见的“纳什均衡”，更专业、更具概括性的说法是，n人有限非合作博弈在混合策略意义下存在至少一个均衡点.

以上，是关于特定条件下纳什均衡存在性的全部证明过程.

关于约翰·纳什和冯·诺伊曼在博弈论领域的研究与贡献，我在“顶级数学家有多厉害？”的回答中进行过简单介绍，这里再稍微补充几句。

尽管纳什均衡对博弈论和经济理论有极为重要的作用，但从前文的证明过程中不难发现，纳什存在定理有一定的局限性：如果选择的集合是无限或非紧的集合，纳什均衡是完全可以不存在的。

举例来说，两个玩家同时说出数字，说出更大数字的玩家获胜；或者，两个玩家同时说出小于1的实数，说出更大数字的玩家获胜。显然，这两个博弈不存在纳什均衡，而类似的例子还有很多。

到此为止，基本完成了关于纳什均衡最基础也最浅薄的入门。

参考

1. ^A Tutorial on the Proof of the Existence of Nash Equilibria by A.X.Jiang, K.Leyton-Brown, University of British Columbia.

编辑于 2021-10-13 13:20