第11章 對(duì)策論

1、10.對(duì)策論,1.概述,1對(duì)策模型,研究?jī)蓚€(gè)或兩個(gè)以上的參加者在某種對(duì)抗性或競(jìng)爭(zhēng)性的場(chǎng)合下各自作出決策，使自己的一方得到盡可能最有利的結(jié)果。 帶有競(jìng)爭(zhēng)性質(zhì)的現(xiàn)象，稱為對(duì)策現(xiàn)象。 日常生活中： 在政治方面： 正經(jīng)濟(jì)領(lǐng)域內(nèi)： 齊王賽馬,10.對(duì)策論,1.概述,1對(duì)策模型,2對(duì)策現(xiàn)象的三個(gè)基本要素,局中人:,決策者,利益得失者,不是公證人、馬、謀士等，可以是團(tuán)體、國(guó)家等； 聰明的，有理智的； 把那些利益完全一致的參加者們看作一個(gè)局中人； 兩人,多人,結(jié)盟,不結(jié)盟,10.對(duì)策論,1.概述,1對(duì)策模型,2對(duì)策現(xiàn)象的三個(gè)基本要素,局中人: 策略:,自始至終的行動(dòng)方案； 把局中人的策略全體，稱做這個(gè)局中人的

2、策略集合； 例如，在齊王與田忌賽馬的例子中，如果開始就要把各人的三匹馬排好次序，然后依次出賽。各局中人都有六個(gè)策略：(1)(上、中、下)，(2) (上、下、中)(3)(中、上、下)(4)(中、下、上)，(5) (下、中、上)， (6) (下、上、中)。這個(gè)策略全體就是局中人的策略集合。 有限,無(wú)限,10.對(duì)策論,1.概述,1對(duì)策模型,2對(duì)策現(xiàn)象的三個(gè)基本要素,局中人: 策略: 得失:,一局對(duì)策結(jié)束時(shí)，每個(gè)局中人的“得失”是全體局中人所取定的一組策略的函數(shù)。通常稱為“支付函數(shù)”。 從每個(gè)局中人的策略集中各取個(gè)策略，組成的策略組，稱作“局勢(shì)”?！暗檬А笔恰熬謩?shì)”的函數(shù)。 如果全體局中人的“得失”相

3、加總是等于零時(shí)，這個(gè)對(duì)策就稱為零和對(duì)策。否則稱為“非零和對(duì)策”。,10.對(duì)策論,1.概述,1對(duì)策模型,2對(duì)策現(xiàn)象的三個(gè)基本要素,3對(duì)策模型的分類,10.對(duì)策論,2.矩陣對(duì)策（Matrix Games）,1定義：,有限二人零和對(duì)策，即參加對(duì)策的局中人只有兩個(gè)，而每個(gè)局中人都有有限個(gè)可供選擇的策略。而且在任一局勢(shì)中，兩個(gè)局中人的得失之和總等于零（一個(gè)局中人的所得即為另一個(gè)局中人的所失）。局中人的利益是沖突的，也稱為對(duì)抗對(duì)策。,2.矩陣對(duì)策（Matrix Games）,例1：配錢幣游戲： 兩個(gè)局中人1和2各出示一枚錢幣，在不讓對(duì)方看見的情況下，將錢幣放在卓上，若兩個(gè)錢幣都呈正面或都呈反面，則局中人1

4、得1分，局中人2得-1分。若兩個(gè)錢幣一正一反，則局中人2得1分?？捎靡粋€(gè)支付矩陣表示.,2.矩陣對(duì)策（Matrix Games）,例2：“石頭 、剪刀、布”游戲,2.矩陣對(duì)策（Matrix Games）,例3：局中人1從p=0,1,2,3四個(gè)數(shù)中選出一個(gè)數(shù)，局中人2在不知道局中人1出什么數(shù)的情況下從q=0,1,2三個(gè)數(shù)中選出一個(gè)數(shù)。局中人1得到的支付由下支付函數(shù)確定： P=p(q-p)+q(q+p) 或 P=q2-p2+2pq,2.矩陣對(duì)策（Matrix Games）,2數(shù)學(xué)模型,設(shè)局中人1有m個(gè)純策略1,2,m;記集合為S1=1,2,m。同樣，局中人2有n個(gè)純策略，集合為S2=1,2,n 支

