3-混合策略的纳什均衡.doc

博弈论教学/混合策略的纳什均衡出自 MyKnowledgeBase＜博弈论教学Bread crumbs: Main Page ＞博弈论教学/混合策略的纳什均衡目录■ 1复习■ 2 混合策略(Mixed strategy)■ 2.1 举例 /Example■ 2.2概念■ 2.3纯策略和混合策略■ 2.4混合策略的争议■ 3混合策略的纳什均衡■ 3.1基本概念■ 3.2混合策略纳什均衡的存在性 /纳什定理■ 3.3学术争议与批评■4混合策略纳什均衡举例■ 4.1 社会福利博弈 Social Welfare Game■ 4.1.1博弈分析(方法1:收益无差异)■ 4.1.2博弈分析(方法2:图形分析法)■ 4.1.3博弈分析(方法3 :导数(Derivative)极值法)■ 4.2普通例子■ 4.3 审计博弈(Tax Game)■ 4.4激励的悖论[5]■ 4.5求解纳什均衡的一般方法■ 5多重纳什均衡■ 5.1多重纳什均衡举例■ 5.1.1夫妻之争■ 5.1.2制式问题■ 5.1.3市场机会博弈■ 5.2多重纳什均衡分析■ 5.2.1 帕累托上策均衡(Pareto Dominated Equilibrium )■ 5.2.1.1 帕累托最优 Pareto optimality■ 5.2.1.2 帕累托上策均衡(Pareto Dominated Equilibrium)■ 5.2.1.3举例分析■ 5.2.2 风险上策均衡(Risk-dominant Equilibrium)■ 5.2.3 聚点均衡(Focal Points Equilibrium)■ 5.2.4相关均衡■ 5.2.5 抗共谋均衡(coalition-proof Nash equilibrium)■ 6纳什均衡的意义■ 7作业■ 8参考文献1复习1. 博弈局势的构造 (How to make the game matrix)2. 基本方法：上策均衡(Dominant equilibrium)、严格下策消去法(Iterated Elimination of Strictly Dominated Strategies)、划线法、箭头法3. 纳什均衡(纯策略) (Nash Equilibrium)2 混合策略(Mixed strategy)2.1 举例 /Example猜硬币博弈正面反面正面1-1-1，丄反面-1，11-1■猜硬币博弈：博弈情景的描述见英文部分。

支付矩阵见 右侧这个例子说明不存在纯策略的纳什均衡但可能存 在混合策略的纳什均衡(博弈双方的概率为 0.5)■ ( 1)不存在前面定义的纳什均衡策略组合■ (2)关键是不能让对方猜到自己策略 ■这类博弈很多，引出混合策略纳什均衡概念2.2概念■混合策略:与纯策略(pure strategy)相对应■混合策略：在博弈■'; ■■ ■ ■■ ■■<■■■■ I ■ 中，博弈方卫的策略空间为% <儿：宀「..、：.〔，贝V博弈方i以概率分布：：：,； In：小 越；随机在其k个可 选策略中选择的 策略”称为一个 混合策略”其中1,对j三1・2二川 都成立，且；-.| ! ■ ,： I o■混合策略扩展博弈：博弈方在混合策略的策略空间(概率分布空间)的选择看作 一个博弈，就是原博弈的 混合策略扩展博弈”■混合策略：在策略型博弈中，局中人的混合策略是在该局中人的行动集合上的一 个概率分布■在完全信息博弈中，如果在每个给定信息下，只能选择一种特定策略，这个策略为纯策 略(pure strategy)o如果在每个给定信息下只以某种概率选择不同策略，称为混合策 略(mixed strategy)混合策略是纯策略在空间上的概率分布，纯策略是混合策略的特 例。

纯策略的收益可以用效用表示，混合策略的收益只能以预期效用表示2.3纯策略和混合策略纯策略提供给参与人要如何进行赛局的一个完整的定义特别地是，纯策略决定在任何一种 情况下要做的行动策略集合是由玩家能够施行的纯策略所组成的集合混合策略是对每个纯策略分配一个概率而形成的策略混合策略允许参与人随机选择一个纯 策略因为概率是连续的，所以即使策略集合是有限的，也会有无限多个混合策略当然，严格来说，每个纯策略都是一个「退化」的混合策略，某一特定纯策略的概率为 其他的则为0完全混合策略是个混合策略，其对每个纯策略都分配了一个不为零的概率完全混合策略 对如颤手完全均衡之类的均衡精细很重要)2.4在1980年代时，混合策略的概念曾遭受很严重的攻击，被认为是 直觉地有问题”］混合策略的核心-随机缺乏行为的支持，人们很少会凭运气做决定此一行为问题在认知的难题上 显得更加严重，因为没有人能够在没有随机数发生器的帮助之下做出随机的决定来在阿里尔？鲁宾斯坦的一篇论文中 ⑵，他描述了另一个了解此一概念的方法首先，基于纯化 理论［3］，并假设混合策略的解释只是反应了对玩家信息和决策过程认识的缺乏明显地，随 机决定被认为是不明确、利益无关的外部因素的结果。

