管理运筹学对策论PPT课件.ppt

对策论 由 齐王赛马 引入 2020 3 17 1 2 1 对策论的基本概念 三个基本要素 1 局中人 参与对抗的各方 2 策略集 局中人选择对付其它局中人的行动方案称为策略 某局中人的所有可能策略全体称为策略集 3 局势对策的益损值 各局中人各自使用一个对策就形成一个局势 一个局势决定了个局众人的对策结果 量化 称为该局势对策的益损值 2020 3 17 3 齐王赛马 齐王在各局势中的益损值表 单位 千金 2020 3 17 4 齐王的策略集 S1 1 2 3 4 5 6 田忌的策略集 S2 1 2 3 4 5 6 下列矩阵称齐王的赢得矩阵 3111 1113111 1A 1 13111 111311111 13111 1113 2020 3 17 5 1 基本概念 续 二人有限零和对策 又称矩阵策略 局中人为2 每局中人的策略集中策略权目有限 每一局势的对策均有确定的损益值 并且对同一局势的两个局中人的益损值之和为零 2020 3 17 6 1 基本概念 续 记矩阵对策为 G S1 S2 A 甲的策略集甲的赢得矩阵乙的策略集 齐王赛马 即是一个矩阵策略 2020 3 17 7 2 矩阵对策的最优纯策略 在甲方赢得矩阵中 A aij m ni行代表甲方策略i 1 2 mj行代表乙方策略j 1 2 naij代表甲方取策略i 乙方取策略j 这一局势下甲方的益损值 此时乙方的益损值为 aij 零和性质 在讨论各方采用的策略是必须注意一个前提就是对方是理智的 这就是要从最有把握取得的益损值情况考虑 2020 3 17 8 2 矩阵对策的最优纯策略 续 例 有交易双方公司甲和乙 甲有三个策略 1 2 3 乙有四个策略 1 2 3 4 根据获利情况建立甲方的益损值赢得矩阵 30 20A 2301 2 4 13问 甲公司应采取什么策略比较适合 2020 3 17 9 甲 采取 1至少得益 3 损失3 20 3 4 损失4 乙 采取 1甲最多得益2 乙最少得益 2 23 乙得益 3 30 乙得益0 43 乙得益 3 取大则取 2maxminaij 0ij 取小则取 3minmaxaij 0ji 2020 3 17 10 甲采取策略 2不管乙采取如何策略 都至少得益 乙采取策略 3不管甲采取如何策略 都至少可以得益 最多损失0 分别称甲 乙公司的最优策略 由唯一性又称最优纯策略 存在前提 maxminaij minmaxaij vijji又称 2 3 为对策G s1 s2 A 的鞍点 值V为G的值 2020 3 17 11 3 矩阵对策的混合策略 设矩阵对策G S1 S2 A 当maxminaij minmaxaijijji时 不存在最优纯策略求解混合策略 2020 3 17 12 3 矩阵对策的混合策略 例 设一个赢得矩阵如下 min595A max6策略 2866imax89min8策略 1j 2020 3 17 13 矛盾 甲取 2 乙取时 1 甲实际赢得8比预期多2 乙就少2 这对乙讲是不满意的 考虑这一点 乙采取策略 2 若甲分析到这一点 取策略 1 则赢得更多为9 此时 甲 乙芳没有一个双方均可接受的平衡局势 一个思路 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 即混合策略 2020 3 17 14 求解方法 线性规划法 其他方法 图解法 迭代法 线性方程法等略 例 59设在最坏的情况下 A 甲赢得的平均值为V 86 未知 STEP11 设甲使用策略 1的概率为X1 X1 X2 1设甲使用策略 2的概率为X2 X1 X2 0 2020 3 17 15 2 无论乙取何策略 甲的平均赢得应不少于V 对乙取 1 5X1 8X2 V对乙取 2 9X1 6X2 V注意V 0 因为A各元素为正 STEP2作变换 X1 X1 V X2 X2 V得到上述关系式变为 X1 X2 1 V V愈大愈好 待定5X1 8X2 19X1 6X2 1X1 X2 0 2020 3 17 16 建立线性模型 minX1 X2s t 5X1 8X2 1X1 1 219X1 6X2 1X2 2 21X1 X2 01 V X1 X2 1 7所以 V 7返回原问题 X1 X1V 1 3X2 X2V 2 3于是甲的最优混合策略为 以1 3的概率选 1 以2 3的概率选 2最优值V 7 2020 3 17 17 同样可求乙的最优混合策略 设乙使用策略 1的概率为Y1 Y1 Y2 1设乙使用策略 2的概率为Y2 Y1 Y2 0设在最坏的情况下 甲赢得的平均值为V 这也是乙损失的平均值 越小越好作变换 Y1 Y1 V Y2 Y2 V建立线性模型 maxY1 Y2s t 5Y1 9Y2 1Y1 1 148Y1 6Y2 1Y2 1 14Y1 Y2 01 V Y1 Y2 1 7所以 V 7 2020 3 17 18 返回原问题 Y1 Y1V 1 2Y2 Y2V 1 2于是乙的最优混合策略为 以1 2的概率选 1 以1 2的概率选 2最优值V 7 当赢得矩阵中有非正元素时 V 0的条件不一定成立 可以作下列变换 选一正数k 令矩阵中每一元素加上k得到新的正矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 解相同 但VG VG k 2020 3 17 19 再讨论 齐王赛马 齐王赛马 的赢得矩阵A有maxminaij 1 minmaxaij 3ijji故需求混合策略 由于A中有非正元素 可选k 2 令矩阵中每一元素加上k得到新的正矩阵A 533313353331A 315333133533333153331335 2020 3 17 20 再讨论 齐王赛马 续 求甲方 齐王 最优策略的线性规划模型 minX1 X2 X3 X4 X5 X6s t 5X1 3X2 3X3 X4 3X5 3X6 13X1 5X2 X3 3X4 3X5 3X6 13X1 3X2 5X3 3X4 3X5 X6 13X1 3X2 3X3 5X4 X5 3X6 1X1 3X2 3X3 3X4 5X5 3X6 13X1 X2 3X3 3X4 3X5 5X6 1X1 X2 X3 X4 X5 X6 0可得两组解 0 1 9 1 9 0 0 1 9 T 1 18 1 18 1 18 1 18 1 18 1 18 T V 3于是 X 0 1 3 1 3 0 0 1 3 T X 1 6 1 6 1 6 1 6 1 6 1 6 TV V 2 1即齐王的最优混合策略值是赢1千金 2020 3 17 21 再讨论 齐王赛马 续 求乙方 田忌 最优策略的线性规划模型 minY1 Y2 Y3 Y4 Y5 Y6s t 5Y1 3Y2 3Y3 3Y4 Y5 3Y6 13Y1 5Y2 3Y3 3Y4 3Y5 Y6 13Y1 Y2 5Y3 3Y4 3Y5 3Y6 1Y1 3Y2 3Y3 5Y4 3Y5 3Y6 13Y1 3Y2 3Y3 Y4 5Y5 3Y6 13Y1 3Y2 Y3 3Y4 3Y5 5Y6 1Y1 Y2 Y3 Y4 Y5 Y6 0可得两组解 1 9 0 0 1 9 1 9 0 T 1 18 1 18 1 18 1 18 1 18 1 18 T V 3于是 Y 1 3 0 0 1 3 1 3 0 T Y 1 6 1 6 1 6 1 6 1 6 1 6 TV V 2 1即田忌的最优混合策略值是输1千金 2020 3 17 22 优超原则 假设矩阵对策G S1 S2 A 甲方赢得矩阵A aij m n 若存在两行 s行的各元素均优于t行的元素 即asj atjj 1 2 n称甲方策略 s优超于 t 若存在两列 s列的各元素均优于t列的元素 即ais aiti 1 2 m称乙方策略 s优超于 t 3 矩阵对策的混合策略 续 2020 3 17 23 优超原则 当局中人甲方的策略 t被其它策略所优超时 可在其赢得矩阵A中划去第t行 同理 当局中人乙方的策略 t被其它策略所优超时 可在矩阵A中划去第t列 如此得到阶数较小的赢得矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 等价 即解相同 3 矩阵对策的混合策略 续 2020 3 17 24 例设甲方的益损值赢得矩阵 32030被第3 4行所优超50259被第3行所优超A 7395946875 560883得到73959被第1列所优超A1 46875 5被第2列所优超60883 3 矩阵对策的混合策略 续 2020 3 17 25 续例得到739A2 465 5603被第1行所优超得到739被第1列所优超A3 465 573最终得到A4 46 3 矩阵对策的混合策略 续 2020 3 17 26 对A4计算 用线性规划方法得到 注意 余下的策略为 3 4 1 2 甲 X 0 0 1 15 2 15 0 TV 5X 0 0 1 3 2 3 0 T乙 Y 1 10 1 10 0 0 0 TV 5Y 1 2 1 2 0 0 0 T注 利用有超原则化简赢得矩阵时 有可能将原对策问题的解也划去一些 多解情况 线性规划求解时有可能是多解问题 习题 P343 1 3 4 3 矩阵对策的混合策略 续 决策分析 2020 3 17 27 附1 SWOT分析 2020 3 17 28 附2 如何安排自己的日程生活呢 2020 3 17 29 附3 谁也不能阻碍你成为一个富人 罗博特 清崎 1 4种人对资产 asset 与负债 liability 的认可是不一样的 2 Viewpointsoneducation1 academic2 professional3 financial 3 Somesuggestions1 vocabularyrelatedtomoney2 team3 mistakes 2020 3 17 30 附4 人的分类与企业剩余的关系 2020 3 17 31 例1 例一 囚徒困境 prisoner sdilemma 在这个例子中 纳什均衡就是 坦白 坦白 囚徒困境反映了一个很深刻的问题 这就是个人理性与集体理性的矛盾 如果两个人都抵赖 各判刑1年 显然比都坦白判刑8年好 但这个帕累托改进办不到 因为它不满足个人理性要求 抵赖 抵赖 不是纳什均衡 该例子在经济学上的应用 如果两个企业联合起来形成卡特尔 选择垄断利润最大化的产量 每个企业都可得到更多的利润 但卡特尔协定不是一个纳什均衡 因为给定对方遵守协议的情况下 每个企业都想增加生产 结果是 每个企业都只能得到纳什均衡产量的利润 它严格小于卡特尔产量下的利润 这个例子说明 在有些情况下 个人理性与集体理性的冲突对逐个社会来说 也许是件好事 尽管它对该集体的成员来说是件坏事 当然这里的前提条件是集体成员的数量严格小于全体社会成员的数量 2020 3 17 32 公共产品的估计也是一个囚徒困境问题 如果大家都出钱兴办公用事业 所有人的福利都会增加 问题是 如果我出钱你不出钱 我得不偿失 而你出钱我不出钱 我就可以占你的便宜 所以每个人的最优选择都是 不出钱 这种纳什均衡使得所有人的福利都得不到提高 经济改革本身也可能是这样 在许多改革中 改革者要付出成本 包括风险 而改革的成果大家享受 结果是 尽管人人都认为改革好 却没有人真正去改革 大家只好在都不满意的体制下继续生活下去 从囚徒困境中 我们可以引出一个很重要的结论 一种制度安排 要发生效力 必须是一种纳什均衡 否则 这种制度安排便不能成立 2020 3 17 33 例2 智猪博弈 boxerpigs 纳什均衡是 大猪按 小猪等 这反映了一个不合理的现象 多劳者不多得 在股票市场 大户是大猪 小户是小猪 一个村子里有两户人家 一个是富裕户 一个是穷户 要修一条路 富户是大猪 穷户是小猪 大猪修路 小猪搭便车 改革中 一部分人的好处比另一部分人的好处多 好处多的人是大猪 后者是小猪 大猪推动改革的进程 2020 3 17 34 例3 性别战 battleofsexes 有两个纳什均衡 足球 足球 芭蕾 芭蕾 究竟实际中发生哪一个 我们不知道 但我们知道这里存在一个先动优势 例4 斗鸡博弈 chickengame 也有两个纳什均衡 进 退 和 退 进 究竟谁进谁退呢 2020 3 17 35 总结一下 公共产品的供给可能是囚徒博弈 也可能是智猪博弈 还可能是斗鸡博弈 这要依据产品而定 例5 市场进入阻挠 entrydeterrence 在这个博弈中 假定进入之前垄断利润为300 进入之后寡头利润合为100 各得50 进入成本为10 有两个纳什均衡 进入 默许 不进入 斗争 例6 关于制贩联盟的定价问题 2020 3 17 36 关于纳什均衡含义的解释纳什均衡的含义 假设有N个人参与博弈 给定其他人参与博弈的条件 每个人选择自己的最优战略 所有参与人选择的战略一起构成一个战略组合 纳什均衡指的是这样一种战略组合 这种战略组合是由所有参与人的最优战略组成 也就是说 给定别人战略的情况下 没有任何单个参与人有积