第10章-對(duì)策論課件

第十章對(duì)策論

§1.引言

1．對(duì)策模型

研究?jī)蓚€(gè)或兩個(gè)以上的參加者在某種對(duì)抗性或競(jìng)爭(zhēng)性的場(chǎng)合下各自作出決策，使自己的一方得到盡可能最有利的結(jié)果。帶有競(jìng)爭(zhēng)性質(zhì)的現(xiàn)象，稱(chēng)為對(duì)策現(xiàn)象。日常生活中：下棋、打牌在政治方面：選舉策略、外交策略在經(jīng)濟(jì)領(lǐng)域：談判策略、價(jià)格策略田忌賽馬2．對(duì)策現(xiàn)象的三個(gè)基本要素

（1）局中人:決策者,利益得失者聰明的、理智的，不存在利用他人失誤的可能性；可以是國(guó)家、團(tuán)體等；可以不是人；把那些利益完全一致的參加者們看作一個(gè)局中人；在田忌賽馬例子中，局中人是田忌、齊王；不是公證人、馬、謀士等局中人的策略全體，稱(chēng)做這個(gè)局中人的策略集合；有限,無(wú)限例如，在齊王與田忌賽馬的例子中，如果一開(kāi)始就要把各人的三匹馬排好次序，然后依次出賽。各局中人都有六個(gè)策略：(1)(上、中、下)，(2)(上、下、中)，(3)(中、上、下)，(4)(中、下、上)，(5)(下、中、上)，(6)(下、上、中)。這個(gè)策略全體就是局中人的策略集合。

2．對(duì)策現(xiàn)象的三個(gè)基本要素

（1）局中人:決策者,利益得失者（2）策略：自始至終的行動(dòng)方案從每個(gè)局中人的策略集中各取一個(gè)策略，組成的策略組，稱(chēng)作“局勢(shì)”?！暗檬А笔恰熬謩?shì)”的函數(shù)。如果全體局中人的“得失”相加總是等于零時(shí)，這個(gè)對(duì)策就稱(chēng)為零和對(duì)策。否則稱(chēng)為“非零和對(duì)策”。在田忌賽馬的例子中，若齊王選定策略（上、中、下），田忌選定策略（下、上、中），則田忌贏得1，齊王贏得-1

2．對(duì)策現(xiàn)象的三個(gè)基本要素

（1）局中人:決策者,利益得失者（2）策略：自始至終的行動(dòng)方案（3）贏得函數(shù)（支付函數(shù)）：一局對(duì)策結(jié)束時(shí)，每個(gè)局中人的“得失”是全體局中人所取定的一組策略的函數(shù)。3．對(duì)策模型的分類(lèi)§2.矩陣對(duì)策（MatrixGames）

1．定義：矩陣對(duì)策即二人有限零和對(duì)策，指參加對(duì)策的局中人只有兩個(gè)，每個(gè)局中人都有有限個(gè)可供選擇的策略。而且在任一局勢(shì)中，兩個(gè)局中人的得失之和總等于零（一個(gè)局中人的所得即為另一個(gè)局中人的所失）。局中人的利益是沖突的，也稱(chēng)為對(duì)抗對(duì)策。如田忌賽馬。

第十章對(duì)策論

例1：配錢(qián)幣游戲兩個(gè)局中人1和2各出示一枚錢(qián)幣，在不讓對(duì)方看見(jiàn)的情況下，將錢(qián)幣放在桌上，若兩個(gè)錢(qián)幣都呈正面或都呈反面，則局中人1得1分，局中人2得-1分。若兩個(gè)錢(qián)幣一正一反，則局中人2得1分，局中人1得-1分。則局中人1的得分可用下表表示：

局中人2局中人11（正）2（反）1（正）1-12（反）-11A=例2：“石頭、剪刀、布”游戲局中人2局中人11（石頭）2（剪刀）3（布）1（石頭）01-12（剪刀）-1013（布）1-10A=例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

局中人2q局中人1p01200141-1272-4183-9-27A=2．?dāng)?shù)學(xué)模型

設(shè)局中人1有m個(gè)純策略α1,α2,…,αm，記集合為S1={α1,α2,…,αm}；同樣，局中人2有n個(gè)純策略β1,β2,…,βn

，集合為S2={β1,β2,…,βn}局中人1的贏得矩陣為：

對(duì)策模型記為Ｇ＝｛S1,S2,A｝

在田忌賽馬例子中

S1={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}

S２={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}齊王的贏得矩陣為A，田忌的支付（贏得）矩陣為-A3．最優(yōu)純策略例4

對(duì)于一個(gè)矩陣對(duì)策Ｇ＝｛S1,S2,A｝,其中S1={α1,α2,α3,α4},S2={β1,β2,β3}求雙方的最優(yōu)策略。解:由A可以看出，局中人I的最大贏得是16，就是說(shuō)局中人I十分希望自己取得16，就會(huì)出α3加入博弈。然而，局中人Ⅱ也在考慮，因?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稱(chēng)為矩陣博弈G的值。它是第2行中最小值，也正好是第2列中的最大值。

對(duì)于給定的Ｇ＝｛S1,S2,A｝,局中人1希望支付值越大越好，局中人2希望支付值越小越好。局中人1可選擇i，使他得到的支付不少于：局中人2可以選擇j，保證他失去的支付不大于:容易證明:例1：配錢(qián)幣游戲-1<1

局中人2局中人11（正）2（反）1（正）1-12（反）-11-1<1例2：“石頭、剪刀、布”游戲局中人2局中人11（石頭）2（剪刀）3（布）1（石頭）01-12（剪刀）-1013（布）1-100=0例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

