第6章博弈论基础解析ppt课件.ppt

《第6章博弈论基础解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章博弈论基础解析ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、,博弈论基础,（对应教材第6章）,现代博弈论开始于1928年冯诺伊曼的工作,本章学习要点,理解博弈论的基本概念,参与人，策略，收益（收益矩阵）最佳应对，占优策略纳什均衡,混合策略，混合策略均衡帕累托最优，社会最优,几种典型博弈的类型,体会“情景博弈求解”过程中的思想,博弈从一个例子开始,“复习考试”还是“准备报告”？,假设在截止日期前一天，你有两件要做的,事情：一是复习（为了参加考试），二是准,备（给一个报告）。你只能选择做一项。,考试成绩可以预计,如果复习，则考试成绩92分，没复习，则80分,报告需要你和你的拍档合作完成,如果你和拍档都准备报告，则每人都是100分 如果只有一人准备报告，则每

2、人都是92分 如果两人都没准备报告，则每人都是84分,那么你该选择做什么呢？（假设你和拍档各,自独立考虑这个问题）,例子：“考试-报告”博弈,设你们都追求平均成绩的最大化：你和搭档都准备报告，则平均成绩均为(80+100)/2=90分 你和搭档都准备,考试成绩可以预期：如果复习，则考试成绩92分 如果没复习，则考试成绩80分 报告是你和你的拍档合作完成的：如果你和拍档都准备报告，则每人100分 如果只有一人准备报告，则每人92分 如果两人都没准备报告，则每人84分,考试，则平均成 若一方复习考试，另一方准备报告：准备报告一方的得：(80+92)/2=86分(92+84)/2=88分 复习的一方

3、得：(9292)/2=92分,收益矩阵（表达收益的一种直观方式）你的拍档,准备报告,复习考试,你,准备报告复习考试,90,9092,86,86,9288,88,其中第一个数字是“你”的收益，第二个是“拍档”的 收益（也称“回报”，payo）,博弈的基本要素,一般情况下，博弈具有三个要素：,（1）参与者（至少两个）；,（2）策略集：每个参与者都有一组关于如,何行为的备选项，此处备选项指参与者的可能策略。,（3）收益（回报）：每个策略行为的选择,，都会使参与人得到一个收益。,这个收益结果还受互动中他人策略选择的影响。同一组策略，不同参与人的收益可能不同,通常，收益的记号：P1(S,T),P2(S,

4、T),博弈行为推理的几点基本假设,每个参与人对博弈结构（收益矩阵）有,充分了解。,参与人都是理性的（ra:onal）,追求自己的收益最大化（尽量大）也知道其他参与人也是如此,决策的独立性,不商量,严格占优策略（strictly dominant strategy）：对一个参与人（A）来说，若存在一个策略，无论另一个参与人（B）选择何种行为策略，该策略都是最佳选择，则这个策略就称为是A的严格占优策略。这个例子中，“复习考试”对双方都是严格占优策略。,“考试-报告”博弈中的行为推理你的拍档,准备报告,复习考试,你,准备报告复习考试,90,9092,86,86,9288,88,“囚徒困境”,假设有两

5、个疑犯被警察抓住。并且被分开关押在不同,的囚室。,警察强烈怀疑他们和一场抢劫案有关。但是，没有充足的证据。然而，他们都拒捕的事实也是可判刑的。,两个疑犯都被告知以下结果：,“如果你坦白，而另外一人抵赖，则你马上释放；另外,一人将承担全部罪行，将会被 判刑10年,如果你们都坦白，你们的罪行将被证实。但由于你们有,认罪的表现判刑4年。,如果你们都不坦白，那么没有证据证明你们的抢劫罪，,我们将以拒捕罪控告你们判刑1年。,另外一方也正在接受这样的审讯。你是坦白还是抵赖？”,疑犯1和疑犯2的严格占优策略都是“坦白”尽管如果两人都抵赖会都判得少些 刻画了“有关个体私利前，建立合作是十分困难”的模型。,“囚

