博弈论讲义完整版.ppt

博弈论 GameTheory 前言 本课程的教学安排本课程的主要内容博弈论概述本课程的教学目的 讲课及考核方式 学时 学分 32 2预修课程 微观经济学 考核方式 作业 30分答卷 70分共计 100分 预期时间安排 时间安排 4月27日开始每周四节课时 32学时 教材及参考书 教材 谢识予 经济博弈论 复旦大学出版社主要参考书 1 张维迎 博弈论与信息经济学 上海三联书店 上海人民出版社 1996 2 JeanTirole 博弈论 中国人民大学出版社 博弈论与经济学1 1经济学 新古典经济学 1 研究内容 稀缺资源的有效配置的 人的经济行为 2 理性人 3 研究对象 价格制度 4 两个基本假定 市场参与者的数量足够多从而市场是竞争性的 参与人之间不存在信息不对称问题 第一章导论 第一章导论 1 2博弈论现实环境往往不能满足上述两个基本假定 不完全竞争市场和信息不对称使得博弈论逐渐成为经济学的基石 第一章导论 1 2 1博弈论的发展历史 1 一般认为 博弈论始于1944年冯 诺依曼 VonNeumann 和摩根斯坦恩 Morgenstern 的 博弈论和经济行为 2 50年代 合作博弈发展到顶峰 代表性的研究成果是Nash 1950 和Shapley 1953 的 讨价还价 模型 3 Nash在1950年和1951年发表的两篇文章代表着非合作博弈的兴起 其间Tucker 1950 定义了 囚徒困境 prisoners dilemma 4 泽尔腾 selten 1965 提出了 子博弈精炼纳什均衡 概念 把动态分析方法应用于博弈论中 第一章导论 5 海萨尼 Harsanyi 1967 1968 把不完全信息的概念引入博弈论的研究 6 80年代动态不完全信息博弈的发展 1 2 2博弈论在经济学中的应用Nash 泽尔腾 海萨尼分享了1994年诺贝尔经济学奖 在经济学的个体研究 信息问题 时序问题等方面 博弈论得到了最广泛的应用 第一章导论 博弈论 gametheory 定义 研究决策主体的行为在直接相互作用时 人们如何进行决策 以及这种决策如何达到均衡 开始于 冯 诺曼 VonNeumann 与摩根斯坦 Morgenstern 在1944年合作的 博弈论与经济行为 TheTheoryofGamesandEconomicBehaciour 第一章导论 注意两点 1 是两个或两个以上参与者之间的对策论当鲁滨逊遇到了 星期五 石匠的决策与拳击手的决策的区别 第一章导论 2 理性人假设理性人是指一个很好定义的偏好 在面临定的约束条件下最大化自己的偏好 博弈论说起来有些绕嘴 但理解起来很好理解 那就是每个对弈者在决定采取哪种行动时 不但要根据自身的利益的利益和目的行事 而且要考虑到他的决策行为对其他人可能的影响 通过选择最佳行动计划 来寻求收益或效用的最大化 囚徒困境 第一章导论 囚徒困境 案例1 囚徒困境 纳什均衡 囚徒A 囚徒B 坦白 抵赖 坦白 抵赖 8大于 100大于 1 坦白 坦白 是纳什均衡 第一章导论 囚徒困境 设定 1 每个局中人都知道博弈规则和博弈结果的支付矩阵 2 每个局中人都是理性的 个人理性和个人最优决策 3 不能 串通 第一章导论 囚徒困境 通俗地讲 纳什均衡的含义是 给定别人战略情况下 没有任何单个参与人有积极性选择其他战略 从而没有人有积极性打破这种均衡 第一章导论 囚徒困境 一只河蚌正张开壳晒太阳 不料 飞来了一只鸟 张嘴去啄他的肉 河蚌连忙合起两张壳 紧紧钳住鸟的嘴巴 鸟说 今天不下雨 明天不下雨 就会有死蚌肉 河蚌说 今天不放你 明天不放你 就会有死鸟 谁也不肯松口 有一个渔夫看见了 便过来把他们一起捉走了 第一章导论 囚徒困境 两个寡头企业选择产量的博弈 如果两个企业联合起来形成卡特尔 选择垄断利润最大化的产量 每个企业都可以得到更多的利润 给定对方遵守协议的情况下 每个企业都想增加产量 结果是 每个企业都只得到纳什均衡产量的利润 它严格小于卡特而产量下的利润 请举几个囚徒困境的例子 第一章导论 囚徒困境 同样的情形发生在 公共产品的供给美苏军备竞赛经济改革中小学生减负 第一章导论 囚徒困境 囚徒困境的性质 个人理性和集体理性的矛盾 个人的 最优策略 使整个 系统 处于不利的状态 思考 为什么会造成囚徒困境是否由于 通讯 问题造成了囚徒困境 要害 是否在于 利己主义 即 个人理性 是否囚徒困境的结果就一定不利 第一章导论 囚徒困境 亚当斯密在1776年发表的经典之作 原富 中认为 我们的晚餐不是来自屠夫 酿酒的商人或面包师傅的仁慈之心 而是因为他们对自己的利益特别关注 每个人都会尽其所能 运用自己的资本争取最大的利益 一般而言 他不会有意图为公众服务 也不自知对社会有什么贡献 他关心的仅仅是自己的安全 自己的利益 但如此一来 他就好象被一只无形的手引领 在不知不觉中对社会改进尽力而为 第一章导论 囚徒困境 人类自私的天性 使他们陷入 囚徒困境 难以自拔 解决囚徒困境问题的 出路 解决个人理性和集体理性之间冲突的办法不是否认个人理性 而是设计一种机制 在满足个人理性的前提下达到集体理性 一种制度安排 要发生效力 必须是一种纳什均衡 否则 这种制度安排便不能成立 囚徒困境的效果在不同情况下对社会而言可能是 负面 的 也可能是 正面 的 第一章导论 智猪博弈 等待 小猪 大猪 按 等待 按 4大于10大于 1 案例2 智猪博弈 纳什均衡 大猪按 小猪等待各得四个单位 4 4 多劳者不多得 第一章导论 智猪博弈 请举类似的例子 第一章导论 智猪博弈 大猪小猪博弈股份公司中大股东小股东监督纳什均衡 大股东担当监督经理的责任 小股东搭便车村中的富人穷人修路纳什均衡 大户修路改革中得到好处多的少的改革股市的大户小户炒股纳什均衡 大户搜集信息 小户跟大户 第一章导论 性别战 芭蕾 女 男 足球 芭蕾 足球 案例3 性别战 纳什均衡 足球 足球 芭蕾 芭蕾先动优势 第一章导论 斗鸡博弈 案例4 斗鸡博弈 退 B A 进 退 进 独木桥 纳什均衡 A进 B退 A退 B进 第一章导论 斗鸡博弈 村子里有两户富户 有两种可能 一家修 另一家就不修 一家不修 另一家就得修 冷战期间美苏抢占地盘 一方抢占一块地盘 另一方就占另一块 夫妻吵架 一方厉害 另一方就出去躲躲 注意 在混合战略纳什均衡条件下 也可能两败俱伤 第一章导论 斗鸡博弈 案例5 市场进入阻挠 斗争 在位者 进入者 进入 不进入 默许 纳什均衡 进入 默许 不进入 斗争 第一章导论 人生是永不停歇的博弈过程 博弈意略达到合意的结果 作为博弈者 最佳策略是最大限度地利用游戏规则 最大化自己的利益 作为社会最佳策略 是通过规则使社会整体福利增加 第一章导论 基本概念 博弈论的基本概念包括 参与人 博弈论中选择行动以最大化自己效用的决策主体 行动 参与人的决策变量战略 参与人选择行动的规则信息 参与人在博弈中的知识 特别是有关其他参与人的特征和行动的知识支付函数 参与人从博弈中获得的效用水平结果 博弈分析真正感兴趣的要素的集合均衡 所有参与人的最优战略的组合参与人 行动 结果称为博弈规则 博弈分析的目的是使用博弈规则决定均衡 第一章导论 博弈的划分 博弈的划分 从参与人行动的先后顺序 静态博弈和动态博弈静态博弈 参与人同时选择行动或非同时行动但后行动者并不知道前行动者采取了什么具体行动 动态博弈 参与人行动有先后顺序 且后行动者能够观察先行动者选择的行动 第一章导论 博弈的划分 参与人对其他参与人 对手 的特征 战略空间及支付函数的知识 完全信息博弈和不完全信息博弈 完全信息 每一个参与人对所有其他参与人的 对手 的特征 战略空间及支付函数有准确的知识 否则为不完全信息 第一章导论 基本概念 博弈的划分 博弈的表述形式 1 博弈的标准型表述标准型表述三个要素 参与人每个参与人可选择的战略支付函数适用于3个以下参与人的静态博弈 博弈的表述形式 1 博弈的扩展型表述标准型表述五个要素 参与人每个参与人选择行动的时点每个参与人在每次行动是可选择的战略集每个参与人在每次行动时有关对手过去行动选择的信息支付函数适用于多个参与人的动态博弈 完全信息动态博弈 子博弈精练纳什均衡 举例 泽尔腾 1965 进入者 进入 不进入 0 300 在位者 合作 40 50 斗争 10 0 市场进入阻挠博弈树 特点 剔除博弈中包含的不可置信威胁 承诺行动 破釜沉舟给定进入者进入 剔除 进入 斗争 进入 默许 是唯一的子博弈精练纳什均衡 举例 结婚 反对 不可置信威胁 支付函数 行动 不完全信息静态博弈 贝叶斯纳什均衡海萨尼 1967 1968 不接受 求爱博弈 品德优良者求爱 求爱者 求爱 不求爱 接受 不接受 你 求爱者 求爱 不求爱 接受 求爱博弈 品德恶劣者求爱 你 100 x 100 1 x 0当x大于1 2时 接受求爱 不完全信息动态博弈 精练贝叶斯纳什均衡泽尔腾 1965 成语故事 黔之驴 驴虎博弈老虎通过不断试探来修正对毛驴的看法 每一步行动都是给定它的信念下最优的 最终将毛驴吃掉 完全信息与完美信息 完全信息是指博弈方都完全了结所有博弈方在各种情况下的得益 是静态的概念 完美信息是指博弈方在轮到行为时对博弈的进程完全了解 是动态的概念 问题 什么叫 完全而不完美信息博弈 第二章完全信息静态博弈 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡 完全信息静态博弈 完全信息 每个参与人对所有其他参与人的特征 包括战略空间 支付函数等 完全了解静态 所有参与人同时选择行动且只选择一次 同时 只要每个参与人在选择自己的行动时不知道其他参与人的选择 就是同时行动博弈分析的目的是预测均衡结果 一博弈的基本概念及战略表述 案例 房地产开发项目 假设有A B两家开发商市场需求 可能大 也可能小投入 1亿 假定市场上有两栋楼出售 需求大时 每栋售价1 4亿 需求小时 售价7千万 如果市场上只有一栋楼需求大时 可卖1 8亿需求小时 可卖1 1亿 一 博弈的基本概念及战略表述 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 一 博弈的基本概念及战略表述 博弈论的基本概念包括 参与人 博弈论中选择行动以最大化自己效用的决策主体 行动 参与人的决策变量战略 参与人选择行动的规则信息 参与人在博弈中的知识 特别是有关其他参与人的特征和行动的知识支付函数 参与人从博弈中获得的效用水平结果 博弈分析真正感兴趣的要素的集合均衡 所有参与人的最优战略的组合 一 博弈的基本概念及战略表述 参与人 博弈论中选择行动以最大化自己效用的决策主体 可以是自然人 也可以是团体 如企业 国家甚至由若干国家组成的集团 OPEC 欧盟等 虚拟参与人 自然 作为虚拟参与人自然 指决定外生的随机变量的机制为分析方便引入 自然作为虚拟参与人没有自己的支付和目标函数 即所有结果对它是无差异的 参与人决策的后果依赖于自然的选择 在不完全信息博弈中 自然选择参与人的类型 一 博弈的基本概念及战略表述 行动 参与人在某个时点的决策变量Ai表示第i个参与人的一个特定行动行动的顺序 行动的顺序对于博弈的结果是非常重要的 事实上 不同的行动顺序意味着不同的博弈 在博弈论中 一般假设参与人的行动空间和行动顺序是所有参与人的共同知识 一 博弈的基本概念及战略表述 信息 参与人在博弈中的知识 特别是有关其他参与人的特征和行动的知识 如房地产开发博弈中 如果A不知道市场需求 而B知道 则A的信息集为 大 小 B的信息集为 大 或 小 完美信息 指一个参与人对其他参与人 包括 自然 的行动选择有准确了解的情况 即每一个信息集只包含一个值 完全信息 指自然不首先行动或自然的行动的初始行动所有参与人观察到的情况 共同知识 指 所有参与人知道所有参与人知道所有参与人知道 的知识 一 博弈的基本概念及战略表述 战略 参与人在给定信息集的情况下选择行动的规则 它规定参与人在什么情况下选择什么行动 是参与人的 相机行动方案 在静态博弈中 战略和行动是相同的 作为一种行动规则 战略必须是完备的 一 博弈的基本概念及战略表述 支付函数 参与人从博弈中获得的效用水平 或者指参与人得到的期望效用水平 博弈的基本特征是一个参与人的支付不仅取决于自己的战略选择 而且取决于所有其他参与人的战略选择 一 博弈的基本概念及战略表述 结果 博弈分析感兴趣的所有东西如均衡战略组合 均衡行动组合 均衡支付组合等 一 博弈的基本概念及战略表述 均衡 所有参与人的最优战略的组合一般记为 一 博弈的基本概念及战略表述 博弈的战略式表述 一 博弈的基本概念及战略表述 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 第二章完全信息静态博弈 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡 二占优战略 上策 均衡 案例1 囚徒困境 囚徒A 囚徒B 坦白 抵赖 坦白 抵赖 8大于 100大于 1 8大于 100大于 1 二占优战略 上策 均衡 占优战略 不论其他人选择什么战略 参与人的最优战略是唯一的 这样的最优战略称为 占优战略 dominantstrategy 二占优战略 上策 均衡 占优战略均衡定义 在博弈的战略表达式中 如果对于所有的i Si 是i的占优战略 下列战略组合称为占优战略均衡 二占优战略 上策 均衡 注意 如果所有人都有 严格 占优战略存在 那么占优战略均衡就是可以预测的唯一均衡 占优战略只要求每个参与人是理性的 而不要求每个参与人知道其他参与人是理性的 也就是说 不要求理性是共同知识 为什么 二占优战略 上策 均衡 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 等待 小猪 大猪 按 等待 按 案例2 智猪博弈 大猪有无严格占优战略 第二章完全信息静态博弈 纳什均衡 一博弈的基本概念及战略表述二占优战略均衡三重复剔除的占优均衡 严格下策反复消去法 四纳什均衡五纳什均衡应用举例 三重复剔除的占优均衡 严格下策反复消去法 重复剔除严格劣战略 思路 首先找到某个参与人的劣战略 假定存在 把这个劣战略剔除掉 重新构造一个不包含已剔除战略的新的博弈 然后再剔除这个新的博弈中的某个参与人的劣战略 一直重复这个过程 直到只剩下唯一的战略组合为止 这个唯一剩下的战略组合就是这个博弈的均衡解 称为 重复剔除的占优均衡 三重复剔除的占优均衡 注意 与占优战略均衡中的占优战略和劣战略不同 这里的占优战略或劣战略可能只是相对于另一个特定战略而言 三重复剔除的占优均衡 等待 小猪 大猪 按 等待 按 案例2 智猪博弈 按 是大猪的占优战略 纳什均衡 大猪按 小猪等待 三重复剔除的占优均衡 重复剔除的占优均衡战略组合称为重复剔除的占优均衡 如果它是重复剔除劣战略后剩下的唯一战略组合 如果这种唯一战略组合是存在的 我们就说该博弈是重复剔除占优可解 注意 如果重复剔除后的战略组合不唯一 该博弈就不是重复剔除占优可解的 三重复剔除的占优均衡 M 列先生 行先生 U D L R 行 没有占优战略列 M严格优于R剔除R 行 L优于D列 无占优战略剔除D M优于L U M 是重复剔除的占优均衡 三重复剔除的占优均衡 练习 在下列战略式表达中 找出重复剔除的占优均衡 C2 R1 R2 C1 C3 R3 三重复剔除的占优均衡 注意 1 重复剔除的占优均衡结果与劣战略的剔除顺序是否有关 取决于剔除的是否是严格劣战略 2 重复剔除的占优均衡要求每个参与人是理性的 而且要求 理性 是参与人的共同知识 即 所有参与人知道所有参与人是理性的 所有参与人知道所有参与人知道所有参与人是理性的 三重复剔除的占优均衡 C2 R1 R2 C1 C3 R3 剔除顺序 R3 C3 C2 R2 战略组合 R1 C1 故一般使用严格劣战略剔除 可以看到 R1 C3 R1 C1 都是纳什均衡 但在这里是不可解的 剔除顺序 C2 R2 C1 R3 战略组合 R1 C3 举例 三重复剔除的占优均衡 尽管许多博弈中重复剔除的占优均衡是一个合理的预测 但并不总是如此 尤其是大概支付某些极端值的时候 参与人B 参与人A U D L R U是A的最优选择 但是 只要有1 1000的概率B选R A就会选D 博弈的结果对不确定性是很敏感的 房地产开发中需求小情况 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 斗鸡博弈 退 B A 进 退 进 独木桥 纳什均衡 A进 B退 A退 B进 对于相当多的博弈 我们无法运用重复剔除劣战略的方法找出均衡解 为了找出这些博弈的均衡解 需要引入纳什均衡 第二章完全信息静态博弈 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡 四划线法 找出自己针对其他博弈方每种策略的最佳对策 在相应的得益下划一短线 上 中 左 博弈方1 博弈方2 2 0 0 2 0 4 0 1 1 3 1 0 右 下 稳定的策略组合 囚徒困境 囚徒A 囚徒B 坦白 抵赖 坦白 抵赖 坦白 坦白 是纳什均衡 四划线法 石头 剪子 剪子 石头 博弈方1 博弈方2 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 布 布 1 不存在确定性的结果 四划线法 足球 芭蕾 芭蕾 足球 男 女 性别战 BattleofSexes 2 存在不止一个结果 四划线法 U M M L 甲 乙 2 8 9 6 3 0 3 6 8 4 2 1 6 2 5 1 4 3 R D U M L 甲 乙 4 6 2 7 1 1 3 4 0 2 2 3 R D 练习 试对下面两个博弈进行分析 第二章完全信息静态博弈 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡 对博弈中每个策略组合进行分析 考察在每个策略组合下各个博弈方能否通过单独改变自己的策略而增加收益 如果能 则从所分析的策略组合对应的得益数组引一箭头 到改变策略后策略组合对应的得益数组 综合对每个策略组合的分析 形成对博弈结果的判断 五箭头法 囚徒困境 囚徒A 囚徒B 坦白 抵赖 坦白 抵赖 坦白 坦白 是纳什均衡 五箭头法 足球 芭蕾 芭蕾 足球 小明 小红 性别战 BattleofSexes 五箭头法 上 中 左 博弈方1 博弈方2 右 下 五箭头法 要综合对各种不同方法对博弈的分析 形成对博弈结果的判断 第二章完全信息静态博弈 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡 六纳什均衡 假设n个参与人在博弈之前达成一个协议 规定每一个参与人选择一个特定的战略 另代表这个协议 在没有外在强制力的情况下 如果没有任何人有积极性破坏这个协议 则这个协议是自动实施的 这个协议就构成了一个纳什均衡 六纳什均衡 通俗地说 纳什均衡的含义就是 给定你的策略 我的策略是最好的策略 给定我的策略 你的策略也是你的最好的策略 即双方在给定的策略下不愿意调整自己的策略 纳什均衡的一致预测性质 如果所有博弈方都预测一个特定的博弈结果会出现 那么所有的博弈方都不会利用这个预测或者这种预测能力 选择与预测结果不一致的策略 即没有哪个博弈方有偏离这个预测结果的愿望 因此这个预测结果最终会成为博弈的结果 六纳什均衡 练习 找出下列两队夫妻的纳什均衡 死了 恩爱夫妻 活着 死了 活着 死了 妻子 相互仇恨夫妻 活着 死了 活着 妻子 丈夫 丈夫 六纳什均衡 一群赌徒在赌钱 每个人将钱放在自己身边 每个人都知道自己的钱有多少 忽然吹来一阵风将所有的钱都混在一起 使他们无法分辨哪些钱是自己的 纳什均衡为他们解决这个问题 六纳什均衡 纳什均衡与占优战略均衡及重复剔除的占优均衡 1 每一个占优战略均衡及重复剔除的占优均衡一定是纳什均衡 但并非每一个纳什均衡都是占优战略均衡或重复剔除的占优均衡 2 纳什均衡一定是在重复剔除严格劣战略过程中没有被剔除掉的战略组合 但没有被剔除掉的组合不一定是纳什均衡 除非它是唯一的 不适用于严格弱劣战略的情况 C2 R1 R2 C1 C3 R3 剔除顺序 R3 C3 C2 R2 战略组合 R1 C1 故一般使用严格劣战略剔除 可以看到 R1 C3 R1 C1 都是纳什均衡 但在这里是不可解的 剔除顺序 C2 R2 C1 R3 战略组合 R1 C3 六纳什均衡 不同均衡概念的关系 占优均衡DSE 重复剔除占优均衡IEDE 纯战略纳什均衡PNE 四纳什均衡 纳什均衡经济应用举例 案例1库诺 Cournot 寡头竞争模型案例2公共地的悲剧案例3公共物品的私人供给 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡七混合战略纳什均衡八纳什均衡的选择和分析方法扩展 第二章完全信息静态博弈 纳什均衡 七混合战略纳什均衡 社会福利博弈 流浪 流浪汉 政府 救济 不救济 寻找工作 没有一个战略组合构成纳什均衡 七混合战略纳什均衡 反面 正面 反面 正面 猜谜游戏两个儿童各拿一枚硬币 若同时正面朝上或朝下 A给B1分钱 若只有一面朝上 B给A1分钱 零和博弈博弈参与者有输有赢 但结果永远是0 没有一个战略组合构成纳什均衡 七混合战略纳什均衡 警察与小偷 银行 酒馆 警察 小偷 2万元 1万元 东边 西边 警察与小偷的最优策略各是什么 七混合战略纳什均衡 上述博弈的特征是 在这类博弈中 都不存在纯纳什均衡 参与人的支付取决于其他参与人的战略 以某种概率分布随机地选择不同的行动每个参与人都不愿意让对方猜透自己的战略 这种博弈的类型是什么 如何找到均衡 七混合战略纳什均衡 请举一些这样的例子 石头 剪子 布游戏老虎 杠子 鸡 虫子游戏扑克游戏橄榄球赛战争中 西边 东边 西边 东边 七混合战略纳什均衡 警察抽签决定去银行还是酒馆 2 3的机会去银行 1 3的机会去酒馆 同样 小偷也抽签决定去银行还是酒馆 2 3的机会去酒馆 1 3的机会去银行 七混合战略纳什均衡 社会福利博弈 流浪 流浪汉 政府 救济 不救济 寻找工作 设 政府救济的概率 1 2 不救济的概率 1 2 流浪汉 寻找工作的期望效用 1 2 2 1 2 1 1 5流浪的期望效用 1 2 3 1 2 0 1 5因此 流浪汉的任何一种战略都是都是对政府混合战略的最优反应 七混合战略纳什均衡 社会福利博弈 流浪 流浪汉 政府 救济 不救济 寻找工作 设 政府救济的概率 1 2 不救济的概率 1 2 流浪汉 寻找工作的概率 0 2 流浪的概率 0 8每个参与人的战略都是给定对方混合战略时的最优战略 七混合战略纳什均衡 反面 正面 反面 正面 猜谜游戏两个小孩的最优策略是采取每个策略的可能性均为1 2 每个小孩各取策略的1 2是纳什均衡 零和博弈 七混合战略纳什均衡 战略 参与人在给定信息集的情况下选择行动的规则 它规定参与人在什么情况下选择什么行动 是参与人的 相机行动方案 纯战略 如果一个战略规定参与人在每一个给定的信息情况下只选择一种特定的行动 该战略为纯战略 混合战略 如果一个战略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动 则该战略为混合战略 七混合战略纳什均衡 混合战略 如果一个战略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动 则该战略为混合战略 七混合战略纳什均衡 纯战略可以理解为混合战略的特例 即在诸多战略中 选该纯战略si的概率为1 选其他纯战略的概率为0 等待 小猪 大猪 按 等待 按 反面 正面 反面 正面 七混合战略纳什均衡 如何寻找混合战略纳什均衡 支付最大化法支付等值法由于混合战略伴随的是支付的不确定性 因此参与人关心的是其期望效用 最优混合战略 是指使期望效用函数最大的混合战略 给定对方的混合战略 在两人博弈里 混合战略纳什均衡是两个参与人的最优混合战略的组合 七混合战略纳什均衡 支付最大化法 即 流浪汉以0 2的概率选择寻找工作 0 8的概率选择游荡 同样 可以根据流浪汉的期望效用函数找到政府的最优混合战略 七混合战略纳什均衡 社会福利博弈 流浪 流浪汉 政府 救济 不救济 寻找工作 设 政府救济的概率 1 2 不救济的概率 1 2 流浪汉 寻找工作的概率 0 2 流浪的概率 0 8每个参与人的战略都是给定对方混合战略时的最优战略 七混合战略纳什均衡 支付等值法 假定最优混合战略存在 给定流浪汉选择混合战略 r 1 r 政府选择纯战略救济的期望效用为 3r 1 1 r 4r 1选择纯战略不救济的效用为 1r 0 1 r r如果一个混合战略 而不是纯战略 是政府的最优选择 一定意味着政府在救济与不救济之间是无差异的 4r 1 rr 0 2 流浪 流浪汉 政府 救济 不救济 寻找工作 七混合战略纳什均衡 社会福利博弈 流浪 流浪汉 政府 救济 不救济 寻找工作 设 政府救济的概率 1 2 不救济的概率 1 2 流浪汉 寻找工作的概率 0 2 流浪的概率 0 8每个参与人的战略都是给定对方混合战略时的最优战略 七混合战略纳什均衡 对的解释 如果流浪汉以找工作的概率小于0 2 则政府选择不救济 如果大于0 2 政府选择救济 只有当概率等于0 2时 政府才会选择混合战略或任何纯战略 对 0 5的解释如果政府救济的概率大于0 5 流浪汉的最优选择是流浪 如果政府救济的概率小于0 5 流浪汉的最优选择是寻找工作 七混合战略纳什均衡 混合战略纳什均衡的含义 纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的最优选择 因此在社会福利博弈中 0 5是唯一的混合战略纳什均衡 从反面来说 如果政府认为流浪汉选择寻找工作的概率严格小于0 2 那么政府的唯一最优选择是纯战略 不救济 如果政府以1的概率选择不救济 流浪汉的最优选择是寻找工作 这又将导致政府选择救济的战略 流浪汉则选择游荡 如此等等 七混合战略纳什均衡 反面 正面 反面 正面 用上述方法 求该猜谜游戏的混合战略纳什均衡 七混合战略纳什均衡 练习 模型化下述划拳博弈 两个老朋友在一起喝酒 每个人有四个纯战略 杠子 老虎 鸡和虫子 输赢规则是 杠子降鸡 鸡吃虫子 虫子降杠子 两人同时出令 如果一个打败另一个 赢的效用为1 输的效用为 1 否则效用为0 写出这个博弈的支付矩阵 这个博弈有纯战略均衡吗 计算其混合战略纳什均衡 一博弈的基本概念及战略表述二占优战略 上策 均衡三重复剔除的占优均衡 严格下策反复消去法 四划线法五箭头法六纳什均衡七混合战略纳什均衡八纳什均衡的选择和分析方法扩展 第二章完全信息静态博弈 纳什均衡 八纳什均衡的选择和分析方法扩展 纳什均衡存在性定理 每一个有限博弈至少存在一个纳什均衡 纯战略的或混合战略的 八纳什均衡的选择和分析方法扩展 多重纳什均衡博弈的分析 两个人分蛋糕 性别战中的博弈 纳什均衡的多重性 博弈论并没有一个一般的理论证明纳什均衡结果一定能出现 芭蕾 女 男 足球 芭蕾 足球 八纳什均衡的选择和分析方法扩展 如何保证均衡出现 1 聚点 均衡 参与人可以使用某些被抽象掉的信息达到一个 聚点均衡 两个人分蛋糕 性别战中的博弈 八纳什均衡的选择和分析方法扩展 2 廉价磋商 协调博弈 帕累托上策均衡和风险上策均衡尽管无法保证磋商会达成一个协议 即使达成协议也不一定会被遵守 但在一些博弈中 事前磋商确实可以使某些均衡实际上出现 R B A U D L R B A U D L 聚点 八纳什均衡的选择和分析方法扩展 猎人博弈和帕累托优势 打兔 猎人乙 猎人甲 猎鹿 打兔 猎鹿 有两个纳什均衡 10 10 与 4 4 可以认为 10 10 比 4 4 有帕累托优势 八纳什均衡的选择和分析方法扩展 大流士阴谋推翻波斯王国的故事 当时 一群波斯贵族聚在一起决定推翻国王 其间有人提议休会 大流士此时站出来大声疾呼 说如果休会的话 就一定会有人去国王那里告密 因为如果别人不那么做的话 他自己就会去做 大流士说唯一的办法就是冲进皇宫 杀死国王 这个谋反的故事还提供了关于协调博弈的出路 在杀死国王之后 贵族们想从自己人中推选出一个人当国王 他们决定不自相残杀 而是在拂晓时分到山上去 谁的马先叫谁就当国王 大流士的马夫在这场随机的安排中做了手脚 从而成为国王 八纳什均衡的选择和分析方法扩展 3 学习过程假定博弈重复多次 即使参与人最初难以协调行动 在博弈若干次后 某种特定的协调模式可能会形成 特别地 假定参与人每一轮根据其对手以前的 平均 战略来选择自己的最优战略 博弈可能收敛于一个纳什均衡 八纳什均衡的选择和分析方法扩展 4 相关均衡 1 5 4 4 0 0 5 1 R 博弈方B 博弈方A U D L 纯策略和混合策略纳什均衡的期望收益总和均为6 相关信号规则 掷色子 A 扔出1点或2点 选U 扔出3 6点 选D B 扔出1 4点 选L 扔出5点或6点 选R U L D R 和 D L 各以三分之一的结果出现 每个参与人的期望效用为3又1 3 八纳什均衡的选择和分析方法扩展 5 共谋和防共谋均衡 纳什均衡应用举例 诺贝尔经济学奖获得者萨缪尔森有一句话 你可以将一只鹦鹉训练成一个经济学家 因为它只需要学习两个词 供给和需求 博弈论专家坎多瑞引申说 要成为现代经济学家 这只鹦鹉必须再多学一个词 就是 纳什均衡 激励的悖论 小偷和守卫的博弈监督博弈 税收检查博弈 纳什均衡应用举例 第三章完全信息动态搏弈 子博弈精炼纳什均衡 一博弈扩展式表述二子博弈精练纳什均衡三应用举例 博弈的战略表述 案例 房地产开发项目 假设有A B两家开发商市场需求 可能大 也可能小投入 1亿 假定市场上有两栋楼出售 需求大时 每栋售价1 4亿 需求小时 售价7千万 如果市场上只有一栋楼需求大时 可卖1 8亿需求小时 可卖1 1亿 博弈战略表述 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 一博弈扩展式表述 博弈的扩展式表述包括三个要素 参与人集合每个参与人的战略集合由战略组合决定的每个参与人的支付 进入者 进入 不进入 0 300 在位者 市场进入阻挠博弈树 不可置信威胁 合作 40 50 斗争 10 0 A 开发 不开发 N N 大 小 1 2 1 2 大 小 1 2 1 2 B B B B 开发 不开发 开发 不开发 开发 不开发 开发 不开发 4 4 8 0 3 3 1 0 0 8 0 0 0 1 0 0 参与人集合参与人行动顺序参与人的行动空间参与人的信息集参与人的支付函数外生事件的概率分布 房地产开发博弈 一博弈扩展式表述 博弈的基本构造结 包括决策结和终点结两类 决策结是参与人行动的始点 终点结是决策人行动的终点 结满足传递性和非对称性x之前的所有结的集合 称为x的前列集P x x之后的所有结的集合称为x的后续集T x 枝 枝是从一个决策结到它的直接后续结的连线 每一个枝代表参与人的一个行动选择 信息集 每个信息集是决策结集合的一个子集 该子集包括所有满足下列条件的决策结 1每个决策结都是同一个参与人的决策结 2该参与人知道博弈进入该集合的某个决策结 但不知道自己究竟处于哪一个决策结 A 开发 不开发 N N 大 小 1 2 1 2 大 小 1 2 1 2 B B B B 开发 不开发 开发 不开发 开发 不开发 开发 不开发 4 4 8 0 3 3 1 0 0 8 0 0 0 1 0 0 B在决策时不确切地知道自然的选择 B的决策结由4个变为2个 房地产开发博弈 A 开发 不开发 N N 大 小 1 2 1 2 大 小 1 2 1 2 B B B B 开发 不开发 开发 不开发 开发 不开发 开发 不开发 4 4 8 0 3 3 1 0 0 8 0 0 0 1 0 0 B知道自然的选择 但不知道A的选择 或A B同时决策 房地产开发博弈 一博弈扩展式表述 只包含一个决策结的信息集称为单结信息集 如果博弈树的所有信息都是单结的 该博弈称为完美信息博弈 自然总是假定是单结的 因为自然在参与人决策之后行动等价于自然在参与人之前行动但参与人不能观测到自然的行动 不同的博弈树可以代表相同的博弈 但是有一个基本规则 一个参与人在决策之前知道的事情 必须出现在该参与人决策结之前 A B 坦白 抵赖 B B A A 坦白 抵赖 坦白 抵赖 8 8 0 10 10 0 1 1 坦白 抵赖 坦白 抵赖 坦白 抵赖 8 8 0 10 10 0 1 1 囚徒困境博弈的扩展式表述 囚徒困境博弈的扩展式表述 扩展式表述博弈的纳什均衡 足球 男的策略 足球 芭蕾 选择足球 还是选择芭蕾 女的策略 足球 芭蕾 芭蕾 足球 芭蕾 芭蕾 足球 足球 1 追随策略 他选择什么 我就选择什么2 对抗策略 他选择什么 我就偏不选什么3 芭蕾策略 不管他选什么 我都选芭蕾 4 足球策略 不管他选什么 我都选足球 策略即 如果他选择什么 我就怎样行动的相机行动方案 在扩展式博弈里 参与人是相机行事 即 等待 博弈到达一个自己的信息集 包含一个或多个决策结后 再采取行动方案 什么是动态博弈 智猪博弈的扩展式表述 等待 小猪 大猪 按 等待 按 案例2 智猪博弈 扩展式表述博弈的纳什均衡 若A先行动 B在知道A的行动后行动 则A有一个信息集 两个可选择的行动 战略空间为 开发 不开发 B有两个信息集 四个可选择的行动 B有四个纯战略 开发策略 不论A开发不开发 我开发 追随策略 A开发我开发 A不开发我不开发 对抗策略 A开发我不开发 A不开发我开发 不开发策略不论A开发不开发我不开发 简写为 开发 开发 开发 不开发 不开发 开发 不开发 不开发 括号内的第一个元素对应A选择 开发 时B的选择 第二个元素对应A选择 不开发 时B的选择 什么是参与人的战略 扩展式 开发 开发 开发 不开发 不开发 开发 不开发 不开发 开发 不开发 开发商B 开发商A 战略式 路径在扩展式博弈中 所有n个参与人的一个纯战略组合决定了博弈树上的一个路径 开发 不开发 开发 决定了博弈的路径 A 开发 B 不开发 1 0 不开发 开发 开发 决定了路径 A 不开发 B 开发 0 1 第三章完全信息动态搏弈 子博弈精炼纳什均衡 一博弈扩展式表述二子博弈精练纳什均衡子博弈精练纳什均衡用逆向归纳法求子搏弈精练纳什均衡承诺行动与子搏弈精练纳什均衡逆向归纳法与子搏弈精练纳什均衡的存在问题三应用举例 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 考虑下列问题 一个博弈可能有多个 甚至无穷多个 纳什均衡 究竟哪个更合理 纳什均衡假定每一个参与人在选择自己的最优战略时假定所有其他参与人的战略是给定的 但是如果参与人的行动有先有后 后行动者的选择空间依赖于前行动者的选择 前行动者在选择时不可能不考虑自己的行动对后行动者的影响 子博弈精练纳什均衡的一个重要改进是将 合理纳什均衡 与 不合理纳什均衡 分开 完全信息动态博弈 子博弈精练纳什均衡 举例 泽尔腾 1965 进入者 进入 不进入 0 300 在位者 合作 40 50 斗争 10 0 市场进入阻挠博弈树 特点 剔除博弈中包含的不可置信威胁 承诺行动 破釜沉舟 背水一战给定进入者进入 剔除 进入 斗争 进入 默许 是唯一的子博弈精练纳什均衡 举例 结婚 反对 不可置信威胁 支付函数 行动 子博弈精炼纳什均衡 不可置信威胁 美国普林斯顿大学古尔教授在1997年的 经济学透视 里发表文章 提出一个例子说明威胁的可信性问题 两兄弟老是为玩具吵架 哥哥老是要抢弟弟的玩具 不耐烦的父亲宣布政策 好好去玩 不要吵我 不管你们谁向我告状 我都把你们两个关起来 关起来比没有玩具更可怕 现在 哥哥又把弟弟的玩具抢去玩了 弟弟没有办法 只好说 快把玩具还我 不然我就要去告诉爸爸 哥哥想 你真要告诉爸爸 我是要倒霉的 可是你不告状不过没有玩具玩 而告了状却要被关禁闭 告状会使你的境遇变得更坏 所以你不会告状 因此哥哥对弟弟的警告置之不理 的确 如果弟弟是会算计自己利益的理性人 在这样的环境下 还是不告状的好 可见 如果弟弟是理性人 他的告状威胁是不可置信的 二子博弈精练纳什均衡 一个纳什均衡称为精练纳什均衡 当只当参与人的战略在每个子博弈中都构成纳什均衡 也就是说 组成精练纳什均衡的战略必须在每一个子博弈中都是最优的 一个精练纳什均衡首先必须是一个纳什均衡 但纳什均衡不一定是精练纳什均衡 承诺行动与子博弈精练纳什均衡 承诺行动与子博弈精练纳什均衡有些战略之所以不是精练纳什均衡 是因为它包含了不可置信的威胁战略 如果参与人能在博弈之前采取某种行动改变自己的行动空间或支付函数 原来不可置信威胁将变得可置信 博弈的精练纳什均衡也会随之改变 这些改变博弈结果而采取的措施称为承诺行动 完全承诺 承诺可以使某项行动完全没有可能 破釜沉舟 不完全承诺 承诺只是增加了某个行动的成本而不是使该活动完全没有可能 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 曹操与袁绍的仓亭之战 曹操召集将领来献破袁之策 程昱献了十面埋伏之计 他让曹操退军河上 诱袁前来追击 到那时 我军无退路 必将死战 可退袁矣 曹操采纳此计 令许褚诱袁军军至河上 曹军无退路 操大呼曰 前无去路 诸军何不死战 众军奋力回头反击 袁军大败 承诺行动与子博弈精练纳什均衡 房地产开发博弈 如果在A决策之前 B与某客户签定了一个合同 规定B若不在特定时期内开发若干面积的写字楼 则将支付违约金3 5 这个合同就是承诺行动 1 3 5 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 泽尔腾引入子博弈精练纳什均衡的概念的目的是将那些不可置信威胁战略的纳什均衡从均衡中剔除 从而给出动态博弈的一个合理的预测结果 简单说 子博弈精练纳什均衡要求均衡战略的行为规则在每一个信息集上是最优的 扩展式 开发 开发 开发 不开发 不开发 开发 不开发 不开发 开发 不开发 开发商B 开发商A 战略式 纳什均衡与均衡结果 存在三个纯战略纳什均衡 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 两个均衡结果 开发 不开发 不开发 开发 注意 均衡不同于均衡结果 子博弈精练纳什均衡 A 开发 不开发 B B 开发 不开发 开发 3 3 1 0 0 1 0 0 不开发 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 如果A选择开发 B的最优选择是不开发 如果A选择不开发 B的最优选择是开发 A预测到自己的选择对B的影响 因此开发是A的最优选择 子博弈精练纳什均衡结果是 A选择开发 B选择不开发 x x 对于 不开发 开发 开发 这个组合之所以构成纳什均衡 是因为B威胁不论A开发还是不开发 他都将选择开发 A相信了B的威胁 不开发是最优选择 但是A为什么要相信B的威胁呢 毕竟 如果A真开发 B选择开发得 3 不开发得0 所以B的最优选择是不开发 如果A知道B是理性的 A将选择开发 逼迫B选择不开发 自己得1 B得0 即纳什均衡 不开发 开发 开发 是不可置信的 因为它依赖于B的一个不可置信的威胁 同样 不开发 不开发 也是一个不可置信威胁 纳什均衡 开发 不开发 不开发 是不合理的 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 子博弈 是原博弈的一部分 它本身也可以作为一个独立的博弈进行分析 1 子博弈必须从一个单结信息点开始 只有决策者在原博弈中确切地知道博弈进入一个特定的决策结时 该决策结才能作为一个子博弈的初始结 如果信息集包含两个以上的决策结 则这两个都不可以作为子博弈的初始结 见下页 2 子博弈的信息集和支付向量都直接继承自原博弈 即当x 和x 在原博弈中属于同一信息集时 他们在子博弈中才属于同一信息集 习惯上 任何博弈的本身称为自身的一个子博弈 A 开发 不开发 X X 大 小 1 2 1 2 大 小 1 2 1 2 B B B B 开发 不开发 开发 不开发 开发 不开发 开发 不开发 4 4 8 0 3 3 1 0 0 8 0 0 0 1 0 0 参与人X的信息集不能开始一个子博弈 否则的话 参与人B的信息将被切割 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 不开发 不开发 房地产开发博弈 找出房地产开发博弈的子博弈 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 子博弈精练纳什均衡 扩展式博弈的战略组合是一个子博弈精练纳什均衡 如果 1 它是原博弈的纳什均衡 2 它在每一个子博弈上给出纳什均衡 A 开发 不开发 B B 开发 不开发 开发 1 0 0 1 0 0 3 3 x x 房地产开发博弈 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 在c上构成均衡 在b上不构成 在b和c上都构成在c上构成均衡 在b上不构成 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 不开发 判断下列均衡结果哪个构成子博弈精练纳什均衡 不开发 b c 完全信息动态博弈 子博弈精练纳什均衡泽尔腾 1965 如果一个博弈有几个子博弈 一个特定的纳什均衡决定了原博弈树上唯一的一条路径 这条路径称为 均衡路径 博弈树上的其他路径称为 非均衡路径 纳什均衡只要求均衡战略在均衡路径的决策结上是最优的 而构成子博弈精练纳什均衡不仅要求在均衡路径上策略是最优的 而且在非均衡路径上的决策结上也是最优的 这是纳什均衡与子博弈精练纳什均衡的实质区别 第三章完全信息动态搏弈 子博弈精炼纳什均衡 一博弈扩展式表述二子博弈精练纳什均衡扩展式表述博弈的纳什均衡子博弈精练纳什均衡用逆向归纳法求子搏弈精练纳什均衡逆向归纳法与子搏弈精练纳什均衡的存在问题三应用举例 用逆向归纳法求 子博弈精练纳什均衡 1 U D L 3 1 0 0 2 2 2 R 给定博弈达到最后一个决策结 该决策结上行动的参与人有一个最优选择 这个最优选择即该决策结开始的子博弈的纳什均衡倒数第二个决策结 找倒数第二个的最优选择 这个最优选择与我们在第一步找到的最优选择构成一个纳什均衡 如此重复直到初始结 每一步都得到对应于子博弈的一个纳什均衡 并且根据定义 该纳什均衡一定是该子博弈的子博弈的纳什均衡 这个过程的最后一步得到整个博弈的纳什均衡 用逆向归纳法求 子博弈精练纳什均衡 用逆向归纳法求子博弈精练纳什均衡对于有限完美信息博弈 逆向归纳法求解子博弈精练纳什均衡是一个最简便的方法 房地产开发博弈 1 U D L 1 1 2 2 0 R U 3 0 0 2 2 D 子博弈精练纳什均衡 U U L U 和L分别是参与人1和参与人2在非均衡路径上的选择 逆向归纳法求解子博弈精练纳什均衡的过程 实质上是重复剔除劣战略的过程 从最后一个决策结依次剔除每个子博弈的劣战略 最后生存下来的战略构成精练纳什均衡 用逆