对策论ppt课件

1、 对策论(一) 刘志新刘志新 2019.10.21主要内容n1.根本概念n2.二人零和有限对策n3.二人非零和有限对策n4.二人零和无限对策根本概念n1.对策论n2.局中人:决策的主体n3.支付:局中人从对策中获得的利益n4.行动:局中人在某时点上的决策变量n5.战略:局中人的行动规那么n6.支付函数根本概念n7.协作对策&非协作对策n8.两人对策&多人对策n9.零和对策&常和对策&变和对策n10.静态对策&动态对策&反复对策n11.完全信息对策&不完全信息对策一个例子n囚徒姿态 乙甲 不坦白 坦白不坦白 (1,1) (10,0)坦白 (

2、0,10) (8,8)研讨对策论常用的两种模型n(一)展开型n(二)正规型展开型对策n例:(2,3)(1,4)(3,1)(2,5)甲乙乙abcdefg展开型对策n定义定义1:有有n个局中人的对策树是指具有以个局中人的对策树是指具有以下性质的三元组下性质的三元组 ,使得使得:n 为树为树,且且 n 为一映射为一映射, 为局中人的集为局中人的集合合n 为一映射为一映射( , ; ; )a u 1).( , ) 2) :aN3) :nuRN展开型对策n定义定义2:设设 为对策树为对策树,称称n 为由为由 产生的产生的n人对策人对策,对策对策 也称为展开型对策也称为展开型对策.n定义定义3:在对策在对

3、策 中中,设有战略组设有战略组 n 使对于任何的使对于任何的 及及 均有均有: ,那那么称么称 n 为对策为对策 的一个平衡点的一个平衡点.n.( , ; ; )a u 1212(,.;,.)nnSSSPPP ( , )S P 12(,.)n iNiiS12111(,.)(.,.)iniiiinPP 展开型对策n定理:设 为对策树,那么 有一个平衡点正规型对策n定义定义1:给定三元组给定三元组 其其中中 均为集合均为集合,而而 是定义在是定义在 n 上的实值函数上的实值函数,那么称那么称 为为一个对策一个对策.n定义定义2:假设有战略假设有战略 ,使使n n 称称 为甲的保守战略为甲的保守战略

4、. ,iii Ni NNSP ,iN S iNiPiiNSS 1212111112()sup inf(,)SSPP 1正规型对策n定义定义3:假设有假设有 满足满足:n 那么称战略对那么称战略对 为对策的非协作为对策的非协作平衡解平衡解.n定义定义4:对于对策对对于对策对 ,假设不存假设不存在战略对在战略对 ,同时同时有有 ,n 那么称为对策的那么称为对策的Pareto最优最优12, 1122111212221212(,)max(,)(,)max(,)SSPPPP 12, 12,v 12, 111212221212(,)(,)(,)(,)PPPP 二人零和有限对策n战略的表示:(矩阵) 乙甲

5、1 2 n 1P(1,1) P(1,2) P(1,n) 2P(2,1) P(2,2) P(2,n) mP(m,1) P(m,2) P(m,m)二人零和有限对策n保守解战略是如下的战略 ,n普通的12, 212112121111221212()sup inf(,)()sup inf (,)SSSSPPvPP 2121112inf sup(,)SSPv 22112211111212sup inf(,)inf sup(,)SSSSvPPv 二人零和有限对策n我们希望 n定义:在二人零和有限对策 中,假设甲的支付函数为 ,设有值 那么称对策 有鞍点,公共值 称为对策的值,相应的战略对 为对策的鞍点.(

6、)0vv 12(,)P :vvvv使得v12,二人零和有限对策n有些时候鞍点是不存在的.例:131312122maxmin( , )minmax( , )4jjiiP i jP i j 乙甲 1 2 3 1 6 -2 3 2 -4 5 4混合战略n引入混合战略n记n思索期望收益1( .),0,1. ,1miiXx xxxximx1( .),0,1. ,1njjYy yyyyjny11( , )mniijjijxAyx a yA x yn定义定义:对于对于 , 假设有战略对假设有战略对 满足满足 , n 其中其中 ,那么称那么称 为为 的鞍的鞍点点., ;X Y A ( , )x y A( ,

7、)( ,y)A(x,y)x yA xy Yy Yx Xx Xmaxmin( , )minmax( , )A x yA x y,xX yY( ,y)x混合对策的存在性定理n定理:设 都是紧的,且 上延续,对于 ,有n(方法1:用凸集分别定理n 方法2:用Kakutani不动点原理n 方法3: ) X,YFx Y在, ;X Y A y Yy Yx Xx Xmaxmin( , )minmax( , )A x yA x yV( )( )gap Agap A优战略n定义定义:对于值为对于值为 而支付函数为而支付函数为 的对策的对策,凡使凡使 的战略的战略 称称为甲的优战略为甲的优战略.而使而使 的战略的

8、战略 称为乙的优战略称为乙的优战略.( , )A x y( , ),A x yV y Yx( , ),Ax yV x Xyv优战略的性质n性质1:每个局中人的优战略集是一个凸集.n性质2:假设 是乙的优战略,并设 那么对甲的任何优战略 ,必有: n 其中 表示甲取战略 ,乙取战略 时的支付.y00,jyx001( ,)niijiA x jxav0( ,)A x jx0j优战略的性质n性质3:设 为对策值, 为甲的任何优战略,有假设对某个 ,有 那么对乙的任何优战略 必有n性质4:设 为对策值,假设对乙的任何优战略 有 那么甲必有一个优战略 ,使得: vx0j0(,),A xjvy00.jyy0