6、徒困境”的收益矩阵疑犯2,抵赖,坦白,疑犯1,抵赖坦白,-1,-10,-10,-10,0-4,-4,这种类型通常称为军备竞赛。竞争双方为保持彼此实力相当，都会选择生产更具危险性的武器，尽管对自己内部会有伤害 运动员伤害身体，国家影响民生。,“兴奋剂”博弈运动员2,没服用,服用,运动员1,没服用服用,3,34,1,1,42,2,关于“收益”的讨论（收益决定选择）“考试-报告”博弈，如果降低考试难度：只要复习了，就会得到100分；否则，也可得到96分。你的拍档,准备报告,复习考试,你,准备报告复习考试,98,9896,94,94,9692,92,囚徒困境类似，如果改变收益矩阵，情况也可不一样,最佳

7、应对与占优策略,设S是参与人甲的一个选择策略，T是参与人,乙的一个选择策略。在收益矩阵中的某个单,元格对应这策略组（S，T）。,P1(S，T)：表示参与人甲从这组决策获得的收益 P2(S，T)：表示参与人乙从这组决策获得的收益 最佳应对：针对参与人乙的策略T，若参与人甲采用策略S产生的收益大于或等于自己的任何其他策略，则称参与人甲的策略S是参与人乙的策略T的最佳应对。,P1(S，T)P1(S，T),其中，S是参与人甲除S外的任何其他策略。,严格最佳应对,严格最佳应对：若S会产生比任何应对策略,T的其他策略都更高的收益，则称参与人甲的策略S是对于参与人乙的策略T的严格,最佳应对。,P1（S，T）

8、P1（S，T）,其中，S是参与人甲的所有其他策略。,注：最佳应对的概念是针对对方的某一个策,略（T），相对于自己的所有策略而言的,对于同一个T，最多只可能有一个严格最佳应对 对于不同的T，最佳应对可能相同，也可能不同,占优策略与严格占优策略,定义：（从最佳应对角度给出）,参与人甲的占优策略S，是指该策略对于参与,人乙的每一策略都是最佳应对。,参与人甲的严格占优策略S，是指该占优策略对于参与人乙的每一策略都是严格最佳应对。如果参与人有严格占优策略，则可预期他会采取该策略（与基本假设的一致性）。注：占优策略的概念是相对于对方所有策,略而言的。,并不是每人总有严格占优策略,例子：“营销战略”博弈,假

9、设有两家公司，分别要规划生产并销售同,一种新产品。该产品有两款可能的规格：廉,价（低档）或高档。如何决策？,设顾客总体被分成两个市场：一部分消费群体（60%）只购买廉价商品，另一部分消费群体（40%）只购买高档次商品。,每家公司从廉价或高档次商品所得利润是等同的（因此利润仅取决于市场占有率）。,每家公司都追求利润最大化。,“营销战略”博弈 假设 若两家公司分别定位生产不同类型的产品，则每家公司都会得到该商品市场的全部份额。公司1品牌形象更佳。因此，若这两家公司在同一市场（廉价或高档次）中竞争，则公司1可以得到80%的市场销售量，公司2只能得到20的市场。公司2,廉价,高档次,公司1,廉价高档次

10、,0.48,0.120.4,0.6,0.6,0.4 0.32,0.08,可以预测此博弈的发展趋向。即公司1将会采取廉价策略，公司2将会采取高档次策略。,博弈的行为推理,如果参与人都有严格占优策略，则可以,预计他们均会采取严格占优策略；,如果只有一个参与人有严格占优策略，,则这个参与人会采取严格占优策略，而,另一方会采取此策略的最佳应对。,如果两个参与人都没有严格占优策略呢？,无占优策略例子（三客户博弈）,假设有两家公司，都希望和A、B、C三个大客户之一洽谈生意,。每家公司都有三种可能的策略：是否找客户A、B或C。,他们决策的条件如下所示：,若两家公司都找同一个客户，则该客户会给每个公司一半,的

