第八章 对策论.ppt

对策论 gametheory 主讲人 宋慧敏山东大学威海分校 博弈论 例1战国时期 齐王与他的大将田忌赛马 双方约定 从各自的上 中 下三个等级的马中选出一匹 比赛时 双方选出的每匹马都轮流参加 输者付给胜者一千金 由于齐王的同等级的马都比田忌的要强 所以田忌的朋友孙膑给田忌出了主意 让田忌用 下马 对齐王的 上马 用 上马 对齐王的 中马 用 中马 对齐王的 下马 比赛结束时 田忌反而得到一千金 例2我方用大炮防守 敌方用坦克进攻 有两个防守方向 我方从两方向中选择一个作为主要防守方向 集中较多的炮 敌方在侦察到我方的主要防守方向后 选择一个方向作为主攻方向 即集中较多坦克来进攻 战斗开始后 我方在了解敌方主攻方向后 在供应弹药时 可选择一个主要供应方向 最后 我方用摧毁敌方坦克的数量作为我方的赢得 注 上述问题都是带有斗争性质的问题 斗争的双方都力图选取最优的策略以获得尽可能好的结果 由 齐王赛马 引入 对策论 亦称博弈论 的主要研究对象 带有斗争 冲突性质的现象 例 下棋 打桥牌 赛球等政治 经济和军事等方面的斗争等 非合作对策 对策论理论模型 noncooperativegame 合作对策 cooperativegame 1对策论的基本概念 模型 局中人两个或两个以上 决策者策略集合策略 决策局势 状态支付函数支付关于局势的函数 决策依据和标准 例l有两个儿童A和B在一起玩 石头一剪子一布 游戏 每个人的出法都只能在 石头 剪子 布 中选择一种 当A B各选定 个出法 亦称策略 时 就确定了一个 局势 或 结局 也就可以定出各自的输赢 如果我们规定性者得1分 负者得 1分 平手时各得零分 则对于各种可能的 局势 和A的得分 可以用下面的矩阵来表示 表5 1 这个矩阵称之为支付矩阵 也称赢得矩阵 在游戏中 A和B都想选取适当的 策略 以取得胜利 注 两个局中人在同一局势下所得支付之和为零 此类对策称为零和对策 非合作对策 策略型 例2囚徒两难 prisoners dilemma 对策 警方拘捕了两个犯罪嫌疑人 记为局中人I和 现有证据尚不能证明他们一定有罪 故将二人分别关押 审讯 即二人不能合作或串通 面对审讯 两个局中人可选择的策略均为 坦白 和 不坦白 在不同的局势下 两个局中人的支付如下 坦白不坦白坦白 6 6 0 10 I不坦白 10 0 1 1 注 两个局中人在同一局势下所得支付之和不为零 此类对策称为非零和对策 合作对策 参与的各方可以结成联盟 为谋更高的利润例6设有三个厂商 简记为厂商1 2 3 联合生产某种仪器 该仪器由两个部件A B组装而成 每台仪器售出可获收益1万元 每一厂商都可以独立生产这种仪器 但成本较高 也可以联合生产以降低成本 形成规模以获取更高利润 记N 1 2 3 N称为局中人集合 N的任意一个子集S称为联盟 表示联盟中的厂商将合作生产 记V S 为合作生产时 联盟S可获的最大利润 根据市场分析有V 1 30 V 2 25 V 3 40 V 1 2 60 V 1 3 80 V 2 3 70 V 1 2 3 120显然 三个厂商联合生产最为有利 但在面临利润分配时 三个厂商又有着利益冲突 那么应如何分配利润才是公平 合理的 这类对策问题称为合作对策问题 合作对策的理论在经济学的均衡分析和费用分配等方面具有广泛的应用 合作对策 分类 局中人两人对策 多人对策策略有限对策 无限对策 非合作对策 合作对策支付零和对策 非零和对策时间单阶段对策 多阶段对策 该章主要讲述二人有限零和对策 简称矩阵对策 策略集 局势集 支付函数 矩阵表示 上述矩阵对策记为 G S1 S2 A 局中人I的策略集局中人I的赢得矩阵局中人II的策略集 矩阵对策 二人有限零和对策 2矩阵对策及其解 纯策略 A 齐王赛马 齐王在各局势中的益损值表 单位 千金 齐王赛马 即是一个矩阵对策 其中 齐王的策略集 S1 1 2 3 4 5 6 田忌的策略集 S1 1 2 3 4 5 6 下列矩阵称齐王的赢得矩阵 31111 11311 11A 1 13111 11131111 1131111 113 例 有交易双方公司甲和乙 甲有三个策略 1 2 3 乙有四个策略 1 2 3 4 根据获利情况建立甲方的 益损值 赢得矩阵 30 20A 2301 2 4 13问 甲公司应采取什么策略比较适合 1 矩阵对策在纯策略意义下的解 注 在讨论各方采用的策略是必须注意一个前提就是对方是理智的 这就是要从最有把握取得的益损值情况考虑 甲 采取 1至少得益 3 损失3 20 3 4 损失4 乙 采取 1甲最多得益2 乙最多损失2 23 乙得益 3 30 乙得益0 43 乙得益 3 取大则取 2maxminaij 0ij 取小则取 3minmaxaij 0ji 30 20A 2301 2 4 13 最稳妥策略 最稳妥策略 最优纯策略 均衡局势 这时 局中人的最稳妥策略即为各自的最优纯策略 证明 例子 均衡局势的存在前提 maxminaij minmaxaij vijji 不存在最优纯策略 改为求解混合策略 当maxminaij minmaxaij时 ijji 例 设一个赢得矩阵如下 59A maxminaij 6策略 286ijminmaxaij 8策略 1ji 矛盾 甲取 2 乙取时 1 甲实际赢得8比预期多2 乙就少2 这对乙讲是不满意的 考虑这一点 乙采取策略 2 若甲分析到这一点 取策略 1 则赢得更多为9 此时 甲 乙方没有一个双方均可接受的平衡局势 思路 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 即混合策略 2 矩阵对策在混合扩充意义下的解 矩阵对策的混合扩充 矩阵对策的混合平衡解 混合平衡局势的存在性 定理3 定理4 矩阵对策的混合扩充存在平衡局势 即 证明 上述两规划互为对偶规划 当且仅当两者都有可行解时 二者都有最优解 且最优值相等 而上述两规划都有可行解 则上述两规划分别有最优解最优值都为 即矩阵对策在混合策略意义下恒有解 V 0 3矩阵对策的线性规划解法 1 优超 因而策略出现的概率为0 可以在支付矩阵中删除该策略对应的行 问题的简化 算例1 算例1 x4 1 16 x3 1 4 y3 3 16 y4 1 8 求解 T G 矩阵对策G的解集 2 关于矩阵对策的其它结论 算例2 算例2 最优策略为 1 3 0 2 3 和 2 3 1 3 0 最优值为4 3 解得x 0 25 0 0 5 y 0 5 0 25 目标函数值为3 4 不良一般 LINGO求解程序 model min x1 x2 x3 2 x1 x3 1 3 x2 2 x3 1 endmodel max y1 y2 2 y1 1 3 y2 1 y1 2 y2 1 end 算例3 求解 LINGO求解程序 model min x2 x3 0 x2 4 x3 1 3 x2 0 x3 1 endmodel max y2 y3 0 y2 3 y3 1 4 y2 0 y3 1 end 结果 矩阵对策的其他解法 1 2 n或m 2对策的图解法 例1求解矩阵对策G S1 S2 A 其中 设局中人II的混合策略为 y 1 y y 0 1 过数轴上坐标为0和1的两点分别做两条垂线I I和II II 垂线上点的纵坐标值分别表示局中人I采取纯策略 1 2和 3时 局中人II采取各纯策略时的支付值 2 11 6 1 0 7 6 2 1 II II I I 2y 7 1 y V 图1 1m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 2 11 6 1 0 7 6 2 1 II II I I 2y 7 1 y V 图1 2m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 当局中人II选择每一策略 y 1 y 时 他的最大可能的损失为由局中人I选择 1 2 3时所确定的三条直线2y十7 1 y V 6y十6 1 y V 11y十2 1 y V在y处的纵坐标中之最大者 如图所示 2 11 6 1 0 7 6 2 1 II II I I 2y 7 1 y V 图1 3m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 当局中人II选择每一策略 y 1 y 时 他的最大可能的损失为由局中人I选择 1 2 3时所确定的三条直线2y十7 1 y V 6y十6 1 y V 11y十2 1 y V在y处的纵坐标中之最大者 如图所示 2 11 6 1 0 7 6 2 1 II II I I 2y 7 1 y V 图1 4m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 当局中人II选择每一策略 y 1 y 时 他的最大可能的损失为由局中人I选择 1 2 3时所确定的三条直线2y十7 1 y V 6y十6 1 y V 11y十2 1 y V在y处的纵坐标中之最大者 如图所示 2 11 6 1 0 7 6 2 1 II II I I 2 1 2y 7 1 y V 图1 5m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 2 11 6 1 0 7 6 2 1 II II I I 2 1 2y 7 1 y V 图1 6m 2对策的图解法 3 2 6y 6 1 y V 11y 2 1 y V 局中人II的最优选择就是确定y使他的损失尽可能地少 按最大最小原则应选择OA1 y OA2而A1B1与A2B2为对策值 2 11 6 1 0 7 6 2 1 II II I I 2 1 2y 7 1 y V 图1 7m 2对策的图解法 A2 A1 3 2 6y 6 1 y V 11y 2 1 y V 局中人II的最优选择就是确定y使他的损失尽可能地少 按最大最小原则应选择OA1 y OA2而A1B1与A2B2为对策值 对策值为6 2 11 6 1 0 7 6 2 1 II II I I 2 1 2y 7 1 y V 图1 8m 2对策的图解法 A2 A1 3 2 6y 6 1 y V 11y 2 1 y V 由方程 2y十7 1 y 6 11y十2 1 y 6 解得OA1 1 5 OA2 4 9 所以 局中人II的最优策略为x y 1 y T其中1 5 y 4 9 而局中人I的最优策略为 0 1 0 T 即为 2 例2求解矩阵对策G S1 S2 A 其中 第2列优超于第3列 划去第3列 2 3 第4列 1 3 第1列 第2列 划去第2列 解得新的赢得矩阵 局中人I的最优混合策略为 x 3 4 1 4 T 1 2 4两线的交点 从图形中看出y3 0 局中人II的最优混合策略由下列方程组解得 4y1 3 8y2 2y4 13 4 y1 5y2 7y4 13 4 y1 y2 y4 1满足上面方程的解有无穷多个 故局中人II有无穷多个最优混合策略 与其它直线域无交点 优超原则解法的缺陷 2 迭代法 近似方法 基本思想 假设两个局中人反复进行对策多次 在每一局中各局中人都从自己的策略集合中选取一个使对方获得最不利结果的纯策略 即k局对策纯策略的选择欲使对手前k 1局中的累计所得最少 或累计所失最多 满足要求精度后停止迭代 用局中人各纯策略出现的频率分布作为最优策略中概率分布的一个近似 矩阵对策的其他解法 例1求解矩阵对策G S1 S2 A 其中 S1 S2 石头 剪子 布 求解矩阵对策G S1 S2 A 假设局中人I先采取策略 其赢得情况如下表 局中人II选择 局中人I