博弈论-课件.ppt

《博弈论-课件.ppt》由会员分享，可在线阅读，更多相关《博弈论-课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、博弈论博弈就是一些个人、队组或其他组织，面对一定的博弈就是一些个人、队组或其他组织，面对一定的环境条件，在一定的规则下，同时或先后，一次或环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并多次，从各自允许选择的行为或策略中进行选择并加以实施，各自取得相应结果的过程。加以实施，各自取得相应结果的过程。博弈论分类o经典博弈n合作博弈n非合作博弈是否允许存在有约束力协议的博弈是区分合作博弈与非合作博弈的标准。o“非典型”博弈，如学习博弈、演化博弈（进化博弈）等是否假定参与者是理性的是区分经典博弈与“非典型”博弈的标准。从游戏到博弈从游戏到博弈o博弈博弈Game，

2、博弈论，博弈论Game Theory，Game即即游戏、竞技游戏、竞技o游戏和经济等决策竞争较量的共同特征：规游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互依存，则、结果、策略选择，策略和利益相互依存，策略的关键作用策略的关键作用n游戏游戏下棋、猜大小下棋、猜大小n经济经济寡头产量决策、市场阻入、投标拍卖寡头产量决策、市场阻入、投标拍卖n政治、军事政治、军事美国和伊朗、以色列和巴勒斯美国和伊朗、以色列和巴勒斯坦、中国和日本等等。坦、中国和日本等等。博弈的基本要素博弈的基本要素o博弈的参加者博弈的参加者(Player)博弈方博弈方o各博弈方的策略各博弈方的策略(Stra

3、tegies)或行动或行动(Actions)o博弈的次序博弈的次序(Order)o博弈方的收益博弈方的收益(Payoffs)（或称支付，或得（或称支付，或得益）益）策略策略o策略：博弈中各博弈方的选择内容策略：博弈中各博弈方的选择内容o策略有定性定量、简单复杂之分策略有定性定量、简单复杂之分o不同博弈方之间不仅可选策略不同，而且可不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同选策略数量也可不同o有限博弈：每个博弈方的策略数都是有限的有限博弈：每个博弈方的策略数都是有限的o无限博弈：至少有某些博弈方的策略有无限无限博弈：至少有某些博弈方的策略有无限多个多个收益收益o收益：各博弈方从博弈

4、中所获得的利益收益：各博弈方从博弈中所获得的利益o收益对应博弈的结果，也就是各博弈方策略收益对应博弈的结果，也就是各博弈方策略的组合的组合o收益是各博弈方追求的根本目标及行为和判收益是各博弈方追求的根本目标及行为和判断的主要依据断的主要依据o根据收益的博弈分类：零和博弈、常和博弈、根据收益的博弈分类：零和博弈、常和博弈、变和博弈变和博弈策略型（或标准型）博弈o三要素：名单、策略单和收益单。可用矩阵，或函数形式表示的博弈收益情况。o猜硬币猜硬币模型o三人古诺模型-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面囚徒的困境o囚徒的困境是图克（囚徒的困境是图克（

5、Tucker）1950年提出的年提出的o该博弈是博弈论最经典、著名的博弈该博弈是博弈论最经典、著名的博弈囚徒囚徒 2坦白不坦白囚囚徒徒1坦白-5，-50，-8不坦白-8，0-1，-1赌胜博弈o赌博、竞技等构成的博弈问题，在经济中也有许多应用，赌胜博弈也是一类重要的博弈问题，对经济竞争和合作也有很大启示o赌胜博弈的特点是一方得等于另一方失，不可能双赢，属于“零和博弈”-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面审计博弈o简单版（BC，Ft）嫌疑人嫌疑人偷税偷税不偷税不偷税税税务务局局审计审计BC，FBC，t不审计不审计0，0B，t例子例子（石头、剪子、

6、布）中的博弈方、策略和中的博弈方、策略和收益收益o博弈方博弈方I（孩子（孩子A，孩子，孩子B）o策略集策略集SASB石头，剪刀，布o收益就是这个矩阵收益就是这个矩阵0，01，-1-1，1-1，11，-10，01，-1-1，10，0石 头剪刀布孩子孩子B石 头剪 刀布孩孩子子A占优均衡o占优占优：不管其它博弈方选择什么策略，一博弈方的某个策略给他带来的得益始终高于其它的策略，至少不低于其他策略的策略 （囚徒的困境中的“坦白”）o占优均衡占优均衡：一个博弈的某个策略组合中的所有策略都是各个博弈方各自的占优，必然是该博弈比较稳定的结果o占优均衡不是普遍存在的（性别之战）纳什均衡o策略空间：策略空间：