局中人2q局中人1p01200141-1272-4183-9-27田忌賽馬：-1<3定義：一個(gè)矩陣對(duì)策，如果它的支付矩陣A的元素滿(mǎn)足：

則稱(chēng)這個(gè)值v為對(duì)策的值。如果純局勢(shì)(i*,j*)使：則稱(chēng)(i*,j*)為對(duì)策G的鞍點(diǎn)(Saddlepoint)，也稱(chēng)它是對(duì)策G在純策略中的解，i*與j*分別為局中人1和局中人2的最優(yōu)解。

即矩陣對(duì)策有兩個(gè)性質(zhì)：鞍點(diǎn)的可交換性，無(wú)差異性。定理：為對(duì)策G的鞍點(diǎn)的充要條件是對(duì)于任意的i,j,有：如:定理：若和都是矩陣對(duì)策A的鞍點(diǎn)，則和也都是它的鞍點(diǎn)，且在鞍點(diǎn)處的值都相等。即：即為該列的最大元素及該行的最小元素.

例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)條件下，秋季貯煤多少?lài)嵅泡^合理?解:把采購(gòu)員當(dāng)作局中人I，他有三個(gè)策略：在秋天時(shí)買(mǎi)10噸、15噸與20噸，分別記為a1，a2，a3。把大自然看作局中人Ⅱ，(可以當(dāng)作理智的局中人來(lái)處理)，大自然(冬季氣溫)有三種策略：出現(xiàn)較暖的、正常的與較冷的冬季，分別記為b1，b2，b3。

故對(duì)策的解為(3，3)，即秋季貯煤20噸合理?，F(xiàn)在把該單位冬季取暖用煤實(shí)際費(fèi)用(即秋季購(gòu)煤時(shí)的用費(fèi)、與冬季不夠時(shí)再補(bǔ)購(gòu)的費(fèi)用總和)作為局中人I的贏得，得例5：……，在正常的冬季氣溫下要消耗15噸，但在較暖與較冷的冬季需要10噸和20噸，假定煤的價(jià)格隨著冬季寒冷程度而有所變動(dòng)，設(shè)在較暖的、正常的、較冷的冬季氣溫下分別為每噸100元，150元，200元，又設(shè)在秋季煤價(jià)是每噸100元……例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)元)，最后的成交價(jià)是22.5萬(wàn)元。4．混合策略

一般情況下,二人零和對(duì)策有:不存在純策略意義上的最優(yōu)解，考慮用多大概率選取各個(gè)純策略?

定義1：對(duì)于支付矩陣A=(aij)mxn,局中人1的一個(gè)混合策略就是一組數(shù)xi≥0,i=1,2,…,m,滿(mǎn)足：；局中人2的一個(gè)混合策略就是一組數(shù)yj≥0,j=1,2,…,n,滿(mǎn)足：設(shè)X=(x1,x2,…,xm)和Y=(y1,y2,…,yn)分別為局中人1和局中人2的混合策略，則局中人1選擇策略i,局中人2選擇策略j，并且支付為aij的概率為xiyj

,局中人1的期望支付為：定義2：稱(chēng)數(shù)學(xué)期望E(X,Y)=

為局中人1的贏得，-E(X,Y)為局中人2的贏得，而(X,Y)稱(chēng)為混合局勢(shì)。定義3：設(shè)S1*是滿(mǎn)足xi≥0的一切X=(x1,x2,…,xm)的混合策略集，S2*是滿(mǎn)足yi≥0的一切Y=(y1,y2,…,yn)的混合策略集，即S1*={X}，S2*={Y}，對(duì)于給定的一個(gè)對(duì)策G={S1,S2,A},稱(chēng)G*={S1*,S2*,E}為G的混合擴(kuò)充（拓展）。（P298，無(wú)須區(qū)別）對(duì)于局中人2，若采取混合策略Y，則可能支出：因此他應(yīng)選取Y，使支出最?。簩?duì)于局中人1，若采取混合策略X，則只能希望贏得：因此他應(yīng)選取X，使贏得最大：定理1：對(duì)于給定的對(duì)策G,有：

定理2：（最小最大值定理、對(duì)策論基本定理）對(duì)于一切矩陣對(duì)策，都有：

定義4：設(shè)G*={S1*,S2*,E}為對(duì)策G={S1,S2,A}的混合擴(kuò)充，如果有混合局勢(shì)(X*,Y*),使：則稱(chēng)V為對(duì)策G的值，而混合局勢(shì)稱(chēng)為G在混合策略下的解。而X*與Y*分別稱(chēng)為局中人1和局中人2的最優(yōu)解。定理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)若

第十章對(duì)策論

§3.矩陣對(duì)策的求解1.特殊情況下的解

1).如果有鞍點(diǎn)，則鞍點(diǎn)就是最優(yōu)解。2).如果沒(méi)有鞍點(diǎn)，但事先知道均不為零，則可將兩組不等式化成線(xiàn)性方程組來(lái)求解。例1：設(shè)

解:無(wú)鞍點(diǎn)，混合策略的各分量不為零，求最優(yōu)混合策略.3).可降低矩陣階數(shù)求解

例2：給定一個(gè)矩陣對(duì)策G={S1,S2,A},求對(duì)策G的值與解。其中若所給矩陣中i行的各個(gè)元素比j行各元素小，則對(duì)局中人1來(lái)說(shuō)策略i明顯不如策略j,稱(chēng)純策略j優(yōu)超純策略i；同理，若i列的元素比j列的對(duì)應(yīng)元素大，則對(duì)局中人2來(lái)說(shuō)策略j優(yōu)超策略i。而明顯不利策略出現(xiàn)的概率為