君，已阅读到文档的结尾了呢~~
对策论方法 对策论方法 对策论方法 对策论方法 对策论方法 对策论方法
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
对策论方法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口当前位置： >>
运筹学与最优化方法课件--第七章--对策论模型--2012
第 七 章 对策论模型7.1引言一、对策论的发展和研究内容对策论(game theory)又称博奕论,是研究具 有竞争或斗争现象的数学理论和方法;它既是现 代数学的分支,也是运筹学中的一个重要分支. 注意: ① 对策论就是研究两个或多个竞争 者之间利益有冲突时,各竞争者应如何分析各方 的局势, 权衡利弊,以决定自己应采取怎样的行 动,得到一个对己方最有利结局的数学理论. ② 对策论的研究非常强调个人理性.1944年J .von Neumann 和 O.Morgenstern出 版了Theory of Games and Economic Behavior,可 以说该书是对策论的奠基之作, 它第一次给对策 (game)以明确的数学描述,对有关理论作出了系统 的论证, 并且讨论了对策在经济学上的一些应用. 这也标志着对策论成为数学和运筹学的一个分支. 从1944年到现在,对策论在理论和应用方面都 有了极大的发展. 在理论方面,从最初的零和二人对策(zero-sum two-person game)发展到非零和n人对策(non-zerosum n-person game), 特别是最近10多年来, 在n人 合作对策 (n-person cooperative game)方面的研究 有很大的进展．在应用方面从最初的经济学领域扩展到军 事、政治、社会学、心理学等方面, 近年来又 有回到经济学方面的趋势. 应强调指出的是,对策论在经济学中的应 用最为广泛也是最成功的.1994年诺贝尔经济 学奖同时授给三位博奕论专家纳什 (Nash),塞 尔腾 (selten)和豪尔沙尼(Harsanyi),就是一最 好的例证. 但这种研究目前主要还是定性的研究。博 弈 论美藉匈牙利数学家冯?诺依曼（John Von Neuman） 和美藉奥地利经济学家摩根斯顿（Morgenstern）相识于 普林斯顿大学，他们于1944年出版了经典著作《博弈论 与经济行为》，为现代博弈论的发展奠定了基础。纳什美国的数学家、经济学家纳什（John Nash）， 美籍匈牙利经济学家海萨尼（John C. Harsanyi） 和德国经济学家泽尔滕（R.Selten）因对博弈论的卓 越贡献而获得1994年度的诺贝尔经济学家。海萨尼值得一提的是纳什，他发表奠定 其在博弈论中重要地位的学术论文时，年 仅22岁，被人称为“一个天才”。1959年， 纳什被精神病医生诊断为“妄想性精神分 裂”，饱受精神病折磨40余年。泽尔滕二、基本概念例1 市场上的某种商品仅由甲,乙两厂生产, 它们都 想通过内部改造,获得更多的市场份额,且两厂分别都有 三个可行方案.据预测,当双方采取不同的方案后甲厂的 市场占有份额(百分比)变动情况如下:甲厂 乙厂?110?2－1?33?1?2?3126108－55例2 “齐王赛马”:一天齐王和他的大臣田 忌赛马,双方约定从各自的上、中、下三个等级 的马中各选一匹参赛,每匹马均只赛一次,每次输 者付给胜者一千两黄金. 已知在同等级马中,齐王的马胜田忌的马,但 若田忌的马比齐王的马等级高,则田忌胜. 当时田忌的谋士给他出了个主意: 每次比赛 先让齐王牵出他要参赛的马, 然后再决定自己的 出马顺序.让田忌依次用下马对齐王的上马,上马 对中马,中马对下马,比赛结束时田忌总共赢得一 千两黄金.齐王的赢得函数如下表所示：田忌齐王上 中 下 上 下 中上 中 下 3 1上 下 中1 3中 上 下 1 1中 下 上 1 1下 上 中下 中 上 1－11－111中 上 下中 下 上1－11311311－11 1下 上 中 下 中 上1 11－113 11 3－1例3 “囚徒困境”: 在西方某国, 一次严重的纵火案 发生后, 警方抓到两个犯罪嫌疑人 (事实上正是他们为了 报复,一起放火烧了这个仓库),但又缺乏足够的证据证明. 于是,警方把他们隔离起来,要求坦白交代. 如果他们都承 认纵火,每人将入狱三年;如果他们都不坦白, 由于证据不 足, 每人将只入狱一年 ; 如果一个抵赖而另一个坦白并 且愿意作证, 那么抵赖者将入狱五年,而坦白者将得到释 放,免予刑事处罚.这样,两个囚徒面临的博弈格局如下表 所示:乙 甲 坦 白 抵 赖坦 白 -3 -3 -5 0抵 赖 0 -5 -1 -1从以上三例中可发现, 对策现象包括以下三 个基本要素： 1.局中人(player): 局中人指有权决定自己行 动方案的对策参加者. 注意: 一个对策中至少应有两个局中人.局中 人可以是人,也可以是集团. 2.策略(strategy)与策略集(strategy set):策略 指局中人预先作出对付其他局中人的一个可能方 案,策略也称为纯策略. 一个局中人的策略全体,称为策略集.如“齐王赛马”中,田忌先出下马,再出上马,最后 出中马, 就是田忌的一个策略. 而齐王和田忌各自的策略 集中均有6个策略．注意 ① 每个局中人拥有策略的个数可相等,也 可不等, 可以是有限个, 也可以是无限个. ②各局中人在自己的策略集中, 选取一个策略 进行对策, 所组成的策略组称为局势. 如“齐王赛马”中齐王采用策略(上,中,下), 田 忌采用策略 (下,上,中)就组成了比赛双方的一个局 势. 3.赢得(winning)与赢得函数(winning function): 当每个局中人确定了所采取的策略后, 他们所获得 相应的收益或损失值称为赢得(支付). 赢得与策略之间的对应关系, 称为赢得函数或 支付矩阵 (payoff matrix). 换句话说, 局中人的得失 是局势的函数.对策的大致分类： 静态对策 结 盟对 策 动态对策 不结盟局中人两 人 对 策 多 人 对 策结 局 零 和 对 策非 零 和 对 策策 纯 策 略 对 策混 合 对 策略 有 限 对 策无 限 对 策赢得函数矩 阵 对 策 非 矩 阵 对 策三.博弈（对策）的基本分类（一）合作博弈和非合作博弈 1.合作博弈：如果各博弈方能达成某种 有约束力的契约 或协议（包括默契）以使他们选择共同的或 联合的策略。 2.非合作博弈：反之，就属于非合作博 弈。（二）单人博弈、双人博弈和多人博弈 （三）有限策略博弈和无限策略博弈 （四）零和博弈、常和博弈与变和博弈1.零和博弈：是指在博弈中，一方的得益就是另一方的损 失，所有博弈方的得益总和为零。 2.常和博弈：是指所有博弈方的得益总和为非零的常数。 3.变和博弈：也称非常和博弈,它意味着不同的策略组合 或结果下各博弈方的得益之和一般是不相同的。（五）静态博弈和动态博弈1.静态博弈：是指所有博弈方同时或可看作同时选择策 略、采取行动的博弈。 2.动态博弈：是指博弈方的选择、行动有先有后，而且后 选择、后行动的博弈方在自己进行选择、行动之前可以看在 他之前选择、行动的博弈方的选择、行动的博弈。（六）完全信息博弈和不完全信息博弈1.完全信息博弈：是指每一参与者都拥有所有其他参 与者的特征、策略集及得益函数等方面的准确信息的博弈。 2.不完全信息博弈：是指参与者只了解上述信息中的 一部分的博弈。 将博弈的信息特征和行为时间特征结合起来，可以进一 步把博弈细分为下面四种类型的非合作博弈，得到四种均衡：信息特征静态 行动先后顺序 动态完全信息 完全信息静态博弈 纳什均衡 完全信息动态博弈 子博弈精炼纳什均衡不完全信息 不完全信息静态博弈 贝叶斯纳什均衡 不完全信息动态博弈 精炼贝叶斯纳什均衡四种博弈及其相应的均衡趣例智猪博弈（boxed pig game）假设猪圈里有一大一小两头猪，猪圈的一头有一个猪食 槽，另一头有一个按钮，控制着猪食的供应。揿一下按钮就 会有10个单位的猪食进槽，供猪食用，但谁揿按钮谁就得付 出2个单位的效用成本。 如果大猪与小猪同时去揿按钮，大猪吃到7个单位的猪食 （扣去2个单位的效用成本，剩下的效用单位为5，显然这里 假设1个单位的猪食提供1个单位的效用），小猪吃到3个单位 的猪食（扣去2个单位的效用成本，剩下的效用单位为1）； 如果大猪去揿按钮,小猪等待，大猪吃到6个单位的猪食（扣去 2个单位的效用成本，剩下的效用单位为4），小猪吃到4个单 位的猪食；如果小猪去揿按钮，等奔过来后只能吃到1个单位 的猪食（扣去成本，得到的效用为-1），先吃的大猪则可吃到 9个单位猪食，即得到9个单位的效用；当然，如果都不去揿 按钮，原地等待，则无猪食进槽，得到的效用均为0。智猪博弈在这个案例中，不论大猪选择“揿”还是“等待”，小 猪的最优选择都是“等待”，在预期小猪“等待”的前提下，大猪的最优策略便是“揿”。也就是说，这个案例的纳什均衡便是图中右上角表示的策略组合及其效用组合：大猪“揿”、 小猪“等待”。从而多劳者不多得。智猪博弈常被用来说明“搭便车”的情形。如大股东 花费大量的时间与精力等监督股份公司的管理层，小股东 搭便车，不去实施监督，却享受大股东的监督带来的利益。 还有富人修路，穷人走修好的路等也是如此。在改革过程中，不同群体的积极性，主动性也是不一样的，从某种意义上说，改革中要注意创造出尽可能多的“大猪”，减少 不劳而获的“小猪”。7.2 两人有限零和对策 7.2.1 两人有限零和对策的数学模型 因为两人有限零和对策是最基本, 最简单的 一类对策,在理论和方法上比较成熟.同时,它又是 研究其它对策模型的基础. 所以我们主要介绍两 人有限零和对策,其次简介两人有限非零和对策. 两人有限零和对策:局中人仅有两个,且各自 只有有限个策略可供选择,同时在任一局势下,两 个局中人的赢得之和为零, 即一局中人的所得等 于另一局中人的所失. 由于赢得函数可用一个矩阵表示, 因而两人 有限零和对策亦称矩阵对策.两人有限零和对策的数学模型 一般地,设两个局中人为Ⅰ、Ⅱ, 且局中人Ⅰ 有m个纯策略?1, ? 2 ,…, ? m ,局中人Ⅱ有n个纯策 略? 1, ? 2,…, ? n, 则局中人Ⅰ, Ⅱ的策略集分别记 为： SⅠ={?1, ?2, …, ?m }， SⅡ={?1, ?2 , … , ?n }． 当局中人Ⅰ,Ⅱ分别采用纯策略?i ,和?j时,就形成 一个局势{?i , ?j }, 设局中人Ⅰ在该局势下的赢得 为aij (其中i=1,2,…,m; j=1,2,…,n), 则局中人Ⅰ的 赢得矩阵为：A=(aij)m×n .? a11 ? ? a21 A=(aij)m×n = ? ... ? ?a ? m1a12 a22 ... am 2... a1n ? ? ... a2 n ? ... ... ? ? ... amn ? ?记两人有限零和对策的数学模型为： Γ={Ⅰ,Ⅱ; SI, SⅡ; A} 或简记为： Γ={ SI, SⅡ; A} 注意:局中人Ⅱ的赢得矩阵是－A .7.2.2 在纯策略下有解对策的解法 下面通过对例1的分析, 说明在纯策略下有 解对策的求解方法及有解的条件. 例1 当对策双方采取不同的方案后甲厂的 市场占有份额(百分比)变动情况如下表所示:甲厂乙厂?110 12 6?2－1 10 8?33 －5 5?1 ?2 ?3这是一个两人有限零和对策，其数学模型为 Γ={ S甲, S乙；A }， 其中, S甲={?1, ?2, ?3}, S乙={?1, ?2, ?3},?10 ? 1 3 ? ? ? 甲厂的赢得矩阵 A= ?12 10 ? 5 ? ?6 8 5 ? ? ? 求解思路: 由于对策双方都不知道对方将采 用的纯策略, 因此各局中人在不冒风险(理性)的 前提下,必须考虑对方会设法使自己的赢得最少. 即在各纯策略出现对己方最坏的情况下, 寻求最 好的结果.?10 ? 1 3 ? ? ? A= ?12 10 ? 5 ? ?6 8 5 ? ? ? 从甲厂的角度考虑,对于分别采用?1, ?2, ?3 三个纯策略的最小赢得(即最坏情况)分别为： ? 1: min｛10, －l, 3｝ = －l， ? 2: min｛12, 10, －5｝= －5， ? 3: min｛6，8，5 ｝ = 5, 因为 max｛－1,－5, 5｝ = 5. 所以甲厂在不冒风险的前提下, 选择策略 ? 3,可至少增加市场份额5％．?10 ? 1 3 ? ? ? A= ?12 10 ? 5 ? ?6 8 5 ? ? ? 从乙厂的角度考虑,对于分别采用?1, ?2, ?3, 三个纯策略的最大损失是： ?1: max｛10, 12, 6｝= 12， ?2: max｛－1, 10, 8｝= 10， ?3: max｛3, －5, 5｝= 5, 因为 min ｛12, 10, 5｝= 5. 所以乙厂在不冒风险的前提下, 选择策略 ? 3,至多减少市场占有份额的5％.?10 ? 1 3 ? ? ? A= ?12 10 ? 5 ? ?6 8 5 ? ? ? 对例l的求解过程可简单地表述如下：第一步, 确定A各行中的最小值,并加圈； 第二步, 确定A各列中的最大值,并加框； 第三步, 若A中的某元素同时被圈、框住, 则该元素即为所求对策的值.该元素所在的行 和列相应的策略,分别为局中人Ⅰ和Ⅱ的最优 纯策略(?3 , ?3).在纯策略下有解对策的解法 一般地, 我们设对策Γ={SI，SⅡ；A},其中 SI = {?1, ?2 , …, ?m }, SⅡ= {?1, ?2 , …, ?n }, A = (aij)m×n 若等式 (7.1) max min aij= min max aij=ai*j*ij ji成立,则称ai*j*为对策Γ的值(鞍点),记为VΓ= ai*j* . 称使(7.1)式成立的纯局势 (?i* , ?j*)为对策Γ 在纯策略下的解(或均衡局势). ?i* 和?j* 分别为局 中人Ⅰ和Ⅱ的最优纯策略.注意: ① 竞争双方都以使自己的损失为最小的原 则,来选择策略;即立足于不利的情况下争取最好 的结果, 这就是所谓的最大最小原则． ② 根据最大最小原则求出的策略, 对双方来 说都是最稳妥的, 任何一方在此时想改变其策略, 都将使自己的损失更大． ③ 在纯策略下有解的矩阵对策值ai*j*,既是所 在行的最小值,又是所在列的最大值.这类矩阵对 策亦称为有鞍点的对策.定理1 在纯策略下矩阵对策Γ={ SI, SⅡ;A} 有解的充要条件是: 存在纯局势 (?i* , ?j* )使得对 于一切 i = 1, 2, … , m, j = 1, 2, … , n，均有 aij*≤ai*j*≤a i*j (7.2) 证明：充分性 对任意i, j均有 aij*≤ai*j*≤ai*j 即 max aij*≤ai*j*≤ min ai*j j i 而 min max aij≤ max aij*j jiimin ai*j≤ max min aijij∴ min max aij ≤ai*j*≤jimax min aij (7.3)ij另设 max min aij = alk j iijmin max aij = al*k*ji当 l=l* 或 k=k* 时 max min aij = alk≤al*k* = min max aij j i 当 l≠l* 且 k≠k* 时 max min aij = alk≤alk*≤al*k* =ij j(7.4)min max aij (7.5)i综合（7.4）（7.5）式得 max min aij ≤ min max aijij j(7.6) (7.1) 充分性得证.i∴由（7.3）（7.6）式得 max min aij=min max aij = ai*j*ij ji现证必要性 ∵ 在纯策略下矩阵对策Γ={ SI, SⅡ;A}有解， ∴ max min aij= min max aij=ai*j* (7.1)ij ji设i*, j*使min ai*j ＝ max min aij j j i max aij*＝ min max aijiji则由（5.1）式得 ∴ maxaij*＝ min ai*j = ai*j* j i a 而 aij*≤ max ij*＝minai*j ≤ ai*jij显然 aij*≤ai*j*≤ai*j必要性得证例4 求矩阵对策Γ= { SI，SⅡ；A}的解和值, 其中SⅠ={?1, ?2, ?3, ?4}, SⅡ ={?1, ?2, ?3, ?4},赢得 矩阵?6 ? ?5 A= ?0 ? ?8 ? 4 4 2 3 5 4? ? 6 4? 7 3? ? 2 ?1? ?解：A=?6 ? ?5 ?0 ? ?8 ?4 4 2 35 4? ? 6 4? ? 7 3 ? ? 2 ?1?对策的解为 (?1, ?2), (?1, ?4), (?2, ?2)和(?2, ?4). 对策的值为VΓ = 4.此例说明,矩阵对策的解可以不唯一,当解不唯一时,解之间的关系具有以下性质：(1)无差别性即若(?i , ?j )和(?k , ?l )是对策Γ的两个解, 则有aij = akl .(2)可交换性即若(?i , ?j )和(?k , ?l )是对策Γ的两个解, 则 (?i , ?l )和(?k , ?j )也是对策Γ的两个解.7.2.3 具有混合策略的对策上面讨论的是在纯策略下有解的对策, 但 一般情况下, 等式max min aij = min max aij = ai*j* j j i i 未必成立.(7.1)例如“齐王赛马”对策就不存在纯策略意 义下的解,此时 min aij = －1≠ min max aij = 3. maxij ji因此,必须把解的意义扩充.例5 设一对策的赢得矩阵为由于 max min aij = 7≠ min max a ij = 8 j j i i所以,该对策在纯策略意义下无解.分析: 此时,双方用最大最小原则选取各自的纯策 略都不会是稳妥的,对策的双方都无法稳定在某一纯策 略上. 既然各局中人都没有最优纯策略可出,即没有稳定 的解,那么是否可以给出一个选取不同策略的概率分布 来解决此问题呢？ 因此，必须考虑随机地选取自己的各个策略,使对 方无法确定自己选用的纯策略．?9 7? ? ?2 8? ? ? ?为此,我们引入混合策略概念． 设局中人Ⅰ选用纯策略?1和?2的概率分别 为x1和x2, 且x1≥0, x2≥0，x1+ x2=1； 局中人Ⅱ选用纯策略?1和?2的概率分别为y1 和y2且y1≥0，y2≥0，y1+ y2=1. 此时二维向量X= (x1, x2)和Y= (y1, y2)分别表 示两局中人进行对策时的一套策略(即混合策略). 当x1, x2, y1,y2的值确定后,局中人I赢得的数 学期望可由下式确定: E(X, Y) =∑∑aij xi yj定义 一般地,设给定Γ={ SI，SⅡ；A},令 X= (x1, x2,…, xm)，Y=( y1, y2,…, yn) SI* = { X | X≥0, ∑xi = 1}, SⅡ*= { Y | Y≥0, ∑yj = 1}, 分别称SI*, SⅡ*为局中人Ⅰ和Ⅱ的混合策略 集,简称策略集; 称X∈SI*,Y∈SⅡ* 分别为局中人 Ⅰ和Ⅱ的混合策略,简称策略. 当X∈SI* ,Y∈SⅡ* 时称(X,Y)为混合局势. 局中人Ⅰ在混合策略下赢得的数学期望为 m n E(X,Y) = ?? aij xi y j = XAYT i ?1 j ?1 称Γ*={ SI*, SⅡ*; E }为原对策Γ的混合扩充.类似于纯策略下的情况，若以下等式成立,Y ?S II X ?S I X ?S I Y ?S II 则称E(X *,Y *)为对策Γ的值;(X *,Y *)为对策Γ在混max min E ? X , Y ? ? min max E ? X , Y ? ? E X , Y * * * **?*?合策略下的解(简称解); X *和Y *分别为局中人Ⅰ 和Ⅱ的最优混合策略(简称最优策略). 注意: ①混合策略X表示局中人Ⅰ以概率xi选 用纯策略?i , Y表示局中人Ⅱ以概率yj 选用纯策略 ?j ；E(X, Y)表示局中人I 的平均赢得. ②纯策略下的解(?i* , ?j*),可看作混合策略下 的特例. 只需将X中取 xi =1, 其他分量为0;Y中取yi =1, 其他分量为0即可.现以例5说明以上概念 解 设X=(x,1－x), Y=(y,1－y) 则 E(X, Y) = XAYT ?9 7? = (x,1－x)? (y,1－y)T ? = 8xy－x－6y+8 用微分求极值的方法,令 ?E/?x = 8y －1= 0 得y=1/8 ?E/?y = 8x －6= 0 得x=3/4 即 x*=(3/4,1/4) , y*=(1/8,7/8)?2 8? ? ?E( X, Y ) = 8xy －x －6y + 8 x*= (3/4 , 1/4), y*= (1/8 , 7/8) E(X*,Y ) = 8×3÷4×y－3/4－6y＋8=7.25, E(X,Y* ) = 8x×1/8－x－6×1/8＋8=7.25, E(X*,Y*) = 8×3÷4×1/8－3/4－6×1/8＋8=7.25. 所以局中人I和局中人Ⅱ的最优混合策略分 别是： X*=(3/4, 1/4), Y*= (1/8, 7/8) ; 对策的值： VΓ=7.25 . 注意: 局中人I的期望赢得, 并不是说他每采 取一纯策略就能得到此数,而是在概率意义下,经 过相当次数的竞争之后所得的平均值．定理2 (对策基本定理)在混合扩充中,任何矩 阵对策都有解．定理3 设Γ={ SI，SⅡ；A}, X*∈SI*, Y*∈SII*, 则(X*, Y*)为对策解的充要条件是 E(X, Y*)≤E(X*, Y*)≤E(X*, Y) (7.7) 注意:定理3的直观意义是,无论局中人I或II, 谁不采用最优策略,谁就有可能受到不应有的损 失. 如果一个策略(X*，Y*)具有以上性质,则它就 是对策的解.例6 设一矩阵对策的赢得矩阵为 ?9 8 7? ? ? ?2 6 8? ? 4 5 6? ? ? 解 可以验证局中人I和II最优策略分别是: X*=(3/4, 1/4, 0)和Y*=(1/8, 0, 7/8) VΓ= X*AY*T ?9 8 7? ? ? = (3/4, 1/4, 0) ? 2 6 8 ? (1/8, 0, 7/8)T=7.25? 4 5 6? ? ?若局中人I不采用最优策略X*,而用混合策略X=(1/3, 1/3, 1/3),则只要局中人Ⅱ用最优策略Y*, 则有?9 8 7? ? ? *)=(1/3,1/3,1/3) 2 6 8 (1/8, 0, 7/8)T E(X, Y ? ? ? 4 5 6? ? ?= 6.75＜7.25= VΓ 可见局中人I若不采用最优策略X*, 有可能 受到不应有的损失.同样对局中人Ⅱ也有类似结 论．定理4 设Γ={ SI，SⅡ；A}, X*∈SI*,Y*∈SII*, 则(X*, Y*)为对策解的充要条件是E(?i , Y*)≤E(X*, Y*)≤E(X*, ?j )(7.8)对于一切的i, j(i =1, 2, …, j =1, 2, …, n)均成立 .证 必要性 ∵ X*, Y*为对策的解 ∴ E(X, Y*) ≤ E(X*, Y* ) ≤ E(X*, Y ) 取混合策略X中的xi = 1,其余分量为0,则由 (5.3)得 E(?i , Y*) = E(X, Y*) ≤ E(X*, Y*) (7.9)类似地有 E(X*, Y* ) ≤ E(X*, ?j ) (7.10) 综合(1), (2)式得 ∴ E(?i , Y*)≤E(X*, Y*)≤E(X*, ?j) (7.11) 必要性得证. 充分性 设E(?i , Y*)≤E(X*, Y*)≤E(X*, ?j)，又 设ei为m维单位向量, 即其中第i个分量为1,其余分 量为0, 则 E(?i , Y*)=ei AY*T，X=∑xi ei E(X, Y*) =XAY*T= (∑xi ei) AY*T=∑(ei AY*T ) xi =∑E(?i , Y*) xi又因xi≥0，由(7.9)式有 xi E(?i , Y*) ≤ E(X*, Y*) xi E(X, Y*) =∑xi E(?i , Y*) ≤∑E(X*, Y*) xi = E(X*, Y*) ∑xi = E(X*, Y*) 同理，由(7.4)式可得 E(X, Y*)≥E(X*, Y*) 综上所述，有 E(X,Y*) ≤ E(X*,Y*) ≤ E(X*,Y) 充分性得证 所以为应用方便，我们给出定理4的等价形式： 定理5 设X*∈SI*，Y*∈SII*,则(X*,Y*)作为 对策的解的充要条件是：存在数v，使得X*和 Y*分别是以下不等式组? ? aij xi ≥v ( j = 1, … , n ), ? i ?1 ? m ? x ? 1, ?? i i ?1 ? x ≥0 ( i = 1, … , m ). ? i的解，且v =VΓ .m? ? aij y j≤v ( i = 1, … , m ), ? j ?1 ? n ? y ? 1, ?? j j ?1 ? y ≥0 ( j = 1, … , n ). ? jn现以例2“齐王赛马”为例,设齐王的赢得矩阵为:? 3 1 1 1 1 ? 1? ? ? 3 1 1 ?1 1 ? ?1 ? 1 ?1 3 1 1 1 ? ? ? 3 1 1? ? ?1 1 1 ? 1 1 ?1 1 ? 3 1? ? ? 1 1 1 ?1 1 ? 3? ?解 由定理5可知，有下列两组不等式组? ? ? ? ? ? ?3y1+y2+y3-y4+y5+y6≤v 3x1+x2+x3-x4+x5+x6≥v y1+3y2-y3+y4+y5+y6≤v x1+3x2-x3+x4+x5+x6≥v y1+y2+3y3+y4-y5+y6≤v x1+x2+3x3+x4-x5+x6≥v y1+y2+y3+3y4+y5-y6≤v x1+x2+x3+3x4+x5-x6≥v y1-y2+y3+y4+3y5+y6≤v x1-x2+x3+x4+3x5+x6≥v -x1+x2+x3+x4+x5+3x6≥v -y1+y2+y3+y4+y5+3y6≤v y1+y2+y3+y4+y5+y6 =1 x1+x2+x3+x4+x5+x6 =1 yj≥0 (j=1,2,…,6) xi≥0 (i=1,2,…,6)? ? ? ? ? ? ?因为矩阵A的各行、各列之和均为6,所以可 认为每个局中人以等可能性选取各自的纯策略. 将以上两不等式组均取等式并分别相加得: 6(x1+x2+x3+x4+x5+x6)=6v， 6(y1+ y2+y3+y4+y5+y6 )=6v， ∑xi=1 ， ∑yj=1. 所以 v=1 齐王和田忌的最优策略分别为： X*=(1/6,1/6,1/6,1/6,1/6,1/6) Y*=(1/6,1/6,1/6,1/6,1/6,1/6) VΓ=17.3 两人有限零和对策的一般解法 对于有鞍点的矩阵对策, 可用最大最小原则 进行求解.对于无鞍点的矩阵对策,可在混合扩充 后,分别用以下方法,求出其最优混合策略或近似 最优混合策略． 7.3.1线性规划法 由定理5得任一矩阵对策Γ = { SI，SII；A}的 解, X*= (x1*, x2*, …, xm*) , Y*= ( y1*, y2*,…, yn* )应 是下述不等式组的解：? ? aij xi ≥v ( j = 1, … , n ), ? i ?1 ? m ? x ? 1, ?? i i ?1 ? x ≥0 ( i = 1, … , m ). ? imm? ? aij y j≤v ( i = 1, … , m ), ? j ?1 ? n ? y ? 1, ?? j j ?1 ? y ≥0 ( j = 1, … , n ). ? jij in其中v=VΓ= max min *xi ?S I 1? j ? n?a xi ?1? min* max ? aij y jy j ?S II 1?i ? m j ?1n设v≥0,作变换 xi′= xi /v ( i = 1, … , m ), yj′= yj /v ( j = 1, … , n ). 上述不等式组等价于互为对偶线性规划问题:? ? a x?≥1 ( j = 1, … , n ), ? ? x ' ≥0 ( i = 1, … , m ).mi ?1min Z ? ? xi?i ?1 ij imi? ? a y?≥1 (i = 1, … , m ), ? ? y ' ≥0 ( j = 1, … , n ).nj ?1max W ? ? y?jj ?1 ij jnj(P)(D)这样就使得局中人I的期望赢得值v = 1/Z 达到最大，局中人Ⅱ的期望损失值v=1/W达到 最小. 由于(P)、(D)是互为对偶问题，因此，可 采用单纯形法求解问题(P)和(D)中的一个，而 另一个的解即可从最终单纯形表中同时得到.注意: 在未求解(P)和(D)之前,VΓ的正负是未知的. 如果局中人I的赢得矩阵A=(aij)m×n中所有元 素均为正值, 则必有v&0,此时建立的线性规划模 型(P)和(D)可以求解, 且其解X' =(x1', x2', … , xm' ), Y' = ( y1', y2' ，…，yn' )均为非负. 但当A中的某些aij为负值时，则有出现v≤0的 可能. 因此xi和yj可能为负值或无意义,这与单纯形 法要求模型中的变量非负相矛盾. 为此,当A中含有负元素时,可根据下述的定 理6进行处理.定理6 设有两个矩阵对策 Γ = {S1, S2; A }, Γ′ = {S1, S2; A′}, 其中A= (aij) m×n , A′= (aij + d ) m×n , d为常数. 则对 策Γ和Γ′有相同的最优混合策略解, 且V′= V+ d, 这里V和V′分别是Γ和Γ′的对策值.用线性规划法求解矩阵对策的具体步骤如下： 第一步, 选择适当的常数d, 使A′ = (aij + d ) 的各元素均为非负.第二步, 对A' 建立相应的线性规划模型 (P) 和 (D), 用单纯形法求解 (D), 分别得最优解X'= (x1', x2', … , xm' ) 和Y'= ( y1', y2', … , yn' ). 第三步, 由v‘ = 1/W W=∑yj′和v = v‘- d及X*= vX ', Y*= v'Y '求得对策的值VΓ = v和局中人Ⅰ,Ⅱ 的最优混合策略X*, Y*. 上述方法也可以用来求解有鞍点的矩阵对策 当然，对于赢得矩阵比较特殊的矩阵对策，用定 理3, 4, 5求解比较方便.7.3.2例 ：设矩阵对策的求解例题且无鞍点，混合策略的各分量不为零，求最优混合策略. 解:7.3.2矩阵对策的求解例题（续）方法：降低矩阵阶数求解若所给矩阵中I行的各个元素比j行各元素小，则对局中人1来说策略i明 显不如策略j,称纯策略 j 优超纯策略 j ，同理，若 i 列的元素比 j 列的 对应元素大，则对局中人2来说策略 j 优超策略 i 。而明显不利策略出现 的概率为零。 例 ：给定一个矩阵对策G={S1,S2,A},求对策G的值与解。其中：7.3.2矩阵对策的求解例题（续）方法： 化简矩阵，使矩阵的元素尽可能多地变成零.定 理 ： 设 两 个 矩 阵 对 策 ： G1=(S1,S2,A), G2=(S1,S2,B), 其 中A=(aij)mxn, B=(bij)mxn,若bij= aij+d,其中d为一常数。则G1和G2有相同的混合策略，且V2=V1+d。（V1和V2分别为G1和G2的对策值）7.3.2矩阵对策的求解例题（续）化简矩阵，使矩阵的元素尽可能多地变成零.例 ：给定一个矩阵对策G={S1,S2,A},求对策G的值与解。其中：解：1）直接解：7.3.2矩阵对策的求解例题（续）解：2) 阵中各元素加1，得：方法： 线性规划法求解对于扩充后的矩阵对策来说，求最优解就是解下列两个不等式组：其中：令:方法： 线性规划法求解 （续）即求线性规划：例 ：给定一个矩阵对策G={S1,S2,A}, 求对策G的值与解。其中：解：因=1/V，所以V=3,又因， 得：7.4 矩阵对策的混合策略-优超原则? 优超原则： 假设矩阵对策 G ={ S1,S2,A } 甲方赢得矩阵 A=[aij]m?n-- 若存在两行（列），s 行（列）的各元素均 优于 t 行（列）的元素，即 asj?atj j=1,2…n ( ais ? ait i=1,2…m ) 称甲方策略?s优超于?t ( ?s优超于?t)7.4 优超原则（续）-- 优超原则：当局中人甲方的策略 ?t 被其它策 略所优超时，可在其赢得矩阵A中划去第 t 行 （同理，当局中人乙方的策略?t 被其它策略 所优超时，可在矩阵A中划去第 t 列）。 如此得到阶数较小的赢得矩阵A’，其对应的矩阵对策G’= { S1,S2,A’}与 G ={ S1,S2,A } 等价，即解相同。7.4 优超原则（续）? 例 设甲方的益损值 赢得矩阵。3 5 7 4 6 2 0 3 6 0 0 2 9 8 8 3 5 5 7 8 0 9 9 5.5 3被第3、4行所优超被第3行所优超A=得到 A1=7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3被第1列所优超被第2列所优超7.4 优超原则（续）? 续例A2=得到7 3 9 4 6 5.5 6 0 3 被第1行所优超7 3 9被第1列所优超得到A3=4 6 5.57 3 最终得到 A4= 4 67.4 优超原则（续）? 对A4计算，用线性规划方法得到： （注意：余下的策略为?3，?4，?1，?2） 甲： X* = (0，0，1/15，2/15，0)T V=5 X*’= (0，0，1/3 ，2/3 ，0)T 乙： Y* = (1/10，1/10，0，0，0)T V=5 Y*’= (1/2 ，1/2 ，0，0，0)T ? 注：C 利用有超原则化简赢得矩阵时，有可能将原对策 问题的解也划去一些（多解情况）； C 线性规划求解时有可能是多解问题。7.5 两人有限非零和对策以上介绍的是两人有限零和对策，对策的双 方利益完全相反，一方所得为另一方所失。 但在现实生活的对策过程中，经常会出现一 个局中人的所得并不一定等于另一局中人的所失. 对于每一局势，两局中人的赢得之和不一定为零， 这就是两人非零和对策。 许多经济活动中的对策模型，经常为非零和 对策。本节简介两人有限非零和对策的数学模型 及其解法。（见例3）例 “囚徒困境”: 在西方某国, 一次严重的纵火案 发生后, 警方抓到两个犯罪嫌疑人 (事实上正是他们为了 报复,一起放火烧了这个仓库),但又缺乏足够的证据证明. 于是,警方把他们隔离起来,要求坦白交代. 如果他们都承 认纵火,每人将入狱三年;如果他们都不坦白, 由于证据不 足, 每人将只入狱一年 ; 如果一个抵赖而另一个坦白并 且愿意作证, 那么抵赖者将入狱五年,而坦白者将得到释 放,免予刑事处罚.这样,两个囚徒面临的博弈格局如下表 所示:乙 甲 坦 白 抵 赖坦 白 -3 -3 -5 0抵 赖 0 -5 -1 -1?? 3 0 ? ? ? ? 5 ? 1? ? 在各列的最大值下画横线得 ? ?甲的赢得矩阵为 乙的赢得矩阵为在各行的最大值下画横线得? ? 3 ? 5? ? ? 0 ?1? ? ? ?? ?? 3 ? 3? ? 综合得 ? ?? 5 0? ? 对策双方的稳定解为(?1 , ?1 )对策的值为(－3 , －3 )?0 ?? 1? 5? ? ? ? 1?? ?7.5.1 两人有限非零和对策的数学模型一般地，我们设两人有限非零和对策的数学 模型为Γ= { SI，SⅡ；（Ａ，Ｂ）}, 其中 SI = {?1, ?2 , …, ?m }, SⅡ= {?1, ?2 , …, ?n }, A = (aij )m×n ， B = (bij )m×n （Ａ，Ｂ）= (aij , bij )m×n 一般A+B≠0。 注意：两人有限非零和对策又称为双矩阵对 策。当B = －A时，双矩阵对策就是矩阵对策。 矩阵对策是双矩阵对策的一种特殊情况。7.5.2 非合作两人对策的解法 假定在两人有限非零和对策中，彼此了解对 方的纯策略集和赢得函数，但不合作，并且局中 人在选择自己策略时不知道对方的选择。 （1）非合作两人对策的解――纳什均衡 由例3可得，对策双方的选择都应稳定在局势 (?1 , ?1 )上，从而达到一种均衡。我们把这种均衡 局势称为纳什均衡，即非合作两人对策的解。 一般地，对于非合作两人对策 Γ= { SI，SⅡ；（Ａ，Ｂ）}, 如果?i∈ＳⅠ, ?ｊ∈ＳⅡ分别是局中人Ⅰ和Ⅱ的最 优纯策略，则称局势(?i , ?j )是一个纳什均衡。求非合作两人对策的解，就是求对策的纳什 均衡，求纳什均衡的方法步骤如下： 第一步：在双矩阵对策（Ａ，Ｂ）表中，对 于矩阵Ａ的每列，分别找出赢得最大值，并在其 下划一横线； 第二步：在双矩阵对策（Ａ，Ｂ）表中，对 于矩阵Ｂ的每行，分别找出赢得最大值，并在其 下划一横线； 第三步：如果表中某格的两个数字下面都被 划有横线，则此格对应于两个局中人相应策略的 组合就是一个（纯策略下的）纳什均衡，否则， 该对策不存在纯策略下的纳什均衡。例： 美苏争霸的囚徒困境 军备竞赛是囚徒困境的又一个典型例子.下面 讲的,源自30年前美国的博弈论课本. 从军事上看,二三十年前美国和前苏联是世界 上的两个超级大国.假定双放都有两种策略选择: 1、扩军,发展战略核武器,实施”星球大战” 计划等; 2、彻底裁军,直至不设军备. 如果双方都扩军,则各花费2000亿美元. 如果双方都彻底裁军,则各自军费为零. 如果一方裁军,另一方扩军,则裁军方的“赢利” 记做－∞；扩军方的“赢利”记做8000亿美元. 双方争霸博弈矩阵如下：美扩裁苏军军扩 －∞军裁军－2000 －200080008000 －∞00? ?? 2000 ? 2000? ? ? ?? ? 8000? ??8000 ? ? ?? ? ? ?0 0? ?对策双方的稳定解为(?1 , ?1 ) 对策的值为(－2000, －2000 )例： 为“和平与发展”作博弈论论证 1984年前后，军委主席邓小平同志主持决策 中国人民解放军百万大裁军。现从博弈论的角度 为百万裁军作论证。 为了讨论简单起见，我们暂时仍限于“二人” 博弈，但是，假设博弈双方都有三个可供选择的 策略：一个是成本为2000亿美元的扩军策略，一 个是预算为0的不设防策略，另一个是成本为500 亿美元的“有限军备”策略。 结合上一节的分析，我们就可以写出新的军 备竞赛博弈格局（见下图）：－2000 －2000 －1600 －1500 －1500 －1600 －500 －500 －∞ －9500 －∞ 80008000 －∞ 9500 －∞ 0 0由优超法得：把左扩军右不设防两列劣势策略 消去再把上扩军下不设防两行劣势策略消去。 则该博弈的纳什均衡是双方都采取有限军备策 略。 对策双方的稳定解为(? , ? )2 2对策的值为(－500, －500 )邓小平同志最早洞察到该博弈有三个 策略可供选择。且不论对方怎样选择，有 限军备才是我们的最优策略，所以果断做 出了百万大裁军的战略决策。通过这个模 型的分析，我们可以发现博弈论的重要性。 而不同的模型会导致不同的结论，关键是 看谁的模型更符合实际。例： 如何让禁鸣喇叭成为交通顺畅的开始 我国一些城市噪音污染十分厉害,城市的噪音 主要来源是由机动车的马达和喇叭产生.马达噪音 由几百万辆机动车的先天质量决定,马上治理难度 很大,且成本也负担不起, 而鸣笛却可以先治. 因为 实施成本不大，这项制度有很好的可行性。 在国外除了路考驾照时, 按考官的指令按响喇 叭说明车况良好以外, 还真没有多少其他按喇叭的 纪录. 其原因是行人、车辆都很守规矩，没有按喇 叭的必要. 其次, 无缘无故按喇叭, 就像开会或听课 时晃腿一样,会被认为是没教养的表现.在这样的环 境里一方面没必要,另一方面行为不“上等”,自然 就很少发生乱按喇叭的事情。和国外相比，我们的行人和车辆都不太遵守 规矩或不守规矩, 随之而来的就是人们缺乏礼让 意识. 谁礼让谁吃亏的现实, 使我们的“交通博弈” 陷入了囚徒困境（见下图）。 车 人 礼 让 强 行 礼 让 8 8 9 1 强 行 1 9 2 2在这个“交通博弈”中，礼让是劣势策略，抢 行是优势策略。运用优势策略消去法，可以知道 博弈的结局是大家都抢行，大家都只得2。这样 我们的“交通博弈”就被锁定在大家都争抢，大 家都吃亏的“双输对局”（2，2）的位置上。禁鸣喇叭最后是否能够真正把交通博弈引导 到规矩礼让, 大家受益的“双赢对局” (8，8)上, 要看行人和自行车是否能够做出回应。若行人和 自行车不能自觉回应，那就应该处罚，让那个9至 少降到7甚至更低, 才能达到相互礼让各自得8的纳 什均衡，从而达到交通顺畅的目标。 若有一个梦想：大家都认识到抢行是没教养 的“不上等”行为，为道义把9降到7甚至更低， 实现车辆和行人、自行车双赢的前景(见下图): 车 人 礼 让 强 行 礼 让 8 8 7 3 强 行 3 7 2 2（2） 混合策略纳什均衡 上面介绍了在纯策略下非合作两人对策纳 什均衡的概念及其求解方法。但有些对策不存 在纯策略下的纳什均衡，如下例： 例： 局中人是流浪汉和政府，流浪汉有两 个策略：寻找工作或游荡；政府也有两个策略： 救济或不救济。政府帮助流浪汉的前提是后者 必须试图寻找工作，否则不予帮助；而流浪汉 只在得不到救济时才会寻找工作。 下表给出了对策双方的赢得双矩阵：流浪汉 政府 救 济找工作 3， 2游 荡 －1，3不救济－1，10， 0容易理解：当给定政府策略为救济时，流浪汉的最优 策略是游荡； 当给定政府策略为不救济时，流浪汉的最优策略是寻 找工作； 当流浪汉选定寻找工作策略时，政府的最优策略是救 济； 当流浪者选定游荡策略时，政府最优策略是不救济。 总之，在纯策略下，没有一个策略组合构成纳什均衡。 但是，此对策却存在混合纳什均衡。定义 一般地,设局中人Ⅰ，Ⅱ的混合策略集 Γ={ SI *，SⅡ *；(A, B ) }, 其中A m×n ，B m×n分别为局中人Ⅰ和Ⅱ的赢 得矩阵， SI* = { X | X≥0, ∑xi = 1}, i=1…n SⅡ* = { Y | Y≥0, ∑yj = 1}, j=1…m 如果一个混合策略组合（X*，Y*）同时满足 XAY*T≤X*AY*T，X*BY T≤X* BY*T， 则称局势（X*，Y*）是一个混合策略纳什均衡， 其中X，Y分别是居中人Ⅰ，Ⅱ的任意混合策略。 现在根据上述定义求解例6的混合策略纳什均 衡的解假定政府以概率x选择救济，概率1－x选择不 救济，即政府的混合策略为（x，1－x）， 流浪汉以概率y选择找工作，以概率1－y选择 游荡，即流浪汉混合策略为（y，1－y）。 那么政府的期望赢得函数为 EA（X，Y）=XAYT =（x，1－x）A（ y，1－y ） =5 x y－ x－y. 用微分求极值的方法，得y*=1/5 这就是说，在混合策略均衡中，流浪汉在对 给定的政府混合策略下，其最优策略是以1/5的概 率选择寻找工作，4/5的概率选择游荡.即Y*=（1/5，4/5）. 同样，流浪汉的期望赢得函数为 EB(X,Y)=XBYT=(x，1-x)B(y，1－y )T =－2 xy + 3x+ y. 用微分求极值的方法，得 在混合策略均衡中，政府在其对给定流浪汉 的混合策略下，最优策略X*=（1/2，1/2） 由于纳什均衡要求每个局中人的混合策略是 在给定的混合策略下的最优选择，因此， X*= （1/2，1/2）, Y*=（1/5，4/5） 构成的（X*，Y*）是唯一的纳什均衡。对于上述的混合策略纳什均衡，还可以这样 理解：如果政府认为流浪汉选择工作的概率y＜1/5 时，那么政府的唯一最优选择策略是不救济； 但当政府以概率1选择不救济时，流浪汉的最 优选择是寻找工作;这又将导致政府救济，此时流 浪汉则又会选择游荡，如此循环下去。因此y＜1/5 不构成纳什均衡。 同样，如果政府认为y＞1/5，政府唯一最优选 择是救济；但当政府以概率1选择救济时，流浪汉 的最优选择是游荡，因此y＞1/5也不构成纳什均衡。 类似地，可以验证x＜1/2和x＞1/2都不构成纳 什均衡。另外，从政府期望赢得函数EA（x，y）和流 浪汉的期望赢得函数EB（x，y）去验证， 可得由 X*=（1/2，1/2） Y*=（1/5，4/5） 构成的（X*，Y*）是唯一的混合策略纳什均衡。 当X*=（1/2，1/2）时， EB（1/2，y）=－2×0.5y＋3×0.5＋y=3/2， 流浪汉选择任何混合策略带来的期望赢得都 是3/2，也就是说，流浪汉的任何一种策略（纯的 或混合的）都是对政府所选择的混合策略的最优 反应。当然，其中Y*=（1/5，4/5）也应是一种最 优的混合策略。当Y*=（1/5，4/5）时， EA（x，1/5）=5x×1/5－ x－1/5=－1/5， 政府的任何策略（纯的或混合的）带给政府期望 赢得均为－1/5. 那么以X*=（1/2，1/2）的混合策略，当然也 应是政府对流浪汉所选择的混合策略的最优反应。 因此，X*和Y*构成一个混合策略纳什均衡。
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。}