9、0.jyxv0(,),A xjv优战略的性质n性质5:假设矩阵 可写作分块矩阵 n 假设 中的每一列严厉超出 中列的凸组合,又设 中的每一行严厉的被 中行的某个凸组合超出,那么 , , 均可删去而不影响甲乙的优战略集.A1234AAAAA2A1A3A1A2A3A4A优战略的计算n定理:设对策值为 , 支付矩阵为 的对策n 其优战略 为端点优战略的充要条件是存在 的子方阵 ,使得:n 式中 表示 的伴随矩阵.Av00,xyAM00(,()0(,()()(,()()(,()ea d jMeMvea d jMee a d jMxea d jMea d jMeyea d jMe()adj MM优战略的

10、计算n例: n 可取 可得:113110025A1102M001001/21/20 xy二人普通和有限对策n双矩阵对策:n定义:在对策 中,假设有战略对 ,使得:n 那么称 为 的一个非协作平衡点, ; ,X Y A B , ; ,X Y A B ( , )x y(, )X Y()()xAyxAyxXxAyxAyyY ( , )x y存在性定理n定理:对每个双矩阵对策 至少存在一个非协作平衡点.n 对 作改良:, ; ,X Y A B .max,0max,0iijjcA yxAydxBxAy( ,y)x11,11jjiiijkkkkydxcxycd判别平衡点 为平衡点( , )x y.()()

11、ijxAyA y iIxByxBjJ.maxmaxii Ijj JxAyA yxByxB.0max()0max()kkii Ijljj JxA yA y kIyxBxBlJ平衡点的Lemke_Howson算法n定理:当对策 为非退化时,对策一定存在平衡点.n (矩阵A非退化是指: 每个方n 子阵都是非奇特的(除去最后的零矩阵)(, ; ,)X Y A B1.11.10A平衡点的Lemke_Howson算法n例:n 选取41A2614B34012(,)z (1)1(,) (1)(1)(,)(1)(1/7,6/7)(1)(5/7,2/7)121212(1)(1)12谈判问题n可行集n谈判的基点(各

12、自的保守收益)n谈判的结果找 ,使得双方都称心即存在映射 ,使得 .( , ),( , )Su v uu vvu v Pareto且最优maxminmaxminy Yx Xx Xy YuxAyvxBy( , )u v( , )( ,)S Nash的谈判公理体系n公理1(个体合理性):n公理2(可行性):n公理3(Pareto最优性)假设 且n 那么 .n公理4(无关方案的独立性):假设 ,n 且 ,那么 . ( , )(,)u vu v( , )u vS( , )u vS( , )( ,)u vS u v( , )( , ),u vu v( , )( , )u vu v(u,v)TS( , )

13、(T,)u vu vNash的谈判公理体系n公理5(线性变换的无关性)设T是由S经如下线性变换 n 而得到的,假设 那么必有n 其中 为正常数, 为常数.n公理6(对称性) :假设S是对称的,即假设n 有 ,且假设 ,那么有 .111111u =u+v =v+( ,)( , )S u vu v11221122( ,)(,)Tuvuv 12, 12, ( , )u vS( , )v uSuvuv谈断定理n定理:对于一切的谈判问题 ,存在独一的满足以上公理的 .( ,)S u v“恫吓问题n思索以下的双矩阵对策:n 都有独立的恫吓战略,谈判的基点:1212(1,4)( 1, 4)( 4, 1)(4

14、,1) 和12e ( , )( , )x yxAye x yxBy二人零和无限对策n问题的描画:n定义:在二人零和无限对策中,假设存在 n 使得对一切 都成立 ,那么称n ( ) 为鞍点. n 在无限对策中,鞍点不一定存在. (, ,)X Y H1:*H XYR,xy( ,)(,)(, )H x yH xyH xy,xX yY,xyn定义定义:在对策在对策 ,点点 称为称为n 鞍点鞍点,假设下式对恣意的假设下式对恣意的 都都成立成立,(, ,)X Y H(,)xy,xX yY( ,)(,)(, )H x yH xyH xy 鞍点无限对策中的混合扩张n定义定义: :集合集合X的子集的的子集的 代

15、数代数n y:集合集合Y的子集的的子集的 代数代数n : ,y上一切的概率测度组上一切的概率测度组成的集合成的集合n 称称 为对策为对策 的混合扩张的混合扩张,n 其中其中,X Y(, ,K)X Y(, ,)X Y HX YK( , )H(x,y)d (x) (x) 混合扩张的平衡点n定义定义: 为二人零和无限对对策为二人零和无限对对策,n 为对策的混合扩张为对策的混合扩张,假设存在假设存在n 使得对一切的使得对一切的 都有都有:n n n 称称 为对策的混合扩张的平衡点为对策的混合扩张的平衡点.n (, ,K)X Y(, ,)X Y H(,) *XY,XYK( ,)(,)(, )KK (,) supinf( , )inf sup( , )KKv 具延续支付函数的对策n定理:二人零和无限对策 中,X,Y为紧集,H为一延续函数,那么存在混合战略对 使得n n 对恣意的 都成立.此时有(, ,)X Y H(,) K( ,)(,)(, )KK ,XYmaxmin( , )minmax( , )YYXXvKK 凸战略与凹战略n定义定义:设设X,Y为紧集为紧集,并且并且Y为凸集为凸集,支付函支付函数数 是延续的是延续的,且对