数学建模第十讲博弈模型ppt课件.ppt

第十讲对策模型 10 1二人零和对策模型10 2进攻与撤退的选择10 3二人常数和对策模型10 4二人非常数和对策模型 对策行为 问题一 甲 乙两名儿童玩 石头 剪子 布 的游戏 石头胜剪子 剪子胜布 布胜石头 那么 甲 乙儿童如何做 使自己获胜的可能最大 问题分析 问题中所涉及的要素 1 游戏决定者 甲 乙儿童两人 3 游戏的收益 支付 胜得分为1 负得分为 1 平得分为0 2 游戏者的决定 石头 剪子 布 问题二 囚徒困境 甲乙两个嫌疑犯因同一罪行被逮捕 如果双方均坦白 则各获刑3年 如果双方均不坦白 则各获刑2年 如果其中一人坦白 另一人不坦白 则坦白一方宽大释放 另一方获刑5年 两个嫌疑犯各自应采取什么策略才能使自己的刑期最短 问题分析 问题中所涉及的要素 1 决定者 甲 乙嫌疑犯两人 3 甲乙的收益 支付 获刑年数 2 可用的决定 坦白 不坦白 对策行为的三要素 1 局中人 在一个对策行为中 有权决定自己行动方案的对策参加者 称为局中人 通常用I表示局中人的集合 如果n个局中人 则I 1 2 n 它可以是一个人 也可以是一个集团或一个自然现象 2 策略集 一局对策中 可供局中人选择的一个实际可行的完整的行动方案 称为一个策略 设i为局中人 i的所有策略构成的集合Si称为i的策略集 3 赢得函数 支付函数 局势 在一局对策中 各局中人所选定的策略形成的策略组称为一个局势 即若设si是第i个局中人的一个策略 则n个局中人的策略组s s1 s2 sn 就是一个局势 全体局势的集合S可用各局中人策略集的笛卡尔乘积表示 即S S1 S2 Sn 赢得函数 当局势出现后 对策的结果也就确定了 也就是说 对任一局势s S 局中人i可以得到一个赢得Hi s 显然 Hi s 是局势s的函数 称之为第i局中人的赢得函数 1 二人有限零和对策 是指有两个参加对策的局中人 每个局中人都只有有限个策略可供选择 在任一局势下 两个局中人的赢得之和总等于零 2 二人零和对策模型 矩阵对策模型 设 分别表示两个局中人 且它们的纯策略集分别为S1 1 2 m 和S2 1 2 n 记局中人 对任一纯局势 i j 的赢得值为aij 并称 为局中人 的赢得矩阵 局中人 的赢得矩阵为 A 通常 将矩阵对策记成G S1 S2 A 或G S1 S2 A 10 1二人零和对策 3 局中人如何选取对自己最有利的纯策略 局中人的 理智行为 双方都不想冒险 都不存在侥幸心理 而是考虑到对方必然会设法使自己的所得最小 从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据 选择原则 局中人 按最大最小原则 局中人 按最小最大原则 即局中人 从所有最小的赢得中选择最大的赢得的策略 局中人 从所有最大的损失中选择最小的损失的策略 解 根据选择的原则 分析局中人的选择的策略 局中人 的策略 纯策略 1 2 2 4可能带来的最小赢得分别 8 2 10 3 所以 最小赢得中最大的值为2 因此局中人 的策略应为 2 局中人 的策略 纯策略 1 2 3可能带来的最大损失分别9 2 6 所以 最大损失中最小的值为2 因此局中人 的策略应为 2 总之 局中人 的最优察纯策略分别为 2 2 4 矩阵对策的解 定义1设G S1 S2 A 为矩阵对策 其中S1 1 2 m S2 1 2 n A aij m n 若等式 成立 记VG ai j 则称VG为对策G的值 称上述等式成立的纯局势 i j 为G在纯策略下的解 或平衡局势 i 与 j 分别称为局中人 的最优纯策略 根据定义1可知 上例中 2 2 是在纯策略下的解 对策值VG a22 2 i 2 j 2 定理的直观解释 如果ai j 既是矩阵A aij m n中第i 行的最小值 又是第j 列的最大值 则ai j 是对策的值 且 i j 是在纯策略意义下的解 定理的对策意义 一个平衡局势 i j 具有这样的性质 当局中人 选择了纯策略 i 后 局中人 为了其所失最小 只能选择 j 否则就可能失去更多 反之 当局中人 选择了纯策略 j 后 局中人 为了得到最大的赢得 只能选择 i 否则就会赢得更少 双方在局势 i j 下达到一个平衡状态 定理1矩阵对策G S1 S2 A 在纯策略意义下有解的充要条件是 存在纯局势 i j 使得对一切i 1 2 m j 1 2 n 均有aij ai j ai j 定理1的一个等价命题 定义2设f x y 为一个定义在x A y B上的实值函数 如果存在x A y B 使得对一切x A y B 有f x y f x y f x y 则称 x y 为函数f x y 的一个鞍点 定理1的等价命题 矩阵对策G在纯策略意义下有解 且VG ai j 的充要条件是 ai j 是矩阵A的一个鞍点 也称为对策的鞍点 矩阵对策的混合策略 定义3设G S1 S2 A 为矩阵对策 其中S1 1 2 m S2 1 2 n A aij m n 记 则S1 和S2 分别称局中人 和 的混合策略集 或策略集 x S1 y S2 分别称为局中人 和 的混合策略 对x S1 y S2 称 x y 为一个混合局势 或局势 这样得到的一个新的对策记成G S1 S2 E 称G 为对策G的混合扩充 局中人 的赢得函数记成 1 纯策略与混合策略的关系 纯策略是混合策略的特例 局中人 的纯策略 k等价与混合策略x x1 x2 xm S1 其中当i k时 xi 1 当i k时 xi 0 混合策略x x1 x2 xm S1 可设想成当两个局中人多次重复进行对策G时 局中人 分别采取纯策略 1 2 m的频率 定义4 设G S1 S2 E 是矩阵对策G S1 S2 A 的混合扩充 如果 记其值为VG 则称VG为G 的值 称满足上述等式的混合局势 x y 为G在混合策略意义下的解 或简称解 x 和y 分别称为局中人 和 的最优混合策略 或简称最优解 E x y E x y E x y 定理2矩阵对策G S1 S2 A 在混合策略意义下有解的充要条件是 存在x S1 y S2 使 x y 为E x y 的一个鞍点 即对一切x S1 y S2 有 2 矩阵对策G在混合策略意义下解的定义 3 混合对策求解方法 下列线性规划问题的解就是局中人 的最优混合策略x 问题一求解 3 混合对策求解方法 下列线性规划问题的解就是局中人 的最优混合策略y 问题一求解 1944年6月初 盟军在诺曼底登陆成功 到8月初的形势 背景 10 2进攻与撤退的抉择 双方应该如何决策 问题分析与模型假设 对策参与者为两方 盟军和德军 盟军有3种使用其预备队的行动 强化缺口 原地待命 东进 德军有2种行动 向西进攻或向东撤退 对策双方完全理性 目的都是使战斗中己方获得的净胜场次 胜利场次减去失败场次 尽可能多 对策模型 对策参与者集合N 1 2 1为盟军 2为德军 盟军行动S1 1 2 3 强化缺口 原地待命 东进 德军行动S2 1 2 向西进攻 向东撤退 无鞍点 混合策略 盟军的混合策略集 赢得函数 S1 x x1 x2 x3 德军的混合策略集 S2 y y1 y2 局中人 求解 局中人 求解 在晚8点至晚9点这时间段 两家电视台在竞争100万电视观众收看自己的电视节目 并且电视台必须实时公布自己在下一时段的展播内容 电视台1可能选择的展播方式及可能得到的观众如下表 10 3二人常数和对策模型 试确定两家电视台各自的策略 10 4二人非常数和对策模型 囚徒困境 甲乙两个嫌疑犯因同一罪行被逮捕 如果双方均坦白 则各获刑3年 如果双方均不坦白 则各获刑2年 如果其中一人坦白 另一人不坦白 则坦白一方宽大释放 另一方获刑5年 两个嫌疑犯各自应采取什么策略才能使自己的刑期最短 双矩阵对策记成G S1 S2 A B 两个局中人 的纯策略集分别为S1 1 2 m 和S2 1 2 n A B分别为局中人 和 的赢得矩阵 双矩阵对策记成G S1 S2 A B A B分别为局中人 和 的赢得矩阵 若存在 则称局势 i j 为G在纯策略意义下的解 或称纳什均衡点 i 与 j 分别称为局中人 的最优纯策略 1 双矩阵对策纯策略意义下的解 2 双矩阵对策G在混合策略意义下的解 设G S1 S2 E1 E2 是矩阵对策G S1 S2 A B 的混合扩充 如果存在x S1 y S2 使得对一切x S1 y S2 有 则称混合局势 x y 为G在混合策略意义下的解 也称双矩阵对策的纳什均衡点 E1 x y E1 x y E2 x y E2 x y 3 双矩阵混合对策求解方法 下列线性规划问题的解就是局中人 的最优混合策略x 下列线性规划问题的解就是局中人 的最优混合策略y 可以合并为下列线性规划问题 比赛策略