5、付矩陣（或贏得矩陣）:局中人贏得矩陣為：,對(duì)策模型記為：S1,S2,A,2.矩陣對(duì)策（Matrix Games）,2數(shù)學(xué)模型,如齊王賽馬： S1=(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中) S=(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中),田忌的支付（贏得）矩陣為-A,3最優(yōu)純策略,例4 對(duì)于一個(gè)矩陣對(duì)策I,S1,S2,A，其中S1=1,2,3,4，S2=1,2,3,求雙方的最優(yōu)策略。 解 由A可以看出，局中人I的最大贏得是16，就是說(shuō)局中人I十分希望自己取得16，就會(huì)出3加入博弈。然而，局中

6、人也在考慮，因?yàn)榫种腥薎有出3的心理狀態(tài)，于是局中人就想出3進(jìn)行博弈，這樣不僅不能使I得到16，反而要輸9(即贏得-9)。同樣，I也會(huì)這樣想，有出3的心理狀態(tài)，于是I就會(huì)出2，結(jié)果不但得不到9，反而要輸5。同樣，如果I出2，則會(huì)出2，使I的贏得達(dá)到最小2。而對(duì)于I來(lái)說(shuō)，如果出2，I的最優(yōu)策略仍然是2，可獲得最大贏得值2。2和2分別是雙方的最優(yōu)策略，a22=2稱為矩陣博弈G的值。它是第2行中最小值，也正好是第2列中的最大值。,3最優(yōu)純策略,對(duì)于給定的S1,S2,A,局中人1希望支付值越大越好，局中人2希望支付值越小越好。 局中人1可選擇i，使他得到的支付不少于：,局中人2可以選擇j，保證他失去的

7、支付不大于:,容易證明:,例1：配錢幣游戲：,-11,3最優(yōu)純策略,-11,例2：“石頭 、剪刀、布”游戲,3最優(yōu)純策略,0=0,例3：,3最優(yōu)純策略,齊王賽馬：,-13,3最優(yōu)純策略,定義：一個(gè)矩陣對(duì)策，如果它的支付矩陣A的元素滿足：,則稱這個(gè)值v為對(duì)策的值。如果純局勢(shì)(i*,j*)使：,則稱(i*,j*)為對(duì)策G的鞍點(diǎn)(Saddle point)，也稱它是對(duì)策G在純策略中的解，i*與j*分別為局中人1和局中人2的最優(yōu)解。,3最優(yōu)純策略,即矩陣對(duì)策有兩個(gè)性質(zhì)：一是鞍點(diǎn)的可交換性，二是各鞍點(diǎn)的值都相等。,定理： 為對(duì)策G的鞍點(diǎn)的充要條件是對(duì)于任意的i,j,有：,如:,定理：若 和 都是矩陣對(duì)策

8、A的鞍點(diǎn)，則 和 也都是它的鞍點(diǎn)，且在鞍點(diǎn)處的值都相等。即：,即該列的最大元素及該行的最小元素.,3最優(yōu)純策略,例5：某單位在秋天要決定冬季取暖用煤貯量問(wèn)題，在正常的冬季氣溫下要消耗15噸，但在較暖與較冷的冬季需要10噸和20噸，假定煤的價(jià)格隨著冬季寒冷程度而有所變動(dòng)，設(shè)在較暖的、正常的、較冷的冬季氣溫下分別為每噸100元，150元，200元，又設(shè)在秋季煤價(jià)是每噸100元，在沒(méi)有關(guān)于當(dāng)年冬季準(zhǔn)確的氣象預(yù)報(bào)條件下，秋季貯煤多少噸才較合理?,解:把采購(gòu)員當(dāng)作局中人I，他有三個(gè)策略：在秋天時(shí)買10噸、15噸與20噸，分別記為a1，a2，a3。 把大自然看作局中人，(可以當(dāng)作理智的局中人來(lái)處理)，大自

