第九章 运筹学博弈论ppt课件.ppt

第九章博弈论 引言完全信息静态博弈 有鞍点的博弈 混合策略 纳什均衡 完全信息静态博弈 非零和的情况 纳什均衡 教学目的与要求 理解具有竞争性问题的博弈思想 对纳什均衡概念有初步的认识 掌握矩阵博弈的求解方法 重点与难点 有鞍点的静态博弈和无鞍点的静态博弈 难点是纳什均衡的概念 教学方法 通过大量的实例讲解相关概念和解法 并进行课堂讨论 思考题 讨论题 作业 两个课堂讨论题 本章习题 参考资料 见前言 学时分配 6学时 引言 1 在社会活动 经济和经济管理 军事活动中 经常会遇到具有竞争性或利益相对抗的现象 例如下棋 打桥牌 体育竞赛 市场竞争 广告战 价格战 军事斗争等 竞争的各方总是想用最好的策略击败对方 取得尽可能好的结果 这就是博弈现象 博弈现象是一种特殊的决策 在不确定决策分析中 决策者的对手是 大自然 它对决策者的各种策略不产生反应 但在博弈现象中 代替 大自然 的是 有理性的人 因而任何一方做出的决定都必须充分考虑其他对手可能作出的反应 早期的博弈实例是中国春秋战国时代的齐王和田忌赛马的故事 齐王有上 中 下三等马 他麾下的大将也有上 中 下三等马 但是同等级的马都比齐王差一些 赛马时齐王表示按上 中 下的顺序出马 而田忌的谋士让他按下 上 中的顺序出马 比赛结果田忌赢了一千金 请思考 这是一种什么类型的博弈 理论上齐王不会输 但他为什么输了 在国外 1912年E Zermelo用集合论研究过下棋问题 四十年代由于生产和战争的需要 博弈理论得到了发展 系统博弈理论的形成则以1944年V Neumann O Morgensten合著的 博弈论和经济行为 一书为标志 1994年瑞士皇家科学院决定将诺贝尔经济学奖授予纳什 Nash 哈萨尼 Harsanyi 和泽尔腾 Selten 三人 表彰他们在博弈理论和应用研究方面作出的杰出贡献 目前 博弈论在定价 招投标 拍卖 委托代理以及很多重要的经营决策中得到应用 它已成为现代经济学的重要基础 约翰 纳什 JOHNF NASH 美国人 1928 由于他与另外两位数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献 对博弈论和经济学产生了重大影响 而获得1994年诺贝尔经济奖 约翰 海萨尼 JOHNC HARSANYI 美国人 由于他与另外两位数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献 对博弈论和经济学产生了重大影响 由此获得诺贝尔经学奖 约翰 纳什1928年生于美国 约翰 海萨尼1920年生于美国 莱因哈德 泽尔腾1930年生于德国 三人在非合作博弈的均衡分析理论方面做出了开创性贡献对博弈论和经济学产生了重大影响 瑞典诺贝尔基金会官方网站透露了近20年诺贝尔经济学奖得主名单及其主要贡献 即获奖理由 2004年挪威经济学家芬恩 基德兰德 FinnE Kydland 和美国经济学家爱德华 普雷斯科特 EdwardC Prescott 获奖理由 在动态宏观经济学方面做出了巨大贡献 2003年美国经济学家罗伯特 恩格尔 RobertF EngleIII 和英国经济学家克莱夫 格兰杰 CliveW J Granger 获奖理由 在经济时间数列中运用了统计学的方法 2002年美国学者丹尼尔 卡尼曼 DanielKahneman 和弗农 史密斯 VernonL Smith 获奖理由 在心理和实验经济学研究方面做出了开创性工作 2001年三位美国学者乔治 阿克尔洛夫 GeorgeA Akerlof 迈克尔 斯彭斯 A MichaelSpence 和约瑟夫 斯蒂格利茨 JosephE Stiglitz 获奖理由 在 对充满不对称信息市场进行分析 领域做出了重要贡献 2000年美国芝加哥大学的詹姆斯 赫克曼 JamesJ Heckman 和加州大学伯克利分校的丹尼尔 麦克法登 DanielL McFadden 获奖理由 在微观计量经济学领域做出了重大贡献 1999年加拿大著名经济学家罗伯特 蒙代尔教授 RobertA Mundell 获奖理由 对不同汇率体制下的货币和财政政策以及最优货币区域的分析做出了伟大贡献 1998年印度籍经济学家阿马蒂亚 森 AmartyaSen 获奖理由 对福利经济学以及发展经济学做出了突破性贡献 1997年美国经济学家迈伦 斯科尔斯 MyronS Scholes 和罗伯特 默顿 RobertC Merton 获奖理由 前者给出了著名的布莱克 斯科尔斯期权定价公式 该法则已成为金融机构涉及金融新产品的思想方法 后者对布莱克 斯科尔斯公式所依赖的假设条件做了进一步减弱 在许多方面对其做了推广 1996年英国人 JamesA Mirrlees 和美国人威廉 维克瑞 WilliamVickrey 获奖理由 前者在信息经济学理论领域做出了重大贡献 尤其是不对称信息条件下的经济激励理论的论述 后者在信息经济学 激励理论 博弈论等方面都做出了重大贡献 1995年美国人罗伯特 卢卡斯 RobertE LucasJr 获奖理由 倡导和发展了理性预期与宏观经济学研究的运用理论 深化了人们对经济政策的理解 并对经济周期理论提出了独到的见解 1994年美国人约翰 海萨尼 JohnC Harsanyi 和美国人约翰 纳什 JohnF NashJr 以及德国人莱因哈德 泽尔腾 ReinhardSelten 获奖理由 在非合作博弈的均衡分析理论方面做出了开创性的贡献 对博弈论和经济学产生了重大影响 1993年美国人罗伯特 福格尔 RobertW Fogel 和道格拉斯 诺斯 DouglassC North 获奖理由 前者用经济史的新理论及数理工具重新诠释了过去的经济发展过程 后者建立了包括产权理论 国家理论和意识形态理论在内的 制度变迁理论 1992年美国人加里 贝克 GaryS Becker 获奖理由 揭示并澄清了经济制度结构和函数中交易费用和产权的重要性 1990年美国人哈里 马科维茨 HarryM Markowitz 默顿 米勒 MertonH Miller 和威廉 夏普 WilliamF Sharpe 获奖理由 在金融经济学方面做出了开创性工作 1989年挪威人特里夫 哈维默 TrygveHaavelmo 获奖理由 建立了现代经济计量学的基础性指导原则 1988年法国人莫里斯 阿莱斯 MauriceAllais 获奖理由 在市场理论及资源有效利用方面做出了开创性贡献 并对一般均衡理论重新做了系统阐述 1987年美国人罗伯特 索洛 RobertM Solow 获奖理由 对增长理论做出贡献 提出长期的经济增长主要依靠技术进步 而不是依靠资本和劳动力的投入 1986年美国人詹姆斯 布坎南 JamesM BuchananJr 获奖理由 将政治决策的分析同经济理论结合起来 使经济分析扩大和应用到社会 政治法规的选择1985年意大利人弗兰科 莫迪利安尼 FrancoModigliani 获奖理由 第一个提出储蓄的生命周期假设 这一假设在研究家庭和企业储蓄中得到了广泛应用 什么是博弈论 所谓博弈是指局中人按一定规则 在充分考虑其他局中人可能采取的策略的基础上 从自己的策略集中选取相应策略 并从中得到回报的过程 博弈是一种特殊的决策 在决策论中 决策者的对手是大自然 在博弈论中 代替大自然的是有理性的人 因而任何一方做出决定时 都必须考虑其他对手可能作出的反应 构成博弈的三个要素 1 局中人 Players 是指参与竞争的各方 它可以是一个人 也可以是一个集团 但局中人必须是有决策权的主体 而不是参谋或从属人员 在博弈中局中人可以有两方 称为二人博弈 也可以有多方 称为多人博弈 在多人博弈中又可分为结盟和不结盟的情况 2 策略 Strategies 指局中人所拥有的对付其他局中人的手段 方案的集合 在静态博弈中 策略必须是一个独立的完整的行动 而不能是若干相关行动中的某一步 例如在齐王和田忌赛马的博弈中 双方都有六个策略 上 中 下 上 下 中 中 上 下 中 下 上 下 中 上 下 上 中 这六个策略形成一个策略集合 在一局对策中 局中人的策略只有有限个 称为有限策略 否则为无限策略 相应每个局中人的策略选择形成的策略组称为一个局势 3 收益函数 Payofffunction 指一局博弈后各局中人的输赢得失 用正的数字表示局中人的赢得 负的数字表示局中人的损失 显然 收益函数的取值与局中人选定的策略有关 于是一局博弈的 得失 是 局势 的函数 博弈论的研究建立在下述假设前提下 即参与博弈的各局中人都是理性的 对 理性 的理解 理性人是指有一个很好定义的偏好 在面临给定的约束条件下最大化自己的偏好 博弈中一个理性的决策必定建立在预测其他局中人的反应之上 一个局中人将自己置身于其他局中人的位置并为他着想从而预测其他局中人将选择的行为 在这个基础上该局中人决定自己最理想的行动 博弈的三个要素 即局中人 策略集和收益函数构成了博弈信息 根据不同信息可对博弈做如下分类 1 按局中人对信息掌握情况分为 完全信息博弈和不完全信息博弈 2 按局中人采取行动的次序分为 如果同时采取行动或在互相保密情况下采取行动 称为静态博弈 如果采取行动有先后 后采取行动的人可以观察到前面人采取的行动 称为动态博弈 我们只研究完全信息静态博弈 2 完全信息静态博弈 一 设博弈中只有局中人A B 局中人A的策略集为局中人B的策略集为 完全信息是指所有局中人对其他局中人各自策略集以及不同局势下的收益函数都有完全的了解 一 二人零和博弈 博弈的三个要素的矩阵表示 局中人A的收益 局中人A的收益函数可用如下的矩阵表示 二人零和博弈也称为矩阵博弈 博弈可表为 例1写出 石头 剪子 布 游戏的收益矩阵 石头赢剪刀1分 布赢石头1分 剪刀赢布1分 解 甲的策略集为 石头 布 剪刀 乙的策略集为 石头 布 剪刀 例2写出齐王和田忌赛马中齐王的收益矩阵 赢一场得一千金 解 二 具有鞍点的博弈 通过下面的例3说明 什么是局中人的最优纯策略 如何求出这个纯策略以及博弈解和博弈值的概念 博弈过程的描述 从收益表中可知 甲方的最大收益是19 他当然希望得到这个值 于是甲使用策略对付乙 但是乙方已估计到甲方的心理而使用策略对付甲 使他不但得不到19 反而要输掉12 此时甲也估计到乙方的心理 使用策略 使乙得不到12反而输掉6 当甲方使用策略时 乙方使用任何策略都要输 当然他希望输的少一些 因此乙方只能使用策略 这时甲赢得2 乙输掉2 达到了平衡 博弈结束 我们注意到 博弈论是研究有理智的局中人在每一个局势下采取的行动 他们在选择策略时 要考虑到对方总是采取对自己最不利的策略来对抗 基于这一原则 最优策略不是冒险性的结果 而是审慎的留有余地的周密安排 如果双方都不存在冒险心理 为了达到最佳结局 甲必须计算他的每个策略与乙的各策略博弈后的结果 从而求出使用每个策略带来的最坏收益 再从这些最坏收益中选出一个最大收益值 这个值对应的行策略就是甲方的最优纯策略 同样乙方应从收益表中每列找出最大正数 恰为乙方输掉的数值 为了减少损失 应从这些数字中求出最小数 它所对应的列策略为乙方的最优纯策略 计算过程如下 几点说明 1 在有鞍点的矩阵博弈中 鞍点可以不唯一 例如 2 策略的优超性 策略的优超性的定义 说明 这种做法可能会丢掉一些最优解 但不会影响博弈的结论 如果上面的不等式有严格不等式 就不会出现丢解的现象了 利用策略的优超性化简下面的矩阵博弈 并求出局中人的最优纯策略和博弈值 3 有鞍点的博弈是少数情况 大量的博弈问题不存在鞍点 齐王的收益矩阵就不存在鞍点 博弈问题的实例1 百货商店的选址问题 假设有一条街道 居民对各种日用品的需求是均匀的 为一个常数 且愿意就近购买 现有两家百货商店 分别想沿街道选定自己的位置 问如何选址对双方最有利 将街道看成一条曲线 博弈问题的实例2 某城市由汇合的三条河分割为三个区 城市居民中40 住在A区 30 住在B区 30 住在C区 现有甲 乙两公司要在市内修建超级市场 甲公司建两个 乙公司建一个 每个 公司都知道 如果在一个区内建两个超市 则两个市场平分该区业务 如果某区建一个超市 则独揽该区业务 若某区无超市其业务平均分散在三个超市中 每个公司都想把超市建在营业额最多的地方 1 将该问题表达成一个二人零和博弈 并写出甲公司的收益矩阵 2 甲 乙两公司的最优策略是什么 在两公司都取得最优策略时 它们各占有多大的市场份额 三 无鞍点矩阵博弈的混合策略 1 2 2无鞍点矩阵博弈的特殊解法 例4 该矩阵博弈显然不存在鞍点 对他们的博弈过程作出如下的描述 2 无鞍点矩阵博弈的线性规划解法 例5 解 设A的混合策略为B的混合策略为 解得到 例6求齐王与田忌赛马中双方的最优混合策略 解 齐王的线性规划为 解得齐王的最优混合策略为 问题 理论上齐王应赢得一千金 但是实际比赛中他为什么输掉一千金 在无鞍点的矩阵博弈中 双方采取何种纯策略是应当保密的 3 无鞍点矩阵博弈的布朗 Brown 算法 布朗 Brown 算法是一种近似算法 给定局中人A的收益矩阵 算法步骤 1 甲方任选一行 然后乙方选择与该行中最小元素相对应的那一列 2 在第1步里乙方所选的列中 与最大元素相对应的行即为甲方应选的行 3 乙方把到目前为止甲方选择的各行求和 并选择与最小和元素对应的列 4 甲方把到目前为止乙方选择的列求和 并选择与最大和元素对应的行 如果要求迭代的次数已达到 转第5步 否则转回第3步 5 分别计算博弈值的上界和下界 6 令是甲方选择i行的次数比例 是乙方选择j列的次数比例 分别为甲 乙的近似混合策略 例7用布朗算法求解矩阵博弈 迭代10次 四 纳什均衡 Nashequilibrium 纳什均衡是博弈论的基础 在二人零和博弈中 双方寻求的最优解是一种均衡解 达到这种均衡时 无论是纯策略解还是混合策略解 只要其他局中人不改变自己的策略 则任何一方单独改变自己的策略只能带来收益或效用的减少 因此这些均衡解也称为纳什均衡 换言之 纳什均衡是一种策略组合 它是每个局中人的策略对其他局中人策略的最优反应 纳什证明了在任何非合作有限博弈中 都存在至少一个纳什均衡 3 完全信息静态博弈 二 现在研究二人非零和博弈 一 用划线法求具有纯策略的纳什均衡 例7二人博弈如下表所示 解 先利用策略的优超性简化双元矩阵 纳什均衡是每个局中人策略对其他局中人策略的最优反应 对于A来说 针对B分别采取策略时 A的最优反应分别是策略其收益值分别是5 6 4 按划线法 在这几个数字下分别划一横线 对于B来说 相对于A采取的策略 B的最优反应策略是 分别在对应的收益值6 6下划横线 如果收益值下都有横线 这一对值就是纳什均衡解 对应的策略组合为本题中 纳什均衡解为 4 6 对应的策略组为 纳什均衡解为 4 6 对应的策略组为 二 两个著名的博弈例子 例8囚徒困境问题 1950年数学家塔克任美国斯坦福大学教授 在给一些心理学家讲演时 对当时正在研究的博弈问题作了形象的描述 设有甲 犯乙两名嫌疑因同一桩罪行被捕 警方希望他们坦白并提供对方犯罪证据 规定如两人均坦白各判刑3年 如一方坦白另一方不坦白 坦白一方从轻释放 不坦白一方判刑8年 如两人均不坦白 由于犯罪事实证据很多不能成立 只能每人各判1年 分析甲 乙两名犯罪嫌疑人的各自策略和纳什均衡解 解 根据划线法纳什均衡解是 坦白 坦白 但是从表中明显看出 两名犯罪嫌疑人最好的结局是 1 1 即双方均不坦白 如何理解这一矛盾的结果呢 这个例子说明 就个人利益和群体利益而言 在考虑最优解时 出发点不同 结果也不同 个人的理性选择与群体的理性选择是不一致的 在某些情况下 群体的理性选择反而比个人角度来选的好 就本例来说 双方都担心对方会坦白 作证 对自己非常不利 损失很大 因而都采取坦白的策