未必孤独网 > 是不是所有 2×2 博弈中,有两个纯策略纳什均衡就一定有一个混合策略纳什均衡?

是不是所有 2×2 博弈中,有两个纯策略纳什均衡就一定有一个混合策略纳什均衡?

【Manolo的回答(48票)】:

答主提的这个博弈是一经典例子,恰好落在@Richard Xu 给的奇数定理中“几乎所有”之外,只有两个纳什均衡(正,正)和(反,反)。这个问题已见过不止一次,干脆直接写个证明。

奇数定理可分步作更严格表述:首先,几乎所有博弈都是准强(quasi-strong)的;其次,几乎所有博弈都是正则(regular)的;再次,所有正则和准强的博弈都只有奇数个均衡;因此,几乎所有博弈都只有奇数个均衡。这里选用证明来自Harsanyi(1973),完全是几何的思路,非常优美。由于答主懒惰,大部分地方只给证明概要,强烈建议照着原文做一次。答案以下部分按符号说明、几何直觉和证明主体顺序排列。结尾简单提及其它证明思路。

首先是符号,都是博弈论教材和书籍中常用记法。记有限博弈

中有

位参与者,其中第

位参与者策略空间是

是有限集。令第

位参与者策略集中第

个策略为

,则

是全体参与者的一组纯策略。每个参与者以一定概率选取不同纯策略称为混合策略,我们记第

位参与者在第

个策略上赋予概率

,则一组混合策略剖面可记为

,其中

代表第

个参与者在

上选取的概率分布。令

代表参与者收益,则

完整描述了有限博弈

Harsanyi证明思路如下:首先,构造一个新博弈

,其中

。这是退化(degenerate)博弈,个体支付与他人决策无关,有唯一纳什均衡

。接着再构造一个博弈

,其中支付函数

。当

时,这个博弈就是

,有唯一均衡点;当

时,这个博弈就是原博弈

。当

上左右移动时,策略空间和确定纳什均衡所需条件交出一组代数曲线。

全体混合策略空间

是紧凸集,故这组曲线在策略空间内可以取到起点和终点。不妨令

处均衡为起点,因此处雅可比行列式大于

,根据隐函数定理知这不可能是终点,故

处必然还有一个均衡构成曲线起点。如果

处,即原博弈,还有其它均衡,它必然是代数曲线上一支的解析延长。又此分支向另一端解析延长不可能交边界点于

处,故这个交点必然在

处,而这意味着除了之前那个构成起点均衡,其它纳什均衡必然成对出现。为得到以上证明需要准强和正则条件,所以接下来说明“几乎所有博弈都准强”和“几乎所有博弈都正则”即可。证明前者需要说明非准强博弈构成欧氏空间中紧凸集边界,再用Sard定理即可证明后者,这就构成了完整证明。

接下来开始描述证明梗概。考虑博弈

,一组策略

构成纳什均衡条件为对所有参与者

,有

。记个体

在策略

中赋予正概率的所有纯策略集合为

,称支撑集。则上式可化简为以下两类条件:一是支撑集内部所有纯策略收益相等,即对

,有

,二是支撑集内任一策略收益至少和不在支撑集中纯策略收益一样大,即对

,有

。如果这些不等式全是严格不等号,我们称这一均衡是准强的。否则,我们称这一均衡是极弱的(extra-weak)。

注意到当

时,支撑集必然包含全体纯策略,否则,不在支撑集中策略将给出给出

收益。因此,当

时,只需要第一个条件,再对概率做一点规定即可确保满足条件的策略必然构成纳什均衡,这等价于对任意参与者

的第

个策略,我们都有

。注意到

对任意

是严格凹的,二阶条件自动满足。所以上式给出了纳什均衡的必要条件。在此基础上,利用事实

,我们可进一步化简均衡条件为如下形式:对任意参与者

的第

到第

个策略,有

。这里有

个等式约束,加上

个约束,共计

个等式约束。再加上对任意

个不等式约束,这

个约束共同给出了

一组均衡。

,这是一

维欧式子空间。令集体

是全体满足以上

个等式约束的全体

的集合,在非退化情形里,

是一维代数射影。再令集合

是具备以下特征全体

的集合:不仅满足前

个约束,还满足后

个不等式约束。这意味着

给出了全体

博弈的解。令

是博弈全体均衡集合,根据前面分析,可证原文定理1:当

时,

;当

时,

我们现在定义正则。考虑对应

,我们可以写出其雅可比行列式:对任意个体

的混合策略

。其中对任意

。对

之间

。考虑原博弈

的一个均衡

,如果

,我们就称均衡

是正则的,否则就是非正则均衡。博弈

正则的,当且仅当它的所有均衡都是正则均衡,雅可比行列式大于

作者接下来引入几个代数几何中的定理,这里简要叙述。首先是原文定理2:记

维欧氏空间

中代数曲线

上一段弧且

,则

可在

处解析延长。证明按

是否奇异点分类讨论即可。非奇异点情形用隐函数定理马上证出,奇异点情形用Puiseux定理构造收敛列即可。这一定理马上导出关键引理:令