9、然(冬季氣溫)有三種策略：出現(xiàn)較暖的、正常的與較冷的冬季，分別記為b1，b2，b3。 現(xiàn)在把該單位冬季取暖用煤實(shí)際費(fèi)用(即秋季購(gòu)煤時(shí)的用費(fèi)、與冬季不夠時(shí)再補(bǔ)購(gòu)的費(fèi)用總和)作為局中人I的贏得，得矩陣如下；,3最優(yōu)純策略,例5：某單位在秋天要決定冬季取暖用煤貯量問(wèn)題，在正常的冬季氣溫下要消耗15噸，但在較暖與較冷的冬季需要10噸和20噸，假定煤的價(jià)格隨著冬季寒冷程度而有所變動(dòng)，設(shè)在較暖的、正常的、較冷的冬季氣溫下分別為每噸100元，150元，200元，又設(shè)在秋季煤價(jià)是每噸100元，在沒(méi)有關(guān)于當(dāng)年冬季準(zhǔn)確的氣象預(yù)報(bào)條件下，秋季貯煤多少噸才較合理?,故對(duì)策的解為(3，3)，即秋季貯煤20噸合理。(決策

10、論中的悲觀準(zhǔn)則),3最優(yōu)純策略,例6：甲、乙雙方談判簽訂一項(xiàng)合同，甲方的“要價(jià)”是25萬(wàn)元，而乙方的“出價(jià)”是20萬(wàn)元，談判陷于僵局。為打破僵局，雙方約定，再各報(bào)一個(gè)價(jià)。以下述價(jià)格成交：誰(shuí)讓步多，取誰(shuí)出的價(jià)；如果雙方讓步相同，則取雙方報(bào)價(jià)的中間值。問(wèn)甲、乙雙方應(yīng)如何報(bào)價(jià)?最后的成交價(jià)是多少?,解 顯然，甲、乙雙方的報(bào)價(jià)都在20萬(wàn)元到25萬(wàn)元之間。不妨取整數(shù)值，甲、乙各有6個(gè)策略：報(bào)價(jià)20,21,25(單位：萬(wàn)元)。由約定知，甲的支付矩陣可用表所示。,(23，22)是鞍點(diǎn)。甲方的最優(yōu)純策略是要價(jià)23萬(wàn)元，乙方的最優(yōu)純策略是出價(jià)22萬(wàn)元，雙方的讓步相同(甲方降低2萬(wàn)元，乙方提高2萬(wàn)元)，最后的成交

11、價(jià)是22.5萬(wàn)元。,2.矩陣對(duì)策（Matrix Games）,4混合策略,一般情況下,二人零和對(duì)策有:,用多大概率選取各個(gè)純策略?,定義1：對(duì)于支付矩陣A=(aij)mxn,局中人1的一個(gè)混合策略就是一組數(shù)xi0,i=1,2,m,滿足： 局中人2的一個(gè)混合策略就是一組數(shù)yj0,j=1,2,n,滿足：,設(shè)X=(x1,x2,xm)和Y=(y1,y2,yn)分別為局中人1和局中人2的混合策略，則局中人1選擇策略i, 局中人2選擇策略j，并且支付為aij的概率為xiyj,局中人1的期望支付為：,2.矩陣對(duì)策（Matrix Games）,4混合策略,定義2：稱數(shù)學(xué)期望E(X,Y)= 為局中人1的贏得，

12、- E(X,Y)為局中人2的贏得，而(X,Y)稱為混合局勢(shì)。,定義3：設(shè)S1*是滿足xi0的一切X=(x1,x2,xm)的混合策略集，S2*是滿足yi0的一切Y=(y1,y2,yn)的混合策略集，即S1*=X，S2*=Y，對(duì)于給定的一個(gè)對(duì)策G=S1,S2,A,稱G*=S1*,S2*,E為G的混合擴(kuò)充。,2.矩陣對(duì)策（Matrix Games）,4混合策略,對(duì)于局中人2，若采取混合策略Y，則可能支出： 因此他應(yīng)選取Y，使支出最?。?對(duì)于局中人1，若采取混合策略X，則只能希望贏得： 因此他應(yīng)選取X，使贏得最大：,2.矩陣對(duì)策（Matrix Games）,4混合策略,定理1：對(duì)于給定的對(duì)策G,有：,