11、业务。,公司1规模太小，以至于不能靠自身找到客户源。所以，只要它和公司2分别寻找不同的客户洽谈生意，则公司1获得的收益将会是0（生意做不成）。,假设公司2单独寻找客户B或C洽谈生意，则会得到客户B或C的全部业务。但是A 是一个大客户。寻找客户A洽谈生意时，必须和其它公司合作才能接下业务。,因为A是一个大客户，和它做生意的收益是8（假设两家公司合作，则每家公司会得到收益4）。但是，和B或C做生意的收益价值是2（合作的话，每个公司收益是1）,“三客户”博弈的推理 收益矩阵 公司2,A,B,C,A公司1 BC,4,40，00，0,0,21,10,2,0,20,21,1,两家公司都没有严格占优策略,纳

12、什均衡,假定参与人甲选择策略S，参与人乙选择策略T。若S是T的最佳应对，且T也是S的最佳应对，则称策略组（S，T）是一个纳什均衡。,在均衡状态，任何参与人都没有动机（理性,的理由）去换一种策略。,纳什均衡可以被看成是一种信念上的均衡,互为最佳应对，谁也不可能通过单方面改变策,略而得到额外好处，尽管如果两人都改变可能,都会更好（相比都不改变而言）,存在纳什均衡：(A，A)寻找纳什均衡的两种途径：一是，检查每一个策略组，看它们中的每一项是否是彼此间策略的最佳应对策略。二是，找出每个参与人对于对方每个策略的最佳应对，然后发现互为最佳应对的策略组。,“三客户”博弈的纳什均衡公司2,A,B,C,A公司1

13、 BC,4,40，00，0,0,21,10,2,0,20,21,1,多重均衡：协调博弈,多重均衡存在多个均衡 例子：协调博弈,假设你和你拍档都为一个合作项目准备幻灯,片简报（双方不能通过电话等方式联系,商量）。,你必须决定是用微软的PPT或是用苹果,的Keynote软件来制作你负责的半份幻灯片。假设你们使用同样的软件来设计，那就比较,容易合并你们的幻灯片。,存在两个纳什均衡：（PPT，PPT），（Keynote，Keynote）。如何预测协调博弈中参与人的行为？托马斯 谢林（获得2005年诺贝尔经济学奖）提出一种聚点的想法，利用一些其他外部因素，例如社会习俗。,协调博弈的推理你的拍档,PPT,

14、Keynote,你,PPTKeynote,1,10，0,0，01，1,谢林的聚点理论表明，可以预测到参与人会精选策略，倾向于收益情况更好的均衡。,不对等协调博弈 假设你和项目拍档都更喜欢使用苹果软件。你的拍档,PPT,Keynote,你,PPTKeynote,1,10，0,0，02，2,此时很难预测具体哪种均衡会被采取。可以通过了解他们之间平常发生冲突时解决的惯例来预测。,两人的喜好不同呢 假设你和你的拍档喜欢的软件不同。你的拍档,PPT,Keynote,你,PPTKeynote,1,20，0,0，02，1,选择何种均衡？要在高收益和由于另一方不合作而造成损失之间进行权衡。,猎鹿博弈 假设两猎

15、人外出猎物。若他们合作，则可以猎到鹿（这可以给猎者带来最高的收益）。猎人若分开单干，都能猎到兔。若一方想单独猎鹿，则收益是0。另一方依然能猎到兔。猎人2,猎鹿,猎兔,猎人1,猎鹿,4，4,0，3,猎兔,3，0,3，3,多重均衡：鹰鸽博弈,假设两只动物要决定一块食物在彼此之,间何如分配。,每种动物都可以选择争夺行为（鹰派,策略）或分享行为（鸽派策略）。,若两种动物都选择分享行为，他们将会均匀,的分配食物，各自的收益是3。,若一方行为表现为争夺，另一方行为表现是,分享，则争夺方会得到大多数食物，获得收,益是5，分享方只能得到收益为1。,当两只动物都表现为争夺行为，由于在争夺中践踏了食物，则它们得到

