第十二章 对策论.ppt

第十二章对策论 第一节引言 对策现象和对策论 对策论又称博奕论或竞赛论 gametheory 是研究具有对抗或竞争性质现象的数学理论和方法 是应用数学的一个分支 也是运筹学的一个重要学科 还被认为是经济学研究的一个重要工具 近年来由于对策论在经济管理中的广泛应用而日益受到人们的重视 对策现象是指具有对抗或竞争性质的现象 对策论就是研究在对策现象中各方是否存在最合理的行动方案 以及如何找到合理的行动方案的数学理论与方法 典型的历史案例 齐王赛马 齐王 上马中马下马 田忌 上马中马下马 各出马一匹进行比赛 田忌策略 负者要支付胜者千金 上马 下马 中马 上马 下马 中马 对策现象的三要素 局中人 players 指对策中有权决定自己行动方案的对策的参与者 通常用I表示局中人的集合 常常直接用数字标识局中人 对策论关于局中人的一个重要假设是 每个局中人都是 理智的 策略 strategies 对策中可供局中人选择的一个实际可行的完整的行动方案 在对策中局中人i的策略集记成Si 一般一个局中人的策略集中至少包含两个策略 一个对策中 由每个局中人所出的策略构成的策略组称为一个局势 设第i个局中人策略记为si 则s s1 s2 sn 是一个局势 而全部局势的集合可表示为 对策现象的三要素 续 赢的函数 支付函数 payofffunction 对策中当每一个局势s出现后 应该为每个局中人i规定一个赢得值 支付值 Hi s 显然Hi s 是定义在S上的函数 例如在 齐王赛马 中 设s1 上 中 下 是齐王的一个策略 s2 中 下 上 是田忌的一个策略 则s1与s2构成了一个局势s12 并且在这一局势中齐王和田忌的赢得值分别为H1 s12 1 H2 s12 1 一般地 当局中人 策略集 赢得函数这3个要素确定后 一个对策模型也就确定了 对策问题举例及对策的分类 1 例1市场购买力争夺问题 p387 市场 下一年的饮食品购买力为4000万元 乡镇企业策略 出售特色饮食品 出售一般饮食品 中心城市企业战略 出售高档饮食品 出售低档饮食品 乡镇企业赢得 2000 3000 1000 3000 对策问题举例及对策的分类 2 例2 p387 局中人 企业I 企业II 策略 企业I在时刻x出售 企业II在时刻y出售 其中x y 0 1 赢得函数 在局势 x y 下企业I的赢得值为 对策问题举例及对策的分类 3 例3费用分摊问题 p387 例4拍卖问题 p387 例5囚犯难题 p388 囚犯甲策略 承认 不承认 囚犯乙策略 承认 不承认 甲赢得 乙赢得 7 7 0 9 9 0 1 1 对策问题举例及对策的分类 4 分类 按局中人的个数 二人对策和多人对策 按各局中人的赢得函数的代数和是否为零 零和对策和非零和对策 按局中人之间是否允许合作 合作对策和非合作对策 按局中人的策略集的元素个数 有限对策和无限对策 按策略的选择是否与时间无关 静态对策和动态对策 按模型的数学特征 矩阵对策 连续对策 微分对策 凸对策 随机对策等等 今后我们主要讨论二人有限零和对策 又称为矩阵对策 第二节矩阵对策 矩阵对策 二人有限零和对策 策略 局中人1 局中人2 赢得函数值 对于局势 局中人1 局中人2 其中 称矩阵A aij 为局中人1的赢得矩阵 明显地A就是局中人2的支付矩阵 因此对矩阵对策 一旦给出矩阵A 则模型随之确定 矩阵对策的纯策略 一般地 矩阵对策记为G S1 S2 A 其中S1与S2分别是局中人1和2的策略集 作为理论探讨实际上并不关心这些策略集中具体有哪些策略 而只关心有几个策略 为了与后面的混合策略区别 这些策略集中的每个策略称为一个纯策略 例 p389 设有一矩阵对策G S1 S2 A 其中 矩阵对策的解 局中人1 局中人2 策略3 策略3 策略4 策略1 局中人如果从自己的角度出发考虑 可见这样做 局中人实际上难以达到使自身利益最大化的目标 因此局中人应该这样考虑每一个策略 当自己采用一个策略时 对方可以肯定会采用某个特定的策略 在此基础上来选择对自己最有利的策略 矩阵对策的解 续1 从对局中人1的策略来看 对其采用的每个策略 局中人2必定会采用矩阵A中该行最小数对应的策略 因此局中人1选择其最优策略的方式是 选出A中每行中的最小数 然后再在选出来的数中的最大者对应的策略 也即局中人1选择对应的策略 同样 局中人2选择其最优策略的方式是 选出A中每列中的最大数 然后再在选出来的数中的最小者对应的策略 也即局中人1选择对应的策略 矩阵对策的解 续2 若在矩阵A中若 则这个数对应的各自的策略所组成的局势就是双方都不得不接受也同意接受的局势 相应的策略就是双方的最优策略 例中局中人1的最优策略为策略2 局中人2的最优策略也是其策略2 矩阵对策的解 续3 定义1设G S1 S2 A 为一矩阵对策 其中A aij m n 若 成立 记其值为Vij 则称Vij为对策的值 也常记为VG 称使得上式成立的纯局势为在纯策略意义下的解 或平衡局势 相应的纯策略称为局中人1和局中人2的最优纯策略 矩阵对策的解 续4 在例中 可以看到A中平衡局势对应元素a22既是其所在行的最小元素 又是其所在列的最大元素 也就是对所有的i和j 有 定理1矩阵对策G S1 S2 A 在纯策略意义下有解 存在平衡局势 的充分必要条件是 矩阵A中存在一个元素 它既是所在行的最小元素又是所在列的最大元素 也即存在使得 矩阵A中满足上述条件的点称为鞍点 矩阵对策的解 续5 上述定理的意义是设是对应着ai j 的平衡局势 则当局中人1选择策略 i 时 局中人2为了使其所失最小 只能选择策略 j 否则所失更大 反之亦然 例 p391 设有矩阵对策G S1 S2 A 其中 易见 因此 都是对策的解 且VG 5 矩阵对策的解 续6 上例表明矩阵对策的解可能不是唯一的 若矩阵对策的解不唯一 则解之间具有如下性质 性质1 无差别性 若和是矩阵对策G的两个解 则 性质2 可交换性 若和是矩阵对策G的两个解 则和也是矩阵对策G的解 矩阵对策的解 续7 例 p392 局中人1 采购员 局中人2 自然 min 3000 2500 2000 max 1000 1500 2000 平衡局势为 即采购员最优策略是采购20t煤 矩阵对策的混合策略 在上面的讨论中可以看到 在矩阵对策G S1 S2 A 中 局中人1能保证的至少赢得是 局中人2能保证的至多所失是 明显地 v1 v2 当v1 v2时 矩阵对策G存在纯策略意义下的解 且VG v1 v2 然而若v1 v2 这时按定义 矩阵对策G不存在纯策略意义下的解 矩阵对策的混合策略 续1 例 p393 设矩阵对策的矩阵是 min 34 max max 56 min 因此v1 4 5 v2 于是不存在平衡局势 由此可见局中人1既可能采用策略 1也可能采取策略 2 同样局中人2既可能采用 1也可能采用 2 矩阵对策的混合策略 续2 既然局中人1没有必然要采用的优势策略 就可以考虑采用一种这样的策略 分别以概率x和 1 x 采用策略 1和策略 2 同样局中人2也可以这样考虑 分别以概率y和 1 y 采用 1和 2 局中人这样采用的策略称为混合策略 例如在上面的对策G中 可以看成是局中人2的一个混合策略 即局中人以20 的可能性采用策略 1而以80 的可能性采用策略 2 矩阵对策的混合策略 续3 定义2设有矩阵对策G S1 S2 A 其中 记 则分别称和为局中人1和局中人2的混合策略集 或策略集 和的元素分别称为局中人1和局中人2的混合策略 由他们的混合策略构成的策略组称为混合局势 矩阵对策的混合策略 续4 对于一个混合局势 x y 局中人1的赢得函数值 期望赢得值 为 此外称为G的混合扩充 纯策略是混合策略的一种特殊情形 一个混合策略 x1 xm T可以理解为 若进行多次的对局 它是局中人1取策略 1 m的频率 若只进行一次对局 则它反映了局中人1对各策略的偏爱程度 矩阵对策在混合意义下的解 像纯策略的情况一样 若局中人是理智的 则他们会这样考虑自己的策略 当自己采用一个策略时 对方必然采用一个怎样的特定策略 然后据此确定对自己最有利的策略 例如当局中人1采用策略x时 局中人2为使自己所失最小必定采用满足的策略 因此局中人1的最优策略就应使 类似地 局中人2的最优策略就应使 矩阵对策在混合意义下的解 续1 定义3设是G的混合扩充 如果 记其值为VG 则称VG为对策G的值 称使上式成立的混合局势 x y 为G在混合策略意义下的解 或平衡局势 并分别称x 和y 为局中人1和2的最优混合策略 今后约定 对矩阵对策G和其混合扩充G 一般不加区别 都用G S1 S2 A 表示 如果G在纯策略意义下的解不存在 则自然认为讨论的是混合策略意义下的解 矩阵对策在混合意义下的解 续2 类似定理1 也可以建立混合策略意义下的鞍点型充分必要条件 定理2矩阵对策G在混合策略意义下有解的充分必要条件是 存在使得对任意 例 p394 矩阵对策在混合意义下的解 续3 取 则 从而 故x 和y 分别是局中人1和2的最优策略 对策的值 局中人1的期望赢得值 为VG 9 2 矩阵对策的基本定理 记号 易见E i y 是E x y 在x 0 0 1 0 0 T时的值 即局中人1取纯策略 i时的值 类似地 E x j 是局中人2在取纯策略 j的值 第i个 和 矩阵对策的基本定理 续1 定理3矩阵对策G在混合策略意义下有解的充分必要条件是 存在使得对任意i 1 2 m j 1 2 n 有 与定理2比较可知定理3大大地简化了局势 x y 是平衡局势的验算工作 理论上 定理2需要无穷多次验算 而定理3只需要经过m n次验算 矩阵对策的基本定理 续2 定理4设则 x y 是矩阵对策G解的充分必要条件是 存在数v使得x 和y 分别是下面的不等式组的解 矩阵对策的基本定理 续3 将上面的两个不等式组稍做修改为 容易看出右边两个线性规划问题互为对偶问题 且都存在可行解 矩阵对策的基本定理 续4 定理5任一矩阵对策G S1 S2 A 一定存在混合意义下的解 上面的讨论实际上蕴涵了求解矩阵对策的一般方法 对任意矩阵对策问题只要求解线性规划问题 和其对偶问题就可得到局中人1和2的最优策略 从而得到矩阵对策的解 关于具体求解方法后面将进一步介绍 矩阵对策及其解的基本性质 定理6设 x y 是矩阵对策G的解 v VG 则 1 若 则 2 若 则 3 若 则 3 若 则 矩阵对策及其解的基本性质 续1 下面记矩阵对策G的解集为T G 定理7设有两个矩阵对策G1 S1 S2 A1 G2 S1 S2 A2 其中A1 aij A2 aij L L为任一常数 则 1 2 T G1 T G2 定理8设有两个矩阵对策G1 S1 S2 A G2 S1 S2 aA 其中a 0 为任一常数 则 1 2 T G1 T G2 矩阵对策及其解的基本性质 续2 定理9设G S1 S2 A 其中A AT为斜对称矩阵 这样的矩阵对策也称为对称对策 则 1 VG 0 2 T1 G T2 G 其中T1 G 和T2 G 分别为局中人1和2的最优策略集 矩阵对策的解法 图解法 1 这种方法适合于求解矩阵对策中有一个局中人只有两个策略的问题 下面通过例子来说明该方法 例 p398 O I I II II 1 2 3 11 2 5 7 3 2 1 x x x b1 矩阵对策的解法 图解法 2 很明显 一般情况下局中人1的赢得值z满足 z 2x 7 1 x 同理z 3x 5 1 x 以及z 11x 2 1 x 于是 z min 2x 7 1 x 3x 5 1 x 11x 2 1 x 这表明局中人1的赢得值对应的点必落在图中的阴影区域 而且局中人1将在区域中找一点使对应的赢得最大 这点就是A A x 矩阵对策的解法 图解法 3 A x 可见局中人1的最优策略就是 x 1 x 其中x OA 他的最大赢得值就是图中A点的纵坐标VG 通过解下列方程组就可得到x 和VG 解得x 3 11 VG 49 11 从而得到局中人1的最优混合策略为 3 11 8 11 矩阵对策的解法 图解法 4 A x 由图中可以看出局中人2的最优混合策略仅由 2和 3组成 实际上设是局中人2的最优混合策略 则因 根据定理6 必有 又因 3y2 11y3 49 11 5y2 2y3 49 11 y2 y3 1 得局中人2的最优混合策略为 0 9 11 2 11 矩阵对策的解法 图解法 5 例 p399 设局中人2的最优混合策略为 y 1 y 则当局中人1取策略 1时 局中人2的支付为2y 7 1 y O I I II II 1 2 3 11 2 6 7 3 1 y 2 一般情况下局中人2的支付不小于2y 7 1 y 从而局中人2的支付值对应的点落在下阴影区域 矩阵对策的解法 图解法 6 O I I II II 1 2 3 11 2 6 7 3 1 2 y 明显地 局中人2要适当地选择y 使得直线y y 与阴影部分的交点的纵坐标尽可能小 B1 B2 A1 A2 如图可知 A1 y A2 并且局中人2最小的支付VG 6 由方程组 得A1 1 5 A2 4 9 因此局中人2的最优混合策略为 y 1 y 其中1 5 y 4 9 矩阵对策的解法 方程组法 1 由定理4知 求矩阵对策的解等价于求解不等式组 由定理6 若在最优策略中有则上述不等式组的求解又转化为如下的方程组的求解 矩阵对策的解法 方程组法 2 如果这两个方程组存在非负解 则得到矩阵对策问题的解 如果这两个方程组不存在非负解 则可视具体情况将方程组中的某些等式改为不等式 继续试求解 直到求的矩阵对策的解 这种方法由于事先假定因此当最优策略的某些分量实际不为零时 这两个方程组可能无解 矩阵对策的解法 方程组法 3 但如果矩阵对策中的矩阵为2 2的矩阵 即 若不存在鞍点 则可以证明最优混合策略中的均大于零 于是这时的方程组 一定存在严格的非负解 它就是要求的最优策略 矩阵对策的解法 方程组法 4 此外矩阵对策的值此时为 优超原则 1 对于矩阵对策问题 若矩阵A中第i行的各元素均大于或等于第j行的对应元素 则称局中人1的策略 i优超于 j 当 i优超于 j时 局中人1在任何情况下将优先使用策略 i而不会使用策略 j 因此可在矩阵A中将 i对应的行去掉 对于矩阵A的列 若某一列的各元素都小于或等于另一列的对应元素 则称该列对应的策略优超于另一列对应的策略 并且求解时可将矩阵的另一列去掉 优超原则 2 在求解时 利用优超原则有时可以将较高阶的矩阵化为较低阶的矩阵 从而简化求解 例 p400 求解矩阵对策G S1 S2 A 其中 优超原则 3 3优超于 2 4优超于 1 2优超于 3 4 5 3优超于 5 累次取优 优超原则 4 这样本例转化为求解如下矩阵对应的对策问题 由方程组法 只需要解方程组 其非负解为 原问题的一个解为 齐王赛马问题的解 1 齐王赛马问题中两人的策略为 齐王的赢得矩阵为 p389 齐王赛马问题的解 2 显然 齐王赛马问题中的矩阵不存在鞍点 因此不存在纯策略意义上的解 而求混合意义下的解可转化为求解方程组 p402 的问题 方程组的一个解是 xi 1 6 i 1 2 6 yj 1 6