【正文】 第八章 對策與決策模型 浙江大學(xué)數(shù)學(xué)建?；? 第八章 對策與決策模型 對策與決策是人們生活和工作中經(jīng)常會遇到的擇優(yōu)活動。人們在處理一個問題時，往往會面臨幾種情況，同時又存在幾種可行方案可供選擇，要求根據(jù)自己的行動目的選定一種方案，以期獲得最佳的結(jié)果。 有時，人們面臨的問題具有競爭性質(zhì)，如商業(yè)上的競爭、體育中的比賽和軍事行動、政治派別的斗爭等等。這時競爭雙方或各方都要發(fā)揮自己的優(yōu)勢，使己方獲得最好結(jié)果。因而雙方或各方都要根據(jù)不同情況、不同對手做出自己的決擇，此時的決策稱為對策。在有些情況下，如果我們把可能出現(xiàn)的若干種情況也看作是競爭對手可采取的幾種策略，那么也可以把決策問題當(dāng)作對策問題來求解。 167。 對策問題 對策問題的特征是參與者為利益相互沖突的各方，其結(jié)局不取決于其中任意一方的努力而是各方所采取的策略的綜合結(jié)果。 先考察幾個實際例子。 例 （田忌賽馬） 田忌賽馬是大多數(shù)人都熟知的故事，傳說戰(zhàn)國時期齊王欲與大將田忌賽馬，雙方約定每人挑選上、中、下三個等級的馬各一匹進(jìn)行比賽，每局賭金為一千金。齊王同等級的馬均比田忌的馬略勝一籌，似乎必勝無疑。田忌的朋友孫臏給他出了一個主意，讓他用下等馬比齊王的上等馬，上等馬對齊王的中等馬，中等馬對齊王的下等馬，結(jié)果田忌二勝一敗，反而贏了一千金。 例 （石頭 — 剪子 — 布） 這是一個大多數(shù)人小時候都玩過的游戲。游戲雙方只能選石頭、剪子、布中的一種，石頭贏剪子，剪子贏布，而布又贏石頭，贏者得一分，輸者失一分，雙方相同時不得分，見下表。 表 石頭 剪子 布 石頭 0 1 － 1 剪子 － 1 0 1 布 1 － 1 0 例 （囚犯的困惑） 警察同時逮捕了兩人并分開關(guān)押，逮捕的原因是他們持有大量偽幣，警方懷疑他們偽造錢幣，但沒有找到充分證據(jù)，希望他們能自己供認(rèn)，這兩個人都知道：如果他們雙方都不供認(rèn)，將被以使用和持有大量偽幣罪被各判刑 18個月；如果雙方都供認(rèn)偽造了錢幣，將各被判刑 3年；如果一方供認(rèn)另一方不供認(rèn)，則供認(rèn)方將被從寬處理而免刑，但另一方面將被判刑 7年。將嫌疑犯 A、 B被判刑的幾種可能情況列表如下 ： 表 嫌疑犯 B 供認(rèn) 不供認(rèn) 嫌疑犯 A 供認(rèn) 不供認(rèn) （ 3， 3） （ 0， 7） （ 7， 0） （ ， ） 表中每對數(shù)字表示嫌疑犯 A、 B被判刑的年數(shù)。如果兩名疑犯均擔(dān)心對方供認(rèn)并希望受到最輕的懲罰，最保險的辦法自然是承認(rèn)制造了偽幣。 一、對策的基本要素 （ 1） 局中人 。參加決策的各方被稱為決策問題的局中人，一個決策總是可以包含兩名局中人（如棋類比賽、人與大自然作斗爭等），也可以包含多于兩名局中人（如大多數(shù)商業(yè)中的競爭、政治派別間的斗爭）。局中人必須要擁用可供其選擇并影響最終結(jié)局的策略，在例 ，局中人是 A、 B兩名疑犯，警方不是局中人。兩名疑犯最終如何判刑取決于他們各自采取的態(tài)度，警方不能為他們做出選擇。 從這些簡單實例中可以看出對策現(xiàn)象中包含的幾個基本要素。 （ 2） 策略集合 。局中人能采取的可行方案稱為策略，每一局中人可采取的全部策略稱為此局中人的策略集合。對策問題中，對應(yīng)于每一局中人存在著一個策略集合，而每一策略集合中至少要有兩個策略，否則該局中人可從此對策問題中刪去，因為對他來講，不存在選擇策略的余地。應(yīng)當(dāng)注意的是，所謂策略是指在整個競爭過程中對付他方的完整方法，并非指競爭過程中某步所采取的具體局部辦法。例如下棋中的某步只能看和一個完整策略的組成部分，而不能看成一個完整的策略。當(dāng)然，有時可將它看成一個多階段對策中的子對策。策略集合可以是有限集也可以是無限集。策略集為有限集時稱為有限對策，否則稱為無限對策。 記局中人 i的策略集合為 Si。當(dāng)對策問題各方都從各自的策略集合中選定了一個策略后，各方采取的策略全體可用一矢量 S表示，稱之為一個純局勢（簡稱局勢）。 例如 ，若一對策中包含 A、 B兩名局中人，其策略集合分別為SA = { 1,…, m}， SB = { 1,…, n}。若 A選擇策略 i而 B選策略 j，則（ i, j）就構(gòu)成此對策的一個純局勢。顯然， SA與SB一共可構(gòu)成 m n個純局勢，它們構(gòu)成表 。對策問題的全體純局勢構(gòu)成的集合 S稱為此對策問題的局勢集合。 ? ? ? ? ?? ? ?( m, n) … ( m, j) … ( m, 2) ( m, 1) m … … … … … … … ( i, n) … ( i, j) … ( i, 2) ( i , 1) i … … … … … … … ( 2, n) … ( 2, j) … ( 2, 2) ( 2, 1) 2 ( 1, n) … ( 1, j) … ( 1, 2) ( 1, 1) 1 A的策略 n … J … 2 1 B的策略 ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?（ 3） 贏得函數(shù)（或稱支付函數(shù)）。對策的結(jié)果用矢量表示，稱之為贏得函數(shù)。贏得函數(shù) F為定義在局勢集合 S上的矢值函數(shù)，對于 S中的每一純局勢 S， F（ S）指出了每一局中人在此對策結(jié)果下應(yīng)贏得（或支付）的值。綜上所述，一個對策模型由局中人、策略集合和贏得函數(shù)三部分組成。記局中人集合為 I = {1,?, k}，對每一 i∈ I，有一策略集合 Si，當(dāng) I中每一局中人 i選定策略后得一個局勢 s；將 s代入贏得函數(shù) F，即得一矢量 F(s) = ( F1(s),?, Fk(s))，其中 Fi(s)為在局勢 s下局中人 i的贏得（或支付）。 本節(jié)討論只有兩名局中人的對策問題，即兩人對策，其結(jié)果可以推廣到一般的對策模型中去。對于只有兩名局中人的對策問題，其局勢集合和贏得函數(shù)均可用表格表示。例如，表 給出了例 。 二、零和對策 存在一類特殊的對策問題。在這類對策中，當(dāng)純局勢確定后，A之所得恰為 B之所失，或者 A之所失恰為 B之所得，即雙方所得之和總為零。在零和對策中，因 F1(s)= － F2(s)，只需指出其中一人的贏得值即可，故贏得函數(shù)可用贏得矩陣表示。例如若A有 m種策略， B有 n種策略，贏得矩陣 11 12 121 22 212nnmnm m mna a aa a aRa a a????????????表示若 A選取策略 i而 B選取策略 j，則 A之所得為 aij（當(dāng) aij0時為支付）。 在有些兩人對策的贏得表中， A之所得并非明顯為 B之所失，但雙方贏得數(shù)之和為一常數(shù)。例如在表 ，無論 A、 B怎樣選取策略，雙方贏得總和均為 10，此時，若將各人贏得數(shù)減去兩人的平均贏得數(shù)，即可將贏得表化為零和贏得表。表 對策在轉(zhuǎn)化為零和對策后，具有贏得矩陣 表 局中人 B 1 2 3 局中人 A 1 (8, 2) (1, 9) (7, 3) 2 (4, 6) (9, 1) (3, 7) 3 (2, 8) (6, 4) (8, 2) 4 (6, 4) (4, 6) (6, 4) 3 4 21 4 23 1 31 1 1R??????????????????給定一個兩人對策只需給出局中人 A、 B的策略集合 SA、SB及表示雙方贏得值的贏得矩陣 R。綜上所述，當(dāng)遇到零和對策或可轉(zhuǎn)化為零和對策的問題時， R可用通常意義下的矩陣表示，否則 R的元素為一兩維矢量。 故兩人對策 G又可稱為矩陣對策并可簡記成 G = { SA, SB, R } 例 給定 G = { SA, SB, R}，其中 SA = { 1, 2, 3}， SB = { 1, 2, 3, 4} ? ?? ? ? ? ?1 2 3 4123 1 2 6 3 0 2 21 4 2 1 8 1 06 0 1 0 1 6R? ? ? ?????????????????從 R中可以看出，若 A希望獲得最大贏利 30，需采取策略 1，但此時若 B采取策略 4， A非但得不到 30，反而會失去 22。為了穩(wěn)妥，雙方都應(yīng)考慮到對方有使自己損失最大的動機(jī)，在最壞的可能中爭取最好的結(jié)果。局中人 A采取策略 3時，最壞的贏得結(jié)果分別為 ??? ? ?min { 12, － 6, 30, － 22 } = － 22 min { 14, 2, 18, 10} =2 min {－ 6, 0, － 10, 16} = － 10 其中最好的可能為 max {－ 22,2,－ 10}=2。如果 A采取策略 2，無論 B采取什么策略， A的贏得均不會少于 2. ?B采取各方案的最大損失為 max {12,14, － 6}=14， max {－ 6,2,0}=2， max {30,18, － 10}=30和 max {－ 22,10,16} =16。當(dāng) B采取策略 2時，其損失不會超過 2。注意到在贏得矩陣中， 2既是所在行中的最小元素又是所在列中的最大元素。此時，只要對方不改變策略，任一局中人都不可能通過變換策略來增大贏得或減小損失，稱這樣的局勢為對策的一個穩(wěn)定點或穩(wěn)定解，（注：也被稱為鞍點） ?定義 對于兩人對策 G = { SA, SB, R}，若有 ，則稱 G具有穩(wěn)定解，并稱 VG為對策 G的值。若純局勢（ ）使得 ，則稱（ ）為對策 G的鞍點或穩(wěn)定解，贏得矩陣中與（ ）相對應(yīng)的元素 稱為贏得矩陣的鞍點， 與 分別稱為局中人 A與 B的最優(yōu)策略。 m a x m in m in m a xi j i j Gjjiia a V?**,ij??**m in m a xi j ij Gj ja a V??**,ij?? **,ij??**ija *i? *j?對（ ）式中的贏得矩陣，容易發(fā)現(xiàn)不存在具有上述性質(zhì)的鞍點。給定一個對策 G，如何判斷它是否具有鞍點呢？為了回答這一問題，先引入下面的極大極小原理。 定理 設(shè) G = { SA, SB, R }， 記 ， 則必有 μ+ν≤0 m a x m in m in m a xij ijjjiiaa??? ? ?，證明 : ， m a x m in (ijij a? ?? )易見 μ為 A的最小贏得， ν為 B的最小贏得， 由于 G是零和對策，故 μ+ν≤0必成立。 定理 零和對策 G具有穩(wěn)定解的充要條件為 μ +ν = 0。 證明： （充分性） 由 μ 和 ν 的定義可知，存在一行（例如 p行） μ為 p行中的最小元素且存在一列（例如 q列），－ ν 為 q列中的最大元素。故有 apq≥ μ 且 apq≤ － ν 又因 μ +ν = 0，所以 μ =－ ν ，從而得出 apq=μ ， apq為贏得矩陣的鞍點，（ p, q）為 G的穩(wěn)定解。 ? ?（必要性） 若 G具有穩(wěn)定解（ p , q ），則 apq為贏得矩陣的鞍點。故有 ? ?m a x m in m inij p j p qjji a a a? ? ? ?m in m a x m a xij iq p qj iia a a?? ? ? ?從而可得 μ +ν ≥0 ，但根據(jù)定理 ， μ +ν ≤0 必成立，故必有 μ +ν =0。 上述定理給出了對策問題有穩(wěn)定解（簡稱為解）的充要條件。當(dāng)對策問題有解時，其解可以不唯一。例如，若 1 2 3 4 51234 9 4 3 1 1010 1 15 1 85 1 8 2 64 1 5 1 3R? ? ? ? ?????? ? ? ????????? ? ???則易見，（ 2, 2），（ 2, 4），（ 4, 2），（ 4, 4）均為此對策問題的解。 一般又可以證明。 ? ? ? ?? ? ? ?定理 對策問題的解具有下列性質(zhì)： （ 1）無差別性。若（ , ）與（ , ）同為對策 G的解，則必有