博弈论第讲精品课件

1、博弈论第讲第1页，共59页，2022年，5月20日，3点31分，星期二2 局中人2 L R U局中人1 M D5，10，21，34，14，22，3No dominant strategies and dominated strategies , what about the result?第2页，共59页，2022年，5月20日，3点31分，星期二Best Response (BR)3U does best against L;M does best against R第3页，共59页，2022年，5月20日，3点31分，星期二L、R概率为0.5时Expected payoff of U：2.

2、5Expected payoff of M：2.5Expected payoff of D：3此时，D does best。4第4页，共59页，2022年，5月20日，3点31分，星期二假定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页，2022年，5月20日，3点31分，星期二6）第6页，共59页，2022年，5月20日，3点31分，星期二BR是期望收益最大时的反应图中 x=1/3，y=3/5由图

3、可知，p(r)1/3时，1的最佳反应是选U；1/3p(r)3/5时，1的最佳反应是选D；p(r) 3/5时，1的最佳反应是选M。7第7页，共59页，2022年，5月20日，3点31分，星期二8第8页，共59页，2022年，5月20日，3点31分，星期二点球博弈9第9页，共59页，2022年，5月20日，3点31分，星期二10第10页，共59页，2022年，5月20日，3点31分，星期二Partnership Game2 人拥有一家公司，每人分享利润的一半每人的策略: 精力投入水平，Si=0,4利润：4S1 + S2 +b S1 S2 b=0,1/4U1= 2S1 + S2 +b S1 S2 -

4、 S1 S1U2= 2S1 + S2 +b S1 S2 S2 S211第11页，共59页，2022年，5月20日，3点31分，星期二参与人的BR是什么？12第12页，共59页，2022年，5月20日，3点31分，星期二13b=1/4时第13页，共59页，2022年，5月20日，3点31分，星期二14第14页，共59页，2022年，5月20日，3点31分，星期二纳什均衡15第15页，共59页，2022年，5月20日，3点31分，星期二16Nash EquilibriumThe action profile s* is a Nash Equilibrium if, for every player

5、 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页，2022

6、年，5月20日，3点31分，星期二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* ): u

7、i( s1*, sn-1* , si* , sn+1* , sn* ) ui( s1*, sn-1* , si , sn+1* , sn* ) (NE) 第17页，共59页，2022年，5月20日，3点31分，星期二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页，2022年，5月20日，3点31分，星期二19纳什均衡(Nash

8、 Equilibrium)定义。对于一个策略式表述的博弈G= N,Si, ui, iN。称策略组合s*=(s1, si, , sn)是一个纳什均衡，如果对于每一个i N, si*是给定其他参与人选择s-i*=s1*, ,si-1*, si+1*, ,sn*情况下参与人i的最优策略（经济理性策略），即：ui(si*, s-i*) ui(si, s-i*), 对于任意的 siSi ,任意的 iN均成立。第19页，共59页，2022年，5月20日，3点31分，星期二20纳什均衡的通俗定义 纳什均衡是一种策略组合，给定对手的策略，每个参与人选择自己的最优策略。第20页，共59页，2022年，5月20日

9、，3点31分，星期二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

10、 is necessary that each player be willing to choose the strategy predicted by the theory. 第21页，共59页，2022年，5月20日，3点31分，星期二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-en

11、forcing, 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页，2022年，5月20日，3点31分，星期二232 一种稳定的策略组合：当所有参与人的选择公开以后，每个人都满意自己作出了正确的选择；没有人能得到更好的结果了。在博弈论中这种结果被称为NE。第23页，共59页，2022年，5月20日，3点31分，星期二243 NE的哲学含义

12、：n个参与人在博弈之前协商达成一个协议，规定每一个参与人选择一个特定的策略。问题是，给定其他参与人都遵守该协议，在没有外在强制的情况下，是否有人选择不遵守？第24页，共59页，2022年，5月20日，3点31分，星期二25只有当遵守协议带来的效用大于不遵守时，参与人才会遵守。如果没有任何参与人有积极性不遵守这个协议，该协议是可以自动实施的（self-enforcing），构成纳什均衡；否则，就不是纳什均衡。第25页，共59页，2022年，5月20日，3点31分，星期二26 4 纳什均衡是一种策略组合，每个参与人的策略是对其他参与人策略的最优反应。 纳什均衡是博弈将会如何进行的“一致”（cons

