完全信息动态博弈.ppt

2 3完全信息动态博弈 本节内容 一博弈扩展式表述二子博弈完美纳什均衡三应用举例 博弈的战略表述 案例 房地产开发项目 假设有A B两家开发商市场需求 可能大 也可能小投入 1亿 假定市场上有两栋楼出售 需求大时 每栋售价1 4亿 需求小时 售价7千万 如果市场上只有一栋楼需求大时 可卖1 8亿需求小时 可卖1 1亿 博弈战略表述 不开发 开发商A 开发 不开发 开发 不开发 开发商B 开发商A 开发 不开发 开发 开发商B 需求小的情况 需求大的情况 博弈的战略式表述 博弈的扩展式表述 扩展式表述所 扩展 的主要是参与人的战略空间战略式表述简单地给出参与人有些什么战略可以选择 而扩展式表述要给出每个战略的动态描述 谁在什么时候行动 每次行动时有些什么具体行动方案可供选择 以及知道些什么此时的战略 如果你这样 我将怎样 博弈的扩展式表述 要素 参与人集合参与人的行动顺序参与人的行动空间参与人的信息集参与人的支付函数外生事件 即 自然 的选择 的概率分布 A 开发 不开发 N N 大 小 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该参与人知道博弈进入该集合的某个决策结 但不知道自己究竟处于哪一个决策结 信息集 房地产博弈II B在决策时不确切地知道自然的选择 B的决策结由4个变为2个 信息集 房地产博弈III B知道自然的选择 但不知道A的选择 或A B同时决策 信息集 房地产博弈IV 博弈扩展式表述 只包含一个决策结的信息集称为单结信息集 如果博弈树的所有信息都是单结的 该博弈称为完美信息博弈 自然总是假定是单结的 因为自然在参与人决策之后行动等价于自然在参与人之前行动但参与人不能观测到自然的行动 不同的博弈树可以代表相同的博弈 但是有一个基本规则 一个参与人在决策之前知道的事情 必须出现在该参与人决策结之前 A B 坦白 抵赖 B B A A 坦白 抵赖 坦白 抵赖 8 8 0 10 10 0 1 1 坦白 抵赖 坦白 抵赖 坦白 抵赖 8 8 0 10 10 0 1 1 囚徒困境博弈的扩展式表述 囚徒困境博弈的扩展式表述 智猪博弈的扩展式表述 等待 小猪 大猪 按 等待 按 案例2 智猪博弈 动态博弈的战略的表述 战略 参与人在给定信息集的情况下选择行动的规则 它规定参与人在什么情况下选择什么行动 是参与人的 相机行动方案 在静态博弈中 战略和行动是相同的 作为一种行动规则 战略必须是完备的 性别战博弈的扩展式表述 扩展式表述博弈的战略 足球 男的策略 足球 芭蕾 选择足球 还是选择芭蕾 女的策略 足球 芭蕾 芭蕾 足球 芭蕾 芭蕾 足球 足球 1 追随策略 他选择什么 我就选择什么2 对抗策略 他选择什么 我就偏不选什么3 芭蕾策略 不管他选什么 我都选芭蕾 4 足球策略 不管他选什么 我都选足球 策略即 如果他选择什么 我就怎样行动的相机行动方案 在扩展式博弈里 参与人是相机行事 即 等待 博弈到达一个自己的信息集 包含一个或多个决策结 后 再采取行动方案 扩展式表述博弈的纳什均衡 若A先行动 B在知道A的行动后行动 则A有一个信息集 两个可选择的行动 战略空间为 开发 不开发 B有两个信息集 四个可选择的行动 B有四个纯战略 开发策略 不论A开发不开发 我开发 追随策略 A开发我开发 A不开发我不开发 对抗策略 A开发我不开发 A不开发我开发 不开发策略不论A开发不开发我不开发 简写为 开发 开发 开发 不开发 不开发 开发 不开发 不开发 括号内的第一个元素对应A选择 开发 时B的选择 第二个元素对应A选择 不开发 时B的选择 什么是参与人的战略 扩展式 开发 开发 开发 不开发 不开发 开发 不开发 不开发 开发 不开发 开发商B 开发商A 战略式 路径在扩展式博弈中 所有n个参与人的一个纯战略组合决定了博弈树上的一个路径 开发 不开发 开发 决定了博弈的路径为A 开发 B 不开发 1 0 不开发 开发 开发 决定了路径 课堂练习 参与人1 丈夫 和参与人2 妻子 必须独立决定出门时是否带伞 他们知道下雨和不下雨的可能性均为50 支付函数为 如果只有一人带伞 下雨时带伞者的效用为 2 5 不带伞者的效用为 3 不下雨时带伞的效用为 1 不带的效用为0 如两人都不带伞 下雨时每人的效用为 5 不下雨时每人的效用为1 给出下列四种情况下的扩展式及战略式表述 1 两人出门前都不知道是否会下雨 并且两人同时决定是否带伞 即每一方在决策时都不知道对方的决策 2 两人在出门前都不知道是否会下雨 但丈夫先决策 妻子观察到丈夫是否带伞后才决定自己是否带伞 3 丈夫出门前知道是否会下雨 但妻子不知道 但丈夫先决策 妻子后决策 4 同 3 但妻子先决策 丈夫后决策 完全信息动态博弈 子博弈完美纳什均衡泽尔腾 1965 考虑下列问题 一个博弈可能有多个 甚至无穷多个 纳什均衡 究竟哪个更合理 纳什均衡假定每一个参与人在选择自己的最优战略时假定所有其他参与人的战略是给定的 但是如果参与人的行动有先有后 后行动者的选择空间依赖于前行动者的选择 前行动者在选择时不可能不考虑自己的行动对后行动者的影响 子博弈完美纳什均衡的一个重要改进是将 合理纳什均衡 与 不合理纳什均衡 分开 完全信息动态博弈 子博弈完美纳什均衡 举例 泽尔腾 1965 进入者 进入 不进入 0 300 在位者 合作 40 50 斗争 10 0 市场进入阻挠博弈树 特点 剔除博弈中包含的不可置信威胁 承诺行动 破釜沉舟 背水一战给定进入者进入 剔除 进入 斗争 进入 默许 是唯一的子博弈完美纳什均衡 不可置信威胁 支付函数 行动 子博弈完美纳什均衡 一个纳什均衡称为完美纳什均衡 当只当参与人的战略在每个子博弈中都构成纳什均衡 也就是说 组成完美纳什均衡的战略必须在每一个子博弈中都是最优的 一个完美纳什均衡首先必须是一个纳什均衡 但纳什均衡不一定是完美纳什均衡 承诺行动 当事人使自己的威胁战略变得可置信的行动 完全信息动态博弈 子博弈完美纳什均衡泽尔腾 1965 泽尔腾引入子博弈完美纳什均衡的概念的目的是将那些不可置信威胁战略的纳什均衡从均衡中剔除 从而给出动态博弈的一个合理的预测结果 简单说 子博弈完美纳什均衡要求均衡战略的行为规则在每一个信息集上是最优的 子博弈完美纳什均衡 不可置信威胁 美国普林斯顿大学古尔教授在1997年的 经济学透视 里发表文章 提出一个例子说明威胁的可信性问题 两兄弟老是为玩具吵架 哥哥老是要抢弟弟的玩具 不耐烦的父亲宣布政策 好好去玩 不要吵我 不管你们谁向我告状 我都把你们两个关起来 关起来比没有玩具更可怕 现在 哥哥又把弟弟的玩具抢去玩了 弟弟没有办法 只好说 快把玩具还我 不然我就要去告诉爸爸 哥哥想 你真要告诉爸爸 我是要倒霉的 可是你不告状不过没有玩具玩 而告了状却要被关禁闭 告状会使你的境遇变得更坏 所以你不会告状 因此哥哥对弟弟的警告置之不理 的确 如果弟弟是会算计自己利益的理性人 在这样的环境下 还是不告状的好 可见 弟弟是理性人 他的告状威胁是不可置信的 子博弈完美纳什均衡 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的一个不可置信的威胁 同样 不开发 不开发 也是一个不可置信威胁 纳什均衡 开发 不开发 不开发 是不合理的 子博弈完美纳什均衡 泽尔腾引入子博弈完美纳什均衡的概念的目的是将那些不可置信威胁战略的纳什均衡从均衡中剔除 从而给出动态博弈的一个合理的预测结果 简单说 子博弈完美纳什均衡要求均衡战略的行为规则在每一个信息集上是最优的 什么是子博弈 什么是子博弈完美纳什均衡 有没有更好的方法找到子博弈完美纳什均衡 子博弈由一个决策结x和所有该决策结的后续结T x 包括终点结 组成 它满足下列条件 1 x是一个单结信息集 2 子博弈不改变原博弈的信息集和支付向量 子博弈 条件1说的是一个子博弈必需从一个单结信息集开始 即 1 当且仅当决策者在原博弈中确切地知道博弈进入一个特定的决策结时 该决策结才能作为一个子博弈的开始 2 如果一个信息集包含两个以上决策结 没有任何一个决策结可以作为子博弈的初始结 条件2说的是 子博弈的信息集和支付向量都直接继承自原博弈 并不会发生任何变化 这意味着子博弈不能分割原博弈的信息集 完全信息动态博弈 子博弈完美纳什均衡泽尔腾 1965 不开发 不开发 房地产开发博弈 找出房地产开发博弈的子博弈 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 完全信息动态博弈 子博弈完美纳什均衡泽尔腾 1965 子博弈完美纳什均衡 扩展式博弈的战略组合是一个子博弈完美纳什均衡 如果 1 它是原博弈的纳什均衡 2 它在每一个子博弈上给出纳什均衡 A 开发 不开发 B B 开发 不开发 开发 1 0 0 1 0 0 3 3 x x 房地产开发博弈 不开发 开发 开发 开发 不开发 开发 开发 不开发 不开发 在c上构成均衡 在b上不构成 在b和c上都构成在b上构成均衡 在c上不构成 完全信息动态博弈 子博弈完美纳什均衡泽尔腾 1965 不开发 判断下列均衡结果哪个构成子博弈完美纳什均衡 不开发 b c 子博弈精炼纳什均衡 可信性问题子博弈和逆向归纳法子博弈精炼纳什均衡应用举例有同时选择的两阶段动态博弈 可信性 开金矿博弈 甲在开采一价值4万元的金矿时缺1万元资金 而乙正好有1万元资金可以投资 甲希望乙能将1万元资金借给自己用于开矿 并许诺在采到金子后与乙对半分成 乙是否该将钱借给甲呢 开金矿I 无法律的博弈 1 0 开金矿II 有法律保障的博弈 逆向归纳法 逆向归纳法就是从动态博弈的最后一个阶段或最后一个子博弈开始 逐步向前倒推以求解动态博弈的方法 用逆向归纳法求解的子博弈完美纳什均衡也要求 所有的参与人是理性的 是共同知识 如果博弈由多个阶段组成 则从逆向归纳法得到的均衡可能并不非常令人信服 子博弈精炼纳什均衡 扩展式博弈的战略组合s s1 si sn 是一个子博弈精炼纳什均衡 如果 1 它是原博弈的纳什均衡 2 它在每一个子博弈上给出纳什均衡 一个战略组合是一个子博弈精炼纳什均衡 当只当它在每一个子博弈上都构成一个纳什均衡 子博弈精炼纳什均衡应用举例 斯坦克尔伯格 Stackelberg 寡头竞争模型劳资博弈讨价还价博弈 Stackelberg寡头竞争模型 一个市场上只有两个企业 他们的行动都是选择产量 但行动有先后顺序 企业1 领头企业 Leader 首先选择产量q1 0 企业2 尾随企业 Follower 观测到q1 然后选择自己的产量q2 0 设总产量Q q1 q2 两个企业有相同的不变单位成本c 0 需求函数P Q a Q a q1 q2 问题 两个企业应如何决策 库诺特模型与斯氏模型比较 库诺特模型均衡结果 q1 q2 1 3 a c q1 q2 2 3 a c 1 2 1 9 a c 2 斯氏模型均衡结果 q1 1 2 a c q2 1 4 a c q1 q2 3 4 a c 1 1 8 a c 2 2 1 16 a c 2 张教材107页 张教材43页 劳资博弈 工会决定工资水平 但企业决定雇用多少人 工会不只追求高工资 还希望被雇人数多 不喜欢高工资高失业 也不喜欢低工资低失业 工会方的效用是工资水平和雇用人数两者的函数u u w L 工会的目标是最大化总效用假设收益是劳动雇用量的函数R L 边际效益递减 再假设只有劳动成本 工厂的利润函数为 w L R L w L 讨价还价博弈 1 假设有甲乙两人就如何分割1万元进行谈判 并且已定下了如下规则 首先 由甲提出一个分割比例 对此 乙可以接受也可以拒绝 如果乙拒绝 则乙自己应提出另一个方案 让甲选择接受与否 如此循环 在循环中 只要有任何一方接受对方的方案博弈就告结束 而如果方案被拒绝 则被拒绝的方案与以后的讨价还价过程不再有关系 讨价还价博弈 2 每次一方提出一个方案和另一方选择是否接受为一个阶段 再假设讨价还价每多进行一个阶段 由于谈判费用和利息损失等 双方的得益都要打一次折扣 折扣率为 0 1 称为消耗系数 如果限制讨价还价最多只能进行三个阶段 到第三阶段乙必须接受甲的方案 这就是一个三阶段讨价还价博弈 接受不接受 出S乙必须接受 讨价还价博弈 3 甲 出S1 乙 接受不接受 出S2 甲 S1 10000 S1 S2 10000 S2 2S 2 10000 S 第一阶段第二阶段第三阶段 轮流出价的讨价还价模型 分蛋糕的动态博弈游戏规则 第一轮由第一个参与人 小鹃 提出条件 第二个参与人小明可以接受 从而游戏结束 也可以不接受 则游戏进入第二轮 小明提出条件 小鹃可以接受 从而结束游戏 也可以不接受 从而进入第三轮 蛋糕融化呈线性 游戏结束 蛋糕融化 第一种情况 假设博弈只有一步 小鹃提出分配方案 如果小明同意 两个人按照约定分蛋糕 如果小明不同意 两人什么也得不到 结果会怎样 轮流出价的讨价还价模型 第二种情况 桌上放了一个冰淇淋蛋糕 但两轮谈判过后 蛋糕将完全融化 博弈结果如何 第三种情况 桌上的冰淇淋蛋糕在三轮谈判后将完全融化 结果又如何 第四种情况 桌上的冰淇淋蛋糕在四轮谈判后将完全融化 或者在五轮谈判 六轮 100轮谈判后将完全融化 结果又如何 博弈的结果是 假如 轮数 是偶数 双方各得一半 假若轮数是奇数 则小鹃得到 n 1 2n 小明得到 n 1 2n 囚徒的救赎 好莱圬大片 肖申克的救赎 是一部很好看的电影 主要内容是一个被冤屈的囚犯如何凭着坚定的信念和聪明才智逃出牢房 我们的 囚犯 也可以通过好的策略合作 摆脱 困境 的诅咒 囚徒的救赎 一报还一报 一报还一报能够赢得竞赛不是靠打击对方 而是靠从对方引出使双方都有好处的行为 如果重复博弈多次 就有报复的机会 这种惩罚的规则是 人家对你怎么做 你就对他怎么做 如果他上次背叛了你 你这次背叛他 如果上次他与你合作 你这次就选择与他合作 艾克谢罗德认为 一报还一报体现了这个策略符合四个优点 清晰 善意 报复性和宽恕性 这一法则不会引发作弊 所以是善意的 它不会让作弊者逍遥法外 所以是报复的 它不会长时间怀恨在心 只要作弊者改正 就愿意恢复合作 所以是宽恕的 一报还一报从自己的不可欺负性得到好处 还放弃了占他人便宜的可能性 囚徒的救赎 重复囚徒困境的几个建议 1 不要嫉妒2 不要首先背叛3 对合作和背叛都要给予回报4 不要耍小聪明 旅行者困境 做人不要太精明 哈佛大学巴罗教授 两个旅行者从一个以生产细瓷花瓶闻名的地方旅行回来 在提取行李的时候 发现花瓶被摔坏了 就向航空公司索赔 航空公司知道花瓶的价格大概杂八 九十元 但不知道他们购买的确切价格 因此航空公司请两位旅客在100元以内写出花瓶的价格 如果两个人写得一样 就按照写的数额赔偿 如果不一样 原则上按照低的价格赔偿 并认为该旅客讲了真话 奖励2元 而讲假话的罚款2元 这个博弈的最终结果将是什么 旅行者困境 一位富翁的狗在散步时跑丢了 于是他急匆匆到电视台发了一则启示 有狗丢失 归还者得酬金1万元 并附有狗的彩照 一个乞丐看到广告后 第二天一大早就报着狗准备去领酬金 当他经过一家大商店的墙体屏幕时 发现酬金涨到了3万元 乞丐又折回住处 把狗重新拴在那里 在接下来的几天里 乞丐从来没有离开过这只大屏幕 当酬金涨到使全市居民感到惊讶时 乞丐返回他的住处 可是那只狗已经死了 在这个世界上 金钱一旦被作为筹码 就不会再买到任何东西 重复博弈和无名氏定理 序贯博弈 不同阶段的博弈结构不同重复博弈 同样结构的博弈重复多次 其中的每次博弈可称 阶段博弈 影响重复博弈均衡结果有二 其一 博弈重复次数 多次博弈可能使参与人选择 合作 影响重复博弈均衡结果之二 信息的完备性 当一个人的支付函数 包括行动和结果 不为其他人所知时 他可能有积极性选择 合作 策略从而建立 好 声誉以换取长期利益 有限次重复博弈 连锁店悖论 市场的 先来后到 重复博弈中 在位者在第一次选择 斗争 时不可置信的威胁 惟一的子博弈精炼纳什均衡是他总是 默许 倒着想 如果已经进入了n 1个 在最后一个时 其威胁本来是不可置信的 则最后一个会 默许 再往前推 由于每阶段的 斗争 都是不可置信的 则所有大门都在 默许 下向后来者敞开悖论 我n大的市场岂容你染指 斗 但事实不会如此只要博弈的重复次数是有限的 重复 并不改变囚徒困境的结果 无限次重复博弈和无名氏定理 解开连锁店难题的办法之一是引入信息的不完全性 不确定性可以成为经济运行的资源 当博弈重复无限次时 存在着完全不同与一次博弈的子博弈精炼纳什均衡冷酷战略或触发战略 只要你骗我一次 背叛 我永远不理你 不合作 无名氏定理 有一个一次博弈G可作为某无穷博弈的一个阶段 G有纳什均衡及其结果 对于无限博弈 肯定存在一个贴现因子 使无限博弈的结果不劣 弱优 于G的纳什均衡结果 参与人不固定的重复博弈 重复博弈时 厂商不敢以劣货欺人在经济学或管理学中使用 信誉 这样一个不好解释的概念 但在博弈论中却在某些假设之下 逻辑地 证明了 所谓 信誉 无非对自己行为的预期为什么买于 坐贾 而非 行商 为什么车站旁边的劣质品那么多 企业存在的一个原因是创造一个 长期参与人 因其考虑长期利益而遵章守纪 态度积极 不确定环境下的重复博弈 寡头市场上 低需求时容易使他们都选择 合作 但在高需求时 利润的诱惑使他们都选择 背叛 这种情况可以重复能同甘却不能共苦 似乎有道德谴责的意味 但这一现象总是发生 发生的逻辑是什么 博弈论可以解释 作业 五个海盗抢到100颗宝石 他们决定按如下方法来分配 先抽签决定顺序 1 2 3 4 5 然后先由1号提出分配方案 其余的人进行表决 当且仅当有半数和超过半数的人同意时 则按1号所提方案分配 否则将1号扔进大海喂鲨鱼 当1号提出分配方案被否决后 则由2号提出分配方案 其余的人进行表决 当且仅当半数和超过半数的人同意时 则按2号所提方案分配 否则将2号扔进大海喂鲨鱼 以后依此类推 假定这些海盗都是理性人 问第一个海盗应提出怎样的分配方案才能获得通过并使自己的收益最大