对策论博弈论PPT课件.ppt

2020 3 18 运筹学第12讲 对策论 博弈论 简介 广州大学地理科学学院蔡砥 1 2020 3 18 内容 对策现象及其三个要素对策问题举例及对策的分类矩阵对策 矩对策 的基本理论关于纯策略与混合策略 2 2020 3 18 对策现象及其三个要素 3 2020 3 18 经典案例 囚徒困境 两个犯罪嫌疑人被捕并受到指控 但除非至少一个人招认犯罪 警方并无充足证据将他们按罪判刑 警方把他们关入不同牢房 并对他们说明不同行动带来的后果 如果两人都不坦白 将均被判为轻度犯罪 入狱一个月 如果双方都坦白招认 都将被判入狱6个月 最后 如果一人招认而另一人拒不坦白 招认的一方将马上获释 而另一人将判入狱9个月 所犯罪行6个月 干扰司法加判3个月 前提 两囚犯是非合作的 4 2020 3 18 囚徒困境的双变量矩阵表示 囚徒面临的问题可用上图的双变量矩阵表来描述 双变量 指的是在两个参与者的博奔中 每一单元格有两个数字 分别表示两个参与者的收益 习惯上 横行代表的参与者 囚徒1 的收益在两个数字中放前面 列代表的参与者 囚徒2 的收益置于其后 无论囚徒1选择沉默 不坦白 或者招认 囚徒2都会选择招认 反之也然 5 2020 3 18 对策现象的三个要素 局中人 策略 集 赢得函数 一般 当局中人 策略集和赢得函数这3个要素确定后 一个对策模型也就给定 6 2020 3 18 局中人 players 一个对策中 有权决定自己行动方案的对策参与者称为局中人 通常用I表示局中人的集合 一个对策中至少有两个局中人 局中人是广义的 可以是单个个人 也可以是一个集体 利益完全一致的参与者只能看成一个局中人 局中人都是 理性的 遵从博弈 game 的规则并总是采取最利己的策略 7 2020 3 18 关于理性局中人的一个有趣例子 海盗分宝石 5个海盗抢到了100颗宝石 每一颗都一样的大小和价值连城 他们决定这么分 1 抽签决定自己的号码 1 2 3 4 5 2 首先 由1号提出分配方案 然后大家5人进行表决 当且仅当超过半数的人同意时 按照他的提案进行分配 否则提案人将被扔入大海喂鲨鱼 3 如果1号死后 再由2号提出分配方案 然后大家4人进行表决 当且仅当超过半数的人同意时 按照他的提案进行分配 否则将被扔入大海喂鲨鱼 4 依次类推问 最终的方案为如何 前提 海盗们非常遵守规则 并谋求利益最大化命不能丢宝石要尽量多 8 2020 3 18 理性的破坏 照 三国 1命刀斧手埋伏于帐侧 到时候一声令下 将其他4个统统剁成肉泥 照 水浒 1奋起一脚掀掉桌子 挑一个最有主见的 抽刀砍了 来个林冲刀砍王伦 其他几个立马跪地告饶 哥哥息怒 哥哥但要独得 尽管拿去就是了 引自网易科技论坛 码帖人 乱话三千 9 2020 3 18 策略 strategies 博弈中 可供局中人选择的一个实际可行的完整的行动方案称为一个策略 局中人i的策略集记为Si 一般的 每一个局中人的策略集中至少应包括2个策略 囚徒困境问题中 囚徒的策略有2个 沉默或招认 海盗问题中提出方案的海盗有多个策略 各种可能的分配方案其它海盗的策略有2个 支持或否决 10 2020 3 18 赢得函数 payofffunction 支付函数 博弈中 每一个局中人所出的策略形成的策略组称为一个局势 即设si是第i个局中人的一个策略 则n个局中人的策略形成的策略组s s1 s2 sn 就是一个局势 当一个局势s出现后 应该为每一个局中人i规定一个赢得值 或所失值 Hi s 不同的局势对应的赢得值不同 Hi是s的函数 称为赢得函数 11 2020 3 18 对策问题举例及对策的分类 12 2020 3 18 市场购买力争夺问题 13 2020 3 18 销售竞争问题 14 2020 3 18 费用分摊问题 假设沿某一河流有相邻的3个城市A B C 各城市可单独建立水厂 也可合作兴建一个大水厂 经估算 合建一个大水厂 加上敷设管道的费用 要比单独建3个小水厂的总费用少 但合建大厂的方案能否实施 显然要看总的建设费用分摊得是否合理 如果某个城市分摊到的费用比它单独建设水厂的费用还多的话 它显然不会接受合作的方案 问题是应如何合理地分摊费用 使合作兴建大水厂的方案得以实现 15 2020 3 18 对策的分类 根据局中人的个数 分为2人对策和多人对策 根据各局中人的赢得函数的代数和是否为零 分为零和对策与非零和对策 根据各局中人间是否允许合作 分为合作对策和非合作对策 根据局中人的策略集里的策略个数 分为有限对策和无限对策等等 此外 还有许多其它的分类方式根据策略的选择是否与时间有关 可分为静态对策和动态对策 根据对策模型的数学持征 可分为矩阵对策 连续对策 微分对策 阵地对策 凸对策 随机对策等 16 2020 3 18 矩阵对策的基本理论 仅讨论纯策略情况 17 2020 3 18 矩阵对策 矩阵对策为2人有限零和对策 博弈中的局中人只有2人 双方 有限 是指每个局中人的策略集均为有限集 零和 是指在任一局势下 两个局中人的赢得之和总等于零 即一个局中人的所得恰好等于另一个局中人的所失值 双方的利益是完全对抗的 田忌赛马 是一个典型的2人有限零和对策 18 2020 3 18 田忌赛马 19 2020 3 18 市场购买力争夺问题 20 2020 3 18 矩阵表示 由于是零和对策 因此无须给出双变量矩阵 而简化为单变量矩阵 21 2020 3 18 Exp 一个矩阵对策的解 22 2020 3 18 定义 平衡局势 23 2020 3 18 矩阵对策有解的充要条件 24 2020 3 18 田忌赛马问题无最优解 最优纯策略 25 2020 3 18 关于纯策略与混合策略 26 2020 3 18 一个无纯策略解的问题 由于不满足前文的充要条件 因此 该问题如果博弈双方都只可能采用单纯的一个策略时 本问题没有解 所谓没有解 是指找不到一个双方都可以接受的平衡局势 27 2020 3 18 混合策略 既然局中人没有最优的策略可出 局中人的一个可能是 以一定的概率随机地挑选策略 每一个策略有一定的概率 这就构成了混合策略 即一个混合策略是由多个纯策略按照一定的概率组合在一起的 例如 上面问题中 局中人I以概率pI和 1 pI 选取纯策略 1和 2 而局中人II以概率pII和 1 pII 选取纯策略 1和 2 28 2020 3 18 田忌赛马中关于齐王的讨论 齐王在多次比赛中 均采用 上中下 的策略 赢得了多次