13、istent）预测。如果所有参与人预测特定纳什均衡会出现，那么没有参与人有动力采用与均衡不同的行动。第26页，共59页，2022年，5月20日，3点31分，星期二27纳什均衡（也只有纳什均衡）一致预测性。任何非纳什均衡的出现意味着至少有一个参与人“犯了错”，或者是对对手行动的预测上犯了错，或者是（给定那种预测）在最大化自己的收益时犯了错。 (Jean Tirole)第27页，共59页，2022年，5月20日，3点31分，星期二28纳什均衡的一致预测性如果所有参与方都预测一个特定的博弈结果会出现，那么所有的参与方都不会利用该预测或者这种预测能力来选择与预测结果不一致的策略，即没有哪个参与方有偏离

14、这个预测结果的愿望，因此这个预测结果最终就真会成为博弈的结果。“一致”的意义在于各博弈方的实际行为选择与他们的预测一致。第28页，共59页，2022年，5月20日，3点31分，星期二假设各参与方预测的策略组合相同，以及各参与方都是完全理性的，也就是不会犯错误的情况下，不可能预测任何非纳什均衡是博弈的结果。29第29页，共59页，2022年，5月20日，3点31分，星期二30纳什均衡的立法意义纳什均衡是一种稳定局面。给定别人遵守协议的情况下，没有人有积极性偏离协议规定。如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个人会违背这个协议，不满足纳什均衡要求的协议是没有意义的。第30页，

15、共59页，2022年，5月20日，3点31分，星期二立法的目标与其实施的结果要一致，必须使得参与博弈的各方达到纳什均衡。否则，立法就仅仅是正式或官方规则，而实际有效的支配人们的是潜规则。31纳什均衡的立法意义第31页，共59页，2022年，5月20日，3点31分，星期二32纳什均衡的立法意义潜规则的要害是三方博弈：私下达成默契的双方，蒙骗正式制度和公正原则的代表。预测是博弈分析最基本的目的之一。纳什均衡的一致预测性质是其预测能力的基本保证。第32页，共59页，2022年，5月20日，3点31分，星期二33纳什均衡应用的局限性我们对纳什均衡应用的广泛性和有效性不能过分夸大，尽管纳什均衡非常重要，

16、但不是说学到了这种分析方法你就能预测所有博弈的结果。纳什均衡分析仅仅保证个体理性的智能人的博弈结果是唯一纯策略纳什均衡时的预测。纳什均衡分析并不能保证对所有博弈的结果都作出准确的预测。第33页，共59页，2022年，5月20日，3点31分，星期二34纳什均衡应用的局限性 现实中的博弈可能是下面三种情况之一：有许多博弈不存在纯策略纳什均衡；有些博弈是多重纳什均衡；博弈方可能是集体理性或有限理性。第34页，共59页，2022年，5月20日，3点31分，星期二35第35页，共59页，2022年，5月20日，3点31分，星期二36Existence of Nash Equilibrium*Nash在1

17、950年证明：任何有限博弈，都至少存在一个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页，2022年，5月20日，3点31分，星期二37Wilson（1971）证明，几乎所有有限博弈，都存在有限奇数个NE，包括纯策

18、略NE和混合策略NE。Oddness Theorem第37页，共59页，2022年，5月20日，3点31分，星期二38纳什于1950年提出并证明了纳什定理纳什定理的主要内容为：在一个有n个参与人的策略式博弈G=S1,Sn; u1,un中，如果n是有限的，且Si是有限集（i=1,n），则该博弈至少存在一个纳什均衡（在混合策略意义下）纳什定理第38页，共59页，2022年，5月20日，3点31分，星期二39纳什定理的一些说明纳什定理的证明要用到不动点定理。所谓不动点定理，是指一个定义在X X上的函数f(x)，集合X是非空的、闭的、有界的和凸的函数f是连续的则至少存在一个x，使得f(x)=x, x

