学生建设网站,旅游网站开发目标,WordPress圆形图片,深圳市保障性住房轮候申请系统纳什均衡#xff08;或者纳什平衡#xff09;#xff0c;Nash equilibrium ,又称为非合作博弈均衡#xff0c;是博弈论的一个重要策略组合#xff0c;以约翰纳什命名。
定义
经济学定义 数学定义
纳什均衡的定义#xff1a;在博弈G﹛S1,…,Sn#xff1a;u1,…#x… 纳什均衡或者纳什平衡Nash equilibrium ,又称为非合作博弈均衡是博弈论的一个重要策略组合以约翰·纳什命名。
定义
经济学定义 数学定义
纳什均衡的定义在博弈G﹛S1,…,Snu1,…un﹜中如果由各个博弈方的各一个策略组成的某个策略组合s1*,…sn*中任一博弈方i的策略si*都是对其余博弈方策略的组合s1*,…si-1,si1,…sn*的最佳对策也即uis1*,…si-1,si,si1,…sn≥uis1*,…si-1,sij,si1,…sn对任意sij∈Si都成立则称s1*,…sn*为G的一个纳什均衡。 注经济学定义从字面上还是相对比较好理解的这里稍微解释一下数学定义博弈论也称Game Theory一场博弈用G表示Si表示博弈方i的策略ui表示收益。因此纳什均衡的意思是任何一方采取的策略都是对其余所有方采取策略组合下的最佳对策当所有其他人都不改变策略时为了让自己的收益最大任何一方都不会或者无法改变自己的策略这个时候的策略组合就是一个纳什均衡。
纳什证明了在每个参与者都只有有限种策略选择、并允许混合策略的前提下纳什均衡一定存在。以两家公司的价格大战为例纳什均衡意味着两败俱伤的可能在对方不改变价格的条件下既不能提价否则会进一步丧失市场也不能降价因为会出现赔本甩卖。于是两家公司可以改变原先的利益格局通过谈判寻求新的利益评估分摊方案也就是Nash均衡。类似的推理当然也可以用到选举群体之间的利益冲突潜在战争爆发前的僵局议会中的法案争执等。
纳什均衡分类
纳什均衡可以分成两类“纯战略纳什均衡”和“混合战略纳什均衡”。 所谓纯战略是提供给玩家要如何进行赛局的一个完整的定义。特别地是纯战略决定在任何一种情况下要做的移动。战略集合是由玩家能够施行的纯战略所组成的集合。而混合战略是对每个纯战略分配一个机率而形成的战略。混合战略允许玩家随机选择一个纯战略。混合战略博弈均衡中要用概率计算因为每一种策略都是随机的达到某一概率时可以实现支付最优。因为机率是连续的所以即使战略集合是有限的也会有无限多个混合战略。 当然严格来说每个纯战略都是一个“退化”的混合战略某一特定纯战略的机率为 1其他的则为 0。 故“纯战略纳什均衡”即参与之中的所有玩家都玩纯战略而相应的“混合战略纳什均衡”之中至少有一位玩家玩混合战略。并不是每个赛局都会有纯战略纳什均衡例如“钱币问题”就只有混合战略纳什均衡而没有纯战略纳什均衡。不过还是有许多赛局有纯战略纳什均衡如协调赛局囚徒困境和猎鹿赛局。甚至有些赛局能同时有纯战略和混合战略均衡。
分析问题的一般方法 有效率的纳什均衡、无效率的纳什均衡
一些概念
1. 政府代价(price of anarchy, PoA)
在一个game中全局最优解一般来说不可能达到一般都是达到纳什均衡解均衡解可能不止一个也有好有坏那么为了反映这个纳什均衡的解的情况到底好不好好到什么程度坏到什么程度就有学者提出了POA和POS。 POA等于这个game中的全局最优解 比 纳什均衡解中的最小值也就是说POA越大意味着纳什均衡解中差的那一面越差。 POS等于这个game中的全局最优解 比 纳什均衡解中的最大值POS越接近1代表这个纳什均衡解好的那一面越好。
2. Pareto optimality
帕雷托最优Pareto optimality或帕雷托最适也称为帕雷托效率Pareto efficiency是指资源分配的一种理想状态假定固有的一群人和可分配的资源从一种分配状态到另一种状态的变化中在没有使任何人境况变坏的前提下使得至少一个人变得更好这就是帕累托改进或帕累托最优化。 是经济学中的重要概念并且在博弈论、工程学和社会科学中有着广泛的应用。 与其密切相关的另一个概念是帕雷托改善。 帕累托最优状态就是不可能再有更多的帕累托改进的余地换句话说帕累托改进是达到帕累托最优的路径和方法。 (从此以后非损人不能利己。)
纳什均衡案例
1囚徒困境
假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯对每一个犯罪嫌疑人警方给出的政策是如果一个犯罪嫌疑人坦白了罪行交出了赃物于是证据确凿两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白则两人各被判刑8年如果另一个犯罪嫌人没有坦白而是抵赖则以妨碍公务罪因已有证据表明其有罪再加刑2年而坦白者有功被减刑8年立即释放。如果两人都抵赖则警方因证据不足不能判两人的偷窃罪但可以私入民宅的罪名将两人各判入狱1年。 此时产生了两个嫌疑人之间的一场博弈 表中的数字表示AB各自的判刑结果。博弈论分析中一般都用这样的表来表示。 该案例显然最好的策略是双方都抵赖结果是大家都只被判1年。但是由于两人处于隔离的情况首先应该是从心理学的角度来看当事双方都会怀疑对方会出卖自己以求自保、其次才是亚当·斯密的理论假设每个人都是“理性的经济人”都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程假如他坦白如果我抵赖得坐10年监狱如果我坦白最多才8年假如他要是抵赖如果我也抵赖我就会被判一年如果我坦白就可以被释放而他会坐10年牢。综合以上几种情况考虑不管他坦白与否对我而言都是坦白了划算。两个人都会动这样的脑筋最终两个人都选择了坦白结果都被判8年刑期。
注亚当·斯密的理论“看不见的手”原理在市场经济中每一个人都从利己的目的出发而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论从利己目的出发结果损人不利己既不利己也不利他。
2智猪博弈
猪圈里有两头猪一头大猪一头小猪。猪圈的一边有个踏板每踩一下踏板在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果有一只猪去踩踏板另一只猪就有机会抢先吃到另一边落下的食物。当小猪踩动踏板时大猪会在小猪跑到食槽之前刚好吃光所有的食物若是大猪踩动了踏板则还有机会在小猪吃完落下的食物之前跑到食槽争吃到另一半残羹。 那么两只猪各会采取什么策略答案是小猪将选择“搭便车”策略也就是舒舒服服地等在食槽边而大猪则为一点残羹不知疲倦地奔忙于踏板和食槽之间。 原因何在因为小猪踩踏板将一无所获不踩踏板反而能吃上食物。对小猪而言无论大猪是否踩动踏板不踩踏板总是好的选择。反观大猪已明知小猪是不会去踩动踏板的自己亲自去踩踏板总比不踩强吧所以只好亲力亲为了。
3普通范式博弈
GOO公司和SAM公司是某手机产品生态的两大重量级参与者双方在产业链的不同位置上各司其职且关系暧昧有时也往往因商业利益和产品影响力的争夺而各怀异心。二者的收益也随着博弈的变化而不断更替。 上图表格模拟了两家公司的博弈现状双方各有两个可选策略“合作”与“背叛”格中的四组数据表示四个博弈结局的分数收益每组数据的第一个数字表示GOO公司的收益后一个数字表示SAM公司的收益。 博弈是同时进行的一方参与者必须站在对方的角度上来思考我方的策略选择以追求收益最大化。这在博弈论里称作Putting yourselves into other people’s shoes。 现在我们以GOO公司为第一人称视角来思考应对SAM公司的博弈策略。假如SAM公司选择合作那么我方也选择合作带来的收益是3而我方选择背叛带来的收益是5基于理性的收益最大化考虑我方应该选择背叛这叫严格优势策略假如SAM公司选择背叛那么我方选择合作带来的收益是-3而选择背叛带来的收益为-1为使损失降到最低我方应该选择背叛。最后GOO公司的分析结果是无论SAM公司选择合作还是背叛策略我方都必须选择背叛策略才能获得最大化的收益。 同理当SAM公司也以严格优势策略来应对GOO公司的策略选择时我们重复上述分析过程就能得出结论无论GOO公司选择合作还是背叛策略SAM公司都必须选择背叛策略才能获得最大化收益。 最后我们发现本次博弈的双方都采取了背叛策略各自的收益都为-1这是一个比较糟糕的结局尽管对任何一方来说都不是最糟糕的那种。这种局面就是著名的“囚徒困境”。 但是博弈的次数往往不止一次就像COO与SAM公司双方的商业往来也许会有很多机会。当二者经历了多次背叛策略的博弈之后发现公式上还有一个33收益的双赢局面这比-1-1的收益结果显然要好很多因此二者在之后的博弈过程中必然会尝试互建信任从而驱使双方都选择合作策略。 这里有一个理想化假设那就是假设双方都知道博弈次数是无限的话也就是说双方的商业往来是无止尽的那么二者的策略都将持续选择合作最终的博弈收益将定格在33这就是一个纳什均衡。既然博弈次数是无限的那么任何一方都没有理由选择背叛策略去冒险追求5点短暂收益而招致对方在下一轮博弈中的报复这种报复在博弈论里称作“以牙还牙”策略。 还有另一种假设情况是假使双方都知道博弈次数是有限的也许下一次博弈就是最后一次那么为了避免对方在最后一轮博弈中选择背叛策略而使我方遭受-3的收益损失于是双方都重新采取了背叛的策略选择最后的博弈结果又回到了-1-1这就形成了第二个纳什均衡。 由此可见随着次数博弈性质的变化纳什均衡点也并非唯一。
4饿狮博弈
假设有A、B、C、D、E、F六只狮子强弱从左到右依次排序和一只绵羊。假设狮子A吃掉绵羊后就会打盹午睡这时比A稍弱的狮子B就会趁机吃掉狮子A接着B也会午睡然后狮子C就会吃掉狮子B以此类推。那么问题来了狮子A敢不敢吃绵羊 为简化说明我们先给出此题的解法。该题须采用逆向分析法也就是从最弱的狮子F开始分析依次前推。假设狮子E睡着了狮子F敢不敢吃掉狮子E答案是肯定的因为在狮子F的后面已没有其它狮子所以狮子F可以放心地吃掉午睡中的狮子E。 继续前推既然狮子E睡着会被狮子F吃掉那么狮子E必然不敢吃在他前面睡着的狮子D。 再往前推既然狮子E不敢吃掉狮子D那么D则可以放心去吃午睡中的狮子C。依次前推得出C不吃B吃A不吃。所以答案是狮子A不敢吃掉绵羊。 推理结果如下图 但是如果我们在狮子F的后面增加了一只狮子G总数变成7只用逆向分析法按照上题步骤再推一次很容易得出结论狮子G吃狮子F不吃E吃D不吃C吃B不吃A吃。这次的答案变成了狮子A敢吃掉绵羊。 对比两次博弈我们发现狮子A敢不敢吃绵羊取决于狮子总数的奇偶性总数为奇数时A敢吃掉绵羊总数为偶数时A则不敢吃。因此总数为奇数和总数为偶数的狮群博弈结果形成了两个稳定的纳什均衡点。
5硬币正反
你正在图书馆枯坐一位陌生美女主动过来和你搭讪并要求和你一起玩个数学游戏。美女提议“让我们各自亮出硬币的一面或正或反。如果我们都是正面那么我给你3元如果我们都是反面我给你1元剩下的情况你给我2元就可以了。”那么该不该和这位姑娘玩这个游戏呢 每一种游戏依具其规则的不同会存在两种纳什均衡一种是纯策略纳什均衡也就是说玩家都能够采取固定的策略(比如一直出正面或者一直出反面)使得每人都赚得最多或亏得最少或者是混合策略纳什均衡而在这个游戏中便应该采用混合策略纳什均衡。 假设我们出正面的概率是x反面的概率是1-x美女出正面的概率是y反面的概率是1-y。为了使利益最大化应该在对手出正面或反面的时候我们的收益都相等由此列出方程就是 3x (-2)(1-x)(-2) * x 1*( 1-x )——解方程得x3/8同样美女的收益列方程-3y 2( 1-y) 2y (-1) * ( 1-y)——解得y也等于3/8。 于是我们就可以算美女每次的期望收益是 1-y(2x-(1-x)) y(-3x2(1-x)) 1/8元也就是说双方都采取最优策略的情况下平均每次美女赢1/8元。 其实只要美女采取了(3/8,5/8)这个方案不论你再采用什么方案都是不能改变局面的。如果全部出正面每次的期望收益是 (333-2-2-2-2-2)/8-1/8元如果全部出反面每次的期望收益也是(-2-2-211111)/8-1/8元。比如你用完全随机1/21/2策略收益是1/2(3/8 * 3 5/8 * (-20)) 1/2(3/8 * (-2) 5/8 * 1) -1/8实际上不论你用什么策略你的收益都是-1/8也就是说随便玩一种策略你都是在纳什均衡状态中的所以这个把戏你随便怎么玩都是亏的。
以下一段补充说明 这个例子中是没有纯战略纳什均衡的因为只出一种策略肯定有一方要亏钱所以并不是其均衡状态明明只要换一边就可以赚钱了所以不是最佳策略而混合纳什均衡是纯在的事实上Nash告诉我们“每个参与者都只有有限种策略选择、并允许混合策略的前提下纳什均衡一定存在”如果美女出(3/8,5/8)这个方案另一边任何玩法都是期望收益一样的也就满足了纳什均衡的条件。
Algorithms for Finding the NE
For a general N-player game, finding the set of NEs is not possible in polynomial time! Unless the game has a certain structure Some existing algorithms Fictitious play (based on empirical probabilities)Iterative algorithms (converge for certain classes of games)Best response algorithms Popular in some games (continuous kernel games for example) Useful Reference D. Fundenberg and D. Levine, The theory of learning in games, the MIT press, 1998. ———————————————— 版权声明本文部分转载自 作者CSDN博主「大饼博士X」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://blog.csdn.net/xbinworld/article/details/50932559 作者匿名用户 链接https://www.zhihu.com/question/58053187/answer/537695433 来源知乎 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