16、的收益将为0。,很难预测参与者的行为 纳什均衡概念能有助于缩小合理的预测范围，但它并不能给出唯一的预测。,鹰鸽博弈推理动物2,鸽派,鹰派,动物1,鸽派鹰派,3,35，1,1，50，0,几种典型多均衡博弈类型对比,动物2,鸽派,鹰派,鸽派鹰派,3，35，1,1，50，0,你的拍档,PPT,Keynote,PPTKeynote,1，10，0,0，02，2,你的拍档,PPT,Keynote,PPTKeynote,1，20，0,0，02，1,猎人2,猎鹿,猎兔,猎鹿猎兔,4，43，0,0，33，3,简单博弈的推理思路,如果双方都有严格占优策略，则都会采用之 如果只有一方有严格占优策略，则可以预,测另一

17、方会采用此策略的最佳应对,如果不存在严格占优策略，则寻找纳什均衡,存在一个纳什均衡，该均衡对应合理结果 存在多个纳什均衡（需要额外信息辅助决策）,协调博弈，鹰鸽博弈,均衡有助于缩小考虑范围，但不保证有效预测,如果不存在纳什均衡，该怎么办？,此时，不存在一组互为最佳应对（纳什均衡）,混合策略 例子：硬币配对“零和博弈”（zero sum game）两个参与人各持一枚硬币，同时选择手中硬币的正反面。若他们硬币的朝向相同，参与人乙将赢得参与人甲的硬币。反之，则参与人甲将赢得参与人乙的硬币。参与人乙,正面H,反面T,参与人甲,正面H反面T,-1，+1+1，-1,+1，-1-1，+1,混合策略的引入,引

18、入随机性，考虑参与人将以一定的概率,分布在不同策略间进行选择，一种分布对应一个“混合策略”（此时，选择策略就是选择分布）,对于双策略（H和T）博弈，混合策略则可简略表示为一,个概率。纯策略就是概率为（0,1）的混合策略。,通常，我们说,参与人1的策略是概率p，是指参与人1以概率p执行H；,以概率1-p执行T,参与人2的策略是概率q，是指参与人2以概率q执行H，,以概率1-q执行T,混合策略的收益 采用收益期望作为策略的回报测度 设参与人1采用概率p执行H，1-p执行T，则：若参与人2采用H，则其收益期望是,若参与人2采用T，则其收益期望是,类似地，可讨论参与人2采用概率混合策略的情形,P 2(

19、p,H)=p!P 2(H,H)+(1 p)!P 2(T,H),P 2(p,T)=p!P 2(H,T)+(1 p)!P 2(T,T),混合策略的均衡,混合策略的纳什均衡：它是一对混合策略,，彼此都是对方的最佳应对（期望收益）,纳什的奠基性贡献：证明了具有有限参与,者和有限纯策略集的博弈一定存在纳什均,衡（包括混合策略均衡）,一般来说，找到混合策略的纳什均衡是很,困难的，但在某些特定条件下可能有系统,的方法。,双人双策略、没有含纯策略均衡的博弈中的,混合策略纳什均衡求解,给定H，T：基本纯策略。按照纳什定理，存在一个混合策略的纳什均衡（p,q），即p是q的最佳应对，q也是p的最佳应对。如何求p和q

20、？,“没有含纯策略的均衡”的前提意味着p，q都是严格在0,和1之间。,确定参与人2采用的q的方法（确定p的方法对称）,基于q和收益矩阵中的值，分别写出参与人1采用H和采用T的收益期望（q的函数），即P1(H,q)和P1(T,q)，也就是相当于P1(1,q)和P1(0,q),下面的关键是要认识到此时必定有：P1(1,q)P1(0,q)，,从而可以借助这等式求出q,P1(1,q)P1(0,q)：在两个端点“无差异”原理 推理的思路是,若等式不成立，例如 P1(1,q)P1(0,q)，则将,导致H（即p=1）是参与人1的最佳应对的结论，即（H,q）是一个纳什均衡，这与“不,含纯策略纳什均衡”的前提矛

