博弈论教程PPT课件

1 博弈论 第一章导论 1 1什么是博弈论 GameTheory 1 1 1从游戏到博弈 游戏都有一些共同的特点 1 都具有一定的规则 2 都有一个结果 3 策略至关重要 4 策略和利益有相互依存性 2 一 博弈论概述 1 1 1博弈论的定义博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应结局 豪尔绍尼 JohnC Harsanyi 1994年诺贝尔经济学奖获奖致词 博弈论是关于策略相互作用的理论 博弈论研究人与人之间 斗智 的形式和后果 当人们利益存在冲突时 每个人所获得的利益不仅取决于自己所获取的行动 还依赖于其他人采取的行动 每个人都需要针对对方的行为选择作出对自己最有利的反应 3 3 博弈论的分类 1 合作博弈 研究人们达成合作时如何分配合作得到的收益 即收益分配问题 2 非合作博弈 研究人们在利益相互影响的局势中如何选决策使自己的收益最大 即策略选择问题 3 完全信息不完全信息博弈 参与者对所有参与者的策略空间及策略组合下的支付有充了解称为完全信息 反之 则称为不完全信息 4 静态博弈和动态博弈静态博弈 指参与者同时采取行动 或者尽管有先后顺序 但后行动者不知道先行动者的策略 动态博弈 指双方的的行动有先后顺序并且后行动者可以知道先行动者的策略 4 博弈的分类及对应的均衡 5 1 1 2一个非技本性的定义规定或定义一个博弈需要以下几个方面 1 参与人 Player 局中人 指博弈中的决策主体 他的目的是通过选择行动 或策略 以最大化自己的支付 效用 水平 参与人可以是自然人 团体 自然 上帝 作为虚拟的参与人 2 各个参与人各自可选择行动集 actionset Ai ai 是其可以采用的全部行动的集合 一个行动组合 actionproile 是一个由博弈中的n个参与人每个选取一个行动所组成的有序集a a1 a2 an 3 参与人i的策略 strategy 是如下的一项规则 给定其信息集 该策略决定在博弈的每一时点他选择何种行动 6 参与人i的策略集 strategyset Si si 是其可行策略的集合 策略组合 strategyprofile s s1 s2 sn 是由博弈的n个参与人每人选择一个策略所组成的一个有序集 4 参与人i的得益 支 payoff ui s1 s2 sn 表示这样的含义 在所有的参与人和自然都选择了各自的策略且博弈已经完成后 参与人i获得的效用 参与人i获得的期望效用 该期望效用是参与人i及其他参与人所选择的策略的函数 5 一个博弈的结果是指在博弈结束以后 建模者从行动 得益和其他变量的取值中所挑选出来的他所感兴趣的要素的集合 7 1 2几类经典的博弈模型1 2 1囚徒的困境 prisoners dilemma 这个例子本身就部分奠定了非合作博弈论的基础 8 1 2 2智猪博弈猪圈里有两头猪 大猪和小猪 猪圈的一头有一个猪食槽 另 头装有 个按纽 控制着猪食的供应 按一下就会有10单位的猪食进槽 但谁按谁就要付出相当于2单位猪食的成本 当猪食进槽时 若大猪先到 大猪可吃到9单位 小猪先到 则小猪可吃到4单位 大猪吃6单位 若两者同时到 叫大猪可吃7单位 小猪吃3单位 小猪 大猪 按 等 按 等 5 1 4 4 9 1 0 0 9 1 2 3性别战1 2 4斗鸡博弈 女 足球 芭蕾 男 足球 芭蕾 2 1 0 0 0 0 1 3 A B 进 退 进 退 3 3 2 0 0 2 0 0 10 1 2 5市场进入阻挠1 2 6猜硬币博弈1 2 7石头 剪子 布 默许 在位者 进入者 进入 不进入 斗争 40 50 10 0 0 300 0 300 猜硬币方 正 反 正 反 盖硬币方 1 1 1 1 1 1 1 1 石头 剪子 布 石头 剪子 布 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 A B 11 1 3博弈的结构和博弈的分类1 3 1博弈中的博弈方一 单人博弈 实际上是最优化问题 或者是一个参与人与 自然 的博弈 二 双人博弈 最常见 研究得最多的博弈 双人博弈中的两个博弈方之间并不总是相互对抗的 互补性问题 掌握信息较多的一方并不能保证获益大 个人追自身的最大利益并不能保证所得最优 三 多人博弈 可能存在 破坏者 与 联盟 12 1 3 2博弈中的策略博弈中独立决策 独立承担博弈结果的个人或组织称为博弈方 博弈中各博弈方的决策内容称为 策略 但应注意到并不是每个博弈方都有相同的可选略 如果在一个博弈中每个博弈方的策略数都是有限的 则称该博弈为有限博弈 否则就称为无限博弈 1 3 3博弈中的得益 支付 payoff 得益指在一个特定的策略组合下参与人得到效用水平 即各个博弈方从博弈中所获得的利益 13 一 零和博弈二 常和博弈三 变和博弈国内常见的博弈论参考书 1 经济博弈论 第二版 谢识予编著复旦大学出版社 20022 博弈论与信息经济学 张维迎著 上海三联书店 上海人民出版社3 博弈论 施锡铨著 上海财经大学出版社 20024 GameTheory 1991 D Fudenberg J Tirole中译本 中国人民大学出版社 14 第二章完全信息静态博弈 2 1基本分析思路和方法博弈可以有两种不同的表达方式 策略式 Normal 表述和扩展式 extensive 表述 从理论上来讲 这两种表述形式几乎是完全等价的 但从分析的方便性来看 策略式更适合表述静态博弈 在策略式表述中 所有参与人同时选择各自的策略 所有参与人选择的策略一起决定每个参与人的支付 这里的 同时选择 的是策略 而不是行动 15 这里的 同时 是一个信息概念 而不是一个时间概念 可以设想 参与人是处于不同的房间里 要求在彼此没有联络的情况下 选择一个按纽 通常还假设 所有的参与人都知道博弈的结构 知道他们的对手知道这一结构 知道他们的对手了解他们知道 如此直至无穷 也即博弈的结构是共同知识 更准确地 策略式表述给出 博弈的参与人集合 i 1 2 n 每个参与人的策略空间Si i 1 2 n 策略组合 s1 s2 sn 4 每个参与人的支付 收益 函数ui s1 si sn i 1 2 n 16 一般用G S1 S2 Sn u1 u2 un 表示策略式博弈 例 L M R U M D 4 3 5 1 6 2 2 1 8 4 3 6 3 0 9 6 2 8 S1 U M D S2 L M R 支付用矩阵表示 称为双矩阵博弈 参与人A 参与人B 17 2 1 1上策均衡 严格占优战略均衡 如果在某个博弈中 无论其他博弈方选择什么策略 一个博弈方的某个策略给他带来的支付始终不低于其他策略 则称该策略为这个博弈方的一个上策 优势策略Dominantstrategy 如果一个博弈的某个策略组合中所有策略都是各个博弈方自己的上策 则称这样的策略组合为该博弈的一个 上策均衡 例 囚徒的困境 18 2 1 2严格下策反复消去法 逐步剔除严格劣战略 例 L M R U M D 8 3 5 1 6 2 2 1 8 4 3 0 9 6 2 8 3 6 可以预测该博弈的合理结局为 U L 即参与人A 选择策略U 而参与人B选择策略L 19 2 2Nash均衡2 2 1Nash均衡的定义Nash均衡是指这样的策略组合 或剖面 为了极大化自己的收益 或效用 每一个参与人所采取的策略一定应该是关于其他参与人所采取的策略的最佳反应 因此没有一个参与人会轻率地偏离这个策略组合而使自己蒙受损失 20 定义在有n个参与人的博弈G S1 S2 Sn u1 u2 un 中 策略组合s s1 s2 sn 是一个Nash均衡 如果对于每一个i si 是给定其他参与人的选择 S i s1 si 1 si 1 sn 的情况下 第i个人的最优策略 即ui si s i ui si s i 对所有的i 或者用另一种表示方式 si 是下述最大化问题的解 si argui s1 si 1 si si 1 sn i 1 2 n因此 当且仅当没有一个参与人能从单方面背离某个策略组合的预见中增加自己的得益时 这个策略组合就是Nash均衡 Si Si 21 Nash均衡的哲学含义 设想n个参与人在博弈前规定每一个参与人选择一个特定的策略 s si s i 代表这个协议 要问在没有外力强制的情况下 是否有参与人有积极性不遵守该协议 如没有 则说明该协议是可以自动实施的 能够自动实施的协议就可以看作一个Nash均衡 例求下列博弈的Nash均衡 C R 得Nash均衡为 D R 用划线法可求 22 Nash均衡有强弱之分 上述定义中给出的是弱Nash均衡 一个Nash均衡是强的 如果给定其他参与人的策略 每一个参与人的选择是唯一的 即 s 是一个强Nash均衡 当且仅当对每一个i si si 总有 ui si s i ui si s i 如果一个Nash均衡是强的 则没有任何参与人在均衡策略和其他策略之间是无差异的 弱Nash均衡不是 如在以下博弈中 C1 C2 C3 R1 R2 R3 2 12 1 10 1 12 0 12 0 10 0 11 0 12 0 12 0 13 R1 C1 和 R1 C3 都是Nash均衡 但没有 一个强Nash均衡 23 本质上说 Nash均衡的概念对社会计划者和理论家施加了一个约束 使他们不能建议或者预测一种非均衡行为 博弈论可预测到 在均衡集较小的局势中 文化规范的重要性也小 2 2 2Nash均衡的一致性预测性质Nash均衡是参与人将如何博弈的 一致性 consistent 预测 如果所有参与人预测到一个特定的Nash均衡将出现 那么 没有人有兴趣作不同的选择 也只有Nash均衡具有这样的特征 参与人预测到均衡 参与人预测到其他参与人预到均衡 等等 24 对比之下 预测一个非Nash均衡的策略组合意味着至少有一个参与人会犯错误 尽管这样的错误确有可能出现 说Nash是一致性预测并不意味着Nash均衡一定是一个好的预测 但只有Nash均衡才有 一致性 预测的性质 重要结论 一种制度安排要发生效力必须是一种Nash均衡 Nash执行的 NashImplementation 否则 这种制度便不能 稳定 25 2 2 3Nash均衡与严格下策消去法命题2 1在博弈G S1 S2 Sn u1 u2 un 中 如果严格下策反复消去法排除了除 s1 s2 sn 之外的所有策略组合 那么 s1 s2 sn 一定是该博弈唯一的Nash均衡 命题2 2在博弈G S1 S2 Sn u1 u2 un 中 如果 s1 s2 sn 是G的一个Nash均衡 那么严格下策消去法一定不会将它消去 检验纳什均衡 囚徒困境 智猪游戏 26 性别战博弈 27 思考题 为何几乎所有的卡特尔都会遭到失败 28 几乎所有的卡特尔都会遭到失败 原因就在于卡特尔的协定 类似囚犯的攻守同盟 不是一个纳什均衡 没有成员有兴趣遵守 那么是不是不可能有卡特尔合作成功了 理论上 如果是无限期的合作 双方考虑长远利益 他们的合作是会成功的 但只要是有限次的合作 合作就不会成功 比如合作 次 那么在第九次博弈参与人就会采取不合作态度 29 2 3无限策略博弈分析和反应函数2 3 1Gournot 库诺特 双寡头竞争模型 Nash均衡最早的版本 1838年 30 设有两个参与人 分别称为企业1和企业2 每个企业的策略是选择产量 得益是利润 它是两个企业产量的函数 我们用qi 0 表示第i个企业的产量 总供给量为Q q1 q2 Ci qi cqi表示成本函数 P P q1 q2 a q1 q2 表示逆需求函数 售价 第i个企业的利润函数为 ui q1 q2 qiP q1 q2 Ci qi i 1 2即u1 q1 q2 q1P q1 q2 Cq1u2 q1 q2 q2P q1 q2 Cq2 31 q1 q2 是Nash均衡产量意味着 q1 argmaxu1 q1 q2 q1P q1 q2 C1 q1 q2 argmaxu2 q1 q2 q2P q1 q2 C2 q2 找出Nash均衡的一个办法是对每个企业的利润函数求一阶导数并令其为零 32 u1 q1 P q1 q2 q1P q1 q2 C1 q1 0 u2 q2 P q1 q2 q2P q1 q2 C2 q2 0上述两个一阶条件分别定义了两个反应函数 q1 R1 q2 q2 R2 q1 反应函数意味着每个企业的最优策略 产量 是另一个企业产量的函数 两个函数的交点就是Nash均衡q q1 q2 如下图 33 Cournot模型 q1 q2 R1 q2 R2 q1 NE O q1 q2 34 2 4混合策略和混合策略Nash均衡2 4 1严格竞争博弈和混合策略的引进一 严格竞争博弈 正面 反面 正面 反面 盖币方 猜币方 1 1 1 1 1 1 1 1 这个博弈实际上是一个零和博弈 一方所得即 另一方所失 该博弈没有纯策略的Nash均衡 例1 35 例2社会福利博弈 寻找工作游荡 救济 不救济 3 2 1 3 1 10 0 政府 流浪汉 这个博弈也不存在纯策略的Nash均衡 给定政府救济 流浪汉的最佳策略是游荡 给定流浪汉游荡 政府的最佳策略是不救济 上述博弈的显著特征是 每一个参与人都想猜透对方的策略 而每 个参与人又都不想让对方猜透自己的策略 所以此类博弈中都不存在 纯策略 Nash均衡 36 对猜硬币博弈来说 设出正面的概率友p 则出反面的概率为1 p 如果p 1 2 且猜币方全猜正面 他的期望得益为 p 1 1 p 1 2p 1 0即从平均来讲 这时猜币方一定是赢多输少 而如果p 1 2 猜币方也可通过全猜反面而占优 只有p 1 2 对方无法占便宜 从而双方各选1 2作为正反面的概率也就成了一种 均衡 二 混合策略和混合策略Nash均衡定义在博弈G S1 S2 Sn u1 u2 un 中参与人的策略空间为Si si1 si2 sik 则参与人i以概率分布 i i1 ik 随机地在其k个可选策略中选择的 策略 称为 个混合策略 37 其中0 ij 1 且 ij 1纯策略可以理解为混合策略的特例 如纯策略si1可以看作是混合策略 i 1 0 0 我们用 i表示参与人i的混合策略空间 i i用 1 2 n 表示n个博弈方的混合策略组合 用 i表示混合策略组合空间 在纯策略情形下 ui ui s ui u1 ui un 对任何一个给定的纯策略组合 s s1 s2 sn ui取 确定值 与混合策略相伴的是得益 支付 的不确定性 这时 38 ui ui 1 i n ui i i 表示参与人i的期望效用 它可定义为ui i i j sj ui s s S j 1 n 其中 j sj 是混合策略 j赋予纯策略sj的概率 以两人博弈为例 S1 s11 s12 s1p S2 s21 s22 s2q 如果参与人1相信参与人2的混合策略为 2 21 22 2q 那么参与人选择纯策略s1p的期望效用为 2ju1 s1p s2j q j 1 39 参与人选择混合策略 1 11 12 1p 的期望效用 得益 为 u1 1 2 1k 2ju1 s1k s2j p k 1 q J 1 1k 2ju1 s1k s2j K 1 J 1 p q 类似地有u2 1 2 1k 2ju2 s1k s2j k 1j 1 pq 例如对博弈 LMR U4 35 16 2 M2 18 43 6 D3 09 62 8 参与人2 B 参与人1 A 双矩阵博弈 40 下面重新定义Nash均衡定义在博弈G S1 S2 Sn u1 u2 un 中 混合策略组合 1 i n 是一个Nash均衡 如果对任一i 有 ui i i ui i i 对任 i i这个定义也可以写为 定义对在博弈G S1 Sn u1 un 中的混合策略组合 1 i n 如果对所有的参与人i 有ui i i ui sik i 对每一sik Si成立 则称 为博弈G的Nash均衡 41 2 2双矩阵博弈的Nash均衡的求法例1求双矩阵博弈的混合策略Nash均衡 其中A B 解 设 1 x 1 x 2 y 1 y 为Nash均衡点 u1 1 2 xAy 3xy 2x 1 y 4 1 x 1 y x 5y 2 4 4y 如果y2 5 则在x 1时达到最大值 类似地u2 1 2 xBy y 2x 1 4 3x 32 04 21 34 42 要使上式取最大值 应取y 故两者的交点为 2 5 1 2 故混合策略的Nash均衡为 2 5 3 5 1 2 1 2 相应的得益为 U1 2 4 u2 2 5 0 0 x 1 2 0 1 x 1 2 1 1 2 x 1 x y 2 5 1 2 43 例2社会福利博弈 寻找工作流浪 救济 不救济 3 2 1 3 1 10 0 流浪汉 政府 这个博弈不存在纯策略Nash均衡 设政府的混合策略为 G x 1 x 流浪汉的混合策略为 L y 1 y 则政府的 期望效用为uG G L x 5y 1 y 而流浪汉的期望效用 为 uL G L y 2x 1 3x 用类似上例的方法 如图 可得x 1 2 y 1 5 1 1 2 1 0 2 y x 44 例3审计博弈 猜迷博弈的变种 逃税不逃税 检查a C F a Fa C a 不检查0 0a a 纳税人 税收机关 这里a是应纳税款 C是检查成本 F是罚款 设x表示检查的概率 y表示逃税的概率 给定y 选择检查和 不检查的期望得益分别为 uG 1 y yF a C和uG 0 y a 1 y 令uG 1 y uG 0 y 得y C a F 类似地 给定x 纳 税人选择逃税和不逃税的得益 up x 1 a F x和up x 1 a 解up x 1 up x 0得x a a F 由此 x y 45 2 4 2多重均衡博弈和混合策略以上引进的混合策略Nash均衡及其分析方法 是以没有纯策略Nash均衡的严格竞争博弈为基础的 下面讨论有多个纯策略Nash均衡的博弈 例1性别战 芭蕾足球 芭蕾2 10 0 足球0 01 3 女 男 这个博弈有两个纯策略Nash均衡 芭蕾 芭蕾 和 足球 足球 还可以求出一个混合策略均衡 3 4 1 4 1 3 2 3 46 例2 分级 协调博弈 大小 大2 2 1 1 小 1 11 1 A厂 B厂 该博弈也有两个纯策略Nash均衡 大 大 和 小 小 和一个混合策略Nash均衡 2 5 3 5 2 5 3 5 47 2 4 3混合策略和严格下策消去法在混合策略下 下列结论仍然成立 如何博弈方都不会采取任何严格下策 严格下策消去法不会消去任何Nash均衡 如果经反复消去后留下的策略组合是唯一的 那它一定是Nash均衡例 LR U2 0 1 0 M0 00 0 D 1 02 0 参与人1 参与人2 参与人1的策略M不是在纯策略下 的严格下策 但如果参与人1采用混 合策略 1 2 0 1 2 不管对方如何 行动 总能保证期望得盖1 2 从而M 在混合策略意义下是严格下策 48 2 5Nash均衡的存在性2 5 1Nash定理 Nash 1950 每一个有限博弈至少存在一个Nash均衡 混合策略意义下 2 5 2Nash定理的意义及其扩展 上策均衡 重复剔除上策均衡 纯策略Nash均衡 混合策略Nash均衡 49 其它存在性定理定理 Debreu 1952Glicksberg 1952Fan 1952 考虑一个策略型博弈 其中各参与人的策略空间Si为欧氏空间中的非空紧凸子集 得益函数ui关于策略组合s为连续的且关于参与人i的纯策略si为拟凹的 那么博弈存在一个纯策略的Nash均衡 定理 Glicksberg 1952 考虑策略型博弈 其参与人的策略空洵Si是度量空间中的非空紧子集 如果得益函数ui为连续函数 那么博弈至少存在一个混合策略的Nash均衡 50 2 6Nash均衡的选择和分析方法的扩展2 6 1多重Nash均衡的博弈分析一个博弈可能有多个 甚至是无穷多个 Nash均衡 如考虑两个人分一块蛋糕 每人独立地提出自己要求的份额 设x1为参与人1要求的额 x2为参与人2要求的份额 如果x1 x2 1 每个人得到自己的份额 如果x1 x2 1 两个人所得为零 这时 任何满足x1 x2 1的点 x1 x2 都是Nash均衡点 但x1 x2 1的点不是 x1 x2 X1 x2 1 O 1 1 51 在有多个Nash均衡时 要求所有的参与人预测同一Nash均衡是非常困难的 均衡集较大意味着文化影响较大 如在分蛋糕的博中 0 5 0 5 的均衡经常出现 这是一个 焦点 均衡 保证一个Nash均衡出现的另一个方法是参与人在博弈开始前进行不化成本的 廉价磋商 cheaptalk 尽管我们无法保证磋商会达成一个协议 即使达成了协议也不一定被遵守 例如协调博弈 coordinationgame LR U9 90 0 D0 01 1 参与人1 参与人2 52 如果两人在博弈前相遇 参与人1之将选择U 而参与人2告之将选择L 则 U L 这 Pareto上策均衡 将有很大可能出现 在 性别战 博弈中 如果事先打个电话预约 则可先定某一均衡 一 Pareto上策均衡例战争与和平博弈 战争和平 战争 5 58 10 和平 10 810 10 国家1 国家2 该博弈有两个纯策略Nash 均衡 战 战 与 和 和 而 和 和 是Pareto上策均衡 53 二 风险上策均衡例该博弈有两个纯策略Nash均衡 U L 和 D R U L 为Pareto上策均衡 但 D R 为 风险占优均衡 人们通常比较倾向接受预测风险较小的结局 LR U9 90 8 D8 07 7 参与人1 参与人2 54 在本例中 策略D比策略U更 安全 一些 设参与人1取U 而参与人取R的概率为y 则u1 9 1 y 0 y 9 9y参与人1取D时 u1 8 1 y 7y 8 y当y 1 8时 9 9y 8 y 如果参与人1认为参与人2取R的可能性大于1 8 他宁愿取D 因此 从风险占优的角度看 D R 优于 U L 例猎鹿博弈 猎鹿猎兔 猎鹿3 30 1 猎兔1 01 1 猎手1 猎手2 是介于 囚徒的困境 与 协调博弈 之间的博弈 它有两个Nash均衡 鹿 鹿 和 兔 兔 但 兔 兔 是 风险占优的 55 三 聚点均衡 focalPointsEquilibrum 四 相关均衡Nash均衡通常在参与人独立地选择自己的策略范围下才有意义 实际上不少博弈中参与人之间选择的策略是相关的 如与一个 信号装置 有关 如古代战将单打独斗不相上下时 鸣金收兵 例 Aumann 1974 相关均衡他证明如果参与人可以根据某个共同观测到的信号选择行动 就可能出现 相关均衡 56 如博弈 LR U5 10 0 D4 41 5 参与人1 参与人2 该博弈有三个Nash均衡 U L D R 和混合策略 1 2 1 2 1 2 1 2 1 2 相应的得益为 5 1 1 5 2 5 2 5 但假若双方约定抛一枚硬币 正面朝上则1选U 2选L 反面朝上别1选R 2选D 此时每人的期望效用为3 大于混合Nash均衡的期望值 这时 按上述规则行动是一 个Nash均衡 57 更重要的是 Aumann证明 如果每个人收到不同但相关的信号 每个人都能得到更高的期望效用 设想由第三方掷骰子特定方法决定两人的行动 如1 2点出现 则1选U 3 6点出现则1选D 对参与人2则 如果1 4点出现 选L 5 6点出现则选R 再假定第三方只告诉参与人选择什么行动 而不透露什么点数 这时 U R 不会出现 保证三个结果 U L D L D R 各以1 3的概率出现 这时双方的期望得经均为10 3 但 信号装置 是有成本的 58 例三人博弈的得益矩阵为 LRLRLR 乙乙乙 U2 1 30 0 0U2 2 20 0 0U0 1 00 0 0 D1 1 11 0 0D2 2 02 2 2D1 1 01 0 3 甲 甲 甲 ABC 丙 该博弈有唯一的Nash均衡 D L A 相应的得益 1 1 1 但可以建立一个抛均匀硬币的信号装置 甲 乙可以看到结果 甲 看到正面取U 反面取D 乙 看到正面取L 反面取D 丙 总是取B 丙不能看到硬币正反 这时最终得益为 2 2 2 59 2 6 2共谋和防共谋博弈一 多人博弈中的共谋问题例 LRLR U0 0 10 5 5 0U 2 2 0 5 5 0 D 5 5 01 1 5D 5 5 0 1 1 5 AB 丙 甲 甲 乙 乙 易用划线法知 U L A 与 D R B 是纯策略Nash均衡 前者在Pareto意义下优于后者 而后者在风险上优于前者 如不考虑串通结果应为 U L A 但如果考虑甲 乙串通取 D R 则结果应为 D R B 60 二 防共谋均衡防共谋均衡是两个以上博弈方的博弈中 博弈方之间在Pareto上策均衡中进行合作的思想的扩展 定义 如果一个博弈的某个策略组合满足下列条件 没有任何博弈方的串谋会改变博弈的结果 给定选择偏离的博弈方有再次偏离的自由时 没有任何两个博弈方的串谋会改变博弈的结果 依次类推 直到所有博弈方都参加的串谋也不会改变博弈的结果 则称该策略组合为一个防共谋均衡 61 第三章完全信息动态博弈3 1动态博弈的表示法和特点定义与博弈树博弈的展开式所包含的信息和内容 参与人的集合 记为i 1 2 n 用N代表虚拟的参匀人 自然 行动的次序 即谁在什么时候行动 参与人的行的空间 即轮到某参与人行动时 他从该时刻的纯策略空间中选取什么策略 当参与人作出他们的行动决策时 他所观测到或他所了解到的信息 即他在此时获得的信息集合 参与人的得益 支付或效用 它们是已知行动的函数 在任何外生事件的概率分布 62 例房地产开发博弈有两个房地产开发商 分别为参与人1 记为A和参与人2 记为B 在某地开发房地产 但该地的房地产需求状况是不确定的 假定该博弈的行动顺序如下 1 开发商1先行动 选择开发或不开发 2 在1决策后 自然 选择需求的大小 3 开发商2在观测到1的决策和市场的需求后 再决定开发或不开发 如下图 63 房地产开发博弈 A N N B B B B 开发不开发 需求大需求小需求大需求小 开发不开发开发不开发开发不开发开发不开发 4 4 8 0 3 3 1 0 0 8 0 0 0 1 0 0 单位 百万元 hA 1 hN 1 hN 2 hB 1 hB 2 hB 3 hB 4 h表示信息集 64 上述博弈树给出了有限博弈的几乎所有信息 博弈树必须满足下列规则 每一个结 node 至多有一个其他结直接位于它的前面 在博弈中没有一条路径可以使决策集与自身相连 每一个结是唯一初始结的后续结 即博弈树必须有初始结 每个博弈树 正好 只有一个初始结 多于一个可以用 自然 连接 65 不允许出现的情况 由以上规则 对于博弈树中的每一个终点结 我们 完全可以确定从初始结到终点结的路径 同时也展示了博弈的动态过程 信息集 博弈树上的所有决策集分割成不同的信息集 我们用h H来表示这个信息 如果一个信息集包含结x 我们就可以将该信息集记为h x 如果一个信息集只包含一个结 这是最简的情况 我们主要关心的是一个信息集包含不止一个结 假设x与x h x 则恰好拥有信息h x 并正在选择自己行动的参与人其实对自己究竟是处于x还界x 是不确定的 66 要求 如果x h x 则x与x 应该由同一个参与人采取行动 且可以选择的策略空间相同 A x A x 由此可以将信息集h上的行动集记为A h 如果博弈树的所有信息集都是单结的 则称该博弈为完美 perfect 息博弈 无虚线连接 而完全 complete 信息博弈是指得益函数和纯策略空间均为博弈各方的共同知识 完全信息可以是完美的也可以是不完美的 3 2展开型博弈的策略与均衡一 行为策略在策略型博弈中 参与人的策略是进行博弈的计划 或打算 的详细集合 而在展开型博弈中参与人的策略必须确定在该参与人的每一个决策集上所采取的行动 又结与信息集紧密相连 对于参与人i 基于信息hi的行动的 67 的全体记汉A hi 如果令Hi表示参与人i的信息集的集合 则Ai A hi 就是参与人i的所有行动的集合 参与人i的一个纯策略是从Hi到Ai的一个映射si 对每一个hi Ai si hi Ai 所有这些si的全体记为Si 即的的纯策略空间Si 由此 Si A hi hi Hi hi Hi 68 例参与人2有两个策略集 相应地也有两个信息集A h2 1 A h2 2 左 右 1 2 2 1 1 1 1 上 下 左 右 左 右 ABABCDCD h2 1 h2 2 h1 1 h1 2 h1 3 69 其中H2 h2 1 h2 2 参与人2的纯策略空间为 S2 A h2 1 Ah2 2 左 右 左 右 左 左 左 右 右 左 右 右 其中纯策略 左 左 表明 当1取 上 时 2取 左 当1取 下 时 2取 左 参与人1有三个信息集H1 hi i i 1 2 3 1的纯策略空间为 S1 A h1 1 A h1 2 A h1 3 上 下 A B C D 共8种纯策略 一般地 参与人I的纯策略空间的纯策略数目为 Si A hi hi Hi 70 展开型博弈中纯策略是由信息集与行动集定义的 与静态博弈不同 静态博弈中采取纯策略与采取某行动是一个意思 纯策略组合 剖面profile 是由参与人各自的纯策略空间中的任一纯策略构成的组合 在任一纯策略组合s下 总可以从初始结开始 沿着博弈树的某条路径 path 达到s相应的终点结 有一个事实非常重要 s中有些信息集在博弈树的这条路径上 我们称这些信息集是s的路径 path 当然也可能存在s中某些信息集不在此路径上 71 定义了纯策略的得益函数后 我们就可以定义展开型博弈的Nash均衡 定义策略组合s s1 si sn 是展开型博弈的一个Nash均衡 如果对每一个i si 最大化ui si s i 即si argmaxui si s i 对任一i策略型博弈的混合策略实际上是纯策略空间上的概率分布 因此展开型博弈中参与人i的混合策略也可以看作是其纯策略空间Si上的任一概率分布 参与人的每一个特定的纯策略si相当于一本指导说明书 书中每一页表示到了一个特定的信息集hi 在该页上告诉i如何行动 许多的si相当于许多的说明书 Si表示这些说明书的全体 混合策略相当于i以一定的概率分布随机地抽取一本说明书 Luce Raiff 72 参与人i的行为策略bi定义为 bi hi Hi A hi 其中 表示某集合是的概率分布 行为策略的Nash集合是这样一个策略组合 它使得没有一个参与人可以通过不同的使用策略而增加自己的得益 注意 行为策略是在A hi 上随机化 而混合策略则是在Si 即A hi 的乘积空间 上的随机化 73 定理 Kuhn 1953 在完美回忆博弈中 混合策略与行为策略是等价的 完美回忆指没有参与人会忘记以前知道的信息 例下列展开型博弈不具备完美回忆 1 2 2 1 1 1 1 A B L R L R CDCDCDCD 74 现在重新考虑上述房地产开发博弈 以解释信息集的概念 其中开发商B是在知道A的选择和自然的选择之后决策的 如果B在决策时并不知道自然的选择 则有博弈树 A N N B B B B 开发不开发 大 1 2 小 1 2 大 1 2 小 1 2 开发不开发开发不开发开发不开发开发不开发 hB hB hA 75 另一种情况就则B知道自然的选择 但不知道A的选择 这时博弈树如下 A N N B B B B 开发不开发 大小大小 开发不开发开发不开发开发不开发开发不开发 5 5 0 8 3 3 1 0 0 8 0 0 0 1 0 0 76 上述房地产开发博弈还有另一种表示 N A B B A B B 大 1 2 小 1 2 开发不开发开发不开发 开发不开发开发不开发开发不开发开发不开发 77 有了信息集的概念 展开式表示也可以用来表示静态博弈 如 囚徒的困境 博弈可以表示为 1 2 2 坦白不坦白 坦白不坦白坦白不坦白 5 5 0 8 8 0 1 1 78 或者 2 1 1 坦白不坦白 坦白不坦白坦白不坦白 5 5 0 8 8 0 1 1 注意 得益向量的次序与参与人决策的顺序一致 79 同样地 展开型博弈也可以用策略式来表示 如展开型博弈 1 2 2 T B LRLR 2 2 4 0 1 0 3 1 可以表示为 LR T2 24 0 B1 03 1 参与人1 参与人2 80 展开型博弈 1 2 2 T B LRlr 2 2 4 0 1 0 3 1 可以表示成 LllrRlRr T2 22 24 04 0 B1 03 11 03 1 参与人1 参与人2 81 同样地 展开型博弈也可以用策略式来表示 例摊牌博弈 N 1 1 2 2 黑红 0 5 0 5 加注r摊牌f摊牌F加注R 放弃P对抗M放弃P对抗M 1 1 1 1 1 1 2 2 1 1 2 2 y2x2 82 摊牌博弈的策略空间分别为 S1 R F r f Rr Rf Fr Ff S2 M P 可表示为策略型 MP Rr0 01 1 Rf0 5 0 50 6 Fr 0 5 0 51 1 Ff0 00 0 参与人1 参与人2 注 u1 Rf M 2 1 2 1 1 2 0 5u2 Rf M 2 1 2 1 1 2 0 5其中R r 表示加注 F f 表示摊牌 M表示对抗 P表示放弃 该博弈有唯一的Nash均衡 1 2 1 3 Rr 2 2 Rf 2 3 M 1 3 P 它与信念体系一起构成序贯均衡 83 习题1 写出下列博弈的策略型表示 1 2 1 2 2 UD LRLR 2 1 0 0 1 1 3 2 1 2 2 UD LRLR 2 1 0 0 1 1 3 2 84 3 N 1 1 2 2 1 32 3 Y1z1x1w1 2 6 5 6 a2b2a2b2 9 0 0 3 9 5 0 3 85 3 3子博弈与子博弈完美Nash均衡在原则上适用所有的博弈 但对于预测参与人的行为来说 Nash均衡可能并不是一个合理的预测 如房地产博弈 A B B 开不 开不开不 3 3 1 0 0 1 0 0 的策略式表示为 开 开 开 不 不 开 不 不 开 3 3 3 31 01 0 不0 10 00 10 0 参与人B 参与人A 86 由画线法可得三个纯策略Nash均衡 不开发 开发 开发 开发 不开发 不开发 开发 不开发 开发 但 中B的策略是不合理的 这个威胁是不可置信的 中B的策略 不开发 不开发 也不合理 因为若A不开发 B显然应该开发 只有 是一个合理的均衡 2 3 1子博弈定义一个展开式博弈的子博弈G由一个决策结x和所有该决策结的后继结T x 包括终点结0组成 它满足下列条件 x是一个单点信息结即h x x 对于所有的x T x 如果x h x 则x T x 87 例房地产博弈 A B B 开 不 开不开不 有子博弈 和子博弈 X X B B x X 开不 开不 88 1 2 2 UD LRLR 无 真 子博弈 1 2 2 3 3 3 3 UD LRLR CDCDCDCD 参与人2的信息集不能作为子博弈的初始结 否则将导致3的信息被分割 89 3 3 2子博弈完美动态博弈定义展开式博弈的略组s s1 si sn 是一个子博弈完美Nash均衡 如果满足 1 它是原博弈的Nash均衡 2 它在每一个子博弈上给出Nash均衡 混合策略的子博弈完美Nash均衡可类似定义 简单地说 子博弈完美Nash均衡要求均衡策略的行为规则在每一个信息集上都是最优的 包括均衡路径和非均衡路径 定义展开型博弈的一个策略组合称为子博弈完美Nash均衡 如果对于该博弈的每一个子博弈 该策略组合都是Nash均衡 90 例 Selten 1 2 2 2 3 1 0 0 UD LR LR U2 22 2 D3 10 0 该博弈有两个Nash均衡 U R 和 D L 但Nash均衡 U R 从动态博弈的观点来看是不合理的 因为它依赖于参与人2取R这一 空头威胁 91 3 3 3逆向归纳法逆向归纳法包括以几个步骤 从博弈树的终点结出发 追踪到紧接着它的前面的结 在步骤 的中到达的每一个基本结上 通过对该决策结出发到达的每一个终点结上参与人得到的得益求最佳行动 在步骤 中检验过每一个基本决策结中所引起的所有非最优枝删去 如达到树根 则中止 否则回到 1 对每一个参与人 将该参与人在每一个决策结上的最优策略一起收集起来就构成了最佳策略 92 例用逆向归纳法求下列博弈的子博弈完美Nash均衡 1 2 2 1 LR ABCD EF 2 0 1 1 0 1 2 3 1 2 2 h1 h1 h2 h2 解为 R E B D 定理在一个具有完美信息的有限博弈中 使用逆向归纳法所选择的策略组合总是Nash均衡 93 例开金矿博弈 相机选择问题ContingentPlay 乙 甲 借不借 钱 分不分 利益 1 0 2 2 0 4 乙 1 0 0 4 1 0 0 4 考虑法律保障 保障不足 打不打 官司 94 3 4几个经典的动态博弈模型3 4 1Stackelberg寡头竞争模型该模型可以看作是子博弈完美Nash均衡的最早版本 其中企业1 称为领头企业 先选择产量q1 Q1 0 企业2 称为尾随企业 观测到q1后选择自己的产量q2 Q2 0 这时企业2的策应该是从Q1到Q2一个反应函数 S2 Q1 Q2 而企业1的策略就是简单地选择产量q1纯策略均衡结果是产出向量 q1 s q1 支付函数为 ui q1 s2 q1 由于产量是一个连续变量 故不能作出博弈树 95 96 假定逆需求函数为P a q1 q2 两个企业有相同的不变单位成本c 0 则支付 利润 函数为 ui q1 q2 qi P c i 1 2我们可以用逆向归纳法求解这个博弈的子博弈完美Nash均衡 假定q1已经选定 企业2的问题是 maxu2 q1 q2 q2 a q1 q2 c 最优化一阶条件为 s2 q1 1 2 a q1 c 因为企业1预测到企业2将根据s2 q1 选择q2 企业1在第一阶段的问题是 Maxu1 q1 s2 q1 q1 a q1 s2 q1 c 解一阶条件得 q1 0 5 a c 将q1 代入s2 q1 得 q2 s2 q1 0 25 a c 先动优势 97 委托 代理 Principle Agents 理论1 无不确定性的情形 1 2 2 0 0 委托不委托 接受拒绝 努力偷懒 0 0 12 2 7 1 98 2 有不确定性但可监督的情形 1 2 N N 2 委托不委托 接受拒绝 努力偷懒 高产低产高产低产 0 9 0 1 0 1 0 9 0 0 0 0 16 2 6 2 18 1 8 1 99 银行挤兑模型 设两个投资者各具某银行存款D 银行将这两笔存款用于一长期项目 如果在项目到期之前银行被迫抽回资金 仅可挽回2r 其中D r D 2 若银行同意到期后再收回 连本带利将得到2R R D 1 2 2 1 2 2 YN YNYN YN YNYN r r D 2r D 2r D D R R 2R D D D 2R D R R Y 提取 N 不提日期1为投资到期之前 日期2为之后 100 3 4 2讨价还价博弈 Rubinstein 1982 假定两个人分一块蛋糕 参与人1先出价 参与人2可以选择接受或拒绝 如果1接受博弈结束 蛋糕按1的方案分配 如果1拒绝 1再出价 如此直下去直到一个参与人的出价被另一个人接收为止 这是一个无限期完美信息博弈 参与人1在时期1 3 5 出价 参与人2在时期2 4 6 出价 用x表示1的份额 1 x表示2的份额 x1和 1 x1 分别是1出价时1和2的份额 x2和 1 x2 分别表示2出价时参与人1和参与人2的份额 假定参与人1和参与人2的贴现因子分别为 1和 2 则如果在时期t博弈结束 参与人1和参与人 2的支付贴现值分别是u1 1xi和u2 2 1 xi t 1t 1 101 如果博弈是有限期的 可以使用逆向归纳法求解子博弈完美Nash均衡 T为期限 设T 2 参与人2出价 如果他提出x2 0 1只有接受 因为他巳无出价机会 由于2在T 2时得到1单位相当于在t 1时得到 2单位 所以1在t 1时出价1 x1 2时2会接受 这时子博弈完美Nash均衡的结果是 1 2 2 设T 3 设1出价x 1 因为 在T 2时的1单位等于t 2时的 1单位 如果2在t 2时出价x2 1 1 2 1 2 x1 AR 出x2 AR 出x3 x1 1 x1 1x2 2 1 x2 102 参与人1会接受 参与人2在t 2时的1 1单位相当于t 1时的 2 1 1 单位 如果参与人1在t 1时出价1 x1 2 1 1 参与人2会接受 因此 子博弈完美的唯一结果为 x 1 2 1 1 类似地 T 4时的子博弈完美Nash均衡的结果是 x 1 2 1 1 1 2 T 5时的子博弈完美的结果是 x 1 2 1 1 1 2 1 1 当 1 2 0时 x 1 当 2 0时仍为x 1 103 但当 1 0 2 0时结果为x 1 2 如果 1 2 1 即双方都有无限的耐心 那么当T 1 3 5 时结果为x 1 当T 2 4 6 时结果为x 0 后动优势 定理 Rubinstein 1982 在无限期讨价还价博弈中 唯一的子博弈完美Nash均衡的结果是 x 1 2 1 1 2 如果 1 2 x 1 1 无限期讨价还价的子博弈完美Nash均衡的结果决定于参与人的贴现因子 耐心程度 104 证明 T 博弈无最后阶段 但参与人1出价的任何一个阶段开始的子博弈等价于从t 1开始的整个博弈 我们可以应用有限阶段逆向归纳法寻找子博弈完美均衡 假定t 3 1出价 1能得到的最大份额是M1 对1而言t期的M1等价于t 1期的 1M 故2知道在t 1期的任何x2 1M的出价将被1所接受 因此2出价x2 1M 自得1 1M 又对2而言t 1期的1 1M等价于t 2期的 2 1 1M 故1可在t 2期出价x1 1 2 1 1M 因为从t 2期能得到的最大份额一定与从t期开始的博弈完全相同 故我们有 x1 M 1 2 1 1M 解得M 1 2 1 1 2 且结果是唯 的 105 承诺行动与子博弈完美均衡例法律是的要胁诉讼 设原告为P 被告为D P D P 0 0 不指控 指控 提出要求 拒绝接受 起诉放弃 s c s x c p x d c 0 其中指控成本为c如果决定指控 P要求D支付s 0以 私了 P的起诉成本为d 如果P以概率 赢得x 则 x p 106 3 6动态博弈分析的问题和扩展3 6 1逆推归纳法的问题例 1 2 3 n AAAA DDDD 1 1 1 1 2 1 2 1 2 1 3 1 3 1 3 1 n 1 n 1 n 2 2 2 如果参与人的数目n比较小 才能预测到最后 共同富裕 的结果 2 2 2 当n相当大时 情况就会发生变化 设每个参与人取A的概率为0 9 n 20 则0 9 0 314 较小的概率可能动摇1取A的决心 19 107 例 1 2 1 2 1 A1A2A3A4A5 D1D2D3D4D5 1 0 0 1 3 0 2 4 6 3 5 5 这是一个两人轮流行动的博弈 如果使用后退归纳法 则解宣布在每一个决策结上行动的参与人应采取行动Di i 1