13、定理2：（最小最大值定理、對(duì)策論基本定理）對(duì)于一切矩陣對(duì)策，都有：,定義4：設(shè)G*=S1*,S2*,E為對(duì)策G=S1,S2,A的混合擴(kuò)充，如果有混合局勢(shì) (X*,Y*),使：,則稱V為對(duì)策G的值，而混合局勢(shì)稱為G在混合策略下的解。而X*與Y*分別稱為局中人1和局中人2的最優(yōu)解。,2.矩陣對(duì)策（Matrix Games）,4混合策略,定理3：若矩陣對(duì)策G的值為V，則以下兩組不等式的解就是局中人1和局中人2的最優(yōu)策略：,定理4：設(shè)混合局勢(shì)(X*,Y*)是矩陣對(duì)策G的最優(yōu)解，記對(duì)策值V=E(X*,Y*),則： (1)若 (2)若 (3)若 (4)若,3.矩陣對(duì)策的求解,1.特殊情況下的解,1).如果

14、有鞍點(diǎn)，則鞍點(diǎn)就是最優(yōu)解。 2).如果沒(méi)有鞍點(diǎn)，但事先知道均不為零，則可將兩組不等式化成線性方程組來(lái)求解。,例1.齊王賽馬：,沒(méi)有鞍點(diǎn)，且各個(gè)策略出現(xiàn)的可能性均不為零。 解:令,則有線性方程組：ATX=V, AY=V,3.矩陣對(duì)策的求解,各方程相加，得：,因?yàn)?,所以v=1 ,代入方程得：,3.矩陣對(duì)策的求解,例2：設(shè),解:,且無(wú)鞍點(diǎn)，混合策略的各分量不為零，求最優(yōu)混合策略.,3.矩陣對(duì)策的求解,3).可降低矩陣階數(shù)求解,例3：給定一個(gè)矩陣對(duì)策G=S1,S2,A,求對(duì)策G的值與解。其中：,若所給矩陣中I行的各個(gè)元素比j行各元素小，則對(duì)局中人1來(lái)說(shuō)策略i明顯不如策略j,稱純策略j優(yōu)超純策略j，同

15、理，若I列的元素比j列的對(duì)應(yīng)元素大，則對(duì)局中人2來(lái)說(shuō)策略j優(yōu)超策略i。而明顯不利策略出現(xiàn)的概率為零。,3.矩陣對(duì)策的求解,4).化簡(jiǎn)矩陣，使矩陣的元素盡可能多地變成零.,定理1：設(shè)兩個(gè)矩陣對(duì)策：G1=(S1,S2,A), G2=(S1,S2,B),其中A=(aij)mxn, B=(bij)mxn,若bij= aij+d,其中d為一常數(shù)。則G1和G2有相同的混合策略，且V2=V1+d。（V1和V2分別為G1和G2的對(duì)策值）,3.矩陣對(duì)策的求解,4).化簡(jiǎn)矩陣，使矩陣的元素盡可能多地變成零.,例4：給定一個(gè)矩陣對(duì)策G=S1,S2,A,求對(duì)策G的值與解。其中：,解：1）直接解：,3.矩陣對(duì)策的求解,

16、解：2) 陣中各元素加1，得：,2.線性規(guī)劃法求解,其中： 令:,對(duì)于擴(kuò)充后的矩陣對(duì)策來(lái)說(shuō)，求最優(yōu)解就是解下列兩個(gè)不等式組：,2.線性規(guī)劃法求解,即求線性規(guī)劃：,因 =1/V，所以V=3,又因 ， 得：,解：,例5：給定一個(gè)矩陣對(duì)策G=S1,S2,A, 求對(duì)策G的值與解。其中：,4.合作對(duì)策,定義11-6. n人合作對(duì)策模型：設(shè)集合I=1,2,n,若對(duì)任意的 ,總存在V(S)-收益（實(shí)值）函數(shù)，滿足：,稱（I，v）為n人合作博弈（Cooperative n-person game），v為博弈的的特征函數(shù)。n人合作博弈是指定義了特征函數(shù)的I中n個(gè)人的合作分配結(jié)果，用向量表示:,4.合作對(duì)策,例（

