决策理论与方法.ppt

第七章竞争型决策分析 博弈论 gametheory 是由美国数学家冯 诺依曼 Von Neumann 和经济学家摩根斯坦 Morgenstern 于1944年创立的带有方法论性质的学科 它被广泛应用于经济学 人工智能 生物学 火箭工程技术 军事及政治科学等 博弈论是一门十分有趣但理论上又是十分艰深的学问 我今天打算用一些大家能够凭直观或简单分析就能把握的例子为同学们介绍博弈论的基本概念及应用 要想在现代社会做一个有文化的人 你必须对博弈论有一个大致了解 保罗 萨缪尔森 什么是博弈论 博弈论是研究理性的决策者之间的冲突与合作的理论 具体讲就是研究当决策主体的行为在发生直接的相互作用时 人们如何进行决策以及这种决策的均衡问题 什么是博弈 博弈是指代表不同利益主体的决策者 在一定的环境条件和规则下 根据所掌握的信息 同时或先后 一次或多次从各自允许选择的行动方案中加以选择并实施 从而取得各自相应结果的过程 田忌赛马 续篇 古代齐威王与大将田忌赛马 田忌的谋士孙膑运用计谋帮助田忌以弱胜强 比赛规则 田忌与齐威王各出三匹马 一对一比赛三场 每一场的输方要赔1千金给赢方 双方的马按实力都可以分为上 中 下 但齐威王的上 中 下均优于田忌的上 中 下 实际上 田忌的上马 中马要优于齐威王的中马 下马 比赛结果 田忌连输三场 后孙膑建议 以上对中 以中对下 以下对上 结果以2 1赢得比赛 这个案例生动地告诉我们 巧妙地运用策略是多么的重要 但是 事情并没有结束 齐威王也很聪明 他利用各种手段 很快明白了自己输掉比赛的原因而及时地调整了自己的对策 这样 齐威王与田忌的赛马也就成了一个具有策略依存特征的决策较量 构成了一个典型的博弈问题如果把赢一千金记成收益1 输一千金记成收益为 1 则齐威王和田忌在各种策略组合下的收益如下表所示 田忌赛马 续篇 齐威王 田忌 田忌赛马 续篇 田忌赛马 续篇 在上述混合策略下 齐威王的期望得益为1 6 3 1 1 1 1 1 1 田忌的期望得益为1 6 1 3 1 1 1 1 1 即多次进行这样的赛马 齐威王平均每次能赢田忌1千金 这是因为齐威王三匹马的总体实力略胜田忌三匹马总体实力的缘故 博弈的要素 1 参与人 是指博弈中独立决策 独立承担结果的决策主体 他们可以是自然人或团体或法人 如企业 国家 地区 社团 欧盟 北约等 那些不作决策或虽做决策但不直接承担决策后果的被动主体不是参与人 而只能当做环境参数来处理 如指手划脚的看牌人 看棋人 企业的顾问等 博弈的要素 2 策略指每个博弈方在进行决策时可以选择的方法 做法等 策略有纯策略和混合策略之分 纯策略指参与人在博弈中可以选择采用的行动方案 混合策略是在纯策略空间上的一种概率分布 表示参与人实际进行决策时根据这种概率分布在纯策略中随机选择加以实施 博弈的要素 3 支付 每个博弈方从各种策略组合中获得的收益或效用 它是策略组合的函数 所以也称支付函数记为ui s ui s ui s1 s2 si sn 1 sn 博弈的要素 4 博弈方的信息信息是博弈参与方有关其他博弈方的策略 收益等知识 5 博弈的次序规定一个博弈就必须规定其次序 不同的次序是不同的博弈 6 结果和均衡结果指博弈中博弈方的行动所产生的每一可能情形 博弈的分类 一 按参与方数目 1 单人博弈2 两人博弈3 多人博弈 博弈的分类 二 按各博弈方可选策略数量的多少1 有限博弈2 无限博弈 博弈的分类 三 按参加博弈的各个博弈方从博弈中所获得的利益总和1 零和博弈2 常和博弈3 变和博弈 博弈的分类 四 按参与人行动的先后顺序1 静态博弈2 动态博弈 博弈的分类 五 按参与人所掌握的信息1 完全信息博弈2 不完全信息博弈 博弈的分类 综合划分 第二节完全信息静态博弈 一 占优战略均衡二 重复剔除的占优战略均衡三 纳什均衡 一 占优战略均衡 不论其他参与人选择什么战略 他的最优战略是唯一的 这样的最优战略被称为 占优战略 dominantstrategies 占优战略均衡只要求所有的参与人是理性的 而并不要求每个参与人知道其他参与人也是理性的 因为 不论其他参与人是否理性 占优战略总是一个理性参与人的最优选择 1 囚徒困境两个小偷甲和乙联手作案 私入民宅被警方逮住但未获证据 警方将两人分别置于两间房间分开审讯 政策是若一人招供但另一人未招 则招者立即被释放 未招者判入狱10年 若二人都招则两人各判刑5年 若两人都不招则未获证据但因私入民宅各拘留1年 一 从 囚徒困境 谈起 甲和乙是参与博弈的人 称为 局中人 表1中每一个小方格内的数字被称为局中人的支付 其中左边的数字代表甲的支付 右边的是乙的支付 表1中的双变量矩阵称为博弈支付矩阵 局中人所选择的战略构成的组合 招 招 被称为博弈均衡 这个组合中前后两个战略分别表示甲和乙所选择的战略 表1囚徒困境博弈乙招不招招甲不招 问题1 甲 乙如何选择 对甲来说 尽管他不知道乙是选择了 招 还是 不招 他发现他自己选择 招 都是比选择 不招 为好的 因此 不招 是相对于 招 的劣战略 他不会选择劣战略 所以 甲会选择 招 同样 根据对称性 乙也会选择 招 结果是甲乙两人都 招 表1囚徒困境博弈乙招不招招甲不招 甲和乙都不会选择劣战略 不招 称为 剔除劣战略的占优战略均衡 其中 招 是占优于 优于 不招 的占优战略 总结 囚徒困境反映了一个深刻的问题 这就是个人追求最大自身利益的行为 常常并不能导致实现社会的最大利益 也常常不能真正实现个人自身利益的最大化 我们可以利用这个道理来分析日常生活中的许多不合作现象 2 生活中的 囚徒困境 例子 例子1 商家价格战出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利 但实际上却是相互杀价 结果都赚不到钱 当一些商家共谋将价格抬高 消费者实际上不用着急 因为商家联合维持高价的垄断行为一般不会持久 可以等待垄断的自身崩溃 价格就会掉下来 譬如 2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位 他们搞了一个 彩电厂家价格自律联盟 并在深圳举行了由多家彩电厂商首脑参加的 彩电厂商自律联盟高峰会议 当时 国家有关部门还未出台相关的反垄断法律 对于这种在发达国家明显属于违法行为的所谓 自律联盟 国家在法律上暂时还是无能为力的 寡头厂商在光天化日之下进行价格合谋 并且还通过媒体大肆炒作 这在发达国家是不可思议的 但是 尽管政府当时无力制止这种事情 公众也不必担心彩电价格会上涨 这是因为 彩电厂商自律联盟 只不过是一种 囚徒困境 彩电价格不会上涨 在高峰会议之后不到二周 国内彩电价格不是上涨而是一路下跌 这是因为厂商们都有这样一种心态 无论其他厂商是否降价 我自己降价是有利于自己的市场份额扩大的 例子2 为什么要加入WTO WTO是一个自愿性申请加入的自由贸易联盟 即WTO成员国之间实现低关税或零关税的相互间自由贸易 为什么需要一个组织来协调国家之间的自由贸易呢 这是因为 如果没有一个协调组织 国与国之间的贸易就不会呈现低关税或零关税的自由贸易局面 因为这时国与国之间的贸易是一个 囚徒困境 给定一个国家对另一个国家的货物实行低关税 另一个国家反过来对这个国家的货物实行高关税是占优于实行低关税的战略的 二 重复剔除的占优战略均衡 严格劣战略 是指无论其他博弈参与人采取什么战略 某一参与人的相对不利战略是唯一的 1 智猪博弈猪圈中有一头大猪和一头小猪 在猪圈的一端设有一个按钮 每按一下 位于猪圈另一端的食槽中就会有10单位的猪食进槽 但每按一下按钮会耗去相当于2单位猪食的成本 如果大猪先到食槽 则大猪吃到9单位食物 小猪仅能吃到1单位食物 如果两猪同时到食槽 则大猪吃7单位 小猪吃3单位食物 如果小猪先到 大猪吃6单位而小猪吃4单位食物 表4给出这个博弈的支付矩阵 二 智猪博弈 对诸多经济现象的解释 表4智猪博弈小猪按等待按大猪等待 这个博弈没有 剔除劣战略均衡 因为大猪没有劣战略 但是 小猪有一个劣战略 按 因为无论大猪作何选择 小猪选择 等待 是比选择 按 更好一些的战略 所以 如果小猪是理性的 小猪会剔除 按 而选择 等待 大猪知道小猪会选择 等待 从而自己选择 按 所以 可以预料博弈的结果是 按 等待 这称为 重复剔除劣战略的占优战略均衡 其中小猪的战略 等待 占优于战略 按 而给定小猪剔除了劣战略 按 后 大猪的战略 按 又占优于战略 等待 总结 在寻找智猪博弈的均衡解时 我们的做法可归纳如下 1 首先找出某一博弈参与人的严格劣战略 将它剔除掉 从新构造一个不包括已剔除战略的博弈 2 然后继续剔除这个新的博弈中某一参与人的严格劣战略 3 重复进行这一过程 直到剩下唯一的参与人战略组合为止 这唯一的参与人战略组合 就是这个博弈的均衡解 称为重复剔除的占优战略均衡 生活中的智猪博弈 例子1 股市博弈在股票市场上 大户是大猪 他们要进行技术分析 收集信息 预测股价走势 但大量散户就是小猪 他们不会花成本去进行技术分析 而是跟着大户的投资战略进行股票买卖 即所谓 散户跟大户 的现象 例子2 为何股份公司中的大股东才有投票权 在股份公司中 大股东是大猪 他们要收集信息监督经理 因而拥有决定经理任免的投票权 而小股东是小猪 不会直接花精力去监督经理 因而没有投票权 例子3 为什么中小企业不会花钱去开发新产品 在技术创新市场上 大企业是大猪 它们投入大量资金进行技术创新 开发新产品 而中小企业是小猪 不会进行大规模技术创新 而是等待大企业的新产品形成新的市场后生产模仿大企业的新产品的产品去销售 三 纳什均衡 纳什均衡 Nashequilibrium 是指这样一种策略组合 这种策略组合由所有参与人的最优策略组成 也就是说 在给定别人策略的情况下 没有任何单个参与人有积极性选择其他策略 从而没有任何人有积极性打破这种均衡 情侣博弈 大海和美凤正在热恋中 难得的周末又到了 安排什么节目好呢 大海是个超级球迷 周末晚上 中国足球队要在世界杯外围赛中和伊朗队做生死之战 而美凤从小练习芭蕾 对斯拉夫民族的芭蕾艺术崇拜的五体投地 这周末是正宗俄罗斯芭蕾舞剧 胡桃夹子 的谢幕演出 怎么办 我说 一个在家看电视直播的足球 一个去剧院看芭蕾演出不就得了 问题是他们是热恋中的情侣 分开各自度过这难得的周末时光 才是他们最不乐意的事情 于是他们就面临一场温情笼罩下的博弈 见下图 情侣博弈 情侣博弈 在情侣博弈中 双方都没有严格优势策略和严格劣势策略 芭蕾不是大海的劣势策略 因为如果美凤坚持芭蕾 他选足球只得0 选芭蕾还可以得1 足球当然更不是大海的劣势策略 所以 大海没有全面的劣势策略 同样 美凤也没有全面的劣势策略 这样 严格劣势策略消去法就没有用武之地了 情侣博弈 纳什均衡就是解决这类问题的良方 我们只须关心一种双方的 相对优势策略 的组合 在情侣博弈中 双方都去看足球或者双方都去看芭蕾 这就是我们所说的相对优势策略的组合 一旦处于这样的位置 双方都不想单独改变策略 因为单独改变没有好处 准确地说是单独改变不会带来额外好处 所以两人一起去看足球是稳定的结局 两人一起去看芭蕾也是稳定的结局 在情侣博弈中 足球 足球 和 芭蕾 芭蕾 是博弈的两个纳什均衡 斗鸡博弈 同一宿舍的两个男同学关系相当不错 在他们的生活中出现一位女生 他们两人都对这个女生很有好感 现在假如两个人同时公开宣布喜欢这个女生并准备去追求 则他们都觉得很尴尬 而且他们的关系也会出现僵化 这是他们不愿意得到的结果 在这里假定没有哪个同学特别喜欢这个女生 可以不顾一切 也假定这个女生不是特别偏向哪个男生 下面是他们的支付矩阵 斗鸡博弈 斗鸡博弈 要是甲首先宣布开始追求那个女孩 那乙同学的最优选择就是放弃 这样的话就可以避免和好朋友闹翻 这正是他最不愿意看到的 同样 要是乙同学首先宣布开始追求那女孩 那甲同学的最优选择也同样是放弃 道理是一样的 这时候就出现了两个纳什均衡 一个是甲同学追求 乙同学不追求 另一个就是甲同学不追求 乙同学追求 到底哪个均衡会出现了 这要由生活中其他的偶然因素决定 有时是甲同学碰巧先宣布 有时是乙同学碰巧先宣布 经济生活中的实例 在城市街道上 我们常见到一些地段上的商店十分拥挤 构成一个繁荣的商业中心区 但另一些地段却十分冷僻 没什么商店 对于这种现象 我们可以运用纳什均衡的概念来加以解释 甲乙1 2图1商业位置博弈 见图1 有一个长度为1单位的街道 在街道两边均匀地分布着居民 现有两家商店决定在街道上确定经营位置 如果甲在街道中间位置1 2处设店 则乙的最好选择是紧靠甲的左边或右边设店 当乙在甲的右边紧靠甲设店时 其右边街道上的顾客都是乙的顾客 如果乙不是紧靠甲而是远离甲设店 则其顾客只是其右边街道的居民 不如它紧靠甲设店时多 因而在远离甲的位置设店是劣战略 所以给定甲在1 2处设店 乙在紧靠甲的左边或右边设店是最优的 反过来 给定乙在接近1 2处设店 甲的最优选择也是在1 2附近设店 因为在这个位置 谁要是单独移开 一点 就会损失 半点 市场份额 所有谁都不愿意偏离中点的位置 这样 甲和乙挤在1 2处设店就是纳什均衡 这就是商业中心区的形成原理 如果换成三家呢 张五常对博弈论的质疑 第三节完全信息动态均衡 一 子博弈精炼纳什均衡二 重复博弈三 动态博弈战略行动 一 子博弈精炼纳什均衡 在动态博弈中 参与人的行动有先后顺序 而且后行动的参与人在自己行动之前可以观测到先行动者的行动 并选择相应战略 由于先行动者拥有后行动者可能选择战略的完全信息 因而先行动者在选择自己的战略时 就可以预先考虑自己的选择对后行动者选择的影响 并采取相应的对策 以某一房地产开发博弈为例 下图显示了静态条件下双方参与人的得失 图7 4房地产开发博弈 子博弈的定义 子博弈是原博弈的一部分 它本身可以作为一个独立的博弈进行分析 例如图7 4中 每一列或每一行都是一个子博弈 任何博弈本身则被称为自身的一个子博弈 在A先采取行动后 B对A的回应构成包括原博弈在内的三个子博弈 房地产开发商A是先行动者 在行动之前 A对竞争者B的战略进行了预测 认为B有四种战略可选 1 无论A是否开发 B都要开发 2 如果A开发 B也开发 如果A不开发 B也不开发 3 如果A开发 B就不开发 如果A不开发 B就开发 4 无论A是否开发 B必定不开发 将B可能采取的战略与图7 4中博弈双方相应选择的得失结合起来 可以得出下图 图7 5A对B的预测 在表7 4中 存在着两个纳什均衡 即 A开发 B不开发 和 A不开发 B开发 而在B可能选择的战略中 战略1虽然包括了上述后一种纳什均衡 但没有包括前一种纳什均衡 战略4虽然包括了上述前一种纳什均衡 但没有包括后一种纳什均衡 战略2则上述两种纳什均衡都没有包括 只有战略3包括了上述两种均衡 换句话说 如果B选择战略3 那么不论A作出什么选择 B的回应都达到纳什均衡 而在给定B会采取战略3来回应A的选择的前提下 开发是A的最优策略 因而A选择了开发 以上的分析方法 称为子博弈精炼纳什均衡 只有当某一战略选择在每一个子博弈 包括原博弈 上都构成一个纳什均衡时 这一战略组合才是子博弈精炼纳什均衡 而前面提到的B的四种战略中 只有战略3在所有子博弈中都构成纳什均衡 所有这一博弈中唯一的子博弈精炼纳什均衡 就是 开发 不开发 开发 即作为后行动者的B选择战略3 而作为先行动者的A选择开发 注意 在A选择开发时 无论B选择战略3或战略4 其结果都构成纳什均衡 而子博弈精炼纳什均衡法要剔除的 正是这种在特定情况下是合理的 而在其他情况下不合理的战略组合 二 重复博弈 上述博弈是参与人在前一个阶段的选择将决定随后的子博弈的结构 这样的动态博弈称为序贯博弈动态博弈中另外一类是所谓的重复博弈 顾名思义 重复博弈是指同样结构的博弈重复许多次 其中的每次博弈称为阶段博弈 影响重复博弈结果的因素 1 博弈重复的次数当博弈只进行一次时 每个参与人都只关心一次性的支付 但如果博弈重复多次 参与人可能会为了长远利益而牺牲眼前利益 从而选择不同的战略 2 信息的完备性当信息不完全时 参与人为了获得合作带来的长期利益 不愿过早暴露自己的本性 二 重复博弈 我们用一个产品定价博弈的例子来分析重复博弈 表7 6表示了这一博弈的有关情况 该图说明 在一次性的完全信息静态博弈中 两个参与人A与B均有占优战略 占优战略均衡为双方都定低价 图7 6产品定价博弈 二 重复博弈 一次性博弈意味着没有人能够对其他参与人的行为进行奖励或报复 而在动态重复博弈中 所有参与人过去的行为都是可以观测到的 因而某一参与人可以通过自己在本阶段博弈中的选择 来回应其他参与人在以前的阶段博弈中的行为 以产品定价为例 如果上一阶段博弈中 B选择了高价 使得也选择了高价的A得到了好处 那么A可以在本阶段博弈中继续选择高价作为对B的奖励 如果B选择了低价 使得选择了高价的A遭受了损失 那么A可以在本阶段博弈中选择低价作为对B的报复 博弈次数无限 如果B选择与A合作维持产品高价 则B各阶段所得是 32 32 32 32 如果B选择不与A合作 并在第一阶段通过选择低价使选择高价的A受到损失 A则在以后各阶段的博弈中选择低价以报复 则B各阶段所得为 40 24 24 24 可以看出 B在第一阶段博弈中采取不合作行动的好处 将因为A在以后各阶段所采取的报复性选择而抵消 重复博弈若干次后 B将得不偿失 博弈次数无限 在这里 A所采取的战略称为冷酷战略 按照这种战略 A起初选择合作 但如果B在某一阶段博弈中选择不合作的话 A将永远选择不合作 A这样做的理由是 选择不合作 他各阶段的所得是24 而选择合作 他各阶段的所得少于24 因为B在某一阶段博弈中的不合作排除了双方合作获得双赢的可能 因此 A有坚持冷酷战略的积极性 也就是说 冷酷战略意味着任何一个人的一次不合作将触发永远的不合作 无限次重复博弈的所有参与人慑于冷酷战略的严重后果 有积极性维持合作 博弈重复次数有限 所有人都明白在最后一次博弈中选择占优策略 会给自己带来超额利润而不会遭到其他参与人的报复 因此所有参与人在最后阶段博弈都会不约而同地选择低价战略 但是 这也意味着无论B在倒数第二阶段选择什么战略 A在最后阶段都将采取低价战略 因此 在倒数第二阶段 B就没有必要因为担心A报复而采取高价战略 由此从最后阶段开始 逐个阶段推理 可以得到以下结论 在阶段博弈有唯一的纳什均衡时 n次重复博弈的唯一子博弈精炼纳什均衡结果 是阶段博弈的纳什均衡重复n次 即每个阶段博弈出现的都是一次性博弈的均衡结果 三 动态博弈战略行动 一 首先行动优势首先行动优势 first moveradvantage 是指 在博弈中首先作出战略选择并采取相应行动的参与人可以获得较多的利益 例如 在我们前面讲到的情侣博弈中 到底是足球还是芭蕾呢 如果美凤学过博弈论 她就会采取先发制人的策略 先把两张芭蕾票买了 然后对大海强调票很贵很难买到 自己非常想去 那么大海会迫于形势 顺从她的爱好 三 动态博弈战略行动 二 确实可信的威胁确实可信的威胁 crediblethreat 是指 博弈的参与人通过某种行动改变自己的支付函数 从而使得自己的威胁显得可信 参与人为改变博弈结果而采取的措施称为承诺 commitment 前面讲过的房地产开发案例中 在A选择之前 如果B与某一客户签订合同 规定B在一定期限内向客户交付一定面积的住房 如果B不能按时履约 须赔偿客户5单位货币 则原博弈结构发生了根本变化 见下图 图7 7房地产开发博弈 B承诺后 确实可信的威胁 因此 B的第1种战略 无论A是否开发我都要开发成为确实可信的威胁 表7 8表示了A对B的战略估计的变化 所以 这一博弈的子博弈精炼纳什均衡 就由原来的 开发 不开发 开发 变成 不开发 开发 开发 前面介绍的博弈都包含一个基本假设 即完全信息假设 按照这一假设 每一个参与人对所有其他参与人的类型 战略 支付函数都有精确的了解 但是 在许多情况下 参与人对对手的了解往往是不够精确的 这种情况下的博弈就是不完全信息博弈 第四节不完全信息静态博弈 第四节不完全信息静态博弈 不完全信息静态博弈是指 在信息不完全的条件下 所有参与人同时行动 没有机会观察到别人的选择 每个参与人仅仅知道其他参与人有关类型的分布概率 而不知道其真实类型的博弈行为 注意 每一个参与人都不可能知道其他参与人实际上会选择什么战略 这时参与人的决策目标是 在给定自己的类型 以及给定其他参与人类型与战略选择的关系的前提下 使得自己的期望效用最大化 例题 市场进入博弈 某一市场原来被A企业垄断 现在B企业考虑是否进入 B企业知道 A企业是否允许它进入 取决于A企业的阻挠成本 如图7 9所示 如果A的阻挠成本低 那么A企业的占优策略是阻挠 如果A的阻挠成本高 那么A企业的占优策略是默许 但是 B企业所不知道的是 A的阻挠成本到底是高是低 在这里 某一参与人本人知道 其他参与人则不知道的信息称为私人信息 某一参与人所拥有的全部私人信息称为他的类型 第四节不完全信息静态博弈 图7 9市场进入博弈 解决这类问题的方法之一是 把不确定性条件下的选择转换为风险条件下的选择 本例中 B不知道A的类型 但他知道A在这两种类型下会作出的选择以及两种不同类型的分布概率 假定高阻挠成本的分布概率是x 则低成本的分布概率是 1 x 因此 B选择进入的所有期望利润是40 x 10 1 x 选择不进入的期望利润为0 简单的计算表明 当A的阻挠成本高的概率大于20 时 挑战者B选择进入得到的期望利润大于选择不进入的期望利润 此时 选择进入是B的最优策略 将不确定性条件下的选择转换为风险条件下的选择 称为海萨尼转换 通过海萨尼转换 不完全信息博弈变成了完全但不完美信息博弈 在上述转换的基础上 海萨尼提出了贝叶斯纳什均衡贝叶斯纳什均衡 是一种类型依赖型战略组合 在给定自己的类型和其他参与人类型的分布概率的条件下 这种战略组合使得每个参与人的期望效用达到了最大化 上例中的贝叶斯纳什均衡是 挑战者B选择进入 高成本原垄断者选择默许 低成本原垄断者选择阻挠 第五节不完全信息动态博弈 不完全信息动态博弈是指 在博弈开始时 某一参