博弈论-ppt课件

博弈论博弈就是一些个人、队组或其他组织，面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，各自取得相应结果的过程。博弈的基本要素博弈的参加者(Player)——博弈方各博弈方的策略(Strategies)或行动(Actions)博弈的次序(Order)博弈方的收益(Payoffs)（或称支付，或得益）博弈方博弈方：独立决策、独立承担博弈结果的个人或组织博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变博弈方数量对博弈结果和分析有影响根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈策略策略：博弈中各博弈方的选择内容策略有定性定量、简单复杂之分不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同有限博弈：每个博弈方的策略数都是有限的无限博弈：至少有某些博弈方的策略有无限多个收益收益：各博弈方从博弈中所获得的利益收益对应博弈的结果，也就是各博弈方策略的组合收益是各博弈方追求的根本目标及行为和判断的主要依据根据收益的博弈分类：零和博弈、常和博弈、变和博弈策略型（或标准型）博弈三要素：名单、策略单和收益单。可用矩阵，或函数形式表示的博弈收益情况。猜硬币模型三人古诺模型-1，11，-11，-1-1，1正面反面猜硬币方盖硬币方正面反面iiiqqqqqP]20[321几个经典博弈模型囚徒的困境赌胜博弈审计博弈性别之战产量决策的古诺模型囚徒的困境囚徒的困境是图克（Tucker）1950年提出的该博弈是博弈论最经典、著名的博弈囚徒2坦白不坦白囚徒1坦白-5，-50，-8不坦白-8，0-1，-1赌胜博弈赌博、竞技等构成的博弈问题，在经济中也有许多应用，赌胜博弈也是一类重要的博弈问题，对经济竞争和合作也有很大启示赌胜博弈的特点是一方得等于另一方失，不可能双赢，属于“零和博弈”-1，11，-11，-1-1，1正面反面猜硬币方盖硬币方正面反面田忌赛马取胜关键：不让对方猜到自己策略，尽可能猜出对方策略3，-31，-11，-11，-1-1，11，-11，-13，-31，-11，-11，-1-1，11，-1-1，13，-31，-11，-11，-1-1，11，-1，1，-13，-31，-11，-11，-11，-11，-1-1，13，-31，-11，-11，-1-1，11，-11，-13，-3上中下上下中中上下中下上下上中下中上上中下上下中中上下中下上下上中下中上田忌齐威王得益矩阵√√审计博弈简单版（B＜C，F＞t）嫌疑人偷税不偷税税务局审计B－C，－FB－C，－t不审计0，0B，－t性别之战是一种有两个以上纯策略均衡的博弈张帅看足球听音乐何佳看足球2，40，0听音乐1，14，2例子（石头、剪子、布）中的博弈方、策略和收益博弈方I（孩子A，孩子B）策略集SA＝SB＝｛石头，剪刀，布｝收益就是这个矩阵0，01，-1-1，1-1，11，-10，01，-1-1，10，0石头剪刀布孩子B石头剪刀布孩子A占优均衡占优：不管其它博弈方选择什么策略，一博弈方的某个策略给他带来的得益始终高于其它的策略，至少不低于其他策略的策略（囚徒的困境中的“坦白”）占优均衡：一个博弈的某个策略组合中的所有策略都是各个博弈方各自的占优，必然是该博弈比较稳定的结果占优均衡不是普遍存在的（性别之战）严格下策反复消去法严格下策：不管其它博弈方的策略如何变化，给一个博弈方带来的收益总是比另一种策略给他带来的收益小的策略严格下策反复消去1，01，30，10，40，22，0左中右上下1，01，30，40，2左中1，01，3左中1，3纳什均衡策略空间：S1，……Sn博弈方i的第j个策略：sij∈Si博弈方i的得益：ui博弈：G＝｛S1，…，Sn，u1，…，un｝纳什均衡：在博弈G＝｛S1，…，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*）对任意sij∈Si都成立，则称（s1*，…，sn*）为G的一个纳什均衡所有别的游戏者策略的简记法s-i＝（s1，…，si-1，si+1，…，sn）纳什均衡简述为：ui（si*，s-i*）≥ui（si，s-i*），si∈SiA纳什均衡的求解——划线法囚徒困境猜硬币-5，-50，-8-8，0-1，-1-1，11，-11，-1-1，1纳什均衡的求解——箭头法审计博弈（B＞C，F＞t）嫌疑人偷税不偷税税务局审计B－C，－FB－C，－t不审计0，0B，－t连续变量的纳什均衡古诺的寡头模型QQPPqqQ8)(21121111112)](8[)(qqqqqcQPqu212116qqqq221cc221222222)](8[)(qqqqqcQPqu222126qqqq连续变量的纳什均衡解：一阶最优条件为：得到：q1＝q2＝212112122620620uqqquqqq混合策略的引进猜硬币博弈（1）不存在前面定义的纳什均衡策略组合（2）关键是不能让对方猜到自己策略这类博弈很多，引出混合策略纳什均衡概念-1，11，-11，-1-1，1正面反面猜硬币方盖硬币方正面反面猜方是否会老猜正面，或反面？其实“一会儿猜正面，一会儿又猜反面”也是一种策略。田忌赛马中齐王是如何输掉比赛的？混合策略的定义对于游戏者i，其一个混合策略是一个概率密度函数σi：Si→R，使得，对于所有的si∈Si，都有这就是混合策略。0,1iiiiiisSss混合策略的纳什均衡定义如果对于博弈中所有的游戏者i，对于所有的σi∈Mi，都有ui﹙σ*﹚≥ui﹙σi，σ-i*﹚，则称σ*就是一个混合策略的纳什均。如何求混合策略的纳什均衡猜硬币的博弈中解：设猜方猜正方的概率为p，猜反方的概率则为1－p；设盖方盖正方的概率为q，盖反方的概率则为1－q。猜方的期望收益：πz＝q[p－（1－p）]＋（1－q）[－p＋1－p]期望收益最大的一阶条件是：dπz/dq＝（－1＋2p）－（1－2p）＝0即p＝0.5，同理可得q＝0.5。混合纳什均衡的求解——几何法加重对守位的处罚：短期中的效果是使守卫真正尽职在长期中并不能使守卫更尽职，但会降低盗窃发生的概略v，-d-p，00，s0，0睡不睡偷不偷守卫小偷PP’0-d-d’守卫得益(睡)sP小偷偷的概率1-d几何法的证明设守卫睡的概率为Q，小偷偷的概率为P。守卫的期望支付为：π＝P[Q×（－d）＋（1－Q）×0]＋（1－P）[Q×s＋（1－Q）×0]＝－PQd＋（1－P）Qsəπ/əQ＝－Pd＋（1－P）s＝0P＝s/（d＋s）＝P/1＝P（∵▲∽）广延型（扩展型）博弈四要素——名单、博弈分枝结构（节点，或博弈点）、信息集和收益，用对策树形式表示。左右博弈信息不完美静态博弈信息完美动态博弈广延型博弈与策略型博弈【定理】对于每一个广延型博弈，都存在着一个对应的策略型博弈，我们可以把此策略型博弈视为是游戏者同时选择策略的结果。但是，给出一个策略型博弈，一般地，总存在着若干个与此相对应的广延型博弈。(证明从略)将广延型博弈转化为策略型博弈的例子讲真话博弈将策略型博弈转化为广延型博弈的例子囚犯困境博弈广延型博弈的解——反向归纳【定义】反向归纳是指从博弈的最终结局出发，游戏者总是选择对自己最有利的结果；一旦知道博弈的最终结果是什么，然后转向次结局的那个决策点，以同样方法找出该点上的决策者会选择什么决策；然后回到次次结局的那个点→…→如此反复，直到博弈的初始点，在初始点上决策的那个游戏者决定博弈的最终结果。反向归纳的例子例子A√√√√√××××子博弈定义子博弈是展开型的一部分；它是满足下述三个性质的节点和枝的集合：(1)从单个决策节出发。(2)包含了这个节点的每一个后续节。(节点x的后续节是指沿着由x发出的一系列枝可以到达的所有节点。)(3)如果它包含了一个信息集的若干部分，那么它一定包含该信息集中的所有节点。子博弈的例子例子是不是！因z点不是x点后续点。子博弈的例子两个不是子博弈的例子子博弈完美纳什均衡子博弈完美纳什均衡：一个策略组合是子博弈完美纳什均衡，如果它满足：1.对于整个博弈来说，它是一个纳什均衡；2.对于任一个子博弈来说，它也是一个纳什均衡。子博弈完美纳什均衡的例子均衡1（借，分）；均衡2（不借）√√子博弈与完美性配套博弈同时A先××√重复博弈囚犯困境的重复博弈如果存在下列三个条件，则“价格勾结”(高价，高价)便会出现：第一，博弈重复无穷次。第二，双方都采取“冷酷”战略——“以牙还牙”战略，即：(1)从选择“合作”(高价)开始；(2)只要对方一直选择“合作”(高价)，便一直“高价”下去；直到有一天发现对方偷偷实行了“不合作”(低价)，便由此而采取“不合作”(低价)至永远。第三，贴现因子δ＝1/（1＋r）足够的大（r≥0）。这个条件是说，将来的收益经贴现之后还比较值钱。即人们对于时间比较有耐心，而不是只图眼前享受。以牙还牙策略以牙还牙策略：称下列策略为“以牙还牙”策略，如果：1.从一开始便选择“合作”；2.在时期t选对方在时期t－1期所采用的策略，即如对方在t－1期不合作，则我在t期不合作。无名氏（大众）定理无名氏定理：在无穷次重复的由n个游戏者参与的博弈里，如果在每一次重复中博弈的行动集是有限的，则在满足下列三个条件时，在任何有限次重复中所观察到的任何行动组合都是某个子博弈完美均衡的惟一结果：条件1：贴现因子接近于1；条件2：在每一次重复中，博弈结束的概率或等于0，或为非常小的一个正值；条件3：严格占优于一次性博弈中的最小最大收益组合的那个收益组合集是n维的。无名氏定理说明以囚徒困境问题说明此定理设此囚徒困境的收益矩阵为:企业1L1R1企业2L21，15，0R20，54，4无限重复博弈子博弈精练均衡的例子（R1，R2）就是一个子博弈精练均衡（假定δ＝1）假定企业1在t期之前选择了R1，而在t期选择采取“机会主义”L1，而企业2直到t期都选择R2，根据“以牙还牙”策略，从t＋1期开始将一直选择L2，那么企业1从t＋1期也将一直选择L1。采取“机会主义”的t－1期后的收益＝5＋1＋1＋……不采取“机会主义”的t－1期后的收益＝4＋4＋4……显然，企业1不会偏离R1策略，同样企业2也不会偏离R2策略。“江湖义气”也因此产生了。无限重复的囚徒困境子博弈精练均衡有无穷多个子博弈精练均衡在无限重复博弈中，可行收益集（黑色四边形）中的任何一点相对应策略都可以与（1，1）相对应策略构成子博弈精练均衡解。三人博弈均衡是（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