7、S1，Sno博弈方博弈方i的第的第j个策略：个策略：sijSio博弈方博弈方i的得益：的得益：uio博弈：博弈：GS1，Sn，u1，uno纳什均衡：在博弈纳什均衡：在博弈GS1，Sn，u1，un中，如果中，如果由各个博弈方的各一个策略组成的某个策略组合（由各个博弈方的各一个策略组成的某个策略组合（s1*，sn*）中，任一）中，任一i博弈方博弈方si*的策略，都是对其余博弈方策略的组的策略，都是对其余博弈方策略的组合（合（s1*，si-1*，si+1*，sn*）的最佳对策，即）的最佳对策，即ui（s1*，si-1*，si*，si+1*，sn*）ui（s1*，si-1*，sij，si+1*，sn*

8、）对任意对任意sijSi都成立，则称（都成立，则称（s1*，sn*）为）为G的一个纳什均衡的一个纳什均衡所有别的游戏者策略的简记法os-i（s1，si-1，si+1，sn）o纳什均衡简述为：ui（si*，s-i*）ui（si，s-i*），siSiA纳什均衡的求解划线法o囚徒困境囚徒困境o猜硬币猜硬币-5，-50，-8-8，0-1，-1-1，11，-11，-1-1，1纳什均衡的求解箭头法o审计博弈（B C，Ft）嫌疑人嫌疑人偷税偷税不偷税不偷税税税务务局局审计审计BC，FBC，t不审计不审计0，0B，t连续变量的纳什均衡o古诺的寡头模型古诺的寡头模型222126qqqq-=混合策略的引进o猜硬币

9、博弈n（1）不存在前面定义的纳什均衡策略组合不存在前面定义的纳什均衡策略组合n（2 2）关键是不能让对方猜到自己策略）关键是不能让对方猜到自己策略o这类博弈很多，引出混合策略纳什均衡概念这类博弈很多，引出混合策略纳什均衡概念-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面猜方是否会老猜正猜方是否会老猜正面，或反面？面，或反面？其实其实“一会儿猜一会儿猜正面，一会儿又正面，一会儿又猜反面猜反面”也是一也是一种策略。种策略。田忌赛马中齐王田忌赛马中齐王是如何输掉比赛是如何输掉比赛的？的？混合策略的定义o对于游戏者对于游戏者i，其一个混合策略是一个概率密度，其

10、一个混合策略是一个概率密度函数函数i：SiR，使得，对于所有的，使得，对于所有的siSi，都有，都有 这就是混合策略。这就是混合策略。混合策略的混合策略的纳什均衡纳什均衡定义定义o如果对于博弈中所有的游戏者如果对于博弈中所有的游戏者i，对于所有的，对于所有的iMi，都有，都有ui*uii，-i*，则，则称称*就是一个就是一个混合策略的混合策略的纳什均。纳什均。混合纳什均衡的求解几何法o加重对守位的处罚：短期中的效果是使守卫真正尽职o在长期中并不能使守卫更尽职，但会降低盗窃发生的概略v，-d-p，00，s0，0睡不睡偷不偷守卫守卫小小偷偷PP0-d-d守卫得益(睡)sP小偷偷的概率1-d几何法的

11、证明o设守卫睡的概率为Q，小偷偷的概率为P。o守卫的期望支付为：oPQ（d）（1Q）0 （1P）Qs（1Q）0 PQd（1P）Qso/Q Pd（1P）s0oP s/（d s）P/1P（）广延型博弈与策略型博弈o【定理】对于每一个广延型博弈，都存在着一个对应的策略型博弈，我们可以把此策略型博弈视为是游戏者同时选择策略的结果。但是，给出一个策略型博弈，一般地，总存在着若干个与此相对应的广延型博弈。(证明从略)将广延型博弈转化为策略型博弈的例子o讲真话博弈将策略型博弈转化为广延型博弈的例子o囚犯困境博弈广延型博弈的解反向归纳o【定义】反向归纳是指从博弈的最终结局出发，游戏者总是选择对自己最有利的结果

12、；一旦知道博弈的最终结果是什么，然后转向次结局的那个决策点，以同样方法找出该点上的决策者会选择什么决策；然后回到次次结局的那个点如此反复，直到博弈的初始点，在初始点上决策的那个游戏者决定博弈的最终结果。反向归纳的例子o例子A子博弈o定义子博弈是展开型的一部分；它是满足下述三个性质的节点和枝的集合：(1)从单个决策节出发。(2)包含了这个节点的每一个后续节。(节点x的后续节是指沿着由x发出的一系列枝可以到达的所有节点。)(3)如果它包含了一个信息集的若干部分，那么它一定包含该信息集中的所有节点。子博弈的例子o例子是不是！因z点不是x点后续点。子博弈的例子o两个不是子博弈的例子子博弈完美纳什均衡o

