對策論ppt課件

1、 對策論(一) 劉志新劉志新 2019.10.21主要內(nèi)容n1.根本概念n2.二人零和有限對策n3.二人非零和有限對策n4.二人零和無限對策根本概念n1.對策論n2.局中人:決策的主體n3.支付:局中人從對策中獲得的利益n4.行動:局中人在某時點(diǎn)上的決策變量n5.戰(zhàn)略:局中人的行動規(guī)那么n6.支付函數(shù)根本概念n7.協(xié)作對策&非協(xié)作對策n8.兩人對策&多人對策n9.零和對策&常和對策&變和對策n10.靜態(tài)對策&動態(tài)對策&反復(fù)對策n11.完全信息對策&不完全信息對策一個例子n囚徒姿態(tài) 乙甲 不坦白 坦白不坦白 (1,1) (10,0)坦白 (

2、0,10) (8,8)研討對策論常用的兩種模型n(一)展開型n(二)正規(guī)型展開型對策n例:(2,3)(1,4)(3,1)(2,5)甲乙乙abcdefg展開型對策n定義定義1:有有n個局中人的對策樹是指具有以個局中人的對策樹是指具有以下性質(zhì)的三元組下性質(zhì)的三元組 ,使得使得:n 為樹為樹,且且 n 為一映射為一映射, 為局中人的集為局中人的集合合n 為一映射為一映射( , ; ; )a u 1).( , ) 2) :aN3) :nuRN展開型對策n定義定義2:設(shè)設(shè) 為對策樹為對策樹,稱稱n 為由為由 產(chǎn)生的產(chǎn)生的n人對策人對策,對策對策 也稱為展開型對策也稱為展開型對策.n定義定義3:在對策在對

3、策 中中,設(shè)有戰(zhàn)略組設(shè)有戰(zhàn)略組 n 使對于任何的使對于任何的 及及 均有均有: ,那那么稱么稱 n 為對策為對策 的一個平衡點(diǎn)的一個平衡點(diǎn).n.( , ; ; )a u 1212(,.;,.)nnSSSPPP ( , )S P 12(,.)n iNiiS12111(,.)(.,.)iniiiinPP 展開型對策n定理:設(shè) 為對策樹,那么 有一個平衡點(diǎn)正規(guī)型對策n定義定義1:給定三元組給定三元組 其其中中 均為集合均為集合,而而 是定義在是定義在 n 上的實(shí)值函數(shù)上的實(shí)值函數(shù),那么稱那么稱 為為一個對策一個對策.n定義定義2:假設(shè)有戰(zhàn)略假設(shè)有戰(zhàn)略 ,使使n n 稱稱 為甲的保守戰(zhàn)略為甲的保守戰(zhàn)略

