非合作博弈与纳什均衡 李忠睿王大伟张正强 (排名不分先后) (上海交通大学数学与应用数学，上海) 摘要：本文是基于约翰·福布斯·纳什(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 作用下 的一个不动点
4均衡解的求法 当参与者人数和每个人的纯策略数不太大时，我们完全可以像例1和例2 的分析那样，用枚举法逐个验证每个纯策略情形是否是纳什均衡。对于高维情形， 这里给出了两种确定均衡解的方法。 4.1优势法 如果对任何n维策略向量$，p($;S)>p($;s),那么就称s比s严格优。 这就是说不管其他人采取何种策略，参与人ⅰ采取混合策略s得到的支付总是大 于采取s所得到的支付。为了判断出s是否较s严格占优，由于支付函数p的n元 线性性质，我们只需考虑其他参与人的纯策略就够了。 一对混合策略的占优关系往往带来其他占优关系。假设s比S严格优，且t 用到了在$中系数比在$，中系数大的所有纯策略，则对充分小的整数p t=t+p(s;-si) 是一个混合策略，并且据线性性质，t比t严格优。 由均衡解的定义显然可知，均衡解必不包括严格劣策略$。这给我们启发， 在找均衡解的过程中，严格劣策略的集合可以排除。 我们可以证明非劣势策略集的一些性质。它是单连通的，由策略单纯形的一 些面组成。 定理3严格劣策略消去法必不会消去Nash eq. 证明： 设(s1,S2,,Sn)是一个纳什均衡，且在某个过程中s*是上述策略向量 中第一个被消去的策略。则在该时刻存在某s,使得 p(S1,S2,,Si-1,S*,Si+1,,Sn <p(S1,S2,,S-1,S,Si+1,,Sn) 对当时所有未被消去的s1,S2,,S-1,S+1,…,Sn成立 因s*是第一个被消去的
4 均衡解的求法 当参与者人数 n 和每个人的纯策略数不太大时，我们完全可以像例 1 和例 2 的分析那样，用枚举法逐个验证每个纯策略情形是否是纳什均衡。对于高维情形， 这里给出了两种确定均衡解的方法。 4.1 优势法 如果对任何 n 维策略向量$， pi $；s i ' > pi $；si ，那么就称s i '比si严格优。 这就是说不管其他人采取何种策略，参与人 i 采取混合策略s i '得到的支付总是大 于采取si所得到的支付。为了判断出s i '是否较si严格占优，由于支付函数pi的 n 元 线性性质，我们只需考虑其他参与人的纯策略就够了。 一对混合策略的占优关系往往带来其他占优关系。假设s i '比si严格优，且ti 用到了在si中系数比在s i '中系数大的所有纯策略，则对充分小的整数ρ t i ' = ti + ρ s i ' − si 是一个混合策略，并且据线性性质，t i '比ti严格优。 由均衡解的定义显然可知，均衡解必不包括严格劣策略si。这给我们启发， 在找均衡解的过程中，严格劣策略的集合可以排除。 我们可以证明非劣势策略集的一些性质。它是单连通的，由策略单纯形的一 些面组成。 定理 3 严格劣策略消去法必不会消去 Nash eq. 证明： 设 s1 ∗，s2 ∗，……，sn ∗ 是一个纳什均衡，且在某个过程中si∗是上述策略向量 中第一个被消去的策略。则在该时刻存在某s i '，使得 pi s1，s2，…，si−1，si∗，si+1，…，sn < pi s1，s2，…，si−1，s i '，si+1，…，sn 对当时所有未被消去的s1，s2，…，si−1，si+1，…，sn成立. 因si∗是第一个被消去的
故上式对s1*,S2,…,5-1*,S+1,,Sn*成立，即 p(S1*,S2*,,sn）<p(S1*,S2,…,S1-1*,Si,S+1,,sn*) 这与(S1,S2*,,Sn)是纳什均衡矛盾。 定理4有限博弈中，严格劣策略消去法最后留下的必是Nash eq. 证明： 设最后留下的是(S1*,S2,,Sn)且它不是纳什均衡，则存在s,使 p(S1,s2,,5n)<p(S1,52*,,Si-1*,Si,S+1*,,Sn*)① 而$在某个过程中被消去，说明在某个时刻 P1(S1,S2,,Si-1,S,Si+1,,Sn) <p(S1,s2,,S-1,S,S+1,,Sn) 对剩下的所有策略成立 因此 p(S1*,S2,,S-1*,S,Si+1',,Sn*) <p(S1,s2',…,S-1,S,Si+1,,Sn')② (1)若s=s,①与②矛盾。 (2)若s≠S,重复上述过程，存在s",使 p(S1*,S2,,S-1*,S,S+1*,,Sn <p(S1*,S2*,,51-1*,S",Si+1',,5n) 如此下去总能找到某个s0=S,矛盾 例3囚徒困境 甲、乙两个嫌疑人涉嫌谋杀，被警方逮捕。他们被关在两个独立的牢房里， 警长告诉他们，如果两人均承认罪行，则都要被监禁8年；如果一人认罪一人抵 赖，则抵赖者将被监禁15年，另一人无罪释放。但他们心里明白，如果两人都 拒不承认，均只需被监禁1年。这个博弈问题的支付矩阵如下
故上式对s1 ∗，s2 ∗，…，si−1 ∗，si+1 ∗，…，sn ∗成立，即 pi s1 ∗，s2 ∗，……，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ 这与 s1 ∗，s2 ∗，……，sn ∗ 是纳什均衡矛盾。 定理 4 有限博弈中，严格劣策略消去法最后留下的必是 Nash eq. 证明： 设最后留下的是 s1 ∗，s2 ∗，……，sn ∗ 且它不是纳什均衡，则存在s i '，使 pi s1 ∗，s2 ∗，……，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ ……① 而s i '在某个过程中被消去，说明在某个时刻 pi s1，s2，…，si−1，s i '，si+1，…，sn < pi s1，s2，…，si−1，s i ''，si+1，…，sn 对剩下的所有策略成立. 因此 pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i ''，si+1 ∗，…，sn ∗ …………………② （1） 若s i ' ' = si∗，①与②矛盾。 （2） 若s i ' ' ≠ si∗，重复上述过程，存在s i '''，使 pi s1 ∗，s2 ∗，…，si−1 ∗，s i ''，si+1 ∗，…，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '''，si+1 ∗，…，sn ∗ 如此下去总能找到某个s i ' n = si∗，矛盾 例 3 囚徒困境 甲、乙两个嫌疑人涉嫌谋杀，被警方逮捕。他们被关在两个独立的牢房里， 警长告诉他们，如果两人均承认罪行，则都要被监禁 8 年；如果一人认罪一人抵 赖，则抵赖者将被监禁 15 年，另一人无罪释放。但他们心里明白，如果两人都 拒不承认，均只需被监禁 1 年。这个博弈问题的支付矩阵如下
甲\乙 坦白 抵赖 坦白 (-8,-8) (0,-15) 抵赖 (-15,0) (-1,-1) 【分析】 利用严格劣策略消去法求出纳什均衡。 如果乙坦白，甲选择坦白得到-8的支付，选择抵赖将得到-15的支付，因此 坦白所得支付更多；如果乙抵赖，甲选择坦白得到0的支付，选择抵赖将得到-1 的支付，因此坦白所得支付更多。于是抵赖是甲的一个严格劣策略，将甲抵赖这 一行划去。 甲1乙 坦白 抵赖 坦白 (-8,-8) (0,-15) 对乙做同样的分析，可以得出乙抵赖是乙的一个严格劣策略。 于是，（坦白，坦白）是该问题的纯策略纳什均衡。警方通过这种方法，成 功使犯罪嫌疑人认罪伏法。 例4点球大战 足球比赛中，某球员主罚点球，他有左、中、右三个方向可以瞄准，守门员 心里做出预判，扑向左还是右。其支付矩阵如下 守门员射手 左 中 右 左路 (1,0) (1,3) (0,1) 右路 (0,4) (0,2) (2,0) 【分析】 利用严格劣策略消去法求出纳什均衡。 记守门员为参与人1，射手为参与人2对于2而言，P2(*,中)>P2(*,右)， 所以踢右边是2的严格劣策略。将对应列划去。现在1通过以上分析，知道2 不会踢右边。此时1（左路，*）>p1(右路，*)，故守右路是1的严格劣策略。 将对应行划去。2知道1守左路，踢左边又是一个严格劣策略。如此操作，最后 我们得到该博弈问题的一个纯策略均衡是(1守左路，2踢中间)
甲\乙 坦白 抵赖 坦白 （-8，-8） （0，-15） 抵赖 （-15，0） （-1，-1） 【分析】 利用严格劣策略消去法求出纳什均衡。 如果乙坦白，甲选择坦白得到-8 的支付，选择抵赖将得到-15 的支付，因此 坦白所得支付更多；如果乙抵赖，甲选择坦白得到 0 的支付，选择抵赖将得到-1 的支付，因此坦白所得支付更多。于是抵赖是甲的一个严格劣策略，将甲抵赖这 一行划去。 对乙做同样的分析，可以得出乙抵赖是乙的一个严格劣策略。 于是，（坦白，坦白）是该问题的纯策略纳什均衡。警方通过这种方法，成 功使犯罪嫌疑人认罪伏法。 例 4 点球大战 足球比赛中，某球员主罚点球，他有左、中、右三个方向可以瞄准，守门员 心里做出预判，扑向左还是右。其支付矩阵如下 守门员\射手 左 中 右 左路 （1，0） （1，3） （0，1） 右路 （0，4） （0，2） （2，0） 【分析】 利用严格劣策略消去法求出纳什均衡。 记守门员为参与人 1，射手为参与人 2。对于 2 而言，p2 ∗ ，中 > p2 ∗ ，右 ， 所以踢右边是 2 的严格劣策略。将对应列划去。现在 1 通过以上分析，知道 2 不会踢右边。此时p1 左路， ∗ > p1 右路， ∗ ，故守右路是 1 的严格劣策略。 将对应行划去。2 知道 1 守左路，踢左边又是一个严格劣策略。如此操作，最后 我们得到该博弈问题的一个纯策略均衡是（1 守左路，2 踢中间）
守门员射手 中e 左路和 0) (1,3) 4.2反证法 确定均衡解的另一种方法称为反证法。该方法先假设均衡解存在，且均衡时 各分量策略满足某些条件，然后在假说成立时，继续推出均衡解所满足的进一步 条件，最后得出矛盾。该矛盾表明满足初始条件的均衡解时不存在的。 5算例 5.1通用软件matlab 算法A（见附件)是基于文献[2]给出的最优化原理得到的一种求纳什均衡的 高效算法。该程序有两个需要输入的参数，M和U。其中M是一个行向量，每i 个分量表示对应的参与人ⅰ有几个纯策略；U是一个矩阵，行数是所有n维纯策 略向量的数目，列数为n(参与者数目)。程序输出一个矩阵A,A的第ⅰ列表示 在均衡状况下，对应的参与人ⅰ的混合策略。 遗憾的是，对于有多个纳什均衡的博弈问题，该程序只能求出特定的一个均 衡解。 例5进退两难 某行业内有3个寡头A、B和C,对于每个寡头均有2个纯策略（策略1表示 激进，策略2表示保守)。用一个三维行向量表示A、B、C的盈利。以下是三个 寡头采取不同纯策略的情况下的盈利状况：（单位：亿元) (A采取策略1时) B趴C 策略1 策略2 策略1 (2.0,7.5,0.0) (3.0,0.2,0.3) 策略2 (6.0,3.6,1.5) (1.0,3.5,5.0) (A采取策略2时) B\C 策略1 策略2 策略1 (0.0,3.2,9.0) (2.0,3.2,5.0)
4.2 反证法 确定均衡解的另一种方法称为反证法。该方法先假设均衡解存在，且均衡时 各分量策略满足某些条件，然后在假说成立时，继续推出均衡解所满足的进一步 条件，最后得出矛盾。该矛盾表明满足初始条件的均衡解时不存在的。 5 算例 5.1 通用软件 matlab 算法 A（见附件）是基于文献[2]给出的最优化原理得到的一种求纳什均衡的 高效算法。该程序有两个需要输入的参数，M 和 U。其中 M 是一个行向量，每 i 个分量表示对应的参与人 i 有几个纯策略；U 是一个矩阵，行数是所有 n 维纯策 略向量的数目，列数为 n（参与者数目）。程序输出一个矩阵 A，A 的第 i 列表示 在均衡状况下，对应的参与人 i 的混合策略。 遗憾的是，对于有多个纳什均衡的博弈问题，该程序只能求出特定的一个均 衡解。 例 5 进退两难 某行业内有 3 个寡头 A、B 和 C，对于每个寡头均有 2 个纯策略（策略 1 表示 激进，策略 2 表示保守）。用一个三维行向量表示 A、B、C 的盈利。以下是三个 寡头采取不同纯策略的情况下的盈利状况：（单位：亿元） （A 采取策略 1 时） B\C 策略 1 策略 2 策略 1 （2.0，7.5，0.0） （3.0，0.2，0.3） 策略 2 （6.0，3.6，1.5） （1.0，3.5，5.0） （A 采取策略 2 时） B\C 策略 1 策略 2 策略 1 （0.0，3.2，9.0） （2.0，3.2，5.0）
策略2 (0.0,2.0,3.2) (2.1,0.0,6.0) 解： 先建立npg函数的两个参数。 M=[2,2,2]%每个人都有2种纯策略。 U=[2,7.5,0;3,.2,.3;6,3.6,1.5;2,3.5,5;0,3.2,9;2,3.2,5;0,2,3.2;2.1,0,1] %按照（1-1-1)、（1-1-2)、（1-2-1)、(1-2-2)…(2-2-2)这样的广义递增顺 序把支付矩阵内的元素当成行向量，排成矩阵U。 然后调用npg函数进行求解，并得到最终结果。 运行结果 A= /0.93021.00000.4340 0.06980.00000.5660 这表示该博弈问题的一个纳什均衡是：A以93.02%的概率采取激进策略，B 以100%的概率采取激进策略，C以43.40%的概率采取激进策略。 5.2最优化软件LING0 LING0软件是一款适用于求解最优化问题的数学软件。用LING0软件求纳什 均衡主要基于Lemke-Howson算法。Lemke-Howson算法把博弈论问题表达成线性 规划问题，然后就可以很容易用计算机软件求解。Lemke-Howson算法主要运用 下述定理： 对于2人博弈问题，支付函数只有p1,p2两个，可以写成支付矩阵 Bi B2 50005 &1 (c4,c) (c2,c2) (ia 02 (c21,c21) (c2,c2) (c2n' 000000 000e 000000 000000 Cm (cc) A Cmn' 其中ca=(c) 为参与人A的支付矩阵， CB=(c)为参与人B的支付矩阵。 那么纳什均衡的充要条件是
策略 2 （0.0，2.0，3.2） （2.1，0.0，6.0） 解： 先建立 npg 函数的两个参数。 M=[2,2,2]%每个人都有 2 种纯策略。 U=[2,7.5,0;3,.2,.3;6,3.6,1.5;2,3.5,5;0,3.2,9;2,3.2,5;0,2,3.2;2.1,0,1] %按照（1-1-1）、（1-1-2）、（1-2-1）、（1-2-2）……（2-2-2）这样的广义递增顺 序把支付矩阵内的元素当成行向量，排成矩阵 U。 然后调用 npg 函数进行求解，并得到最终结果。 运行结果 A = 0.9302 1.0000 0.4340 0.0698 0.0000 0.5660 这表示该博弈问题的一个纳什均衡是：A 以 93.02%的概率采取激进策略，B 以 100%的概率采取激进策略，C 以 43.40%的概率采取激进策略。 5.2 最优化软件 LINGO LINGO 软件是一款适用于求解最优化问题的数学软件。用 LINGO 软件求纳什 均衡主要基于 Lemke-Howson 算法。Lemke-Howson 算法把博弈论问题表达成线性 规划问题，然后就可以很容易用计算机软件求解。Lemke-Howson 算法主要运用 下述定理： 对于 2 人博弈问题，支付函数只有p1，p2两个，可以写成支付矩阵 β1 β2 …… βn α1 c 11 A ，c 11 B c 12 A ，c 12 B …… c 1nA ，c 1nB α2 c 21 A ，c 21 B c 22 A ，c 22 B …… c 2nA ，c 2nB …… …… …… …… αm cm1 A ，cm1 B cm2 A ，cm2 B …… cmn A ，cmn B 其中C A = c ij A m×n为参与人 A 的支付矩阵， C B = c ij B m×n为参与人 B 的支付矩阵。 那么纳什均衡的充要条件是