19、被称为不动点第39页，共59页，2022年，5月20日，3点31分，星期二40纳什定理的一些说明运用不动点定理证明纳什定理的主要步骤是设计一个策略组合空间上的一个映射，说明该映射的任何不动点都是一个纳什均衡使用不动点定理证明这个映射一定存在一个不动点第40页，共59页，2022年，5月20日，3点31分，星期二41不动点什么是不动点呢？想像有一个容器，里面充满了大量的小球，现在用一个勺子任意搅拌这容器里的小球，搅拌过后，每一个小球都重新占据了容器中的一个位置，如果某个小球的新位置和旧位置重合，那么这个小球就是一个不动点。数学里面有一类经典的定理，说的是这样的不动点总是存在的。无论你怎么搅拌，总

20、有这样的不动点小球，以不变应万变，终点又回到起点！第41页，共59页，2022年，5月20日，3点31分，星期二42纳什定理的一些说明映射选择的是n人最优反应对应其含义是，对于任意一个混合策略组合(p1,pn)，对于每一个参与人i，求出I针对其他参与人混合策略(p1,pi-1, pi+1,pn)的最优反应，然后构建n个参与人最优反应对应的卡氏积。一个最优混合策略组合就是这一对应集的不动点。第42页，共59页，2022年，5月20日，3点31分，星期二43纳什定理的一些说明因此只要证明前面的最优反应对应满足不动点定理条件就可以了。第43页，共59页，2022年，5月20日，3点31分，星期二44

21、纳什均衡(Nash Equilibrium)纳什均衡、占优均衡、重复剔除严劣策略均衡的关系定理a 每一个占优均衡、重复剔除严劣策略均衡一定是纳什均衡，但反过来不一定成立；定理b 纳什均衡一定不能通过重复剔除严劣策略方法剔除。下面对上述定理进行简要证明第44页，共59页，2022年，5月20日，3点31分，星期二45两个定理的证明首先证明定理b：纳什均衡一定不能通过重复剔除严劣策略方法剔除。记纳什均衡时的策略组合为s* =(s1*,si*,sn*)用反证法假定纳什均衡在重复剔除严劣策略均衡中被剔除掉，不失一般性，假设s1*是s*中被首先剔除的策略，则在S1中，一定存在一个尚未被剔除的策略s1，相

22、对参与人1而言，严格优于s1*第45页，共59页，2022年，5月20日，3点31分，星期二46两个定理的证明于是根据重复剔除严劣策略定义，对于此时所有尚未被剔除的其他参与人的任意一个策略组合s-1=(s2, si,sn)，均成立ui(s1, s-1) ui(s1*, s-1)第46页，共59页，2022年，5月20日，3点31分，星期二47两个定理的证明由于前面分析中假设策略s1*是s* =(s1*,si*,sn*)中首先被剔除的策略，因此在s1*被剔除的时候， s2*,si*, ,sn*尚未被剔除，自然满足式，这显然与s*是NE矛盾第47页，共59页，2022年，5月20日，3点31分，星

23、期二48下面开始证明定理a:重复剔除严劣策略均衡一定是纳什均衡(反证法)假设重复剔除严劣策略后，只剩下唯一的一个策略组合s* =(s1*,si*,sn*),但却不是NE。则存在一个s1 S1，使得下列事实成立u1 (s1*,si*,sn*)u1 (s1,si*,sn*)但由于(s1,si*,sn*)在中间过程中被剔除，而s*是被保留下来的唯一一个策略组合。两个定理的证明第48页，共59页，2022年，5月20日，3点31分，星期二49按照严劣策略的定义，有u1 (s1*,si*,sn*)u1 (s1,si*,sn*)比较左右两式，可以得出矛盾两个定理的证明第49页，共59页，2022年，5月2

24、0日，3点31分，星期二50划线法先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳策略总是存在的，不过不一定唯一），然后在此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。这就是划线法。第50页，共59页，2022年，5月20日，3点31分，星期二51 参 与 人 B参与人ALCRU0, 44, 05, 3M4, 00, 45, 3D3, 53, 56, 6图1-8第51页，共59页，2022年，5月20日，3点31分，星期二52箭头法箭头法对于理解博弈关系很有好处,是寻找相对稳定性策略组合的分析方法。对博弈中的每个策略组合进行分析，考察在每个策略组合处各个参与方能否通过改变自己的策略而增加得益。如能，则从所分析的策略组合对应的得益