运筹学、对策论PPT课件.ppt

1 对策论又称博弈论 是运筹学的一个重要分支 对策论所研究的主要对象是带有斗争或竞争性质的现象 由于对策论研究的对象与政治 军事 工业 农业 交通 运输等领域有密切关系 处理问题的方法又有着明显的特色 所以越来越受到人们的重视 第一节引言 一 对策行为与对策论 第五章对策论 1 2 在日常生活中 我们经常看到一些相互之间的竞争 比赛性质的现象 如下棋 打扑克 体育竞赛等 在经济领域 各国之间的贸易谈判 各公司 企业之间的市场争夺 各公司 企业之间的加工 订货 合作谈判等等 都是竞争现象 在政治方面 国际上政府间的各种外交谈判 各方都想在谈判中处于有利地位 争取到对自己有利的结果 各国之间或国内各集团之间的战争 是一种你死我活的斗争 双方都千方百计要战胜对方 2 3 例 两个儿童玩的 石头 剪子 布 游戏和我国古代的 齐王赛马 就是典型的对策论研究的例子 在这类行为中 参加斗争或竞争的各方各自具有不同的目标和利益 为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案 并力图选取对自己最为有利或最为合理的方案 对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案 以及如何找到这个合理的行动方案的数学理论和方法 3 4 二 对策问题的三个基本要素 1 局中人 在一场竞赛或斗争中 每一个有决策权的参与者 个人或集团 称为一个局中人 只有两个局中人的对策现象称为 两人对策 而多于两个局中人的对策称为 多人对策 2 策略 一个对策中 每个局中人都有供他选择的实际可行的完整的行动方案 我们把一个局中人一个可行的自始至终通盘筹划的行动方案 称为这个局中人的一个策略 如果在一个对策中 每个局中人都只有有限个策略 则称为 有限对策问题 否则称为 无限对策问题 4 5 3 赢得函数 支付函数 一局对策结束时的结果 如收入或支出 称为得失 每个局中人在一局对策结束时的得失 不仅与该局中人自身所选择的策略有关 而且与全体局中人所取定的一组策略有关 所以 一局对策结束时每个局中人的 得失 是全体局中人所取定的一组策略的函数 通常称作赢得函数 支付函数 把每个局中人各自所取的一个策略所组成的策略组称为 局势 于是 得失 是 局势 的函数 5 6 第二节矩阵对策的基本定理 特点 局中人只有两人 分别用局中人 和局中人 表示 双方都只有有限个策略可供选择 局中人的 得失 相加等于零 这种对策称为 零和对策 在两人有限零和对策中 局中人 的所获等于局中人 的所失 假定在局势 i j 下 即局中人 取策略 i 局中人 取策略 j时所形成的局势 局中人 的收入或赢得是aij aij 是负数时 表示局中人 是支出 的策略集为 的策略集为 一 矩阵对策的数学模型 6 7 用矩阵表示为 称为局中人 的赢得矩阵或局中人 的支付矩阵 我们称两人有限零和对策为矩阵对策 记为 G S1 S2 A 或G S1 S2 A 7 8 例1 设有矩阵对策 局中人 的支付矩阵如下 如果各局中人都不想冒险 必须考虑对方会选择策略使他得到最差的收入 因此各局中人都选择理智的决策行为 解 3 3 1 4 3 8 9 局中人 的各种策略的最差收入是支付阵中各种策略所对应行的最小数 如果不存侥幸心理 他对每个策略只能期望得到最差的收入 即 那么为了得到尽可能好的结局 只能从这些最小数之中的找最大者 最大的最小者 即选择能在最差的可能结果中得到最好结果的策略 即 8 2 9 3 即选择策略 2 9 10 同样 局中人 的各种策略的最差收入 最大支出 是支付矩阵中各列的最大数 即 局中人 选择这些最大数中的最小者 即 16 2 5 即选择策略 2 的最优策略为 2 的最优策略为 2 10 11 定义 设G S1 S2 A 为矩阵对策 其中S1 1 2 m S2 1 2 n A aij m n 若满足等式 则称纯局势 i j 为G在纯策略下的解 或平衡局势 记VG ai j 称VG为对策G的值 i j 分别称为局中人I II的最优纯策略 例1的对策G的解为 2 2 2 2分别是局中人I和II的最优纯策略 VG 2 从例1中可以看出 矩阵的元素a22既是所在行的最小元素 又是所在列的最大元素 即 11 12 定理1 矩阵对策A aij m n有解的充分必要条件是 存在纯局势 i j 使得对一切i 1 2 m j 1 2 n均有 i 1 2 3 4 j 1 2 3 将这一事实推广到一般矩阵对策 可得如下定理 证明 先证充分性 由于对任意i j均有 故 12 13 另一方面 对任意i j均有 所以 于是 所以 13 14 再证必要性 若G有解 而对于所有的i而言 必存在一个i 使 对于所有的j而言 必存在一个j 使 因为 于是 14 15 称满足条件的 i j 为矩阵对策G的一个鞍点 但 于是有 故对一切的i j都有 意义 如果局中人I选择策略 i 局中人II不选择策略 j 而选择策略 j 则局中人II的支付只会增多 也就是说 策略 j 是II的最优策略 15 16 注意 一个矩阵对策G如果存在鞍点 鞍点可能不止一个 但是在不同的鞍点处 支付值相等 都等于对策的值 无差异性 如果 i j 以及 k l 都是对策G的鞍点 则 k j 与 i l 也是该问题的鞍点 可交换性 同样 如果局中人II选择策略 j 局中人I不选择策略 i 而选择策略 i 则局中人I的所获只会减少 也就是说 策略 i 是局中人I的最优策略 16 17 G有四个鞍点 对策的值为VG 5 例2 给定矩阵对策G S1 S2 A 其中 17 18 二 矩阵对策的混合策略 矩阵对策G有鞍点时 就存在最优解 最优纯策略 但是否一切矩阵对策问题中 各局中人都有上述意义的最优纯策略呢 答案是否定的 例1 石头 剪刀 布 不存在上述纯策略意义下的解 18 19 对于该例而言 直观的看 双方采用三个纯策略的频率均应为1 3 1 3 1 3 由于每个局中人在一局对策中必取某个纯策略 因此采取任何一个纯策略的概率都应是1 3 一般地 设局中人I以概率x1 x2 xm来分别选取他的纯策略 1 2 m 而局中人II以概率y1 y2 yn来选用自己的纯策略 1 2 n 于是 令x x1 x2 xm T y y1 y2 yn T 则称这样的x和y为局中人I II的混合策略 19 20 记 此时 当局中人I以概率xi采用 i时 局中人II以概率yj采用 j时 支付aij出现的概率为xiyj 于是局中人I收入 赢得 的期望值为 则称G S1 S2 E 为G S1 S2 A 的混合扩充 20 21 混合策略对策矩阵可表示如下 混合策略问题的解也是以最大最小化和最小最大化标准为根据的 21 22 当局中人I选择某个混合策略x时 对于局中人II的任意选择y I的期望所获至少是 于是局中人I希望选择x 使上式最大 保证局中人I的期望所获不小于 这就是局中人I的最大最小化标准 同理 当局中人II选择某个混合策略y时 对于I的任意选择x II的期望支付至多是 于是局中人II希望选择y 使上式最小 保证局中人II的期望支付不多于 这就是局中人II的最小最大化标准 22 23 例1 求解矩阵对策G S1 S2 A 其中 如果令 则得问题的最优解 解 设X x 1 x T Y y 1 y T 且对策的值为 23 24 另解 用微分求极值的方法 且对策的值为 24 25 定义 G S1 S2 E 为矩阵对策G S1 S2 A 的混合扩充 若存在 x y 满足等式 则称 x y 为G在混合策略下的解 称VG E x y 为对策G的值 x y 分别称为I II的最优混合策略 定理2 混合策略x 和y 是G的解的充分必要条件是 对一切混合策略x y有 称 x y 是对策问题在混合策略意义下的鞍点 25 26 当局中人I取纯策略 i时 记其赢得函数为 于是 三 矩阵对策的基本定理 当局中人II取纯策略 j时 记其赢得函数为 于是 26 27 则有 定理3 混合策略x 和y 是G的解的充分必要条件是 对任意的i j有 27 28 则 证明 必要性显然 只需证充分性 若对任意i j均有 即 所以x 和y 是G的解 28 29 注意到 可以写成 于是定理3可以改述为 定理4 矩阵对策G S1 S2 A 有解的充要条件是存在数v 使得x y分别是下述两个不等式组的解 29 30 定理5 对策基本定理 任何矩阵对策G在混合策略下一定有解 证明 由定理3 只需证明存在混合策略x 和y 使得 3 式成立 为此考虑如下两个线性规划 30 31 容易验证 P 和 D 是互为对偶规划 而且 是 P 的一个可行解 是 D 的一个可行解 由线性规划对偶理论可知 P 和 D 是都存在最优解 x w 和 y v 且最优值w v 即 i 1 2 m j 1 2 n 31 32 又由 可得 定理5的证明是构造性的证明 同时给出了求解方法 32 33 定理6 设 x y 是矩阵对策G解 v VG 则 33 34 矩阵对策G S1 S2 A 1 若 即A中第k行的每个元素 A中第l行的每个元素 称局中人I的策略 k优超于策略 l 则可在A中去掉第l行 矩阵对策G的解不变 2 如果 即A中第k列的每个元素 A中第l列的每个元素 称局中人II的策略 k优超于策略 l 则可在A中去掉第第l列 矩阵对策G的解不变 优超定理 34 35 第三节矩阵对策的求解 一 2 2对策的方程法 则称G为2 2对策 若G没有纯策略下的解 则G的最优混合策略x x1 x2 T y y1 y2 T满足下列方程组 且其中v VG 35 36 例1 求解求解矩阵对策G S1 S2 A 其中 解 在A中由于 第3行 第2行 第4行 第1行 因此从A中划去1 2两行 得 36 37 在A1中由于 第1列 第3列 第2列 第4列 因此从A1中划去3 4两列 得 在A2中由于 第1行 第3行 因此从A2中划去第3行 得 在A3中由于 第2列 第3列 因此从A3中划去第3列 得 37 38 分别求解方程组得 得x3 1 3 x4 2 3 y1 1 2 y2 1 2 v 5 由此对于原问题A而言 最优解为 38 39 二 2 n和m 2对策的图解法 解 设局中人I的混合策略为 x 1 x T 局中人I的最少得益为如下图中由局中人II选择 1 2 3时所确定的三条直线2x 7 1 x v 3x 5 1 x v 11x 2 1 x v在x处纵坐标的最小者 即如图中折线B1BB2B3 例2 求解求解矩阵对策G S1 S2 A 其中 39 40 3 1 2 B1 B B2 B3 A 所以对局中人I来说 他的策略就是确定x使他的得益达到最大 按最大最小原则应选择x OA 而AB即为对策的值 为求出x和对策的值VG 可联立过B点的两条直线 2和 3所确定的方程 40 41 解得 x 3 11 VG 49 11 此外从图中可看出 局中人II的最优策略只由 2和 3组成 不选 1 可由方程组所确定 解得 y2 9 11 y3 2 11 所以最优解为 41 42 例3 求解矩阵对策G S1 S2 A 其中 解 设局中人II的混合策略为 y 1 y T 局中人II的最大支付为如下图中由局中人I选择 1 2 3时所确定的三条直线2y 7 1 y v 9y 6 1 y v 11y 2 1 y v在y处纵坐标的最小者 即如图中折线上的B点 42 43 0 1 2 6 11 2 9 7 y V V B A 1 2 3 对局中人II来说 他的策略就是确定y使他的支付达到最小 按最小最大原则应选择y OA 为求出y和对策的值VG 可联立过B点的两条直线 1和 2所确定的方程 43 44 解得 y 1 8 VG 51 8 此外从图中可看出 局中人II的最优策略只由 1和 2组成 不选 3 可由方程组所确定 解得 x1 3 8 x2 5 8 所以最优解为 44 45 三 线性规划法 由前面定理可知 对策G的解满足下列线性规划 作变量替换 45 46 则 于是上述线性规划等价于下面的线性规划问题 由此求解一个对策问题 就相当于求解上面的对偶问题 46 47 例4 利用线性规划法求解矩阵对策G S1 S2 A 注 如果aij不满足非负性 则存在一个正数k 使得aij k 0 令B bij aij k 求解对策问题 S1 S2 B 可以证明 问题 S1 S2 B 与问题 S1 S2 A 的最优策略相同 且有 其中 47 48 解 建立相应的线性规划模型 及 用单纯形法求解后一个问题 先标准化为 48 49 用单纯形表求解如下 49 50 50 51 由此最优解为 51 52 第四节两人有限非零和对策 例1 囚徒困境 甲乙是同案囚犯 被隔离审讯 如果两个都抵赖 因为证据不充分 两人都只能判1年 如果只有一方坦白 则无罪释放 而另一方则属抗拒从严 判10年 但如果两人都坦白 则各判5年 下表给出了 囚徒困境 博弈问题的战略式表述 为了实现各自的效用最大化 双方格采取何种策略呢 52 53 假设该博弈是一次性的 对于囚犯甲而言 不管乙选择坦白还是抵赖 他选择坦白都比选择抵赖更好 这种不管对方选择何种策略 局中人的最优选择总是不变的那个策略被称为该局中人的优超策略 此例中坦白为甲的优超策略 同样道理坦白也是乙的优超策略 结果是 两个囚徒争先恐后地都选择坦白 各判刑5年 从而 坦白 坦白 也就构成了该博弈的优超策略均衡 称为纳什均衡 53 54 囚犯困境反映了一个深刻的问题 这就是个人理性与集体理性的矛盾 如果两个人都抵赖 对局中人组成的集体而言 可谓帕累托最优 但是这并不满足个人理性导致的纳什均衡 坦白 坦白 因而 这个帕累托改进在静态博弈中办不到 囚徒困境说明纳什均衡并不一定导致帕累托最优 从而动摇了传统经济学中个人效用最大化行为必然导致社会福利最优的基本命题 对囚犯困境问题作进一步分析 不难发现 尽管甲与乙各自的最佳选择都是坦白 如果双方均选择抵赖 各判刑1年 显然比双方均坦白时答判刑5年的结局要好 因此 其最佳选择与最优结局并不一致 出现所谓的 囚徒困境 54 55 设对策G的局中人 和 双方都只有有限个策略 其中 在局势 i j 下 即局中人 取策略 局中人 取策略 j时所形成的策略组合 局中人 的赢得值是aij 局中人 的赢得值是bij 分别用矩阵表示为A和B 的策略集为 的策略集为 非合作两人对策 55 56 定义 对于非合作两人对策G 如果 i 是局中人 对 的策略 j 的最优策略 j 是局中人 对 的策略 i 的最优策略 则称局势 i j 是该问题的一个纳什均衡 即谁都不愿单独改变策略 56 57 本博弈的纳什均衡为 大猪按 小猪等待 例2 智猪博弈 猪圈有一头大猪 一头小猪 按一下按钮会有10个单位的饲料 但按按钮需要2个单位成本 57 58 例3 夫妻博弈 丈夫喜欢看球赛 妻子喜欢逛商场 他们都宁愿在一起 也不愿分开行动 本例有两个纳什均衡结果会出现 要么一起去看球赛 要么一起去逛商场 但在一次博弈中究竟会出现哪一种 58 59 这个博弈也有两个纳什均衡 一个是 进攻 退却 另一个是 退却 进攻 例4 斗鸡博弈 有两个斗鸡A B 它们各有两个策略 进攻或退却 59 60 这个博弈也有两个纳什均衡 一个是 进入 默许 另一个是 不进入 斗争 而 不进入 默许 却不是一个纳什均衡 例5 市场进入壁垒 设想一个垄断企业已占领市场 称为 在位者 另一个企业很想进入市场 称为 进入者 在位者想保持其垄断地位 就要阻挠进入者进入 假定双方在各种策赂组合下的赢得短阵如表所示 60 61 非合作两人对策的解法 对其他局中人的任一策略组合 找出局中人i的最佳策略 并在其得益值下划线 若存在一个策略组合 使得所有局中人的得益值下都划了线 则该策略组合就是一个纳什均衡 求纳什均衡的方法如下 61 62 例1 囚犯困境 因此 坦白 坦白 构成了该博弈的纳什均衡 62 63 例3 夫妻博弈 这个博弈有两个纳什均衡 一个是 看球赛 看球赛 另一个是 逛商场 逛商场 63 64 例5 市场进入壁垒 因此 进入 默许 和 不进入 阻挠 是该问题的两个钠什均衡 64 65 混合策略纳什均衡 上面介绍了在纯策略意义下非合作两人对策纳什均衡的概念及求解方法 但有些对策不存在纯策略意义下的纳什均衡 考虑下面的例子 65 66 例6 局中人是政府和一个流浪汉 流浪汉有两个策略 寻找工作或游荡 政府也有两个策略 救济或不救济 政府帮助流浪汉的前提是后者必须试图寻找工作 否则 政府不予以帮助 而流浪汉只在得不到救济时才会寻找工作 如表给出了对策的赢得双矩阵 66 67 同样局中人可以考虑按照一定的随机方式来确定一个策略组合的混合策略 每个局中人作出决策时 不是只选用一个纯策略 而是按照预先确定的一组概率来选取他们所有可能采用的策略 容易理解 当流浪汉选择寻找工作时 政府的最优策略是救济 当流浪者选择游荡时 政府的最优策略是不救济 当政府策略为不救济时 流浪汉的最优策略是寻找工作 当政府选择救济时 流浪汉的最优策略是游荡 总之 在纯策略下 没有一个策略组合构成纳什均衡 67 68 局中人I以概率x1 x2 xm来分别选取纯策略 1 2 m 而局中人II以概率y1 y2 yn来选用自己的纯策略 1 2 n 于是 称x x1 x2 xm T y y1 y2 yn T分别为I和II的混合策略 设A B分别为局中人I和II的赢得矩阵 且都是为m n矩阵 68 69 则局中人I和II的混合策略集为 当局中人I和II的混合策略分别为x和y时 局中人I和II的期望赢得值分别为 69 70 如果一个混合策略组合 x y 同时满足 且 则称策略组合 x y 是一个混合策赂纳什均衡 其中 x y 分别是局中人I和II的任意混合策略 例6中假定政府以概率x选择救济 概率1 x选择不救济 即政府的混合策略为 x 1 x 流浪汉以概率y选择寻找工作 以概率1 y选择游荡 即流浪汉的混合策略为 y 1 y 那么政府的期望赢得函数为 70 71 同样 流浪汉的期望赢得函数为 令 得 令 得 71 72 这就是说 在混合策略均衡中 流浪汉在对付政府给定的混合策略下 最优策略是以1 5的概率选择寻找工作 而以4 5的概率选择游荡 即 在混合策略均衡中 政府在对付给定流浪汉的混合策略下 最优策略是 由于纳什均衡要求每个局中人的混合策略是在给定对方的混合策略下的最优选择 因此策略组 X Y 构成唯一的纳什均衡 72 73 对于上述的混合策略纳什均衡 可以这样来理解 如果政府认为流浪汉选择工作的概率y 1 5 那么政府的唯一最优选择策略是不救济 但当政府以1的概率选择不救济 流浪汉的最优选择是寻找工作 这又将导致政府选择救济 此时流浪汉则又会选择游荡 如此等等 因此y 1 5不构成纳什均衡 同样 如果政府认为y 1 5 政府的唯一最优选择是救济 但当政府以x 1选择救济时 流浪汉的最优选择则是游荡 因此y 1 5也不构成纳什均衡 类似地 可以验证x 1 2和x 1 2都不构成纳什均衡 73 74 无限策略博弈分析 在有无限策略 连续策略空间的博弈中 纳什均衡的概念同样适用 我们通过具体模型来说明这种博弈的纳什均衡分析方法 古诺 Cournot 模型 古诺模型是研究寡头垄断市场的经典模型 在古诺模型中 假设一个市场有两家生产同一种产品厂商 如果厂商1的产量为q1 厂商2的产量为q2 则市场总产量为Q q1十q2 设市场出清价格P是