13、子博弈完美纳什均衡：一个策略组合是子博弈完美纳什均衡，如果它满足：1.对于整个博弈来说，它是一个纳什均衡；2.对于任一个子博弈来说，它也是一个纳什均衡。子博弈完美纳什均衡的例子o均衡1（借，分）；均衡2（不借）子博弈与完美性o配套博弈同时同时A先先重复博弈o囚犯困境的重复博弈囚犯困境的重复博弈o如果存在下列三个条件，则如果存在下列三个条件，则“价格勾结价格勾结”(高价，高价高价，高价)便会出便会出现：现：n第一，博弈重复无穷次。第一，博弈重复无穷次。n第二，双方都采取第二，双方都采取“冷酷冷酷”战略战略“以牙还牙以牙还牙”战略，即：战略，即：o(1)从选择从选择“合作合作”(高价高价)开始；开

14、始；o(2)只要对方一直选择只要对方一直选择“合作合作”(高价高价)，便一直，便一直“高价高价”下去；下去；直到有一天发现对方偷偷实行了直到有一天发现对方偷偷实行了“不合作不合作”(低价低价)，便由此而，便由此而采取采取“不合作不合作”(低价低价)至永远。至永远。n第三，贴现因子第三，贴现因子1/（1r）足够的大（足够的大（r0）。这个条件是）。这个条件是说，将来的收益经贴现之后还比较值钱。即人们对于时间比较说，将来的收益经贴现之后还比较值钱。即人们对于时间比较有耐心，而不是只图眼前享受。有耐心，而不是只图眼前享受。以牙还牙策略以牙还牙策略 o以牙还牙策略：称下列策略为以牙还牙策略：称下列策略

15、为“以牙还牙以牙还牙”策略，如果：策略，如果：1.从一开始便选择从一开始便选择“合作合作”；2.在时期在时期t选对方在时期选对方在时期t1期所采用的策略，即期所采用的策略，即如对方在如对方在t1期不合作，则我在期不合作，则我在t期不合作。期不合作。无名氏（大众）定理o无名氏定理：在无穷次重复的由无名氏定理：在无穷次重复的由n个游戏者参与的个游戏者参与的博弈里，如果在每一次重复中博弈的行动集是有限博弈里，如果在每一次重复中博弈的行动集是有限的，则在满足下列三个条件时，在任何有限次重复的，则在满足下列三个条件时，在任何有限次重复中所观察到的任何行动组合都是某个子博弈完美均中所观察到的任何行动组合都

16、是某个子博弈完美均衡的惟一结果：衡的惟一结果：n条件条件1：贴现因子接近于：贴现因子接近于1；n条件条件2：在每一次重复中，博弈结束的概率或等于：在每一次重复中，博弈结束的概率或等于0，或，或为非常小的一个正值；为非常小的一个正值；n条件条件3：严格占优于一次性博弈中的最小最大收益组合的：严格占优于一次性博弈中的最小最大收益组合的那个收益组合集是那个收益组合集是n维的。维的。无名氏定理说明无名氏定理说明o以囚徒困境问题说明此定理以囚徒困境问题说明此定理o设此囚徒困境的收益矩阵为设此囚徒困境的收益矩阵为:企业1L1R1企业2L21，15，0R20，54，4无限重复博弈子博弈精练均衡的例子o（R1

17、，R2）就是一个子博弈精练均衡）就是一个子博弈精练均衡（假定（假定1）o假定企业假定企业1在在t期之前选择了期之前选择了R1，而在，而在t期选择采取期选择采取“机会主义机会主义”L1，而，而企业企业2直到直到t期都选择期都选择R2，根据，根据“以以牙还牙牙还牙”策略，从策略，从t1期开始将一直选择期开始将一直选择L2，那么企，那么企业业1从从t1期期也也将一直选择将一直选择L1。o采取采取“机会主义机会主义”的的t1期后的收益期后的收益511o不采取不采取“机会主义机会主义”的的t1期后的收益期后的收益444o显然，企业显然，企业1不会偏离不会偏离R1策略，同样企业策略，同样企业2也不会偏离也不会偏离R2策略。策略。“江湖义气江湖义气”也因此产生了也因此产生了。无限重复的囚徒困境子博弈精练均衡o有无穷多个子博弈精练均衡有无穷多个子博弈精练均衡在无限重复博弈中，可行收益集（黑色四边形）中的任何一点相对应策略都可以与（1，1）相对应策略构成子博弈精练均衡解。三人博弈o均衡是（D，L，A）乙乙乙LRLRLR甲 U0,1,30,0,0甲U2,2,20,0,0甲U0,1,00,0,0D1,1,11,0,0D2,2,02,2,2D1,1,01,0,3ABC