对策论的基本概念

1 1 对策论的基本概念 对策模型的三个基本要素 对策模型的三个基本要素 1 1 局中人 参与对抗的各方 局中人 参与对抗的各方 2 2 策略集 局中人选择对付其它局中人的行动方案称为策略 某局策略集 局中人选择对付其它局中人的行动方案称为策略 某局 中人的所有可能策略全体称为策略集 中人的所有可能策略全体称为策略集 3 3 一局势对策的益损值 局中人各自使用一个对策就形成了一个局一局势对策的益损值 局中人各自使用一个对策就形成了一个局 势 一个局势决定了各局中人的对策结果 量化 称为该局势对势 一个局势决定了各局中人的对策结果 量化 称为该局势对 策的益损值 策的益损值 齐王赛马齐王赛马 齐王在各局势中的益损值表 单位 千金 齐王在各局势中的益损值表 单位 千金 1 1 对策论的基本概念 其中 齐王的策略集其中 齐王的策略集 S1 1 2 3 4 5 6 田忌的策略集 田忌的策略集 S2 1 2 3 4 5 6 下面矩阵称齐王的赢得矩阵 下面矩阵称齐王的赢得矩阵 3 1 1 1 1 1 1 3 1 1 1 1 A 1 1 3 1 1 1 1 1 1 3 1 1 1 1 1 1 3 1 1 1 1 1 1 3 1 1 对策论的基本概念 二人有限零和对策 又称矩阵对策 二人有限零和对策 又称矩阵对策 局中人为局中人为2 2 每个局中人的策略集的策略数目都是有限的 每一 每个局中人的策略集的策略数目都是有限的 每一 局势的对策均有确定的损益值 并且对同一局势的两个局中人的益局势的对策均有确定的损益值 并且对同一局势的两个局中人的益 损值之和为零 损值之和为零 通常将矩阵对策记为通常将矩阵对策记为 G S1 S2 A S1 甲的策略集 甲的策略集 S2 乙的策略集 乙的策略集 A 甲的赢得矩阵 甲的赢得矩阵 齐王赛马齐王赛马 是一个矩阵策略 是一个矩阵策略 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 在甲方的赢得矩阵中 在甲方的赢得矩阵中 A aij m n i 行代表甲方策略行代表甲方策略 i 1 2 m j 行代表乙方策略行代表乙方策略 j 1 2 n aij 代表甲代表甲 方取策略方取策略 i 乙方取策略 乙方取策略 j 这一局势下甲方的益损值 此时乙方的益损值为 这一局势下甲方的益损值 此时乙方的益损值为 aij 零和性质 零和性质 在考虑各方采用的策略时 必须注意一个前提 就是双方都是理智的 即在考虑各方采用的策略时 必须注意一个前提 就是双方都是理智的 即 双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的 依据 依据 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 例 甲乙乒乓球队进行团体对抗赛 每队由三名球员组成 双方都可排成三种不例 甲乙乒乓球队进行团体对抗赛 每队由三名球员组成 双方都可排成三种不 同的阵容 每一种阵容可以看作一种策略 双方各选一种策略参赛 比赛共赛三局 同的阵容 每一种阵容可以看作一种策略 双方各选一种策略参赛 比赛共赛三局 规定每局胜者得规定每局胜者得1 1分 输者得分 输者得 1 1分 可知三赛三胜得分 可知三赛三胜得3 3分 三赛二胜得分 三赛二胜得1 1分 三赛一胜得分 三赛一胜得 1 1分 三赛三负得分 三赛三负得 3 3分 甲队的策略集为分 甲队的策略集为S S1 1 1 1 2 2 3 3 乙队的策略集为 乙队的策略集为 S S2 2 1 1 2 2 3 3 根据以往比赛的资料 有甲队的赢得矩阵为 根据以往比赛的资料 有甲队的赢得矩阵为A A 如下所示 如下所示 请问这次比赛各队采用哪种阵容上场最为稳妥请问这次比赛各队采用哪种阵容上场最为稳妥 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 矩阵矩阵A A中每行的最小元素分别为中每行的最小元素分别为1 1 3 3 1 1 在这些最少赢得中最好的结果是在这些最少赢得中最好的结果是1 1 故甲队会采取策略 故甲队会采取策略 1 1 无论对手采取何策略 甲队至少 无论对手采取何策略 甲队至少 得得1 1分 对于乙队 分 对于乙队 1 1 2 2 3 3 可能带来的最少赢得 即可能带来的最少赢得 即A A中每列的最大元素 分别为中每列的最大元素 分别为 3 3 1 1 3 3 乙队会采取 乙队会采取 2 2策略 确保甲队不会超过策略 确保甲队不会超过1 1分 分 1 1和和 2 2分别称为局中人甲队 乙队的最优策略 由于双方必然选择这一种策略 所以 这分别称为局中人甲队 乙队的最优策略 由于双方必然选择这一种策略 所以 这 种策略又称为最优纯策略 种策略又称为最优纯策略 这种最优纯策略只有当赢得矩阵这种最优纯策略只有当赢得矩阵A A a aij ij 中等式 中等式 成立时 双方才有最优纯策略 并把 成立时 双方才有最优纯策略 并把 1 1 2 2 称为对策 称为对策G G在纯策略下的解 又称 在纯策略下的解 又称 1 1 2 2 为对 为对 策策G G的鞍点 把其值的鞍点 把其值V V称之为对策称之为对策G SG S1 1 S S2 2 A A 的值 的值 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 例例 某单位采购员在秋天决定冬季取暖用煤的储量问题 已知在正常的冬季气温某单位采购员在秋天决定冬季取暖用煤的储量问题 已知在正常的冬季气温 条件下要消耗条件下要消耗1515吨煤 在较暖和较冷的天气下要消耗吨煤 在较暖和较冷的天气下要消耗1010吨和吨和2020吨 假定冬天的煤价随吨 假定冬天的煤价随 天气寒冷程度而有所变化 在较暖和 正常 较冷的气候条件下每吨煤价分别为天气寒冷程度而有所变化 在较暖和 正常 较冷的气候条件下每吨煤价分别为1010元 元 1515元 元 2020元 又设冬季时煤炭价格为每吨元 又设冬季时煤炭价格为每吨1010元 在没有关于当年冬季准确的气象预报元 在没有关于当年冬季准确的气象预报 的条件下 秋天储煤多少吨能使得单位的支出最少 的条件下 秋天储煤多少吨能使得单位的支出最少 解 局中人解 局中人I I为采购员 局中人为采购员 局中人IIII为大自然 采购员有三个策略 买为大自然 采购员有三个策略 买1010吨 吨 1515吨 吨 2020吨 分别记为吨 分别记为 1 1 2 2 3 3 大自然也有三个策略 暖 正常 冷 分别记为 大自然也有三个策略 暖 正常 冷 分别记为 1 1 2 2 3 3 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 赢得矩阵如下 赢得矩阵如下 在此表上计算 有在此表上计算 有 得得 故 故 3 3 3 3 为对策 为对策G G的解 的解 V VG G 200 200 设矩阵对策设矩阵对策 G S1 S2 A 当 当 max min aij min max aij i j j i 时 不存在最优纯策略 时 不存在最优纯策略 例 设一个赢得矩阵如下例 设一个赢得矩阵如下 minmin 5 5 9 9 5 5 A maxmax 6 6 策略策略 2 8 8 6 6 6 6 i i maxmax 8 8 9 9 minmin 8 8 策略策略 1 j j 当甲取策略当甲取策略 2 2 乙取策略 乙取策略 1 1时 甲实际赢得时 甲实际赢得8比预期的多比预期的多2 2 乙当然不满意 考虑 乙当然不满意 考虑 到甲可能取策略到甲可能取策略 2 2这一点 乙采取策略这一点 乙采取策略 2 2 若甲也分析到乙可能采取策略 若甲也分析到乙可能采取策略 2 2这一点 取这一点 取 策略策略 1 1 则赢得更多为 则赢得更多为9 9 此时 对两个局中人甲 乙来说 没有一个双方均可接 此时 对两个局中人甲 乙来说 没有一个双方均可接 受的平衡局势 其主要原因是甲和乙没有执行上述原则的共同基础 即受的平衡局势 其主要原因是甲和乙没有执行上述原则的共同基础 即 max min aij min max aij i j j i 一个自然的想法 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 一个自然的想法 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 在各种情况下的平均赢得 损失 最多 最少 即混合策略 即混合策略 求解混合策略的问题有图解法 迭代法 线性方程法和线性规划法等 我们这里求解混合策略的问题有图解法 迭代法 线性方程法和线性规划法等 我们这里 只介绍线性规划法 其他方法略 只介绍线性规划法 其他方法略 例 设甲使用策略例 设甲使用策略 1 1的概率为的概率为X1 1 使用策略 使用策略 2 2的概率为的概率为X2 并设在最坏的情况 并设在最坏的情况 下 甲赢得的平均值为下 甲赢得的平均值为V 未知 未知 5 9 A STEP 1 8 6 1 1 X1 X2 1 X1 X2 0 2 2 无论乙取何策略 甲的平均赢得应不少于无论乙取何策略 甲的平均赢得应不少于V V 对乙取对乙取 1 1 5X5X1 1 8X8X2 2 V V 对乙取对乙取 2 2 9X9X1 1 6X6X2 2 V V 注意注意 V 0 V 0 因为因为A A各元素为正 各元素为正 STEPSTEP 2 2 作变换 作变换 X X1 1 X X1 1 V V X X2 2 X X2 2 V V 得到上述关系式变为 得到上述关系式变为 X X1 1 X X2 2 1 V 1 V V V愈大愈好 待定愈大愈好 待定 5X5X1 1 8X8X2 2 1 1 9X9X1 1 6X6X2 2 1 1 X X1 1 X X2 2 0 0 建立线性模型 建立线性模型 minmin X X1 1 X X2 2 s t s t 5X5X1 1 8X 8X2 2 1 1 X X1 1 1 211 21 9X9X1 1 6X 6X2 2 1 1 X X2 2 2 212 21 X X1 1 X X2 2 0 0 1 V 1 V X X1 1 X X2 2 1 7 1 7 所以 所以 V 7V 7 返回原问题 返回原问题 X X1 1 X X1 1V V 1 31 3 X X2 2 X X2 2V V 2 32 3 于是甲的最优混合策略为 于是甲的最优混合策略为 以以1 31 3的概率选的概率选 1 1 以以2 32 3的概率选的概率选 2 2 最优值 最优值V 7V 7 例例 求解 求解 齐王赛马齐王赛马 问题 问题 已知齐王的赢得矩阵已知齐王的赢得矩阵A A 求得求得 故不存在纯策略问题下的解 可求其混合策略 故不存在纯策略问题下的解 可求其混合策略 A A中有负元素 可以取中有负元素 可以取k 2 k 2 在在A A的每个元素上加的每个元素上加2 2得到得到A A 如下 如下 建立对建立对G G S S1 1 S S2 2 A A 中求甲方最佳策略的线性规划如下 中求甲方最佳策略的线性规划如下 MinMin x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 约束条件 约束条件 5x5x1 1 3x 3x2 2 3x 3x3 3 x x4 4 3x 3x5 5 3x 3x6 6 1 1 3x3x1 1 5x 5x2 2 x x3 3 3x 3x4 4 3x 3x5 5 3x 3x6 6 1 1 3x3x1 1 3x 3x2 2 5x 5x3 3 3x 3x4 4 3x 3x5 5 x x6 6 1 1 3x3x1 1 3x 3x2 2 3x 3x3 3 5x 5x4 4 x x5 5 3x 3x6 6 1 1 x x1 1 3x 3x2 2 3x 3x3 3 3x 3x4 4 5x 5x5 5 3x 3x6 6 1 1 3x3x1 1 x x2 2 3x 3x3 3 3x 3x4 4 3x 3x5 5 5x 5x6 6 1 1 x xi i 0 i 1 2 0 i 1 2 6 6 可解得解为 可解得解为 x x1 1 x x4 4 x x5 5 0 0 x x2 2 x x3 3 x x6 6 0 111 0 111 v v 3 3 x x1 1 x x4 4 x x5 5 0 0 x x2 2 x x3 3 x x6 6 1 3 1 3 即即X X 0 1 3 1 3 0 0 1 3 0 1 3 1 3 0 0 1 3 T T 所以甲的最优策略为作出策略 所以甲的最优策略为作出策略 2 2 3 3 6 6的概率都为的概率都为 0 333 0 333 而作出而作出 1 1 4 4 5 5 的概率为的概率为0 0 此时 此时V V G G V V 3 3 同样可以建立对策同样可以建立对策G G S S1 1 S S2 2 A A 中求乙方最佳策略的线性规划如下 中求乙方最佳策略的线性规划如下 MinMin y y1 1 y y2 2 y y3 3 y y4 4 y y5 5 y y6 6 约束条件 约束条件 5y5y1 1 3y 3y2 2 3y 3y3 3 3y 3y4 4 y y5 5 3y 3y6 6 1 1 3y3y1 1 5y 5y2 2 3y 3y3 3 3y 3y4 4 3y 3y5 5 y y6 6 1 1 3y3y1 1 y y2 2 5y 5y3 3 3y 3y4 4 3y 3y5 5 3y 3y6 6 1 1 y y1 1 3y 3y2 2 3y 3y3 3 5y 5y4 4 3y 3y5 5 3y 3y6 6 1 1 3y3y1 1 3y 3y2 2 3y 3y3 3 y y4 4 5y 5y5 5 3y 3y6 6 1 1 3y3y1 1 3y 3y2 2 y y3 3 3y 3y4 4 3y 3y5 5 5y 5y6 6 1 1 y yi i 0 i 1 2 0 i 1 2 6 6 可解得解为 可解得解为 y y1 1 y y4 4 y y5 5 0 111 0 111 y y2 2 y y3 3 y y6 6 0 0 v v 3 3 y y1 1 y y4 4 y y5 5 1 3 1 3 y y2 2 y y3 3 y y6 6 0 0 即 即Y Y 1 3 0 0 1 3 1 3 0 1 3 0 0 1 3 1 3 0 T T 所以田忌的最优混合策略为作出策略所以田忌的最优混合策略为作出策略 1 1 4 4 5 5的概率都为的概率都为1 3 1 3 而作出而作出 2 2 3 3 6 6的概率为的概率为0 0 此时 此时 V VG G V VG G k 1 k 1 齐王赛马问题的对策最优解可简记为齐王赛马问题的对策最优解可简记为X X 0 1 3 1 3 0 0 1 3 0 1 3 1 3 0 0 1 3 T T Y Y 1 3 0 0 1 3 1 3 0 1 3 0 0 1 3 1 3 0 T T 对策值 对策值V VG G 1 1 例例 两个局中人进行对策 规则是两人互相独立的各自从两个局中人进行对策 规则是两人互相独立的各自从1 1 2 2 3 3这三个数字中任意选写一个数这三个数字中任意选写一个数 字 如果两人所写的数字之和为偶数 则局中人乙支付给局中人甲以数量为此和数的报酬 如字 如果两人所写的数字之和为偶数 则局中人乙支付给局中人甲以数量为此和数的报酬 如 果两人所写数字之和为奇数 则局中人甲付给局中人乙以数量为此和数的报酬 试求出其最优果两人所写数字之和为奇数 则局中人甲付给局中人乙以数量为此和数的报酬 试求出其最优 策略 策略 解 首先计算局中人甲的赢得矩阵如下表 解 首先计算局中人甲的赢得矩阵如下表 即甲的赢得矩阵为即甲的赢得矩阵为A A 可知无纯策略意义的解 下面求其在混合策略下的解 可知无纯策略意义的解 下面求其在混合策略下的解 A A的各元素都加上的各元素都加上6 6 得到 得到 建立线性规划模型如下 建立线性规划模型如下 MinMin x x1 1 x x2 2 x x3 3 MaxMax y y1 1 y y2 2 y y3 3 S T 8xS T 8x1 1 3x 3x2 2 10 x 10 x3 3 1 1 8y8y1 1 3y 3y2 2 10y 10y3 3 1 1 3x3x1 1 10 x 10 x2 2 x x3 3 1 1 3y3y1 1 10y 10y2 2 y y3 3 1 1 10 x10 x1 1 x x2 2 12x 12x3 3 1 1 10y10y1 1 y y2 2 12y 12y3 3 1 1 x x1 1 x x2 2 x x3 3 0 0 y y1 1 y y2 2 y y3 3 0 0 得到得到 x x1 1 0 25 0 25 x x2 2 0 50 0 50 x x3 3 0 25 0 25 y y1 1 0 25 0 25 y y2 2 0 50 0 50 y y3 3 0 25 0 25 即此对策的解为即此对策的解为 X X 0 25 0 50 0 25 0 25 0 50 0 25 T T Y Y 0 25 0 50 0 25 0 25 0 50 0 25 T T V VG G V VG G k 0 k 0 例例4 4 甲乙两个企业生产同一种电子产品 甲企业可以采取的策略措施有甲乙两个企业生产同一种电子产品 甲企业可以采取的策略措施有 1 1 降低产品价格 降低产品价格 2 2 提高产品质量 提高产品质量 3 3 推出新产品 乙企业考虑采取的策略措施有推出新产品 乙企业考虑采取的策略措施有 1 1 增加广告费用 增加广告费用 2 2 增设增设 维修网点 加强售后服务 维修网点 加强售后服务 3 3 改进产品性能 由于甲乙两个企业财力有限 都只能采取一个措改进产品性能 由于甲乙两个企业财力有限 都只能采取一个措 施 假定这两个企业所占有的市场总份额一定 由于各自采取的措施不同 通过预测今后两个施 假定这两个企业所占有的市场总份额一定 由于各自采取的措施不同 通过预测今后两个 企业的市场占有份额变动情况如下表 试求出这两个企业各自的最优策略 企业的市场占有份额变动情况如下表 试求出这两个企业各自的最优策略 解 解 易知此对策无纯策略意义下的解 把易知此对策无纯策略意义下的解 把A A的每一个元素加上的每一个元素加上1212 得到 得到A A 建立线性规划模型如下 建立线性规划模型如下 MinMin x x1 1 x x2 2 x x3 3 MaxMax y y1 1 y y2 2 y y3 3 S T 22xS T 22x1 1 20 x 20 x2 2 1 1 22y22y1 1 6y 6y2 2 15y 15y3 3 1 1 6x6x1 1 17x 17x2 2 22x 22x3 3 1 1 20y20y1 1 17y 17y2 2 7y 7y3 3 1 1 15x15x1 1 7x 7x2 2 20 x 20 x3 3 1 1 22y22y2 2 20y 20y3 3 1 1 x x1 1 x x2 2 x x3 3 0 0 y y1 1 y y2 2 y y3 3 0 0 得到 得到 x x1 1 0 027 x 0 027 x2 2 0 020 x 0 020 x3 3 0 023 0 023 y y1 1 0 0225 y 0 0225 y2 2 0 0225 y 0 0225 y3 3 0 025 0 025 V 14 29V 14 29 x x1 1 0 3858 0 3858 x x2 2 0 2858 0 2858 x x3 3 0 3286 0 3286 y y1 1 0 3215 y 0 3215 y2 2 0 3215 y 0 3215 y3 3 0 3572 0 3572 即此对策的解为即此对策的解为 X X 0 3858 0 2858 0 3286 0 3858 0 2858 0 3286 T T Y Y 0 3215 0 3215 0 3572 0 3215 0 3215 0 3572 T T V VG G V VG G k 2 29 k 2 29 优超原则 优超原则 假设矩阵对策假设矩阵对策 G G S