第十章_对策论.ppt

齐王赛马 《史记》中有这样一个故事： 鉴于第一次赛马的惨败，所以当齐王满面春风地再次邀请田忌赛马时，田忌感到很为难。一方面君王的旨意不好违拗，另一方面自己对这种必败的赛局失去了信心。田忌的军师孙膑，是得名师鬼谷子真传的颇有才能的军事家。他了解到主将闷闷不乐的缘由，便替田忌出了一个主意：用自己的下等马和国王的上等马比赛，而用自己的上等马和国王的中等马比赛，中等马和国王的下等马比赛。比赛开始，第一场国王的马以极大的优势取得了胜利。国王没有料到田忌的马竟然如此不堪一击，为此俯仰大笑，得意不已。但美景不长，在二、三场中田忌的马都取得了胜利。这一轮国王非但没有赢，反而输了一千两黄金。可笑的是，齐王输了钱还弄不清自己是怎样输的呢! 这个故事表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。 研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；它是运筹学中的一部分内容。 概论 解的概念 矩阵对策的解法 合作对策 概 论 名称 Game Theory 博奕论 发展历史 对策论模型 分 类 例 子 发 展 简 史 早期工作 1912年E.Zermelo “关于集合论在象棋对策中的应用” 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想 产生标志 1944年J.V.Neumann和O.Morgenstern “对策论与经济行为” 发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策, 1994年诺贝尔经济学奖授予了三位博奕论专家：纳什(Nash)、塞尔腾(Selten)和豪尔沙尼(Harsanyi)，其中最重要的原因之一是他们在非合作博奕论方面作出了突出的贡献。 策略集合：对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）策略；参加对策的每一局中人i?I的策略集记为Si。一般每一局中人的策略集中至少应包括两个（纯）策略。如《齐王赛马》中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。齐王与田忌的策略集中，各自都有六个纯策略：S1,S2={(上、中、下),(上、下、中),(中、上、下), (中、下、上),(下、上、中),(下、中、上)} 局势：对策中，每一局中人所选定策略形成的策略组合称一个局势。设局中人1从自己的策略集S1={?1,?2 …,?m}中选定策略?i，局中人2从自己的策略集S2={?1, ?2 …, ?n}选定策略?j，则(?i, ?j)就构成两人对策中的一个局势。 在n个对策中，设si表示第i局中人的一个策略，则n个局中人的策略组合形成的局势为S=(s1,s2,…sn)。 研究对策论常用的两种模型 (一)展开型 (二)正规型 展开型对策 例: 展开型对策 定义1:有n个局中人的对策树是指具有以下性质的三元组 ,使得: 为树,且 为一映射, 为局中人的集合 为一映射 展开型对策 定义2:设 为对策树,称 为由 产生的n人对策,对策 也称为展开型对策. 定义3:在对策 中,设有策略组 使对于任何的 及 均有: ,则称 为对策 的一个平衡点. . 展开型对策 定理:设 为对策树,则 有一个平衡点 正 规 对 策 模 型 局中人 两个或两个以上---决策者 策略集合 策略----决策 局势----状态 支付函数 支付关于局势的函数----决策依据和标准 模型 按对策元素分类 局中人 两人对策、多人对策 策略 有限对策、无限对策；非合作对策、合作对策 支付 零和对策、非零和对策 时间 单阶段对策、多阶段对策 按对策行为的分类 例 子 两个参加者甲、乙各出示一枚硬币，在不让对方看见的情况下，将硬币放在桌子上，若两个硬币都呈正面或都呈反面则