博弈中纯策略纳什均衡点

博弈论及其应用第2章纳什均衡《博弈论及其应用》（汪贤裕）2•主要内容：§2.1基本概念§2.2纳什均衡§2.3混合策略纳什均衡§2.4矩阵博弈第2章纳什均衡《博弈论及其应用》（汪贤裕）3§2.1基本概念§2.1.1基本概念§2.1.2占优均衡《博弈论及其应用》（汪贤裕）4§2.1.1基本概念例2.1.1智猪博弈例2.1.2夫妻爱好问题例2.1.3猜钱币游戏※完全信息静态博弈的三个基本要素《博弈论及其应用》（汪贤裕）5智猪博弈猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有一个食槽，另一边安装一个控制按钮，它能控制食料的供应。按一下按钮有8个单位的食料进入猪食槽，但需要支付2个单位的劳动成本。在吃食的过程中，若大猪先到，大猪能吃7个单位的食料，小猪只能吃1个单位。若小猪先到，小猪能吃到4个单位的食料，大猪只能吃4个单位。若两只猪同时到，大猪吃5个单位，小猪吃3个单位的食料。大猪和小猪都有两个策略，按或等待。《博弈论及其应用》（汪贤裕）6智猪博弈（续）两只猪在不同策略下的支付矩阵：大猪和小猪分别采取什么样的策略，且各自的收益分别为多少?《博弈论及其应用》（汪贤裕）7夫妻爱好问题OR《博弈论及其应用》（汪贤裕）8猜钱币游戏《博弈论及其应用》（汪贤裕）9完全信息静态博弈三要素•局中人集合局中人集合即博弈参加人的集合。若给定局中人，则记•策略集每个局中人有一个策略集Si，策略集Si，可以是有限集，也可以是无限集，当策略集是有限集时，我们记：当每个局中人选定一个策略si后，形成一个策略组合，并称为一个局势，记为：我们也引入如下记号：显然，也是一个局势，且。•支付函数每个局中人有一个支付函数。是局势s的函数，是局中人在局势下所能得到的收益。当然，每个局中人都希望自己的尽可能大。},,2,1{nNi}{\iNiiS()iiN()()()12{}{,,,}iiiiiimSssss1,2,inis12(,,,)nssss,1,2,,iisSin111||(,,,,,,)iiiinstsstssiiSt||ist||isss完全信息静态博弈三要素完全信息静态博弈就是在上述三要素的基础上，分析各局中人为实现自身利益最大化的策略行为分析。简记为：}]{},{,[iiPSNG《博弈论及其应用》（汪贤裕）10《博弈论及其应用》（汪贤裕）11§2.1.2占优均衡定义2.1.1严格占优策略定义2.1.2占优均衡定义2.1.3重复剔除占优均衡《博弈论及其应用》（汪贤裕）12定义2.1.1严格占优策略在博弈中，若和是局中人的两个策略，对任意策略组合都有：（2.1.1）则称，局中人的策略严格占优策略，或称策略相对于是严格劣策略。《囚徒困境》中、犯罪嫌疑人A和B策略（承认）就是一个严格占优策略。}]{},{,[iiPSNG)(iks)(ihsis)||()||()()(ihiikissPssPi)(iks)(ihs()ihs()iks《博弈论及其应用》（汪贤裕）13定义2.1.2占优均衡在博弈中，若每一个局中人都存在一个策略，使得占优于中任何策略，那么策略组合称为的占优策略均衡，简称占优均衡。对应的称为占优均衡结果。}]{},{,[iiPSNGi)(,'NiSsii'is}{\'iisS),,('''2'1nssssG}|)'({NisPi《博弈论及其应用》（汪贤裕）14定义2.1.2占优均衡（续）《囚徒困境》中严格占优均衡：（承认，承认）均衡结果《博弈论及其应用》（汪贤裕）15定义2.1.3重复剔除占优均衡在博弈中，经过重复剔出严格劣策略后，每个局中人只剩下一个唯一的策略：那么，策略组合称为博弈的重复剔除占优均衡。对应称为的重复剔除占优均衡结果。}]{},{,[iiPSNGiiisS),,2,1(ni12(,,)nssssG{()|1,2,,}iPsinG《博弈论及其应用》（汪贤裕）16定义2.1.3重复剔除占优均衡（续）《智猪博弈》中重复剔除占优均衡：（按，不按）均衡结果《博弈论及其应用》（汪贤裕）17§2.2纳什均衡§2.2.1纯策略纳什均衡§2.2.2双矩阵博弈的划线法§2.2.3无限策略的纯策略纳什均衡《博弈论及其应用》（汪贤裕）18§2.2.1纯策略纳什均衡定义2.2.1纯策略纳什均衡点和均衡结果定理2.2.1重复剔除占优均衡与纯策略纳什均衡※纳什均衡点与多目标规划求解比较《博弈论及其应用》（汪贤裕）19纯策略纳什均衡点和结果定义2.2.1在人非合作博弈中，若有策略组合，使得每一个，对任意都有（2.2.1）则称是的一个纯策略纳什均衡点，对应的称为对应的均衡结果。n),,,(21nssssiiSs1,2,,inNiiiSt)()()||()(sPtsPiiini,,2,1),,,(21nssssG},,2,1|)({nisPi[,{},{}]iiGNSP{1,2,,}Nn《博弈论及其应用》（汪贤裕）20纯策略纳什均衡点和结果《夫妻爱好》博弈中纯策略纳什均衡点：（足球，看足球）&（看芭蕾，看芭蕾）均衡结果均衡结果《博弈论及其应用》（汪贤裕）21纯策略纳什均衡点和结果（续）《猜钱币游戏》中不存在纯策略纳什均衡点。《博弈论及其应用》（汪贤裕）22定理2.2.1在人非合作博弈中：若，是重复剔除占优均衡，则一定是纯策略纳什均衡点。n}]{},{,[iiPSNG),,,(21nssss),,,(21nssss《博弈论及其应用》（汪贤裕）23定理2.2.1的证明证明：用反证法。若是重复剔除占优均衡，但不是纯策略纳什均衡点。则有和,,使得（2.2.2）那么在局中人在对的剔除过程中应有对任意的策略组合满足（2.2.1）式。这里策略组合当然也包括，即因此（2.2.2）式是不可能出现的，即（2.2.2）式与剔除严格劣策略过程矛盾。从而定理2.2.1成立。12,,,nssssNi()iitsiiSt)()||()||()(iiiitsPssPi)(itss()(||)(||)iiiiPssPst《博弈论及其应用》（汪贤裕）24纳什均衡点与多目标规划求解比较•在n人非合作博弈中，对每一个局中人，都在寻找自己的策略使得自己的收益最大，但是局中人单方面不能找到自己的最佳策略，其结果是相互影响的，是由策略组合决定的。这就是一个有相互影响的多人决策问题。有人可能这样设想：是否有一个局外人，将个局中人的收益最大作为个目标的多目标规划问题，即求：（2.2.3）纳什均衡点和上面的（2.2.3）的多目标规划的求解是两个不同的概念。12(,,,)nssss[,{},{}]iiGNSPiNiisS12(,,,)inPsssinn121max((),(),,()).nniPsPsPsstisS《博弈论及其应用》（汪贤裕）25纳什均衡点与多目标规划求解比较（续）•囚犯困境是一个2人非合作博弈两个局中人策略集和支付函数都表示在表1.2.1中•图2.2.1囚犯困境中的局中人收益图12,SS12,PPOP1P2-4-6-8-10-2-4-6-8-10DACB-2以囚徒困境为例《博弈论及其应用》（汪贤裕）26纳什均衡点与多目标规划求解比较（续）各点代表不同策略组合下双方的收益：•A点对应策略组合（承认，承认）•B点对应策略组合（承认，不承认）•C点对应策略组合（不承认，不承认）•D点对应策略组合（不承认，承认）•B点、C点和D点所代表的策略组合都是单人决策的多目标规划（2.2.3）中的非劣解。•但策略组合（承认，承认）是唯一的纳什均衡点。OP1P2-4-6-8-10-2-4-6-8-10DACB-2《博弈论及其应用》（汪贤裕）27纳什均衡点与多目标规划求解比较（续）结论：（一）非合作博弈中的纳什均衡点，不可能用（2.2.3）表示的多目标规划作为替代，双方有不同的思想基础。（二）博弈论与多目标规划这类多人决策问题的差异，进一步显示出纳什均衡思想在博弈论中的重要地位。《博弈论及其应用》（汪贤裕）28§2.2.2双矩阵博弈的划线法※双矩阵博弈的定义※纯策略纳什均衡的简单求解方法—划线法※定理2.2.2划线法与纯策略纳什均衡《博弈论及其应用》（汪贤裕）29双矩阵博弈的定义在博弈中，若三要素的前两个要素满足：•只有两个局中人，即;•策略集有限，即，此类博弈我们称为双矩阵博弈。}2,1{N},,,{211mS},,,{212nS双矩阵博弈称呼的由来（补充1）在双矩阵博弈中，对任意策略组合，记支付函数，，将两个局中人的支付函数分别记为矩阵A和矩阵B如下：111212122212()nnijmnmmmnaaaaaaAaaaa),(jiijjiaP),(1ijjibP),(2111212122212()nnijmnmmmnbbbbbbBBbbb《博弈论及其应用》（汪贤裕）30《博弈论及其应用》（汪贤裕）31双矩阵博弈称呼的由来（补充2）（2.2.4）回到：划线法定理2.2.2111112121121212222221122(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)nnnnijijmnmmmmmnmnabababababababababab划线法(1)对局中人1，在（2.2.4）式的每一行中，找出对方支付矩阵B中该行的最大元素,即并在下划线。当不唯一时，均在下面划线。(2)对局中人2，在（2.2.4）式每一列中，找出对方支付矩阵A中该列的最大元素即并在下划线。当不唯一时，均在下面划线。iijb},,2,1|max{njbbijijijbijbijajijaijamax{|1,2,,}ijijaaim《博弈论及其应用》（汪贤裕）32划线法(续)(3)若存在一对，使得其两个元素和下面都有划线，则是纯策略纳什均衡点，和是对应的纳什均衡结果。(4)若不存在满足（3）的数对，则该博弈无纯策略纳什均衡。),(jijiajibjiajib),(ji《博弈论及其应用》（汪贤裕）33《博弈论及其应用》（汪贤裕）34定理2.2.2在双矩阵博弈中划线法的使用：(1)若和同时得到划线，则一定是的纯策略纳什均衡点。(2)若不存在能够同时得到划线的数对，则无纯策略纳什均衡点。Gjiajib),(jiGG《博弈论及其应用》（汪贤裕）35定理2.2.2的证明•设和都得到划线，则下面两式同时成立：（2.2.5）（2.2.6）是博弈的纯策略纳什均衡点。•若不存在同时得到划线的数对，即不存在同时满足（2.2.5）和（2.2.6）式，则博弈也就不存在纯策略纳什均衡点。jiajib}{\),,(),(111ikjkkjjijiSPaaP}{\),,(),(212jhhihijijiSPbbP),(ji),(jiG《博弈论及其应用》（汪贤裕）36§2.2.3无限策略的纯策略纳什均衡定理2.2.3无限纯策略纳什均衡点存在性定理无限策略纳什均衡点的求解思路例2.2.2古诺模型例2.2.3伯川德双寡头垄断模型例2.2.4公共地的悲剧例2.2.5豪泰林价格竞争模型《博弈论及其应用》（汪贤裕）37定理2.2.3在博弈中，若局中人的策略集是有界闭区域，支付函数对任意都是的拟凹连续函数，则博弈一定存在有纯策略纳什均衡点。注：严格拟凹函数定义点击}]{},{,[iiPSNGiiS),(iiissPiisSisG《博弈论及其应用》（汪贤裕）38严格拟凹函数定义设是凸集上的函数，对任意及任意，若有：（2.2.8)则为上的拟凹函数。若（2.2.8）式中不等号为严格不等号，则称为上的严格拟凹函数。unRXXxx21,]1,0[))(),(min())1((212