是一代数曲线,

是任意一点,则通过

点的

的弧永远是偶数条(可能不存在)且成对出现。成对出现意指:它们是彼此的解析延长而不是任何其它弧的解析延长。原文定理3如下:记

是代数曲线

的弧且整体坐落在有非空内部的紧凸集

内。不失一般性,假设

的边界点,那么根据定理2和代数曲线性质,我们总可以在

处作足够远的解析延长,使

于边界点

回忆前面记号,

恰是一紧凸集,我们记其边界为

,再记解集合

交于

考虑

,如果

不是孤立点,那么以下二点必居其一且仅居其一:

是博弈

的均衡;

是博弈

的均衡。我们分两步证明这一点。首先,当

时,所有均衡支集都包含所有策略,这意味着

内部。而这又意味着当

时,纳什均衡不可能是边界点,故只有

时均衡在边界点上。当

时,因

不是孤立点,这意味着我们可以用一组序列

去逼近。又由于Debreu证明了对应

是上半连续的,故

必然是一组均衡。再计算均衡

处雅可比行列式可知

,故这是非奇异点,仅是代数曲线上一个分支的终点,以上证毕定理4和5。

命题6要求我们证明如果博弈

是准强且正则的,则

,即博弈

处任意一个均衡都是非奇异点,且仅是代数曲线上一个分支的终点。令这个均衡是

,如果

内部,直接使用定理5证法即证。如果不是这样,说明部分纯策略不在支撑集中。证明此命题等价于说明对任意不在支集中的策略

,有

。不失一般性,我们首先假设

(1),再将

两边对

微分,再令

,马上得到

(2)。注意到因为策略

不在支撑集中,又博弈是准强的,这意味着

(3)。结合(1)(2)(3)就得到了

,证毕。至此,我们已准备好了一切工具。

现在即可证明核心命题:令

是一准强且正则博弈,则

至多只有有限个纳什均衡。

处存在唯一突出均衡(distinguished equilibrium)与对应博弈

处唯一均衡相互连接。

其它所有均衡均成对出现,彼此相互连接。因此,任一准强且正则均衡必然有奇数个均衡。我们首先证明有限性。回忆最开始

的定义:代数射影

和紧凸集

的重合部分。这意味着

至多只有有限个分支。又

的均衡必然坐落在

某个分支终点上。分支数量有限,结合一个分支至多只有两个端点,有限性证毕。再考虑博弈

处唯一均衡,由于这个均衡是

中一个分支的非奇异边界点,这个分支必然可以延伸到

处。否则,这个分支另一边界点是

自身,矛盾。不妨记

处边界点是

,这就找到了前述突出均衡,第二部分证毕。假设

处还有其它均衡,它们都是非奇异边界点,恰好在一个分支上。由定理5可知它们不能延伸到自身和突出均衡处,由定理4和前述分析知它们不能延伸至

处,故其只能成对出现,证毕。

接下来只需要证明以下两个命题:全体非准强博弈构成零测集;全体非正则博弈构成零测集。这里思路简单,符号繁琐,只给概要。为证明前一命题,只要看到非准强意味着确定纳什均衡条件中部分不等式取等号,而这意味着全体非准强博弈构成欧氏空间中一内部非空紧凸集合的边界,必定是零测集。后一命题需要Sard定理:如果映射“足够”连续可微,定义域中雅可比行列式为0点的像构成0测集。重排策略后构造映射再用Sard定理即证。综合以上所有命题,我们即可得到 @Richard Xu回答的奇数定理:几乎所有有限博弈都只有奇数个纳什均衡

这个定理最早由Wilson在1971给出,证明用单纯形法,也很优美。不过自己觉得无论是优美程度还是几何直觉,都属Harsanyi证明更优,故介绍这个版本。再次强烈推荐阅读原文。

参考文献:

Harsanyi J. Oddness of the number of equilibrium points: a new proof[J]. International Journal of Game Theory, 1973, 2(1): 235-250.

Wilson R. Computing equilibria of n-person games[J]. SIAM Journal on Applied Mathematics, 1971, 21(1): 80-87.

【RichardXu的回答(14票)】:

奇数定理:几乎所有有限策略博弈都有奇数个纳什均衡。

【LZHCHAOS的回答(0票)】:

从我有限的科普级知识来看 显然大家趋向于选一

【前提是我选一并不付出额外代价】

如果双方信息不能互通 并假设两人理性 无额外成本 那么一是最佳选择

因为在对方选一时

【共赢】

在对方选二时

【我也不亏】

那么我选一就是最佳 不管对方选什么 而且根据我的分析 对方必然选一

然后 因为两边的选择与后果是对称的 那么大概就会有奇数个均衡解吧

【并不是很清楚这个在两边的选择不对称是是否能证】

最后 题主你有字打错了

【每人】打成了

【没人】

【Regon的回答(0票)】:

仅答第三问。

