對(duì)策論ppt課件

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

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

3、策 中中,設(shè)有戰(zhàn)略組設(shè)有戰(zhàn)略組 n 使對(duì)于任何的使對(duì)于任何的 及及 均有均有: ,那那么稱么稱 n 為對(duì)策為對(duì)策 的一個(gè)平衡點(diǎn)的一個(gè)平衡點(diǎn).n.( , ; ; )a u 1212(,.;,.)nnSSSPPP ( , )S P 12(,.)n iNiiS12111(,.)(.,.)iniiiinPP 展開(kāi)型對(duì)策n定理:設(shè) 為對(duì)策樹(shù),那么 有一個(gè)平衡點(diǎn)正規(guī)型對(duì)策n定義定義1:給定三元組給定三元組 其其中中 均為集合均為集合,而而 是定義在是定義在 n 上的實(shí)值函數(shù)上的實(shí)值函數(shù),那么稱那么稱 為為一個(gè)對(duì)策一個(gè)對(duì)策.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ī)型對(duì)策n定義定義3:假設(shè)有假設(shè)有 滿足滿足:n 那么稱戰(zhàn)略對(duì)那么稱戰(zhàn)略對(duì) 為對(duì)策的非協(xié)作為對(duì)策的非協(xié)作平衡解平衡解.n定義定義4:對(duì)于對(duì)策對(duì)對(duì)于對(duì)策對(duì) ,假設(shè)不存假設(shè)不存在戰(zhàn)略對(duì)在戰(zhàn)略對(duì) ,同時(shí)同時(shí)有有 ,n 那么稱為對(duì)策的那么稱為對(duì)策的Pareto最優(yōu)最優(yōu)12, 1122111212221212(,)max(,)(,)max(,)SSPPPP 12, 12,v 12, 111212221212(,)(,)(,)(,)PPPP 二人零和有限對(duì)策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)二人零和有限對(duì)策n保守解戰(zhàn)略是如下的戰(zhàn)略 ,n普通的12, 212112121111221212()sup inf(,)()sup inf (,)SSSSPPvPP 2121112inf sup(,)SSPv 22112211111212sup inf(,)inf sup(,)SSSSvPPv 二人零和有限對(duì)策n我們希望 n定義:在二人零和有限對(duì)策 中,假設(shè)甲的支付函數(shù)為 ,設(shè)有值 那么稱對(duì)策 有鞍點(diǎn),公共值 稱為對(duì)策的值,相應(yīng)的戰(zhàn)略對(duì) 為對(duì)策的鞍點(diǎn).(

6、)0vv 12(,)P :vvvv使得v12,二人零和有限對(duì)策n有些時(shí)候鞍點(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定義定義:對(duì)于對(duì)于 , 假設(shè)有戰(zhàn)略對(duì)假設(shè)有戰(zhàn)略對(duì) 滿足滿足 , 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混合對(duì)策的存在性定理n定理:設(shè) 都是緊的,且 上延續(xù),對(duì)于 ,有n(方法1:用凸集分別定理n 方法2:用Kakutani不動(dòng)點(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定義定義:對(duì)于值為對(duì)于值為 而支付函數(shù)為而支付函數(shù)為 的對(duì)策的對(duì)策,凡使凡使 的戰(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:每個(gè)局中人的優(yōu)戰(zhàn)略集是一個(gè)凸集.n性質(zhì)2:假設(shè) 是乙的優(yōu)戰(zhàn)略,并設(shè) 那么對(duì)甲的任何優(yōu)戰(zhàn)略 ,必有: n 其中 表示甲取戰(zhàn)略 ,乙取戰(zhàn)略 時(shí)的支付.y00,jyx001( ,)niijiA x jxav0( ,)A x jx0j優(yōu)戰(zhàn)略的性質(zhì)n性質(zhì)3:設(shè) 為對(duì)策值, 為甲的任何優(yōu)戰(zhàn)略,有假設(shè)對(duì)某個(gè) ,有 那么對(duì)乙的任何優(yōu)戰(zhàn)略 必有n性質(zhì)4:設(shè) 為對(duì)策值,假設(shè)對(duì)乙的任何優(yōu)戰(zhàn)略 有 那么甲必有一個(gè)優(yōu)戰(zhàn)略 ,使得: vx0j0(,),A xjvy00.jyy0

9、0.jyxv0(,),A xjv優(yōu)戰(zhàn)略的性質(zhì)n性質(zhì)5:假設(shè)矩陣 可寫(xiě)作分塊矩陣 n 假設(shè) 中的每一列嚴(yán)厲超出 中列的凸組合,又設(shè) 中的每一行嚴(yán)厲的被 中行的某個(gè)凸組合超出,那么 , , 均可刪去而不影響甲乙的優(yōu)戰(zhàn)略集.A1234AAAAA2A1A3A1A2A3A4A優(yōu)戰(zhàn)略的計(jì)算n定理:設(shè)對(duì)策值為 , 支付矩陣為 的對(duì)策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、計(jì)算n例: n 可取 可得:113110025A1102M001001/21/20 xy二人普通和有限對(duì)策n雙矩陣對(duì)策:n定義:在對(duì)策 中,假設(shè)有戰(zhàn)略對(duì) ,使得:n 那么稱 為 的一個(gè)非協(xié)作平衡點(diǎn), ; ,X Y A B , ; ,X Y A B ( , )x y(, )X Y()()xAyxAyxXxAyxAyyY ( , )x y存在性定理n定理:對(duì)每個(gè)雙矩陣對(duì)策 至少存在一個(gè)非協(xié)作平衡點(diǎn).n 對(duì) 作改良:, ; ,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)對(duì)策 為非退化時(shí),對(duì)策一定存在平衡點(diǎn).n (矩陣A非退化是指: 每個(gè)方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談判問(wèn)題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(個(gè)體合理性):n公理2(可行性):n公理3(Pareto最優(yōu)性)假設(shè) 且n 那么 .n公理4(無(wú)關(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(線性變換的無(wú)關(guān)性)設(shè)T是由S經(jīng)如下線性變換 n 而得到的,假設(shè) 那么必有n 其中 為正常數(shù), 為常數(shù).n公理6(對(duì)稱性) :假設(shè)S是對(duì)稱的,即假設(shè)n 有 ,且假設(shè) ,那么有 .111111u =u+v =v+( ,)( , )S u vu v11221122( ,)(,)Tuvuv 12, 12, ( , )u vS( , )v uSuvuv談斷定理n定理:對(duì)于一切的談判問(wèn)題 ,存在獨(dú)一的滿足以上公理的 .( ,)S u v“恫嚇問(wèn)題n思索以下的雙矩陣對(duì)策:n 都有獨(dú)立的恫嚇戰(zhàn)略,談判的基點(diǎn):1212(1,4)( 1, 4)( 4, 1)(4

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

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