第10章-對策論課件

第十章對策論

§1.引言

1．對策模型

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

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

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

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

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

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

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

第十章對策論

例1：配錢幣游戲兩個局中人1和2各出示一枚錢幣，在不讓對方看見的情況下，將錢幣放在桌上，若兩個錢幣都呈正面或都呈反面，則局中人1得1分，局中人2得-1分。若兩個錢幣一正一反，則局中人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四個數(shù)中選出一個數(shù)，局中人2在不知道局中人1出什么數(shù)的情況下從q=0,1,2三個數(shù)中選出一個數(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個純策略α1,α2,…,αm，記集合為S1={α1,α2,…,αm}；同樣，局中人2有n個純策略β1,β2,…,βn

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

對策模型記為Ｇ＝｛S1,S2,A｝

在田忌賽馬例子中

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

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

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

對于給定的Ｇ＝｛S1,S2,A｝,局中人1希望支付值越大越好，局中人2希望支付值越小越好。局中人1可選擇i，使他得到的支付不少于：局中人2可以選擇j，保證他失去的支付不大于:容易證明:例1：配錢幣游戲-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四個數(shù)中選出一個數(shù)，局中人2在不知道局中人1出什么數(shù)的情況下從q=0,1,2三個數(shù)中選出一個數(shù)。局中人1得到的支付由下支付函數(shù)確定：

P=p(q-p)+q(q+p)

或P=q2-p2+2pq

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

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

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

例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)作理智的局中人來處理)，大自然(冬季氣溫)有三種策略：出現(xiàn)較暖的、正常的與較冷的冬季，分別記為b1，b2，b3。

故對策的解為(3，3)，即秋季貯煤20噸合理?，F(xiàn)在把該單位冬季取暖用煤實際費用(即秋季購煤時的用費、與冬季不夠時再補購的費用總和)作為局中人I的贏得，得例5：……，在正常的冬季氣溫下要消耗15噸，但在較暖與較冷的冬季需要10噸和20噸，假定煤的價格隨著冬季寒冷程度而有所變動，設(shè)在較暖的、正常的、較冷的冬季氣溫下分別為每噸100元，150元，200元，又設(shè)在秋季煤價是每噸100元……例6：甲、乙雙方談判簽訂一項合同，甲方的“要價”是25萬元，而乙方的“出價”是20萬元，談判陷于僵局。為打破僵局，雙方約定，再各報一個價。以下述價格成交：誰讓步多，取誰出的價；如果雙方讓步相同，則取雙方報價的中間值。問甲、乙雙方應(yīng)如何報價?最后的成交價是多少?

解：顯然，甲、乙雙方的報價都在20萬元到25萬元之間。不妨取整數(shù)值，甲、乙各有6個策略：報價20,21,…,25(單位：萬元)。由約定知，甲的支付矩陣可用表所示。

(23，22)是鞍點。甲方的最優(yōu)純策略是要價23萬元，乙方的最優(yōu)純策略是出價22萬元，雙方的讓步相同(甲方降低2萬元，乙方提高2萬元)，最后的成交價是22.5萬元。4．混合策略

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

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

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

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

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

定義4：設(shè)G*={S1*,S2*,E}為對策G={S1,S2,A}的混合擴充，如果有混合局勢(X*,Y*),使：則稱V為對策G的值，而混合局勢稱為G在混合策略下的解。而X*與Y*分別稱為局中人1和局中人2的最優(yōu)解。定理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).如果有鞍點，則鞍點就是最優(yōu)解。2).如果沒有鞍點，但事先知道均不為零，則可將兩組不等式化成線性方程組來求解。例1：設(shè)

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

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