17、三人經(jīng)商問(wèn)題）：A、B、C三人經(jīng)商，若單干，每人獲利1元，A和B合作可獲利7元，A和C合作可獲利5元，B和C合作可獲利4元，三個(gè)合作可合可獲10元，問(wèn)三人合作時(shí)怎樣合理分配10元的收入？,方案: A B C AB AC BC ABC 效益: 1 1 1 7 5 4 10,設(shè)x1,x2,x3為A,B,C各得的分配, 應(yīng)滿足： x1+x2+x3=10， x1, x2, x31 , x1+x2=7, x1 +x3=5, x2+x3=4,滿足上式的解有無(wú)窮多個(gè)，如（5,3,2），(4,3,3).,4.合作對(duì)策,設(shè)V(S)為集合S中元素合作的收益，則： A：V(A,B,C)-V(B,C)=10-4=6,

18、 V(A,B)- V(B)=6, V(A,C)-V(C)=4 B：V(A,B,C)-V(A,C)=5, V(A,B)-V(A)=6, V(B,C)-V(C)=3 C：V(A,B,C)-V(A,B)=3, V(A,C)-V(A)=4, V(B,C)-V(B)=3,方案: A B C AB AC BC ABC 效益: 1 1 1 7 5 4 10,A，B，C的總貢獻(xiàn)為:16,14,10, 因此x1:x2:x3=:16:14:10, 且x1+x2+x3=10,得： x1=10*16/(16+14+10)=4, x2=10*14/40=3.5, x3=10*10/40=2.5,n人合作對(duì)策模型,Sha

19、play公理: 設(shè)（I，v）給定的一個(gè)n人合作博弈，則由v決定的一個(gè)分配應(yīng)滿足： 1). 合作獲利對(duì)每個(gè)人的分配與賦予他的記號(hào)i無(wú)關(guān); 2). 各人分配之和等于合作獲利; 3). 如果i對(duì)于每一個(gè)他參加的合作都沒(méi)有貢獻(xiàn)，那么他不應(yīng)從全體的合作獲利中得到報(bào)酬; 4). 當(dāng)n人同時(shí)進(jìn)行兩項(xiàng)合作時(shí)，每人獲利可分兩項(xiàng)合作計(jì)算,n人合作對(duì)策模型,Shaplay證明了滿足上四假設(shè)的分配是有唯一解：,其中：Si是I中包含i的所有子集; |S|是S的人數(shù); 是加權(quán)因子 可看作i對(duì)合作S的貢獻(xiàn),稱 為由V定義的合作的Shaplay值. 其意義為：對(duì)于一個(gè)n人合作對(duì)策模型，其第i個(gè)人的收入應(yīng)按照i對(duì)各種形式的合作

20、的貢獻(xiàn)的加權(quán)平均來(lái)確定。,Shaplay n人合作對(duì)策模型,三人經(jīng)商問(wèn)題 （對(duì)于第一個(gè)人）,1=1*1/3+6*1/6+4*1/6+6*1/3=4 同理：2=3.5, 3=2.5,4.合作對(duì)策,設(shè)Q為污水量（T/S）,L為管道長(zhǎng)（km） 已知：建處理廠的費(fèi)用:CT=730Q0.712; 鋪管道費(fèi)用:Cp=6.6Q0.51L; 污水量:Q1=5，Q2=3，Q3=5; 距離:L12=20，L23=38。,問(wèn)題:沿河有三鎮(zhèn)1、2、3，污水需經(jīng)處理后流入河中。若聯(lián)合建廠，廠址應(yīng)在下游，問(wèn)如何聯(lián)合及如何投資？,污水處理問(wèn)題,三鎮(zhèn)聯(lián)合建一個(gè)處理廠投資方案：,1）平分：5560/3=18531600 城2反對(duì) 2）城3提出：建廠費(fèi)按三城的污水量之比5:3:5分擔(dān)，管道費(fèi)由城1,