然而，一个由不明确的因素决定的结 果很难令人感到满意第二个解释是，想象有许多组玩家在进行赛局，每组玩家都选择一个纯策略，且利益是依赖 玩家们选择策略的百分比来决定的因此，混合策略便表示是每一组玩家所选择的纯策略的 分布然而，这对玩家都是单独的一组时，提不出什么合理的解释之后，奥曼和布兰登博格 ［4］重新将纳什均衡解释成是一种「信念」的均衡，而不是行动的 例如，在剪刀、石头、布里，信念的均衡即每个玩家都 相信”对方会平均地施行每一个策略然而，此一解释弱化了纳什均衡的预测能力，因为在此均衡里， 确实”地施行石头的纯策略也是可能的直至今日，学者们对混合策略的结果依然是很矛盾的混合策略依然广泛地被应用不存在纯 策略均衡的赛局中，以提供其一个纳什均衡，但这些模型都无法说清楚为何且如何玩家能够 随机化他们的决定混合策略不像纯策略那样能直观明确地说明一次博弈中各参与人的具体选择和博弈的确定结 果但混合策略可以表明参与人决策的具体方式以及平均意义上的收益(期望效用或者期望 收益)3.1基本概念■定义：在博弈G =_ -SnH/l 也｝中，假设/是一个混合策略，如果成立，则称，，是一个混合策略纳什均衡( Mixed Strategy Nash Equilibrium )。

■如果对于局中人 及其的每一个混合策略"，局中人 关于“的期望盈利至少与局中人•关 于， 的期望盈利一样大，即 汕 u 则称混合策略组合pa是这个博弈的一个纳什均衡■注意：在纳什均衡下，没有参与人有积极性单独偏离或改变该策略或策略组合 ■在策略型博弈中，局中人的混合策略是在该局中人的行动集合上的一个概率分 布3.2混合策略纳什均衡的存在性'瞳■/纳什定理■几个均衡之间的关系：如图所示 The Relatio nship amo ng four equilibriums:#H豊费碼*=匸 _ "~L J_ 二 T—MH i^rteh 內■”上集均宵J'."^*"18——: 二 “ R _— —*~1_上■均■■纳什定理：在一个由 个博弈方构成的博弈 中，如果■'-■是有限的，且对每个局中人i的战略空I可J都是有限集(对. ，)，则该博弈至少存在一个纳什均衡(纯策略或者混合策略)■纳什均衡的普遍存在性正是纳什均衡成为非合作博弈分析核心概念的根本原因之一3.3学术争议与批评第一，(Nash)的关于非合作(non-cooperative )博弈论的平衡不动点解(equilibrium/fixpoint )学术证明是非构造性的( non-constructive )，就是说纳什用角谷静夫的不动点定理(Kakutani fixed point theorem )证明了平衡不动点解是存在的，但却不能指出 以什么构造算法如何去达到这个平衡不动点解。

这种非构造性的发现对现实生活里的博弈的 作用是有限的，即使知道平衡不动点解存在，在很多情况下卻找不到，因此仍不能解决问 题第二，纳什的非合作(non-cooperative )博弈论模型仅仅是突破了博弈论中的一个局限一个 更大的局限是，博弈论面对的往往是由几十亿节点的庞大对象构成的社会、经济等复杂行 为，但冯诺伊曼(Von Neumann)和纳什的研究是针对两三个节点的小规模博弈论(有人称 之为 tiny-scale toy case )这个假设的不完善处，可能比假设大家都是合作的( cooperative)更严重因为在经济学里，一个庞大社会里的人极不可能全部都是合作的，非合作的情况通常在庞大对象的情形中 更普遍，而在两三个节点的小规模经济中倒反而影响较小既然改了合作前提为非合作前 提，却仍然停留在两三个节点的小规模博弈论中，这是一个不可忽视的缺陷 MIT的一位计算机科学博士生的博士论文 (PDF http://people.csail.mit.edu/costis/thesis.pdf ) 获得 2008年度美国计算机协会学位论文奖一一认为经济学家的推测是错误的，找到纳什均衡点是几乎不可能的事。

目前担任MIT电机工程和计算机科学系助理教授的 Constantinos Daskalakis与UC伯克利的Christos Papadimitriou、英国利物浦大学的 Paul Goldberg合作，证明对某些博弈来说， 穷全世界所有计算机之力，在整个宇宙寿命的时间内也计算不出纳什均衡点 Daskalakis相信，计算机找不到，人类也不可能找到纳什均衡属于 NP问题，Daskalakis证明它属于NP问题的一个子集，不是通常认为的 NP-完全问题，而是PPAD-完全问题这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展不過在同一篇論文裡， Daskalakis也指出，在參與者匿名的情況下，則僅需多項式時間即可逼近纳什均衡4混合策略纳什均衡举例4.1 社会福利博弈 Social Welfare Game博弈模型：政府(Government)想救济(succour)流浪汉(rover)，但前提是你要找工作(find a job )，但又不能区分每个流浪汉是否在找工作，因此只能统一对待流浪汉只有在政府不救济时才会找工作政府与流浪汉之间关于社会福利的博弈，其盈利矩阵如下图所示，求该博弈的混 合策略纳什均衡解。

找工作 流浪救济3,2-1,3不救济-1,10,0社会福利博弈4.1.1博弈分析（方法1:收益无差异裳）1. 政府的最优策略：政府不可以选择救济或不救济的纯策略，因为流浪汉相应的策略使政府的效用降低政府应以某一概率选择救济 （P）或不救济（1-P），使流浪汉找工作和游荡的预期效用相同p X 2+（1-p） X 1 = p X, 3可得pp=0.5X 0当政府救济与否的概率都是 0.5时（混合策略），则流浪汉找工作的预期效用：0.5 X 2+0.5 X；游荡的预期效用： 0.5 X 3+0.5 X； 0=1.5流浪汉找工作或游荡（纯策略），或者以任何概率选择找工作和游荡（混合策略）的预 期效用都一样这是政府的最优策略因为，如果救济的概率大于不救济的概率，流浪汉游荡的预期效 用大于找工作的预期效用，流浪汉会选择游荡（纯策略），政府也就要选择不救济（纯 策略），流浪汉又找工作，政府又救济 ……，不。