21、盾,直观上，若 P1(T,q)P1(H,q)，参与人1在应对q的时候采用H就是最好，将任何机会（概率）分给T都只会导致较低收益,数学上就是,P1(p,q)=pP1(H,q)+(1-p)P1(T,q)P1(H,q),for p1,混合策略的收益计算例子 用收益期望来表达回报参与人2,正面H(q),反面T(1-q),参与人1,正面H反面T,-1，+1+1，-1,+1，-1-1，+1,例如，当参与人2采用策略q时，若参与人1使用纯策略，则他的回报分别为：纯策略H的期望收益=(-1)(q)+(+1)(1-q)=1-2q 纯策略T的期望收益=(1)(q)+(-1)(1-q)=2q-1如果系统不存在包含纯

22、策略的均衡，则上述两个表达式必须相等。,设（p，q）是纳什均衡。对参与人2的策略q，参与人1用纯策略H的期望收益=(-1)(q)+(+1)(1-q)=1-2q 参与人1用纯策略T的期望收益=(1)(q)+(-1)(1-q)=2q-1 这是一个不存在含有纯策略均衡的博弈，由“无差异”原理，须有1-2q=2q-1，即q=1/2 对称地，可以得到参与人1的最佳应对p=1/2 因此，（1/2,1/2）是一个混合策略纳什均衡（合直觉）,硬币配对博弈的混合策略均衡参与人2,正面H(q),反面T(1-q),参与人1,正面H反面T,-1，+1+1，-1,+1，-1-1，+1,混合策略：进一步的例子 持球-抛球

23、博弈 美式足球比赛：进攻方可以选择持球或者是抛球。防御方可以选择拦断持球或者选择防守抛球。假设正确阻止了进攻方的行为，则进攻方的收益为0。假设进攻方选择持球而防守方却选择防守抛球行为，则进攻方的收益为5（防守方相应损失）。假设进攻方选择抛球，同时防守方却选择拦断持球，则进攻方的收益是10（防守方相应损失）。防守方,防守抛球,拦断持球,进攻方,抛球持球,0，0 5，-5,10，-100，0,进攻方选择抛球的期望收益：0*q10(1-q)进攻方选择持球的期望收益：5q0*q 依无差异原理，令 10-10q=5q，解得 q=2/3,持球抛球博弈的混合策略均衡 这是一个没有纯策略纳什均衡的博弈 设防守

24、方选择防守抛球的概率为q 防守方,防守抛球(q),拦断持球(1-q),进攻方,抛球持球,0，0 5，-5,10，-100，0,防守方选择防守抛球的期望收益：-5(1-p)防守方选择拦断持球的期望收益：-10p 令-10p=-5(1-p)，解得 p=1/3 于是，这个博弈的混合策略均衡为(1/3,2/3),持球抛球混合策略均衡（续）进攻方选择抛球的概率为p 防守方,防守抛球,拦断持球,进攻方,抛球(p)持球(1-p),0，0 5，-5,10，-100，0,讨论,为什么抛球有可能收益更大，而均衡中进攻方选择抛球的概率只有1/3？由于防守方高概率防守抛球，若抛球概率p1/3，则损失会比较大 为什么进

25、攻方在均衡的抛球概率只有p=1/3，但防守方还要更多的防守抛球？由于抛球对进攻方更有利，需要加大防守力度,防守方,进攻方,抛球(1/3)持球(2/3),防守抛球(2/3)0，0 5，-5,拦断持球(1/3)10，-100，0,例子：罚点球博弈 2002年，有人做了一项有关罚点球研究 射手要决定从球门的左侧或是右侧进球。守门员则是要决定是扑向左侧或是右侧拦断进球。两人需要同时做选择。守门员,L,R,射球方,LR,0.58，-0.58 0.93，-0.93,0.95，-0.950.70，-0.70,统计数据。可以看到，罚球方总是有赢头（符合实际）。,计算得到的均衡：0.58q+0.95(1-q)=

