博弈论模板PPT课件

1 上次内容回顾 博弈论的定义什么是博弈博弈的要素 参与人 策略集和效用 共同知识假设博弈论的知识体系完全信息静态博弈及其表示占优策略和占优均衡严劣策略和重复剔除严劣策略均衡 2 局中人2LRU局中人1MD Nodominantstrategiesanddominatedstrategies whatabouttheresult 3 BestResponse BR UdoesbestagainstL MdoesbestagainstR 4 L R概率为0 5时 ExpectedpayoffofU 2 5ExpectedpayoffofM 2 5ExpectedpayoffofD 3此时 Ddoesbest 5 假定1认为2选择r的概率为p r 则1选U M D的期望收益分别为 Eu1 U p r 1 p r 5 p r 0Eu1 M p r 1 p r 1 p r 2Eu1 D p r 1 p r 4 p r 2 6 7 BR是期望收益最大时的反应 图中x 1 3 y 3 5由图可知 p r 1 3时 1的最佳反应是选U 1 3 p r 3 5时 1的最佳反应是选D p r 3 5时 1的最佳反应是选M 8 9 点球博弈 10 11 PartnershipGame 2人拥有一家公司 每人分享利润的一半每人的策略 精力投入水平 Si 0 4 利润 4 S1 S2 bS1S2 b 0 1 4 U1 2 S1 S2 bS1S2 S1S1U2 2 S1 S2 bS1S2 S2S2 12 参与人的BR是什么 13 b 1 4时 14 15 纳什均衡 16 NashEquilibrium Theactionprofiles isaNashEquilibriumif foreveryplayeriandeveryactionsiofplayeri s isatleastasgoodasaccordingtoplayeri spreferencesasthetheactionprofile si s i inwhichplayerichoosessi whileeveryotherplayerchooses i Equivalently foreveryplayeri ui s ui si s i Foreveryactionofplayeri 17 DefinitionInthen playergameG S1 Sn u1 un thestrategiesprofile s1 sn areaNashequilibriumif foreachplayeri si is atleasttiedfor 至少不劣于 playeri sbestresponsetothestrategiesspecifiedforthen 1otherplayers s1 sn 1 sn 1 sn ui s1 sn 1 si sn 1 sn ui s1 sn 1 si sn 1 sn NE 18 foreveryfeasiblestrategysiinSi Thatis si solvesmaxui s1 sn 1 si sn 1 sn si Si上述均衡概念是1951年由数学家约翰 纳什 JohnNash 首先提出的 称为纳什均衡 19 纳什均衡 NashEquilibrium 定义 对于一个策略式表述的博弈G N Si ui i N 称策略组合s s1 si sn 是一个纳什均衡 如果对于每一个i N si 是给定其他参与人选择s i s1 si 1 si 1 sn 情况下参与人i的最优策略 经济理性策略 即 ui si s i ui si s i 对于任意的si Si 任意的i N均成立 20 纳什均衡的通俗定义 纳什均衡是一种策略组合 给定对手的策略 每个参与人选择自己的最优策略 21 1Ifgametheoryistoprovideauniquesolutiontoagame theoreticproblemthenthesolutionmustbeaNashequilibrium inthefollowingsense Supposethatgametheorymakesauniquepredictionaboutthestrategyeachplayerwillchoose Inorderforthispredictiontobecorrect itisnecessarythateachplayerbewillingtochoosethestrategypredictedbythetheory 22 Thuseachplayer spredictedstrategymustbethatplayer sbestresponsetothestrategiesoftheotherplayers Suchapredictioncouldbecalledstrategicallystableorself enforcing becausenosingleplayerwantstodeviatefromhisorherPredictedstrategy WewillcallsuchapredictionaNashequilibrium RobertGibbons 23 2一种稳定的策略组合 当所有参与人的选择公开以后 每个人都满意自己作出了正确的选择 没有人能得到更好的结果了 在博弈论中这种结果被称为NE 24 3NE的哲学含义 n个参与人在博弈之前协商达成一个协议 规定每一个参与人选择一个特定的策略 问题是 给定其他参与人都遵守该协议 在没有外在强制的情况下 是否有人选择不遵守 25 只有当遵守协议带来的效用大于不遵守时 参与人才会遵守 如果没有任何参与人有积极性不遵守这个协议 该协议是可以自动实施的 self enforcing 构成纳什均衡 否则 就不是纳什均衡 26 4纳什均衡是一种策略组合 每个参与人的策略是对其他参与人策略的最优反应 纳什均衡是博弈将会如何进行的 一致 consistent 预测 如果所有参与人预测特定纳什均衡会出现 那么没有参与人有动力采用与均衡不同的行动 27 纳什均衡 也只有纳什均衡 一致预测性 任何非纳什均衡的出现意味着至少有一个参与人 犯了错 或者是对对手行动的预测上犯了错 或者是 给定那种预测 在最大化自己的收益时犯了错 JeanTirole 28 纳什均衡的一致预测性 如果所有参与方都预测一个特定的博弈结果会出现 那么所有的参与方都不会利用该预测或者这种预测能力来选择与预测结果不一致的策略 即没有哪个参与方有偏离这个预测结果的愿望 因此这个预测结果最终就真会成为博弈的结果 一致 的意义在于各博弈方的实际行为选择与他们的预测一致 29 假设各参与方预测的策略组合相同 以及各参与方都是完全理性的 也就是不会犯错误的情况下 不可能预测任何非纳什均衡是博弈的结果 30 纳什均衡的立法意义 纳什均衡是一种稳定局面 给定别人遵守协议的情况下 没有人有积极性偏离协议规定 如果一个协议不构成纳什均衡 它就不可能自动实施 因为至少有一个人会违背这个协议 不满足纳什均衡要求的协议是没有意义的 31 立法的目标与其实施的结果要一致 必须使得参与博弈的各方达到纳什均衡 否则 立法就仅仅是正式或官方规则 而实际有效的支配人们的是潜规则 纳什均衡的立法意义 32 纳什均衡的立法意义 潜规则的要害是三方博弈 私下达成默契的双方 蒙骗正式制度和公正原则的代表 预测是博弈分析最基本的目的之一 纳什均衡的一致预测性质是其预测能力的基本保证 33 纳什均衡应用的局限性 我们对纳什均衡应用的广泛性和有效性不能过分夸大 尽管纳什均衡非常重要 但不是说学到了这种分析方法你就能预测所有博弈的结果 纳什均衡分析仅仅保证个体理性的智能人的博弈结果是唯一纯策略纳什均衡时的预测 纳什均衡分析并不能保证对所有博弈的结果都作出准确的预测 34 纳什均衡应用的局限性 现实中的博弈可能是下面三种情况之一 有许多博弈不存在纯策略纳什均衡 有些博弈是多重纳什均衡 博弈方可能是集体理性或有限理性 35 36 ExistenceofNashEquilibrium Nash在1950年证明 任何有限博弈 都至少存在一个NE Theorem Nash1950 Inthen playernormal formgameG S1 Sn u1 un ifnisfiniteandSiisfiniteforeveryithenthereexistsatleastoneNashequilibrium possiblyinvolvingmixedstrategies 37 Wilson 1971 证明 几乎所有有限博弈 都存在有限奇数个NE 包括纯策略NE和混合策略NE OddnessTheorem 38 纳什于1950年提出并证明了纳什定理纳什定理的主要内容为 在一个有n个参与人的策略式博弈G S1 Sn u1 un 中 如果n是有限的 且Si是有限集 i 1 n 则该博弈至少存在一个纳什均衡 在混合策略意义下 纳什定理 39 纳什定理的一些说明 纳什定理的证明要用到不动点定理 所谓不动点定理 是指一个定义在X X上的函数f x 集合X是非空的 闭的 有界的和凸的函数f是连续的则至少存在一个x 使得f x x x被称为不动点 40 纳什定理的一些说明 运用不动点定理证明纳什定理的主要步骤是设计一个策略组合空间上的一个映射 说明该映射的任何不动点都是一个纳什均衡使用不动点定理证明这个映射一定存在一个不动点 41 不动点 什么是不动点呢 想像有一个容器 里面充满了大量的小球 现在用一个勺子任意搅拌这容器里的小球 搅拌过后 每一个小球都重新占据了容器中的一个位置 如果某个小球的新位置和旧位置重合 那么这个小球就是一个不动点 数学里面有一类经典的定理 说的是这样的不动点总是存在的 无论你怎么搅拌 总有这样的不动点小球 以不变应万变 终点又回到起点 42 纳什定理的一些说明 映射选择的是n人最优反应对应其含义是 对于任意一个混合策略组合 p1 pn 对于每一个参与人i 求出I针对其他参与人混合策略 p1 pi 1 pi 1 pn 的最优反应 然后构建n个参与人最优反应对应的卡氏积 一个最优混合策略组合就是这一对应集的不动点 43 纳什定理的一些说明 因此只要证明前面的最优反应对应满足不动点定理条件就可以了 44 纳什均衡 NashEquilibrium 纳什均衡 占优均衡 重复剔除严劣策略均衡的关系定理a每一个占优均衡 重复剔除严劣策略均衡一定是纳什均衡 但反过来不一定成立 定理b纳什均衡一定不能通过重复剔除严劣策略方法剔除 下面对上述定理进行简要证明 45 两个定理的证明 首先证明定理b 纳什均衡一定不能通过重复剔除严劣策略方法剔除 记纳什均衡时的策略组合为s s1 si sn 用反证法 假定纳什均衡在重复剔除严劣策略均衡中被剔除掉 不失一般性 假设s1 是s 中被首先剔除的策略 则在S1中 一定存在一个尚未被剔除的策略s1 相对参与人1而言 严格优于s1 46 两个定理的证明 于是根据重复剔除严劣策略定义 对于此时所有尚未被剔除的其他参与人的任意一个策略组合s 1 s2 si sn 均成立ui s1 s 1 ui s1 s 1 47 两个定理的证明 由于前面分析中假设策略s1 是s s1 si sn 中首先被剔除的策略 因此在s1 被剔除的时候 s2 si sn 尚未被剔除 自然满足 式 这显然与s 是NE矛盾 48 下面开始证明定理a 重复剔除严劣策略均衡一定是纳什均衡 反证法 假设重复剔除严劣策略后 只剩下唯一的一个策略组合s s1 si sn 但却不是NE 则存在一个s1 S1 使得下列事实成立u1 s1 si sn u1 s1 si sn 但由于 s1 si sn 在中间过程中被剔除 而s 是被保留下来的唯一一个策略组合 两个定理的证明 49 按照严劣策略的定义 有u1 s1 si sn u1 s1 si sn 比较左右两式 可以得出矛盾 两个定理的证明 50 划线法 先找出自己针对其他博弈方每种策略或策略组合 对多人博弈 的最佳对策 即自己的可选策略中与其他博弈方的策略或策略组合配合 给自己带来最大得益的策略 这种相对最佳策略总是存在的 不过不一定唯一 然后在此基础上 通过对其他博弈方策略选择的判断 包括对其他博弈方对自己策略判断的判断等 预测博弈的可能结果和确定自己的最优策略 这就是划线法 51 图1 8 52 箭头法 箭头法对于理解博弈关系很有好处 是寻找相对稳定性策略组合的分析方法 对博弈中的每个策略组合进行分析 考察在每个策略组合处各个参与方能否通过改变自己的策略而增加得益 如能 则从所分析的策略组合对应的得益数组引一箭头到改变策略后策略组合对应的得益数组 最后综合对每个策略组合的分析情况 形成对博弈结果的判断 划线法和箭头法的结果是一致的 可以相互替代 53 小鸡博弈 thegameofchicken 汤姆和吉米进