第11章對策論

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

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

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

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

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

6、人也在考慮，因為局中人I有出3的心理狀態(tài)，于是局中人就想出3進行博弈，這樣不僅不能使I得到16，反而要輸9(即贏得-9)。同樣，I也會這樣想，有出3的心理狀態(tài)，于是I就會出2，結(jié)果不但得不到9，反而要輸5。同樣，如果I出2，則會出2，使I的贏得達到最小2。而對于I來說，如果出2，I的最優(yōu)策略仍然是2，可獲得最大贏得值2。2和2分別是雙方的最優(yōu)策略，a22=2稱為矩陣博弈G的值。它是第2行中最小值，也正好是第2列中的最大值。,3最優(yōu)純策略,對于給定的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)純策略,定義：一個矩陣對策，如果它的支付矩陣A的元素滿足：,則稱這個值v為對策的值。如果純局勢(i*,j*)使：,則稱(i*,j*)為對策G的鞍點(Saddle point)，也稱它是對策G在純策略中的解，i*與j*分別為局中人1和局中人2的最優(yōu)解。,3最優(yōu)純策略,即矩陣對策有兩個性質(zhì)：一是鞍點的可交換性，二是各鞍點的值都相等。,定理： 為對策G的鞍點的充要條件是對于任意的i,j,有：,如:,定理：若 和 都是矩陣對策

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

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

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

11、價是22.5萬元。,2.矩陣對策（Matrix Games）,4混合策略,一般情況下,二人零和對策有:,用多大概率選取各個純策略?,定義1：對于支付矩陣A=(aij)mxn,局中人1的一個混合策略就是一組數(shù)xi0,i=1,2,m,滿足： 局中人2的一個混合策略就是一組數(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.矩陣對策（Matrix Games）,4混合策略,定義2：稱數(shù)學(xué)期望E(X,Y)= 為局中人1的贏得，

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

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

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

15、理，若I列的元素比j列的對應(yīng)元素大，則對局中人2來說策略j優(yōu)超策略i。而明顯不利策略出現(xiàn)的概率為零。,3.矩陣對策的求解,4).化簡矩陣，使矩陣的元素盡可能多地變成零.,定理1：設(shè)兩個矩陣對策：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的對策值）,3.矩陣對策的求解,4).化簡矩陣，使矩陣的元素盡可能多地變成零.,例4：給定一個矩陣對策G=S1,S2,A,求對策G的值與解。其中：,解：1）直接解：,3.矩陣對策的求解,

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

17、三人經(jīng)商問題）：A、B、C三人經(jīng)商，若單干，每人獲利1元，A和B合作可獲利7元，A和C合作可獲利5元，B和C合作可獲利4元，三個合作可合可獲10元，問三人合作時怎樣合理分配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,滿足上式的解有無窮多個，如（5,3,2），(4,3,3).,4.合作對策,設(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的總貢獻為: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人合作對策模型,Sha

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

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