26、0.93q+0.70(1-q)，q=0.42-0.58p-0.93(1-p)=-0.95p-0.70(1-p)，p=0.39 实战统计得到的数据：q=0.42,p=0.40,混合策略均衡守门员,L(q),R,射球方,L(p)R,0.58，-0.58 0.93，-0.93,0.95，-0.950.70，-0.70,除了两个纯策略均衡（PPT,PPT）和（Keynote,Keynote）外，还存在一个混合策略均衡：q=2(1-q),q=2/3；p=2(1-p),p=2/3,兼具纯策略和混合策略均衡的博弈 例子：不平衡的协调博弈 你的拍档,PPT(q),Keynote,你,PPT(p)Keynote

27、,1，10，0,0，02，2,关于混合策略均衡的一般性推理,若双人双策略博弈存在混合策略均衡（p,q），0,p,q 1,甲所选择的p，应该使乙在他的两个纯策略上无差异；否则乙就会用优势策略（例如1）作为应对，收益期望(p,1)收益期望(p,q)，即没有q1是p的最佳应对，从而与存在上述混合策略均衡矛盾,于是可利用这无差异原则，试求p；类似地，求q。（注意，并不保证总能求出在（0,1）上的p和q）,若分别求得了（0,1）区间中的p和q，则说明,对于甲的策略p，乙采用0,1上的任何策略都是一样的，即都是最佳应对，后来求出的q当然也是。对于p也有对称的认识，亦即p和q互为最佳应对,想想混合策略组：(

28、p,q+q)q+q 依然是p的最佳应对，但p却不是q+q 的最佳应对了！q+q 的最佳应对会是甲的某一个纯策略！,P 2(p,H)=p!P 2(H,H)+(1 p)!P 2(T,H)P 2(p,T)=p!P 2(H,T)+(1 p)!P 2(T,T)Set P 2(p,H)=P 2(p,T)to solve p,P 2(q,p)=q!P 2(p,H)+(1q)!P 2(p,T),对任何q都无差异！,乙在两个纯策略上的收益期望,P1(1,q)=q*90+(1-q)*86;P1(0,q)=q*92+(1-q)*88 容易检查，不存在q，使 P1(1,q)=P1(0,q),考试报告博弈没有混合策略你

29、的拍档,准备报告,复习考试,你,准备报告复习考试,90,9092,86,86,9288,88,混合策略均衡的概率也可能恰好取在端点,q*1+0=0+(1-q)*2,q=2/3 p*2+0=p*2+(1-p)*1,p=1,你的拍档,PPT,Keynote,你,PPTKeynote,1，20，0,0，22，1,这个例子中，纯,策略均衡有两个，（PT,PT）和,（KT,KT）PTPT,KTKTKTPTPTKTKT,(1,2/3)为混合均衡。从收益矩阵也能看出，当你采取PT，对手有什么都无差异,纯策略均衡不是概率恰好取端点的混合策略均衡！,帕累托最优和社会最优“个体最优”与“整体最优”帕累托（Pare

30、to）最优 一个策略组：每个参与者对应其中一个策略选择。一个策略组被称为帕累托最优，若不存在其他策略组满足：所有参与者得到至少和目前一样高的回报，且至少有一个参与者会得到严格较高的回报。你的拍档,准备报告,复习考试,你,准备报告复习考试,90,9092,86,86,9288,88,这个例子中，存在三个Pareto最优，但都不是均衡。,（报告，报告）是社会最优。社会最优也一定会是帕累托最优。,社会最优 定义：一组策略选择是社会最优（或社会福利最大化），若它使参与者的回报之和（总收益）最大。你的拍档,准备报告,复习考试,你,准备报告复习考试,90,9092,86,86,9288,88,社会最优和纳什均衡有可能一致 按照下面的收益矩阵，（报告，报告）既是社会最优也是纳什均衡你的拍档,准备报告,复习考试,你,准备报告复习考试,98,9896,94,94,9692,92,用博弈论思想分析问题,理解不同博弈的类型，以及求解的基本方法重要（science）。均衡是一个基本目标。将问题（情景）要求准确抽象成收益矩阵至少同样重要（art）。,情景描述,收益矩阵,博弈求解,作业,第6章练习2，3，10，12,