对策论(一).ppt

《对策论(一).ppt》由会员分享，可在线阅读，更多相关《对策论(一).ppt（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、主要内容n1.基本概念n2.二人零和有限对策n3.二人非零和有限对策n4.二人零和无限对策基本概念n1.对策论n2.局中人:决策的主体n3.支付:局中人从对策中获得的利益n4.行动:局中人在某时点上的决策变量n5.战略:局中人的行动规则n6.支付函数基本概念n7.合作对策&非合作对策n8.两人对策&多人对策n9.零和对策&常和对策&变和对策n10.静态对策&动态对策&重复对策n11.完全信息对策&不完全信息对策一个例子n囚徒困境研究对策论常用的两种模型n(一)展开型n(二)正规型展开型对策n例:展开型对策n定义定义1:有n个局中人的对策树对策树是指具有以下性质的三元组 ,使得:为树,且 为一映

2、射,为局中人的集合 为一映射展开型对策n定义定义2:设 为对策树,称 为由 产生的n人对策,对策 也称为展开型对策展开型对策.n定义定义3:在对策 中,设有策略组 使对于任何的 及 均有:,则称 为对策 的一个平衡点平衡点.展开型对策n定理:设 为对策树,则 有一个平衡点正规型对策n定义定义1:给定三元组 其中 均为集合,而 是定义在 上的实值函数,则称 为一个对对策策.n定义定义2:若有策略 ,使 称 为甲的保守策略保守策略.正规型对策n定义定义3:若有 满足:则称策略对 为对策的非合作平衡非合作平衡解.n定义定义4:对于对策对 ,若不存在策略对 ,同时有 ,则称为对策的Pareto最优最优

3、二人零和有限对策n策略的表示:(矩阵)二人零和有限对策n保守解策略是如下的策略 ,n一般的二人零和有限对策n我们希望 n定义定义:在二人零和有限对策 中,若甲的支付函数为 ,设有值 则称对策 有鞍点,公共值 称为对策的值,相应的策略对 为对策的鞍点鞍点.二人零和有限对策n有些时候鞍点是不存在的.例:混合策略n引入混合策略n记n考虑期望收益n定义定义:对于 ,若有策略对 满足 ,其中 ,则称 为 的鞍点鞍点.混合对策的存在性定理n定理:设 都是紧的,且 上连续,对于 ,有(方法1:用凸集分离定理 方法2:用Kakutani不动点原理 方法3:)优策略n定义定义:对于值为 而支付函数为 的对策,凡

4、使 的策略 称为甲的优策略优策略.而使 的策略 称为乙的优策略.优策略的性质n性质1:每个局中人的优策略集是一个凸集.n性质2:若 是乙的优策略,并设 则对甲的任何优策略 ,必有:其中 表示甲取策略 ,乙取策略 时的支付.优策略的性质n性质3:设 为对策值,为甲的任何优策略,有若对某个 ,有 则对乙的任何优策略 必有n性质4:设 为对策值,若对乙的任何优策略 有 则甲必有一个优策略 ,使得:优策略的性质n性质5:若矩阵 可写作分块矩阵 若 中的每一列严格超出 中列的凸组合,又设 中的每一行严格的被 中行的某个凸组合超出,则 ,均可删去而不影响甲乙的优策略集.优策略的计算n定理:设对策值为 ,支

5、付矩阵为 的对策 其优策略 为端点优策略的充要条件是存在 的子方阵 ,使得:式中 表示 的伴随矩阵.优策略的计算n例:可取 可得:二人一般和有限对策n双矩阵对策:n定义定义:在对策 中,若有策略对 ,使得:则称 为 的一个非合作平衡点非合作平衡点存在性定理n定理:对每个双矩阵对策 至少存在一个非合作平衡点.对 作改进:判断平衡点 为平衡点平衡点的Lemke_Howson算法n定理:当对策 为非退化时,对策肯定存在平衡点.(矩阵A非退化是指:每个方 子阵都是非奇异的(除去最后的零矩阵)平衡点的Lemke_Howson算法n例:选取谈判问题n可行集n谈判的基点(各自的保守收益)n谈判的结果找 ,使

6、得双方都满意即存在映射 ,使得 .Nash的谈判公理体系n公理1(个体合理性):n公理2(可行性):n公理3(Pareto最优性)若 且 则 .n公理4(无关方案的独立性):若 ,且 ,则 .Nash的谈判公理体系n公理5(线性变换的无关性)设T是由S经如下线性变换 而得到的,如果 则必有 其中 为正常数,为常数.n公理6(对称性):若S是对称的,即若 有 ,且若 ,则有 .谈判定理n定理:对于所有的谈判问题 ,存在唯一的满足以上公理的 .“恐吓”问题n考虑以下的双矩阵对策:n 都有独立的恐吓策略,谈判的基点:二人零和无限对策n问题的描述:n定义定义:在二人零和无限对策中,若存在 使得对所有

7、都成立 ,则称 ()为鞍点鞍点.在无限对策中,鞍点不一定存在.n定义定义:在对策 ,点 称为 鞍点鞍点,若下式对任意的 都成立,鞍点无限对策中的混合扩张n定义定义:集合X的子集的 代数 y:集合Y的子集的 代数 :,y上所有的概率测度组成的集合 称 为对策 的混合扩张混合扩张,其中混合扩张的平衡点n定义定义:为二人零和无限对对策,为对策的混合扩张,若存在 使得对所有的 都有:称 为对策的混合扩张的平衡点混合扩张的平衡点.具连续支付函数的对策n定理:二人零和无限对策 中,X,Y为紧集,H为一连续函数,则存在混合策略对 使得 对任意的 都成立.此时有凸策略与凹策略n定义定义:设X,Y为紧集,并且Y为凸集,支付函数 是连续的,且对任意固定的 ,H(x,y)关于y是凸的,则对策 称为凸对策凸对策.n当X为凸集,支付函数H是连续的,且对任意固定的 ,H(x,y)关于x是凹的,则称对策为凹对策凹对策 凸策略与凹策略n定理:设对策 为凸对策,则对局中人来说都存在一个最优存策略,且策略的值为 .Thank You