两个参与者在进行决策时。均会考虑到选正的收益上限为1,收益下限为0;选反的收益上限为0,收益下限为0,所以两个参与者均会选择正。

混合策略纳什均衡就是加上一个概率算一下,结果是一样的。

【seneca5的回答(0票)】:

正好在学博弈论,初学者,强答一个吧

第一问

找纳什均衡最通俗的办法就是:猜对手的策略,然后针对自己的猜测找占优策略,对其他所有player采取这个方法,最后得出解,但前提是猜测正确

检验起来也不复杂,要用数学符号表示可能会非常复杂,用文字也可以描述,我用自己的话概括了一下:

1你们都这么玩,谁不这么玩就傻逼了,不信自己试

2咱们都这么玩,对大家都好

2这么玩结果最好,再给我一次机会选,我也不换

但是这些办法仍然有一定局限性,解决简单问题还是适用的

第二问 是的

第三问 正,正

所有纯策略其实都是混合策略

新闻聚焦
热门推荐
  • 低俗靡乱!喜宴竟充斥惊艳脱衣舞表演

    中新网12月7日电 据台湾《联合报》报道,桃园县内喜宴、庙会、社团、晚会充斥钢管、清凉秀、脱衣舞,县议员舒翠玲以自己参加的场合为证,当场看见辣妹和客人磨蹭,甚至指导单位是“桃园县政府”、“公所”的活动也如......

    01-13 来源:未知

    分享
  • 《我是特种兵之霹雳火》崔华盾扮演者张进个人资料及照

    《我是特种兵之霹雳火》崔华盾扮演者 本篇电视资讯由未必孤独网(www.vbgudu.com)独家整理,如有转载请注明出处。 曾经同是“特警小虎队”一员的李飞和张进这次将重新在《霹雳火》中集结,并且再度并肩作战。 由李......

    01-13 来源:未知

    分享
  • 郎永淳老婆吴萍患肿瘤赴美疗养 郎永淳近况

    郎永淳温馨全家福 央视新闻主播郎永淳虽然在电视上天天与观众见面,因播报新闻成了公众人物,并拥有了很多的粉丝。但生活中的郎永淳却十分很低调,不仅从未谈及过自己的私生活,就连他的另一半及孩子也未被曝光过。......

    01-13 来源:未知

    分享
  • 《我是特种兵之霹雳火》王星扮演者李飞个人资料及照片

    《我是特种兵之霹雳火》王星扮演者李飞 本篇电视资讯由未必孤独网(www.vbgudu.com)独家整理,如有转载请注明出处。 《我是特种兵之霹雳火》作为刘猛导演特种兵系列的第四部作品,自筹划以来就备受网友关注。承继着......

    01-13 来源:未知

    分享
  • 梦鸽:为孩子做什么都不为过 李案会造成世界影响

    梦鸽(资料图) 李某某等涉嫌强奸案从2月份发酵至今,持续半年,热度不减。作为被告李某某的监护人,梦鸽放下红色明星、部队歌唱家的尊严,发布声明、反诉、上访,走进长枪短炮的包围圈,代替独子站在第一线。 为了......

    01-13 来源:未知

    分享
  • 雷!彪悍美女竟在大街上做超不雅动作

    ......

    01-13 来源:未知

    分享
  • 孙俪微博拍卖老公邓超的爱裤,邓超与孙俪感情好不好

    今天我们来盘点一下娱乐圈的模范夫妻。孙俪和邓超是娱乐圈有名的模范夫妻,两人相爱至今都没有穿过其他的绯闻,而在邓超走向逗比之路的过程中,娘娘孙俪也开始受到影响,近日邓超在网上晒了一张与孙俪的另类合影,网......

    01-12 来源:

    分享
  • 巩俐与孙红雷谈过恋爱吗?巩俐孙红雷主演的电影是哪部

    从绯闻女友巩俐、左小青,到王骏迪,孙红雷绯闻伴随走红。在《窈窕绅士》发布会上,孙红雷大晒幸福,并直言,“我现在还不会和女友公开亮相,以免被人说我在炒作。”被问及是否有意结婚,他说,“谈婚论嫁对我来说不......

    01-12 来源:

    分享
  • 曝盛一伦喜欢骂人成瘾,盛一伦同性恋是真的吗?

    子妃升职记不仅火啦张天爱,也让男主盛一伦踏进拉娱乐圈。盛一伦被曝骂人成瘾 骂人聊天记录图片,近日,盛一伦将东家乐漾影视诉至法院,索片酬1051.5万元,朝阳法院已受理此案。12月12日,盛一伦发长文回应解约风波称......

    01-12 来源:

    分享
  • 北京学生卡坐地铁打折吗?北京现在有几条地铁?

    北京的物价使出拉名的贵,许多北漂为啦省钱想尽办法。近日,在北京部分地铁站周边,出现贩卖“”的卡贩子,100元就能办一张大,还送学生证。新京报记者探访发现,从卡贩子手中购得的,能顺利充值并可享受2.5折优惠。......

    01-12 来源:

    分享
返回列表