4、. ,iii Ni NNSP ,iN S iNiPiiNSS 1212111112()sup inf(,)SSPP 1正規(guī)型對策n定義定義3:假設(shè)有假設(shè)有 滿足滿足:n 那么稱戰(zhàn)略對那么稱戰(zhàn)略對 為對策的非協(xié)作為對策的非協(xié)作平衡解平衡解.n定義定義4:對于對策對對于對策對 ,假設(shè)不存假設(shè)不存在戰(zhàn)略對在戰(zhàn)略對 ,同時同時有有 ,n 那么稱為對策的那么稱為對策的Pareto最優(yōu)最優(yōu)12, 1122111212221212(,)max(,)(,)max(,)SSPPPP 12, 12,v 12, 111212221212(,)(,)(,)(,)PPPP 二人零和有限對策n戰(zhà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保守解戰(zhàn)略是如下的戰(zhàn)略 ,n普通的12, 212112121111221212()sup inf(,)()sup inf (,)SSSSPPvPP 2121112inf sup(,)SSPv 22112211111212sup inf(,)inf sup(,)SSSSvPPv 二人零和有限對策n我們希望 n定義:在二人零和有限對策 中,假設(shè)甲的支付函數(shù)為 ,設(shè)有值 那么稱對策 有鞍點(diǎn),公共值 稱為對策的值,相應(yīng)的戰(zhàn)略對 為對策的鞍點(diǎn).(

6、)0vv 12(,)P :vvvv使得v12,二人零和有限對策n有些時候鞍點(diǎn)是不存在的.例:131312122maxmin( , )minmax( , )4jjiiP i jP i j 乙甲 1 2 3 1 6 -2 3 2 -4 5 4混合戰(zhàn)略n引入混合戰(zhàn)略n記n思索期望收益1( .),0,1. ,1miiXx xxxximx1( .),0,1. ,1njjYy yyyyjny11( , )mniijjijxAyx a yA x yn定義定義:對于對于 , 假設(shè)有戰(zhàn)略對假設(shè)有戰(zhàn)略對 滿足滿足 , n 其中其中 ,那么稱那么稱 為為 的鞍的鞍點(diǎn)點(diǎ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定理:設(shè) 都是緊的,且 上延續(xù),對于 ,有n(方法1:用凸集分別定理n 方法2:用Kakutani不動點(diǎn)原理n 方法3: ) X,YFx Y在, ;X Y A y Yy Yx Xx Xmaxmin( , )minmax( , )A x yA x yV( )( )gap Agap A優(yōu)戰(zhàn)略n定義定義:對于值為對于值為 而支付函數(shù)為而支付函數(shù)為 的對策的對策,凡使凡使 的戰(zhàn)略的戰(zhàn)略 稱稱為甲的優(yōu)戰(zhàn)略為甲的優(yōu)戰(zhàn)略.而使而使 的戰(zhàn)略的

8、戰(zhàn)略 稱為乙的優(yōu)戰(zhàn)略稱為乙的優(yōu)戰(zhàn)略.( , )A x y( , ),A x yV y Yx( , ),Ax yV x Xyv優(yōu)戰(zhàn)略的性質(zhì)n性質(zhì)1:每個局中人的優(yōu)戰(zhàn)略集是一個凸集.n性質(zhì)2:假設(shè) 是乙的優(yōu)戰(zhàn)略,并設(shè) 那么對甲的任何優(yōu)戰(zhàn)略 ,必有: n 其中 表示甲取戰(zhàn)略 ,乙取戰(zhàn)略 時的支付.y00,jyx001( ,)niijiA x jxav0( ,)A x jx0j優(yōu)戰(zhàn)略的性質(zhì)n性質(zhì)3:設(shè) 為對策值, 為甲的任何優(yōu)戰(zhàn)略,有假設(shè)對某個 ,有 那么對乙的任何優(yōu)戰(zhàn)略 必有n性質(zhì)4:設(shè) 為對策值,假設(shè)對乙的任何優(yōu)戰(zhàn)略 有 那么甲必有一個優(yōu)戰(zhàn)略 ,使得: vx0j0(,),A xjvy00.jyy0

9、0.jyxv0(,),A xjv優(yōu)戰(zhàn)略的性質(zhì)n性質(zhì)5:假設(shè)矩陣 可寫作分塊矩陣 n 假設(shè) 中的每一列嚴(yán)厲超出 中列的凸組合,又設(shè) 中的每一行嚴(yán)厲的被 中行的某個凸組合超出,那么 , , 均可刪去而不影響甲乙的優(yōu)戰(zhàn)略集.A1234AAAAA2A1A3A1A2A3A4A優(yōu)戰(zhàn)略的計算n定理:設(shè)對策值為 , 支付矩陣為 的對策n 其優(yōu)戰(zhàn)略 為端點(diǎn)優(yōu)戰(zhàn)略的充要條件是存在 的子方陣 ,使得:n 式中 表示 的伴隨矩陣.Av00,xyAM00(,()0(,()()(,()()(,()ea d jMeMvea d jMee a d jMxea d jMea d jMeyea d jMe()adj MM優(yōu)戰(zhàn)略的

10、計算n例: n 可取 可得:113110025A1102M001001/21/20 xy二人普通和有限對策n雙矩陣對策:n定義:在對策 中,假設(shè)有戰(zhàn)略對 ,使得:n 那么稱 為 的一個非協(xié)作平衡點(diǎn), ; ,X Y A B , ; ,X Y A B ( , )x y(, )X Y()()xAyxAyxXxAyxAyyY ( , )x y存在性定理n定理:對每個雙矩陣對策 至少存在一個非協(xié)作平衡點(diǎn).n 對 作改良:, ; ,X Y A B .max,0max,0iijjcA yxAydxBxAy( ,y)x11,11jjiiijkkkkydxcxycd判別平衡點(diǎn) 為平衡點(diǎn)( , )x y.()()

11、ijxAyA y iIxByxBjJ.maxmaxii Ijj JxAyA yxByxB.0max()0max()kkii Ijljj JxA yA y kIyxBxBlJ平衡點(diǎn)的Lemke_Howson算法n定理:當(dāng)對策 為非退化時,對策一定存在平衡點(diǎn).n (矩陣A非退化是指: 每個方n 子陣都是非奇特的(除去最后的零矩陣)(, ; ,)X Y A B1.11.10A平衡點(diǎn)的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談判的基點(diǎn)(各

12、自的保守收益)n談判的結(jié)果找 ,使得雙方都稱心即存在映射 ,使得 .( , ),( , )Su v uu vvu v Pareto且最優(yōu)maxminmaxminy Yx Xx Xy YuxAyvxBy( , )u v( , )( ,)S Nash的談判公理體系n公理1(個體合理性):n公理2(可行性):n公理3(Pareto最優(yōu)性)假設(shè) 且n 那么 .n公理4(無關(guān)方案的獨(dú)立性):假設(shè) ,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(線性變換的無關(guān)性)設(shè)T是由S經(jīng)如下線性變換 n 而得到的,假設(shè) 那么必有n 其中 為正常數(shù), 為常數(shù).n公理6(對稱性) :假設(shè)S是對稱的,即假設(shè)n 有 ,且假設(shè) ,那么有 .111111u =u+v =v+( ,)( , )S u vu v11221122( ,)(,)Tuvuv 12, 12, ( , )u vS( , )v uSuvuv談斷定理n定理:對于一切的談判問題 ,存在獨(dú)一的滿足以上公理的 .( ,)S u v“恫嚇問題n思索以下的雙矩陣對策:n 都有獨(dú)立的恫嚇戰(zhàn)略,談判的基點(diǎn):1212(1,4)( 1, 4)( 4, 1)(4

14、,1) 和12e ( , )( , )x yxAye x yxBy二人零和無限對策n問題的描畫:n定義:在二人零和無限對策中,假設(shè)存在 n 使得對一切 都成立 ,那么稱n ( ) 為鞍點(diǎn). n 在無限對策中,鞍點(diǎn)不一定存在. (, ,)X Y H1:*H XYR,xy( ,)(,)(, )H x yH xyH xy,xX yY,xyn定義定義:在對策在對策 ,點(diǎn)點(diǎn) 稱為稱為n 鞍點(diǎn)鞍點(diǎn),假設(shè)下式對恣意的假設(shè)下式對恣意的 都都成立成立,(, ,)X Y H(,)xy,xX yY( ,)(,)(, )H x yH xyH xy 鞍點(diǎn)無限對策中的混合擴(kuò)張n定義定義: :集合集合X的子集的的子集的 代

15、數(shù)代數(shù)n y:集合集合Y的子集的的子集的 代數(shù)代數(shù)n : ,y上一切的概率測度組上一切的概率測度組成的集合成的集合n 稱稱 為對策為對策 的混合擴(kuò)張的混合擴(kuò)張,n 其中其中,X Y(, ,K)X Y(, ,)X Y HX YK( , )H(x,y)d (x) (x) 混合擴(kuò)張的平衡點(diǎn)n定義定義: 為二人零和無限對對策為二人零和無限對對策,n 為對策的混合擴(kuò)張為對策的混合擴(kuò)張,假設(shè)存在假設(shè)存在n 使得對一切的使得對一切的 都有都有:n n n 稱稱 為對策的混合擴(kuò)張的平衡點(diǎn)為對策的混合擴(kuò)張的平衡點(diǎn).n (, ,K)X Y(, ,)X Y H(,) *XY,XYK( ,)(,)(, )KK (,) supinf( , )inf sup( , )KKv 具延續(xù)支付函數(shù)的對策n定理:二人零和無限對策 中,X,Y為緊集,H為一延續(xù)函數(shù),那么存在混合戰(zhàn)略對 使得n n 對恣意的 都成立.此時有(, ,)X Y H(,) K( ,)(,)(, )KK ,XYmaxmin( , )minmax( , )YYXXvKK 凸戰(zhàn)略與凹戰(zhàn)略n定義定義:設(shè)設(shè)X,Y為緊集為緊集,并且并且Y為凸集為凸集,支付函支付函數(shù)數(shù) 是延續(xù)的是延續(xù)的,且對