非合作博弈与纳什均衡 李忠睿王大伟张正强 (排名不分先后) (上海交通大学数学与应用数学，上海) 摘要：本文是基于约翰·福布斯·纳什(John Forbes Nash)1950年发表 的博士论文《非合作博弈》(Non-cooperative Games)加以翻译及注释的一篇综 述性文献。原文明确给出了“纳什均衡”的定义，证明了均衡存在性定理，只是 作为博弈论的经典不免有些晦涩。本文在其基础之上，配以相当丰富的例子，最 后用多种数学软件做出算例。 关键词：非合作博弈；均衡解 1引言 博弈论(Game Theory),又称对策论，作为现代数学的一个新分支，已经发 展成为分析理性决策者在策略互动局势下的行为选择模式的标准工具。1928年， 冯·诺依曼(Von Neumann)证明了博弈论的基本原理，从而宣告了博弈论的正 式诞生。1944年，冯·诺依曼和摩根斯坦(Morgenstern)合著的划时代巨著《博 弈论与经济行为》将二人零和博弈问题推广到n人合作博弈理论，并将博弈论系 统地应用于经济领域，从而奠定了这一学科的基础和理论体系。 但是在实际情况下，博弈双方不存在信息交流，即理性的各方独立行动，而 不会结成任何形式的联盟，这就是非合作博弈。非合作博弈适用于完全信息下， 决策者不串谋的博弈行为，比如寡头垄断市场下几大寡头的经济行为。约翰·纳 什于1950年发表的巨著《非合作博弈》就借助于纳什均衡、强解、次强解等一 系列解的概念，建立了这样一套策略性博弈的研究方法。 后面我们将有选择地阐述《非合作博弈》中的内容，简要介绍博弈论中的基 本概念，完成纳什均衡的解释及其存在性的证明，并用数学软件进行具体的实现。 2基本概念 这里我们先定义一些基本术语和记号，作为后几节的预备知识。 1.n人有限博弈
非合作博弈与纳什均衡 李忠睿 王大伟 张正强 （排名不分先后） （上海交通大学 数学与应用数学，上海） 摘 要：本文是基于约翰·福布斯·纳什（John Forbes Nash）1950 年发表 的博士论文《非合作博弈》（Non-cooperative Games）加以翻译及注释的一篇综 述性文献。原文明确给出了“纳什均衡”的定义，证明了均衡存在性定理，只是 作为博弈论的经典不免有些晦涩。本文在其基础之上，配以相当丰富的例子,最 后用多种数学软件做出算例。 关键词：非合作博弈；均衡解 1 引言 博弈论（Game Theory），又称对策论，作为现代数学的一个新分支，已经发 展成为分析理性决策者在策略互动局势下的行为选择模式的标准工具。1928 年， 冯·诺依曼（Von Neumann）证明了博弈论的基本原理，从而宣告了博弈论的正 式诞生。1944 年，冯·诺依曼和摩根斯坦（Morgenstern）合著的划时代巨著《博 弈论与经济行为》将二人零和博弈问题推广到 n 人合作博弈理论，并将博弈论系 统地应用于经济领域，从而奠定了这一学科的基础和理论体系。 但是在实际情况下，博弈双方不存在信息交流，即理性的各方独立行动，而 不会结成任何形式的联盟，这就是非合作博弈。非合作博弈适用于完全信息下， 决策者不串谋的博弈行为，比如寡头垄断市场下几大寡头的经济行为。约翰·纳 什于 1950 年发表的巨著《非合作博弈》就借助于纳什均衡、强解、次强解等一 系列解的概念，建立了这样一套策略性博弈的研究方法。 后面我们将有选择地阐述《非合作博弈》中的内容，简要介绍博弈论中的基 本概念，完成纳什均衡的解释及其存在性的证明，并用数学软件进行具体的实现。 2 基本概念 这里我们先定义一些基本术语和记号，作为后几节的预备知识。 1. n 人有限博弈
n人有限博弈即为有个决策人参与的博弈，每个决策人只有有限个纯策略。 所谓纯策略，即决策人可以做出的决定。如某企业面对价格竞争，可以选择降价 或者维持原价，则“降价”就是该企业的一个纯策略，同样地，“维持原价”也 是一个纯策略。我们用π，B,v等表示第i个参与者的不同纯策略。 2.混合策略，S1 参与者i的混合策略，是指他的所有纯策略的凸组合。我们用s=∑.CicTja 表示一个混合策略，其中ca≥0且∑acia=1。它的实际意义是参与者i做出 纯策略πia的概率为cia。特别地，如果某个cia>0,则称混合策略s用到了a。 我们说n维策略向量，是指所有参与人的策略所组成的一个向量$=(S1,S2 ,,Sn)。同样地，如果混合策略s用到了a,则称策略向量$用到了a。 3.支付函数，P 对于固定的维策略向量$，每个参与者在博弈中会得到一定的效用。记第ⅰ 个参与者得到的效用为P($),称为参与者ⅰ的支付函数。显然，p对每个参与人 的混合策略是线性的(n元线性)。 为方便起见，引入替代符号($；t)=(S1,52,,5-1,,5+1,…,sn, 用($；t;)表示多次替代($；t)；),余此类推。 4.均衡解 我们称一个n维策略向量$是均衡解，当且仅当$满足以下条件： p($)=max{p($;)} 所有r 对一切i=1,2,…,n成立 上式表明，均衡解$表示其他人的策略固定不变的情况下，每一个参与人追 求自身的最大利益（支付）的混合策略。在$中，每一个人的策略都是最优的。 定理1（均衡解的另一充要条件) n维策略向量$是一个均衡解，当且仅当下列条件成立：
n 人有限博弈即为有 n 个决策人参与的博弈，每个决策人只有有限个纯策略。 所谓纯策略，即决策人可以做出的决定。如某企业面对价格竞争，可以选择降价 或者维持原价，则“降价”就是该企业的一个纯策略，同样地，“维持原价”也 是一个纯策略。我们用πiα，πiβ，πiγ等表示第 i 个参与者的不同纯策略。 2. 混合策略，si 参与者 i 的混合策略，是指他的所有纯策略的凸组合。我们用si = α ciαπiα 表示一个混合策略，其中ciα ≥ 0 且 α ciα = 1。它的实际意义是参与者 i 做出 纯策略πiα的概率为ciα。特别地，如果某个ciα > 0，则称混合策略si用到了πiα。 我们说 n 维策略向量，是指所有参与人的策略所组成的一个向量$ = s1，s2 ，……，sn 。同样地，如果混合策略si用到了πiα，则称策略向量$用到了πiα。 3. 支付函数，pi 对于固定的 n 维策略向量$，每个参与者在博弈中会得到一定的效用。记第 i 个参与者得到的效用为pi $ ，称为参与者 i 的支付函数。显然，pi对每个参与人 的混合策略是线性的（n 元线性）。 为方便起见，引入替代符号 $；ti = s1，s2，…，si−1，t i，si+1，…，sn ， 用 $；ti；rj 表示多次替代 $；ti ；rj ，余此类推。 4. 均衡解 我们称一个 n 维策略向量$是均衡解，当且仅当$满足以下条件： pi $ = max 所有ri pi $；ri 对一切 i=1,2，…，n 成立 上式表明，均衡解$表示其他人的策略固定不变的情况下，每一个参与人追 求自身的最大利益（支付）的混合策略。在$中，每一个人的策略都是最优的。 定理 1 （均衡解的另一充要条件） n 维策略向量$是一个均衡解，当且仅当下列条件成立：
如果$用到了ia,那么Pia($)=max Pis($) 其中pia($)=p($;a)。 证明： (必要性) 若$是一个均衡解，则对一切i,p($)=max{p($;r)}。 所有r 另一方面，由于支付函数p(S1,S2,,Sn)关于S是线性的，即 r=〉caia ps:)-∑aps:mw 所以 max{p($;r)}=max{p($;a)}…（*) 所有r 这表明除非π是参与人i的一个最优纯策略，否则$就没有用到πia。 (充分性) 若$用到了ia可以推出Pia($)=max Pis($),则所有满足pia($)<max Pis($) 的a,其对应的cia=0。 因而 pi($)=max{pi($;Tia)} 结合(*)式便知$是均衡解。 上述“均衡解”的概念由纳什博士首次提出，因而称为“纳什均衡”(Nash equilibrium)。值得一提的是，尽管上述定理表明均衡解只会用到最优纯策略， 但是这些纯策略并不一定唯一。换言之，纳什均衡不一定是纯策略均衡。 通过下面的两个例子，读者可以更好地理解以上概念。 例1少数服从多数的投票 上海交通大学考虑修建游泳馆，馆址在A,B,C三处地点中选出。学校采取投 票的形式确定选址，规则规定，由1,2,3三名学生代表参与投票，每人一票且不 能弃权。投票结果按照少数服从多数的原则，即 (1)如果某个选项获得绝对多数的选票，则决定在该处兴建游泳馆：
如果$用到了πiα，那么piα $ = max β piβ $ 其中piα $ = pi $；πiα 。 证明： （必要性） 若$是一个均衡解，则对一切 i，pi $ = max 所有ri pi $；ri 。 另一方面，由于支付函数pi s1，s2，……，sn 关于si是线性的，即 ri = α ciαπiα pi $；ri = α ciα pi $；πiα 所以 max 所有ri pi $；ri = max α pi $；πiα ………………（ ∗ ） 这表明除非πiα是参与人 i 的一个最优纯策略，否则$就没有用到πiα。 （充分性） 若$用到了πiα可以推出piα $ = max β piβ $ ，则所有满足piα $ < max β piβ $ 的πiα，其对应的ciα = 0。 因而 pi $ = max α pi $；πiα 结合（*）式便知$是均衡解。 上述“均衡解”的概念由纳什博士首次提出，因而称为“纳什均衡”（Nash equilibrium）。值得一提的是，尽管上述定理表明均衡解只会用到最优纯策略， 但是这些纯策略并不一定唯一。换言之，纳什均衡不一定是纯策略均衡。 通过下面的两个例子，读者可以更好地理解以上概念。 例 1 少数服从多数的投票 上海交通大学考虑修建游泳馆，馆址在 A,B,C 三处地点中选出。学校采取投 票的形式确定选址，规则规定，由 1,2,3 三名学生代表参与投票，每人一票且不 能弃权。投票结果按照少数服从多数的原则，即 （1） 如果某个选项获得绝对多数的选票，则决定在该处兴建游泳馆；
(2)如果三个选项同票，则在A处修建游泳馆。 事先调查三位代表的偏好，得到支付函数如下： u1(A)=2(B)=u3(C)=2 u1(B)=u2(C)=u3(A)=1 u1(C)=u2(A)=u3(B)=0 【分析】 这是一个3人有限博弈，对每个人来说，其决策空间S={A,B,C是一个有限 集合。其中A,B,C是三个不同的纯策略。容易验证，(A,B,A)是该问题的一个 纳什均衡。这是因为对1来说，A,B同票情况下，1倾向于选A或者C来使自己 获得最大支付；对2来说，A得2票已经当选，选什么无所谓；对3来说，A,B 同票，让C当选已无可能，故选A或者C来使自己获得最大支付。 事实上，这个问题有相当多的纳什均衡，而纯策略均衡只有6个：(A,A,A)、 (AB,A)、(A,B,C)、(A,C,C)、(B,B,B)、(C,C,C)。但（A,B,B)不是纳什均衡， 请读者自行验证。 例2配对游戏 甲、乙两人分别在卡片上写下“正”、“反”两个字中的一个，然后同时翻开 比对。如果两人写的字相同，则乙给甲1元钱；否则，甲给乙1元钱。 【分析】 对于此问题，我们可以写出其支付矩阵为 甲\乙 正 反 正 （1,-1) (-1,1) 反 (-1,1) （1,-1) 验证所有四种情况，可以发现，（正，正），（正，反），（反，正），（反，反） 均不是纳什均衡。故而此问题无纯策略均衡解。 事实上，此问题有混合策略均衡(50%正50%反，50%正50%反)，即甲乙两人 都随机（等概率）地写卡片上的文字。我们可以验证这是一个纳什均衡。设乙在 采取50%-50%策略情况下，甲有p的概率写“正”，则甲赢得钱数ξ的期望是 E5=p:1-p2p+a-p0 1 即甲无论采取何策略赢钱期望是固定的，当然是最大化支付的策略。同理，甲在 采取50%-50%策略情况下，50%-50%策略也是乙的最优策略。因此，（50%正50%
（2） 如果三个选项同票，则在 A 处修建游泳馆。 事先调查三位代表的偏好，得到支付函数如下： u1 A = u2 B = u3 C = 2 u1 B = u2 C = u3 A = 1 u1 C = u2 A = u3 B = 0 【分析】 这是一个 3 人有限博弈，对每个人来说，其决策空间Si = A,B,C 是一个有限 集合。其中 A，B，C 是三个不同的纯策略。容易验证，（A,B,A）是该问题的一个 纳什均衡。这是因为对 1 来说，A,B 同票情况下，1 倾向于选 A 或者 C 来使自己 获得最大支付；对 2 来说，A 得 2 票已经当选，选什么无所谓；对 3 来说，A,B 同票，让 C 当选已无可能，故选 A 或者 C 来使自己获得最大支付。 事实上，这个问题有相当多的纳什均衡，而纯策略均衡只有 6 个：（A,A,A）、 （A,B,A）、（A,B,C）、（A,C,C）、（B,B,B）、（C,C,C）。但（A,B,B）不是纳什均衡， 请读者自行验证。 例 2 配对游戏 甲、乙两人分别在卡片上写下“正”、“反”两个字中的一个，然后同时翻开 比对。如果两人写的字相同，则乙给甲 1 元钱；否则，甲给乙 1 元钱。 【分析】 对于此问题，我们可以写出其支付矩阵为 甲\乙 正 反 正 （1，-1） （-1，1） 反 （-1，1） （1，-1） 验证所有四种情况，可以发现，（正，正），（正，反），（反，正），（反，反） 均不是纳什均衡。故而此问题无纯策略均衡解。 事实上，此问题有混合策略均衡（50%正 50%反，50%正 50%反），即甲乙两人 都随机（等概率）地写卡片上的文字。我们可以验证这是一个纳什均衡。设乙在 采取 50%-50%策略情况下，甲有 p 的概率写“正”，则甲赢得钱数ξ的期望是 Eξ = p· 1 2 − 1 − p · 1 2 − p· 1 2 + 1 − p · 1 2 = 0 即甲无论采取何策略赢钱期望是固定的，当然是最大化支付的策略。同理，甲在 采取 50%-50%策略情况下，50%-50%策略也是乙的最优策略。因此，（50%正 50%
反，50%正50%反)是一个纳什均衡。 3均衡解的存在性 基于角谷静夫(Kakutani)的不动点定理，均衡解存在性的证明已经发表在 Proc.Nat.Acad.Sci.U.S.A,36,pp.48-49。这里纳什给出了一种基于布劳 维尔(Brouwer)不动点定理的更为简便的证法。这种证明的主要思想是，在n 维空间里构造一个连续变换T,使得T的不动点就是博弈的均衡解。 定理2任何有限博弈都有一个均衡解。 证明： 令$为一个n维混合策略向量，p($)是与之对应的第i个参与人的支付函数。 仍记pia($)=p($;a)。我们现在定义一族连续函数： 中ia($)=max{0,pia($)-p($)} 对$的每一个分量s,我们定义一个新的混合策略s' s=s+2a中a(S)ma 1+∑a中ia($) 合起来构成新的n维混合策略向量$=(S1',S2',,Sn。 现在我们只要证明，映射T:$→$'的不动点就是均衡解。 首先考虑任意n维混合策略向量$。在$中第ⅰ个人的策略s将用到他的一些 纯策略。在这些纯策略当中，有一些纯策略，如πg,满足pa($)≤p($)。这表 示第ⅰ个人把自己的策略换成π后，收益反而下降了。我们说这样的纯策略是 “最不经济的”，它将使得中($)=0。 现在如果$在映射T下是一个不动点，那么s中用到的纯策略π在映射T下 一定不减。于是，为使s表达式的分母不超过1，对所有的B,中B($)的值必为 零。 因此，如果$是T的一个不动点，那么对任意i和B有中B($)=0。这意味着 任何参与人都不可能通过改变策略来使自己的支付提高，而这正是均衡解的判据。 反过来，如果$是一个均衡解，则所有的中均为0，这就使得$是在T作用下 的一个不动点
反，50%正 50%反）是一个纳什均衡。 3 均衡解的存在性 基于角谷静夫（Kakutani）的不动点定理，均衡解存在性的证明已经发表在 Proc. Nat. Acad. Sci. U.S.A，36，pp.48-49。这里纳什给出了一种基于布劳 维尔（Brouwer）不动点定理的更为简便的证法。这种证明的主要思想是，在 n 维空间里构造一个连续变换 T，使得 T 的不动点就是博弈的均衡解。 定理 2 任何有限博弈都有一个均衡解。 证明： 令$为一个 n 维混合策略向量，pi $ 是与之对应的第 i 个参与人的支付函数。 仍记piα $ = pi $；πiα 。我们现在定义一族连续函数： φiα $ = max 0，piα $ − pi $ 对$的每一个分量si，我们定义一个新的混合策略si' s i ' = si + αφiα $ πiα 1 + αφiα $ 合起来构成新的 n 维混合策略向量$' = s1 '，s2 '，……，sn ' 。 现在我们只要证明，映射 T：$→$' 的不动点就是均衡解。 首先考虑任意 n 维混合策略向量$。在$中第 i 个人的策略si将用到他的一些 纯策略。在这些纯策略当中，有一些纯策略，如πiα，满足piα $ ≤ pi $ 。这表 示第 i 个人把自己的策略换成πiα后，收益反而下降了。我们说这样的纯策略是 “最不经济的”，它将使得φiα $ = 0。 现在如果$在映射 T 下是一个不动点，那么si中用到的纯策略πiα在映射 T 下 一定不减。于是，为使s i '表达式的分母不超过 1，对所有的β，φiβ $ 的值必为 零。 因此，如果$是 T 的一个不动点，那么对任意 i 和β有φiβ $ = 0。这意味着 任何参与人都不可能通过改变策略来使自己的支付提高，而这正是均衡解的判据。 反过来，如果$是一个均衡解，则所有的φ均为 0，这就使得$是在 T 作用下 的一个不动点