博弈论第讲精.ppt

博弈论第讲博弈论第讲第1页，本讲稿共59页2q 局中人2 L R U局中人1 M D5，10，21，34，14，22，3No dominant strategies and dominated strategies,what about the result?第2页，本讲稿共59页Best Response(BR)3U does best against L;M does best against R第3页，本讲稿共59页L、R概率为概率为0.5时时Expected payoff of U：2.5Expected payoff of M：2.5Expected payoff of D：3此时，D does best。4第4页，本讲稿共59页假定假定1认为认为2选择选择r的概率为的概率为p(r)，则则1选选U、M、D的期望收益分别为的期望收益分别为 E u1(U，p(r)=(1-p(r)5+p(r)0 E u1(M，p(r)=(1-p(r)1+p(r)2 E u1(D，p(r)=(1-p(r)4+p(r)25第5页，本讲稿共59页6）第6页，本讲稿共59页BR是期望收益最大时的反应是期望收益最大时的反应q图中 x=1/3，y=3/5q由图可知，p(r)1/3时，1的最佳反应是选U；q1/3p(r)3/5时，1的最佳反应是选D；qp(r)3/5时，1的最佳反应是选M。7第7页，本讲稿共59页8第8页，本讲稿共59页点球博弈点球博弈9第9页，本讲稿共59页10第10页，本讲稿共59页Partnership Game2 人拥有一家公司，每人分享利润的一半每人的策略:精力投入水平，Si=0,4利润：4S1+S2+b S1 S2 b=0,1/4U1=2S1+S2+b S1 S2-S1 S1U2=2S1+S2+b S1 S2 S2 S211第11页，本讲稿共59页参与人的参与人的BR是什么？是什么？12第12页，本讲稿共59页13b=1/4时第13页，本讲稿共59页14第14页，本讲稿共59页纳什均衡纳什均衡15第15页，本讲稿共59页16Nash EquilibriumThe action profile s*is a Nash Equilibrium if,for every player i and every action si of player i,s*is at least as good as according to player is preferences as the the action profile(si*,s-i*)in which player i chooses si*while every other player choose s-i*.Equivalently,for every player i,ui(s*)ui(si,s-i*),For every action of player i第16页，本讲稿共59页17Definition In the n-player game G=S1,Sn;u1,un,the strategies profile(s1*,sn*)are a Nash equilibrium if,for each player i,si*is (at least tied for（至少不劣于）（至少不劣于）)player is best response to the strategies specified for the n-1 other players,(s1*,sn-1*,sn+1*,sn*):ui(s1*,sn-1*,si*,sn+1*,sn*)ui(s1*,sn-1*,si ,sn+1*,sn*)(NE)第17页，本讲稿共59页18 for every feasible strategy si in Si;That is,si*solves max ui(s1*,sn-1*,si,sn+1*,sn*).siSi 上述均衡概念是上述均衡概念是1951年由数学家约翰年由数学家约翰纳什纳什（John Nash）首先提出的，称为纳什均衡。）首先提出的，称为纳什均衡。第18页，本讲稿共59页19纳什均衡纳什均衡(Nash Equilibrium)q定义。对于一个策略式表述的博弈G=N,Si,ui,iN。称策略组合s*=(s1,si,sn)是一个纳什均衡，如果对于每一个i N,si*是给定其他参与人选择s-i*=s1*,si-1*,si+1*,sn*q情况下参与人i的最优策略（经济理性策略），即：ui(si*,s-i*)ui(si,s-i*),对于任意的 siSi,任意的 iN均成立。第19页，本讲稿共59页20纳什均衡的通俗定义纳什均衡的通俗定义 纳什均衡是一种策略组合，给定对手的策略，每个参与人选择自己的最优策略。第20页，本讲稿共59页21 1 If game theory is to provide a unique solution to a game-theoretic problem then the solution must be a Nash equilibrium,in the following sense.Suppose that game theory makes a unique prediction about the strategy each player will choose.In order for this prediction to be correct,it is necessary that each player be willing to choose the strategy predicted by the theory.第21页，本讲稿共59页22Thus each players predicted strategy must be that players best response to the strategies of the other players.Such a prediction could be called strategically stable or self-enforcing,because no single player wants to deviate from his or her Predicted strategy.We will call such a prediction a Nash equilibrium.-Robert Gibbons第22页，本讲稿共59页232 一种稳定的策略组合：当所有参与人一种稳定的策略组合：当所有参与人的选择公开以后，每个人都满意自己作的选择公开以后，每个人都满意自己作出了正确的选择；没有人能得到更好的出了正确的选择；没有人能得到更好的结果了。在博弈论中这种结果被称为结果了。在博弈论中这种结果被称为NE。第23页，本讲稿共59页243 NE的哲学含义：的哲学含义：n个参与人在博弈之前个参与人在博弈之前协商达成一个协议，规定每一个参与人选择协商达成一个协议，规定每一个参与人选择一个特定的策略。一个特定的策略。问题是，给定其他参与人都遵守该协议，在问题是，给定其他参与人都遵守该协议，在没有外在强制的情况下，是否有人选择不遵没有外在强制的情况下，是否有人选择不遵守？守？第24页，本讲稿共59页25只有当遵守协议带来的效用大于不遵守时，参与人才只有当遵守协议带来的效用大于不遵守时，参与人才会遵守。如果没有任何参与人有积极性不遵守这个协会遵守。如果没有任何参与人有积极性不遵守这个协议，该协议议，该协议是可以自动实施的（是可以自动实施的（self-enforcing），），构成纳什均衡；否则，就不是纳什均衡。构成纳什均衡；否则，就不是纳什均衡。第25页，本讲稿共59页26 4 纳什均衡是一种策略组合，每个参与纳什均衡是一种策略组合，每个参与人的策略是对其他参与人策略的最优反应。人的策略是对其他参与人策略的最优反应。纳什均衡是博弈将会如何进行的纳什均衡是博弈将会如何进行的“一致一致”（consistent）预测。如果所有参与人预测特）预测。如果所有参与人预测特定纳什均衡会出现，那么没有参与人有动力定纳什均衡会出现，那么没有参与人有动力采用与均衡不同的行动。采用与均衡不同的行动。第26页，本讲稿共59页27纳什均衡（纳什均衡（也只有纳什均衡也只有纳什均衡）一致预测性。）一致预测性。任何非纳什均衡的出现意味着至少有一个参与人任何非纳什均衡的出现意味着至少有一个参与人“犯了犯了错错”，或者是对对手行动的预测上犯了错，或者是（给，或者是对对手行动的预测上犯了错，或者是（给定那种预测）在最大化自己的收益时犯了错。定那种预测）在最大化自己的收益时犯了错。(Jean Tirole)第27页，本讲稿共59页28纳什均衡的一致预测性纳什均衡的一致预测性q如果所有参与方都预测一个特定的博弈结果会出现，那么所有的参与方都不会利用该预测或者这种预测能力来选择与预测结果不一致的策略，即没有哪个参与方有偏离这个预测结果的愿望，因此这个预测结果最终就真会成为博弈的结果。q“一致”的意义在于各博弈方的实际行为选择与他们的预测一致。第28页，本讲稿共59页q假设各参与方预测的策略组合相同，以及各参与方都是完全理性的，也就是不会犯错误的情况下，不可能预测任何非纳什均衡是博弈的结果。29第29页，本讲稿共59页30纳什均衡的立法意义纳什均衡的立法意义q纳什均衡是一种稳定局面。给定别人遵守协议的情况下，没有人有积极性偏离协议规定。如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个人会违背这个协议，不满足纳什均衡要求的协议是没有意义的。第30页，本讲稿共59页q立法的目标与其实施的结果要一致，必须使得参与博弈的各方达到纳什均衡。否则，立法就仅仅是正式或官方规则，而实际有效的支配人们的是潜规则。31纳什均衡的立法意义纳什均衡的立法意义第31页，本讲稿共59页32纳什均衡的立法意义纳什均衡的立法意义q潜规则的要害是三方博弈：私下达成默契的双方，蒙骗正式制度和公正原则的代表。q预测是博弈分析最基本的目的之一。q纳什均衡的一致预测性质是其预测能力的基本保证。第32页，本讲稿共59页33纳什均衡应用的局限性纳什均衡应用的局限性q我们对纳什均衡应用的广泛性和有效性不能过分夸大，尽管纳什均衡非常重要，但不是说学到了这种分析方法你就能预测所有博弈的结果。q纳什均衡分析仅仅保证个体理性的智能人的博弈结果是唯一纯策略纳什均衡时的预测。纳什均衡分析并不能保证对所有博弈的结果都作出准确的预测。第33页，本讲稿共59页34纳什均衡应用的局限性纳什均衡应用的局限性 现实中的博弈可能是下面三种情况之一：q有许多博弈不存在纯策略纳什均衡；q有些博弈是多重纳什均衡；q博弈方可能是集体理性或有限理性。第34页，本讲稿共59页35第35页，本讲稿共59页36Existence of Nash Equilibrium*Nash在在1950年证明：任何年证明：任何有限博弈有限博弈，都至，都至少存在一个少存在一个NE。Theorem(Nash 1950):In the n-player normal-form game G=S1,Sn;u1,un,if n is finite and Si is finite for every i then there exists at least one Nash equilibrium,possibly involving mixed strategies.第36页，本讲稿共59页37Wilson（1971）证明，几乎所有有限博）证明，几乎所有有限博弈，都存在有限奇数个弈，都存在有限奇数个NE，包括纯策，包括纯策略略NE和混合策略和混合策略NE。Oddness Theorem第37页，本讲稿共59页38q纳什于纳什于1950年提出并证明了纳什定理年提出并证明了纳什定理q纳什定理的主要内容为：在一个有纳什定理的主要内容为：在一个有n个个参与人的策略式博弈参与人的策略式博弈G=S1,Sn;u1,un中，如果中，如果n是有限的，且是有限的，且Si是有是有限集（限集（i=1,n），则该博弈至少存在），则该博弈至少存在一个纳什均衡（在混合策略意义下）一个纳什均衡（在混合策略意义下）纳什定理纳什定理第38页，本讲稿共59页39纳什定理的一些说明纳什定理的一些说明q纳什定理的证明要用到不动点定理。纳什定理的证明要用到不动点定理。q所谓不动点定理，是指所谓不动点定理，是指v一个定义在一个定义在X X上的函数上的函数f(x)，v集合集合X是非空的、闭的、有界的和凸的是非空的、闭的、有界的和凸的v函数函数f是连续的是连续的v则至少存在一个则至少存在一个x，使得，使得f(x)=x,x 被称为不被称为不动点动点第39页，本讲稿共59页40纳什定理的一些说明纳什定理的一些说明q运用不动点定理证明纳什定理的主要步运用不动点定理证明纳什定理的主要步骤是骤是v设计一个策略组合空间上的一个映射，说设计一个策略组合空间上的一个映射，说明该映射的任何不动点都是一个纳什均衡明该映射的任何不动点都是一个纳什均衡v使用不动点定理证明这个映射一定存在一使用不动点定理证明这个映射一定存在一个不动点个不动点第40页，本讲稿共59页41不动点不动点q什么是不动点呢？想像有一个容器，里面充满了大量的小球，现在用一个勺子任意搅拌这容器里的小球，搅拌过后，每一个小球都重新占据了容器中的一个位置，如果某个小球的新位置和旧位置重合，那么这个小球就是一个不动点。数学里面有一类经典的定理，说的是这样的不动点总是存在的。无论你怎么搅拌，总有这样的不动点小球，以不变应万变，终点又回到起点！第41页，本讲稿共59页42纳什定理的一些说明纳什定理的一些说明q映射选择的是映射选择的是n人最优反应对应人最优反应对应q其含义是，对于任意一个混合策略组合其含义是，对于任意一个混合策略组合(p1,pn)，对于每一个参与人，对于每一个参与人i，求出求出I针对其他参与人混合策略针对其他参与人混合策略(p1,pi-1,pi+1,pn)的最优反应，然后构建的最优反应，然后构建n个参个参与人最优反应对应的卡氏积。与人最优反应对应的卡氏积。q一个最优混合策略组合就是这一对应集一个最优混合策略组合就是这一对应集的不动点。的不动点。第42页，本讲稿共59页43纳什定理的一些说明纳什定理的一些说明q因此只要证明前面的最优反应对应满足因此只要证明前面的最优反应对应满足不动点定理条件就可以了。不动点定理条件就可以了。第43页，本讲稿共59页44纳什均衡纳什均衡(Nash Equilibrium)q纳什均衡、占优均衡、重复剔除严劣策略均衡的关系v定理a 每一个占优均衡、重复剔除严劣策略均衡一定是纳什均衡，但反过来不一定成立；v定理b 纳什均衡一定不能通过重复剔除严劣策略方法剔除。v下面对上述定理进行简要证明第44页，本讲稿共59页45两个定理的证明两个定理的证明q首先证明定理b：纳什均衡一定不能通过重复剔除严劣策略方法剔除。记纳什均衡时的策略组合为s*=(s1*,si*,sn*)用反证法q假定纳什均衡在重复剔除严劣策略均衡中被剔除掉，不失一般性，假设s1*是s*中被首先剔除的策略，q则在S1中，一定存在一个尚未被剔除的策略s1，相对参与人1而言，严格优于s1*第45页，本讲稿共59页46两个定理的证明两个定理的证明q于是根据重复剔除严劣策略定义，对于此时所有尚未被剔除的其他参与人的任意一个策略组合s-1=(s2,si,sn)，均成立qui(s1,s-1)ui(s1*,s-1)第46页，本讲稿共59页47两个定理的证明两个定理的证明q由于前面分析中假设策略s1*是s*=(s1*,si*,sn*)中首先被剔除的策略，因此在s1*被剔除的时候，s2*,si*,sn*尚未被剔除，自然满足式，这显然与s*是NE矛盾第47页，本讲稿共59页48q下面开始证明定理a:重复剔除严劣策略均衡一定是纳什均衡(反证法)q假设重复剔除严劣策略后，只剩下唯一的一个策略组合s*=(s1*,si*,sn*),但却不是NE。q则存在一个s1 S1，使得下列事实成立u1(s1*,si*,sn*)u1(s1,si*,sn*)q但由于(s1,si*,sn*)在中间过程中被剔除，而s*是被保留下来的唯一一个策略组合。两个定理的证明两个定理的证明第48页，本讲稿共59页49q按照严劣策略的定义，有u1(s1*,si*,sn*)u1(s1,si*,sn*)q比较左右两式，可以得出矛盾两个定理的证明两个定理的证明第49页，本讲稿共59页50划线法划线法q先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳策略总是存在的，不过不一定唯一），然后在此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。这就是划线法。第50页，本讲稿共59页51 参 与 人 B参与人ALCRU0,44,05,3M4,00,45,3D3,53,56,6图图1-8第51页，本讲稿共59页52箭头法箭头法箭头法对于理解博弈关系很有好处,是寻找相对稳定性策略组合的分析方法。对博弈中的每个策略组合进行分析，考察在每个策略组合处各个参与方能否通过改变自己的策略而增加得益。如能，则从所分析的策略组合对应的得益数组引一箭头到改变策略后策略组合对应的得益数组。最后综合对每个策略组合的分析情况，形成对博弈结果的判断。划线法和箭头法的结果是一致的，可以相互替代。第52页，本讲稿共59页53小鸡博弈（小鸡博弈（the game of chicken）汤姆和吉米进行勇气比赛：两人分别从一条汤姆和吉米进行勇气比赛：两人分别从一条独木桥的两端冲向对方，谁退却谁就是独木桥的两端冲向对方，谁退却谁就是“小小鸡鸡”。如果两个人都向前冲，则两败俱伤，收益均如果两个人都向前冲，则两败俱伤，收益均为为-2；如果一个勇进一个退却，勇进者收益为如果一个勇进一个退却，勇进者收益为4，退却者为退却者为-1；若两人同时退却，收益均为若两人同时退却，收益均为0.第53页，本讲稿共59页54 吉米吉米 退却退却 勇进勇进 退却退却 汤姆汤姆 勇进勇进0，0-1，44，-1-2，-2有两个均衡。实际会怎样？有两个均衡。实际会怎样？第54页，本讲稿共59页55 局中人2 L C R U局中人1 M D4，35，16，22，18，43，63，09，62，8练习练习1重复剔除严劣策略求解重复剔除严劣策略求解博弈的均衡博弈的均衡 第55页，本讲稿共59页56q 局中人2 L C R U局中人1 M D1，22，11，02，10，10，00，10，01，2练习练习2 划线法求解博弈的均衡划线法求解博弈的均衡 第56页，本讲稿共59页57q 局中人2 L C R U局中人1 M D4，35，16，22，18，43，63，09，62，8练习练习2 划线法求解博弈的均衡划线法求解博弈的均衡 第57页，本讲稿共59页58练习练习2BALCDT1,0 1,3 0,1D0,4 0,2 2,3BALCRT2,0 1,1 4,2M3,4 1,2 2,3D1,3 0,2 3,0第58页，本讲稿共59页59练习练习3q箭头法求解博弈的均衡 猎人2 猎鹿 猎兔 猎鹿猎人1 猎兔5，50，22，02，2第59页，本讲稿共59页