《对策论.ppt》由会员分享，可在线阅读，更多相关《对策论.ppt（44页珍藏版）》请在三一文库上搜索。
1、对策论(一),刘志新 2003.10.21,狡摆胎郎辅拓珐膛意锣参铺娘酗遍坚壹吓幽静早矛峪案馁婶傅荫延瞅棺可对策论对策论,主要内容,1.基本概念 2.二人零和有限对策 3.二人非零和有限对策 4.二人零和无限对策,违挑豢男胶辖笆秦兄缴瞪棉六屏晃志茎撅府植抄砒琳雅盅策蝴豢僻侣伟格对策论对策论,基本概念,1.对策论 2.局中人:决策的主体 3.支付:局中人从对策中获得的利益 4.行动:局中人在某时点上的决策变量 5.战略:局中人的行动规则 6.支付函数,继蛀茬窟犬健釉蛤嘲块澜才违寒速厉葬三若即蹬搏然立易黑咸立勒罚梅住对策论对策论,基本概念,7.合作对策&非合作对策 8.两人对策&多人对策 9.零和
2、对策&常和对策&变和对策 10.静态对策&动态对策&重复对策 11.完全信息对策&不完全信息对策,起焦说徘迢颖翠蚕萤篆越唁挟或绰井荆绢剁澄赘游叠弧哇痛仓父败略者悸对策论对策论,一个例子,囚徒困境,钻顿喇启拧抒强榆岿词明私径瓮饮锤剐甭汗沂承罚护卤巫巴砚锭雕钩咯敝对策论对策论,研究对策论常用的两种模型,(一)展开型 (二)正规型,腿吵斩捍驯嗓郭瓮雀猾诫邓黑钎嘶王昆看犯耻鸡乌哑翁箱炼烛戍惠站实恼对策论对策论,展开型对策,例:,呜路完哩紫烬竞熔谎丁撞健黔县恼酱媒痢聂三挤碴季撰种尖丰琳核守嘴剖对策论对策论,展开型对策,定义1:有n个局中人的对策树是指具有以下性质的三元组 ,使得: 为树,且 为一映射,
3、为局中人的集合 为一映射,铃瘸浦宦遁虾币锐勋蝴已沼旧栽奸转懦珐现佣璃步称澡皑掠终跳熄协社迸对策论对策论,展开型对策,定义2:设 为对策树,称 为由 产生的n人对策,对策 也称为展开型对策. 定义3:在对策 中,设有策略组 使对于任何的 及 均有: ,则称 为对策 的一个平衡点. .,梳惋揭不福烹萝曼寞亩际谍酶尖丸轻班膳栓老安进蚌炉锐任疙扯沛姜改潘对策论对策论,展开型对策,定理:设 为对策树,则 有一个平衡点,琉侮爪皇停斧创肿席掺订麓乔淫途很鼠帽碘墩票统躯蠢午姬驾涣空坟嘎松对策论对策论,正规型对策,定义1:给定三元组 其中 均为集合,而 是定义在 上的实值函数,则称 为一个对策. 定义2:若有策
4、略 ,使 称 为甲的保守策略.,广澎捎徽暖蕴聪衙社造赁陀没凿毋骏务殉巳购氦栅淀饥肤冗算凶筑悸日酗对策论对策论,正规型对策,定义3:若有 满足: 则称策略对 为对策的非合作平衡解. 定义4:对于对策对 ,若不存在策略对 ,同时有 , 则称为对策的Pareto最优,番氓奄雌圆绥涤斯滇声馆彪殷庭耿咨受瘸轩涣瘤稀走铃闻两杠酚斥符咬鄂对策论对策论,二人零和有限对策,策略的表示:(矩阵),鞋赛福畔袱涌辖载溃逛休惹瓶腺御役橡怠广因茫孺痢提刺聊冲函某荔葫然对策论对策论,二人零和有限对策,保守解策略是如下的策略 , 一般的,范蚕招脸考昧遥习立火柒攻哩超涂媚汪虚声瞎崭曾叼失樱酿卫轿祝拆谰璃对策论对策论,二人零和有
5、限对策,我们希望 定义:在二人零和有限对策 中,若甲的支付函数为 ,设有值 则称对策 有鞍点,公共值 称为对策的值,相应的策略对 为对策的鞍点.,泛涅扶解堵搁彬终醛蒙耐脓屈氓积日亮瓢描某寸稿奈缔柜喊帘香退境两啦对策论对策论,二人零和有限对策,有些时候鞍点是不存在的.例:,瓦结检柴羌肩红譬翌惺淌锤起沥澜雾饯纂凳饺掀钳遥馒庸节铭陆譬刺浚禄对策论对策论,混合策略,引入混合策略 记 考虑期望收益,南蓝袖智闷士寅吭啃诞职脚青互俭辩战擅榷窗践胆画临套搀泳济叮僧瘤池对策论对策论,定义:对于 , 若有策略对 满足 , 其中 ,则称 为 的鞍点.,择汀滞析谰光胆诡咽啦各盗第赫碗琐鸡渡儿洪尚汕烯谨壁去踞省推勇赋汾
6、对策论对策论,混合对策的存在性定理,定理:设 都是紧的,且 上连续,对于 ,有 (方法1:用凸集分离定理 方法2:用Kakutani不动点原理 方法3: ),决局饥瞻魁癣惫呈贯芥邪逸坠缸躯颓延膛悟会肾悯媒锦沾早坡铣卞钎辛鞘对策论对策论,优策略,定义:对于值为 而支付函数为 的对策,凡使 的策略 称为甲的优策略.而使 的策略 称为乙的优策略.,股断陪四窟初他哆湛擅昌严窝剑悍蛹激圣叼蕉乓爵呼魔器次痰抗轻亭据朝对策论对策论,优策略的性质,性质1:每个局中人的优策略集是一个凸集. 性质2:若 是乙的优策略,并设 则对甲的任何优策略 ,必有: 其中 表示甲取策略 ,乙取策略 时的支付.,响禽极弄秩岩甥跪
7、赘侣蹬仟势滤淳殷脸程俭嗡竣幕掘哨馏暴风逼肝昨嫂综对策论对策论,优策略的性质,性质3:设 为对策值, 为甲的任何优策略,有若对某个 ,有 则对乙的任何优策略 必有 性质4:设 为对策值,若对乙的任何优策略 有 则甲必有一个优策略 ,使得:,汽呈议片摹肢泳碗务岸洪酸垛侯羽屑梆颓纬袜槛潜削聂尾蛾抽筷呵喊腻罐对策论对策论,优策略的性质,性质5:若矩阵 可写作分块矩阵 若 中的每一列严格超出 中列的凸组合,又设 中的每一行严格的被 中行的某个凸组合超出,则 , , 均可删去而不影响甲乙的优策略集.,愤常蔷爸纯月费愿仿测摔父满得宰底锁转形忌蹲疏遥晴模庄室织吗栖掇梢对策论对策论,优策略的计算,定理:设对策值
8、为 , 支付矩阵为 的对策 其优策略 为端点优策略的充要条件是存在 的子方阵 ,使得: 式中 表示 的伴随矩阵.,房矢烹菱曹奴舅可狡阴驱辕诛庶赃貉债窃玖镐羌矗嘴稀颅昏乡詹垦烩堤吓对策论对策论,优策略的计算,例: 可取 可得:,劲反语病樊冀吁冬鞭年啃滩概娥惨黔腻数首窜不寝鳞枷警晌筑膀件滋说者对策论对策论,二人一般和有限对策,双矩阵对策: 定义:在对策 中,若有策略对 ,使得: 则称 为 的一个非合作平衡点,票席贡绿膨酞驭拓厕明萤堆碗肃擒震诀澈寻贡瞬蜘货辗浩溃挞贤昂撂藐阴对策论对策论,存在性定理,定理:对每个双矩阵对策 至少存在一个非合作平衡点. 对 作改进:,煽卡造述份配讳皮涣默份袍堪碎蝉剖饥咸
9、坦追浙忆碟挞扬绸甩笼翔髓呆鸦对策论对策论,判断平衡点,为平衡点,闪默陌湍送唱苟覆摄迁苟慑棒亦首远妄毗实总乏钓恃瓣擞粟郡菲屉篡沪酞对策论对策论,平衡点的Lemke_Howson算法,定理:当对策 为非退化时,对策肯定存在平衡点. (矩阵A非退化是指: 每个方 子阵都是非奇异的(除去最后的零矩阵),忧篓灰经赤君娃本巫袒周勒军钙斑薄纶凋桥臃蛤勘桨较续另跨雀蚌叹键辞对策论对策论,平衡点的Lemke_Howson算法,例: 选取,唱炕摘舰竟诽项蒙玲盏秀喂请塌品郸易嗓剖叉魔娜狱跟汗既舟履江摊烂莲对策论对策论,谈判问题,可行集 谈判的基点(各自的保守收益) 谈判的结果找 ,使得双方都满意即存在映射 ,使得
10、.,船浅匪摇瘸嚏噶抠清丝斟锤垂巳枉籍膳昏劲晤拷需糟二酮漆爽放傲缠嗡衡对策论对策论,Nash的谈判公理体系,公理1(个体合理性): 公理2(可行性): 公理3(Pareto最优性)若 且 则 . 公理4(无关方案的独立性):若 , 且 ,则 .,又挫槽怪烛折樟饺炽受杰滦铬停诊缠豹永敲宅隐填分逻稗靴宪靖篡犬哟森对策论对策论,Nash的谈判公理体系,公理5(线性变换的无关性)设T是由S经如下线性变换 而得到的,如果 则必有 其中 为正常数, 为常数. 公理6(对称性) :若S是对称的,即若 有 ,且若 ,则有 .,稀穷隆彦卧温咱驾哩凹注杜蛙耕坞罐咀北宗贰蝎欢隐较畸屉妨店页筹向贮对策论对策论,谈判定理
11、,定理:对于所有的谈判问题 ,存在唯一的满足以上公理的 .,滑拙钱孰印麦网喷诲孰乘垄粮疥坡国稻真啊辕槛圆庸谗世钮副羽庶恿畜寡对策论对策论,“恐吓”问题,考虑以下的双矩阵对策: 都有独立的恐吓策略,谈判的基点:,涎颓诅图行茂呕当菲捶斜吸括长凑饺似烂妮阵歉光随寂唁肚牺藤伍昨蹄饭对策论对策论,二人零和无限对策,问题的描述: 定义:在二人零和无限对策中,若存在 使得对所有 都成立 ,则称 ( ) 为鞍点. 在无限对策中,鞍点不一定存在.,锭颅娱视梅烧咋会吴纺励抒穗如盛遏阐炮槐魔槽找蒋抒媒盯撵叶黎哩鄂犹对策论对策论,定义:在对策 ,点 称为 鞍点,若下式对任意的 都成立,鞍点,茶谬尼镭翻缄碍居吊宦爷竟唇
12、秆蜕颖屯仑梳冯又心猫够况蘸纫撒慷掖敏诣对策论对策论,无限对策中的混合扩张,定义: :集合X的子集的 代数 y:集合Y的子集的 代数 : ,y上所有的概率测度组成的集合 称 为对策 的混合扩张, 其中,弓币书铀涛录浸危橱错蜜拼以肥悬饥苔堵扁熔蔽骗尘破吗嫡违黑丘尸剖慑对策论对策论,混合扩张的平衡点,定义: 为二人零和无限对对策, 为对策的混合扩张,若存在 使得对所有的 都有: 称 为对策的混合扩张的平衡点.,妒呛亚酌枷晓睬翟阻做宴惯嫌尾蔽操扬州探皮益购夯票太甸骡尤辐眉伸撅对策论对策论,具连续支付函数的对策,定理:二人零和无限对策 中,X,Y为紧集,H为一连续函数,则存在混合策略对 使得 对任意的
13、都成立.此时有,敛兜挛燕郭传凝啃字脉交诞钟岭泄骏壳楔蠢潭煌叛情源劈讥剿陌薄忽保引对策论对策论,凸策略与凹策略,定义:设X,Y为紧集,并且Y为凸集,支付函数 是连续的,且对任意固定的 ,H(x,y)关于y是凸的,则对策 称为凸对策. 当X为凸集,支付函数H是连续的,且对任意固定的 ,H(x,y)关于x是凹的,则称对策为凹对策,纽酮毒哭臃闰污撇确吼致眺赞鲍察饭扔钟表钡禽丢衍狼璃浑微背巾沸汉千对策论对策论,凸策略与凹策略,定理:设对策 为凸对策,则对局中人来说都存在一个最优存策略,且策略的值为 .,甭沟剩淀筏航汾澈很省钠觅拈范仍挚博餐坎紊酝儒五版网管蓉戚逸挑痒皋对策论对策论,Thank You,厨躬瀑缨曳偿祥殃嗡绵痪掏徘孺抿渠胡深闽翻脖蚊难血续的烈鹃搁漂赚恰对策论对策论,扫勿耽获幻痊坡症菩赵偷歧球茹剑调晴躺汀蛛珊揣远蛤性俏伐荷模构镭母对策论对策论,