運(yùn)籌學(xué) 其他對(duì)策模型

其他對(duì)策模型姓名專業(yè)7.1陣地對(duì)策7.1陣地對(duì)策陣地對(duì)策

對(duì)策論中所謂局中人的一個(gè)策略是指局中人的一個(gè)完整地行動(dòng)方案，例如賽馬的例子中，出賽馬的一個(gè)次序是一個(gè)完整地行動(dòng)方案。但是有的對(duì)策現(xiàn)象中完整地行動(dòng)方案是不容易說清楚的，例如下象棋，要走很多步，每步又有很多可供選擇的走法，那么一個(gè)由始至終的行動(dòng)方案怎么說得清楚呢？但是這種類型的對(duì)策現(xiàn)象有它的特點(diǎn)，即它規(guī)定了各步該誰走，而走的局中人又有多少種走法可選擇，另外走的局中人走時(shí)是否能知道別的局中人在他此步之前是怎么走的信息等等。因此根據(jù)此類對(duì)策現(xiàn)象的特點(diǎn)來形成數(shù)學(xué)模型也是對(duì)策論的工作之一，由于這類對(duì)策現(xiàn)象是一步一步走的，所以給它起個(gè)名字叫“陣地對(duì)策”。7.1陣地對(duì)策特點(diǎn)

假如給局中人編上號(hào)碼1,2,…,n則每步上都規(guī)定了是哪個(gè)局中人的步，對(duì)于不是局中人的步而是機(jī)遇步，我們規(guī)定這種步是局中人”0”的步，那么每一步都有一個(gè)數(shù)與之對(duì)應(yīng)。而每一步上都是可供選擇的路（即走法）的集合。每一步都指出能知道什么信息。最后在各路的終點(diǎn)（即無擇路可走出去的點(diǎn)）上規(guī)定了各局中人的“得失”。所以這樣的對(duì)策可用樹狀圖來表達(dá)。即：（1）一棵定向的樹，樹根表示第一步，其后各分叉點(diǎn)表示后繼各步。

（2）每個(gè)分叉點(diǎn)上所有枝條的個(gè)數(shù)，即為該步擇路的個(gè)數(shù)。

（3）樹的各個(gè)分叉點(diǎn)上都給定0,1,…,n中一個(gè)數(shù)。即規(guī)定在這點(diǎn)上是哪個(gè)局中人的步（帶數(shù)“0”的步即為機(jī)遇步）。

（4）帶數(shù)”0”的分叉點(diǎn)上，如果它有k個(gè)枝條，則在這個(gè)枝條上規(guī)定了一個(gè)概率分布，即給出k個(gè)數(shù)

7.1陣地對(duì)策特點(diǎn)（5）諸分叉點(diǎn)全體組成的點(diǎn)集有一個(gè)劃分，它把一切分叉點(diǎn)完全無遺地分在互斥的子集（稱為信息集）內(nèi)。這些子集滿足下列假設(shè)：

（i）屬于同一信息集的一切分叉點(diǎn)都是屬于同一個(gè)局中人的步。（ii）同一信息集的各個(gè)分叉點(diǎn)有相同數(shù)目的擇路。（iii）帶數(shù)“0”的分叉點(diǎn)所在的信息集只能有這一個(gè)分叉點(diǎn)。（6）這棵樹的每一個(gè)樹梢上都定義有n個(gè)實(shí)數(shù)F1,F2,……,Fn分別表示局中人1,2,……,n的“得失”。7.1陣地對(duì)策例14猜數(shù)對(duì)策局中人甲秘密地選定1,2,3三個(gè)數(shù)之一。局中人乙猜甲所選的數(shù)，并且說出他所猜的是什么數(shù)，每一次局中人乙說出他所猜的數(shù)后，甲按照實(shí)際情況回答“太高”，“太低”或“正確”。對(duì)策繼續(xù)進(jìn)行到乙回答出為止。甲的支付數(shù)等于乙回答出正確答案所需要的次數(shù)。顯然局中人甲的策略是選擇數(shù)1,2,或3。局中人乙的策略可以用一組數(shù)（G;H,L）來表示。其中G是第一次猜的數(shù)，H是局中人乙聽到甲回答“太高”后第二次猜的數(shù)。L是局中人乙聽到甲回答“太低”后第二次猜的數(shù)。很清楚，最多猜兩次對(duì)策就結(jié)束了。因此局中人乙有五個(gè)策略（1;0,2）,（1;0,3）,（2;1,3）,（3;1,0）,（3;2,0）其中0表示這種情況不存在。局中人甲得到的支付數(shù)，是局中人乙直到聽局中人甲說“正確”時(shí)共回答的次數(shù)。支付矩陣列出如下：7.1陣地對(duì)策猜數(shù)對(duì)策也是一個(gè)陣地對(duì)策，可用圖4-1的樹狀圖來描寫：7.2連續(xù)對(duì)策7.2連續(xù)對(duì)策在一個(gè)有限對(duì)策里，每個(gè)局中人的策略集是有限的，即策略的總數(shù)可以很大，但畢竟是一個(gè)有限數(shù)?？墒窃S多軍事和經(jīng)濟(jì)的對(duì)策往往涉及無窮多個(gè)策略的問題。例如在一海域里潛行的潛水艇，為躲過敵方飛機(jī)的偵察，該如何選擇出水換氣的地點(diǎn)的對(duì)策問題。其策略數(shù)目就是無窮多個(gè)。具有無窮多個(gè)策略的對(duì)策稱為無限對(duì)策。最簡(jiǎn)單的一種是被稱為連續(xù)對(duì)策。連續(xù)對(duì)策在其最簡(jiǎn)單的形式下可描述如下：局中人甲在[0,1]閉區(qū)間中選擇一個(gè)點(diǎn)X，同時(shí)局中人乙在[0,1]閉區(qū)間中選擇一個(gè)點(diǎn)Y，而在局勢(shì)

之下，局中人甲得到支付為。假定對(duì)策是零和的，則局中人乙得到的支付為

。并且假設(shè)支付函數(shù)

對(duì)于每個(gè)存在，而對(duì)于每個(gè)

也存在，所以對(duì)局中人甲來說，存在一個(gè)策略，使他至少得到。同樣對(duì)局中人乙來說，存在一個(gè)策略使他至少得到

容易證明下式成立：

7.2連續(xù)對(duì)策

如果上式的等號(hào)成立，那么設(shè)策略X0，Y0使

對(duì)于一切Y成立

對(duì)于一切X成立。則稱X0是局中人甲的最優(yōu)純策略，Y0是局中人乙的最優(yōu)純策略。（X0,Y0）稱為此連續(xù)對(duì)策的鞍點(diǎn)。如果上式的等號(hào)不成立。就沒有最優(yōu)純策略。于是和有限兩人零和對(duì)策中引入混合策略（即是有限集上的概率分布函數(shù)）的概念一樣，我們引無限集上的概率分布函數(shù)為無限對(duì)策中的混合策略。即連續(xù)對(duì)策的混合策略是一個(gè)從[0,1]閉區(qū)間中選擇一個(gè)不大于X的數(shù)的隨機(jī)過程。當(dāng)甲取混合策略即某個(gè)分布函數(shù)F(x)，而乙取混合策略G(y)時(shí)，甲的期望支付是斯蒂爾杰積分：

類似于矩陣對(duì)策當(dāng)

及

7.2連續(xù)對(duì)策

都存在且相等（其中D是[0,1]上的分布函數(shù)的全體組成的集合），則在混合策略中有平衡局勢(shì)。也就是存在甲的混合策略F0(X)，乙的混合策略G0(Y)使對(duì)任何的X,Y有：7.3多人對(duì)策7.3多人對(duì)策當(dāng)局中人是兩個(gè)以上時(shí)，這樣的對(duì)策稱為多人對(duì)策。一般多人對(duì)策中不可避免會(huì)出現(xiàn)合作的情況，例如兩人有默契，合起來對(duì)付第三個(gè)，使第三個(gè)必?cái)?。所以討論多人?duì)策時(shí)，對(duì)局中人之間可能有怎樣的合作必需進(jìn)行研究。所謂正規(guī)型不結(jié)盟多人對(duì)策是指三元體

其中I是局中人集合，Si是局中人I的策略集，Hi是局中人I的得失函數(shù)?，F(xiàn)在我們對(duì)這種多人對(duì)策來討論其中局中人之間可能有怎樣的合作。下面引入特征函數(shù)的概念。當(dāng)我們把I的一個(gè)子集合R看成是一個(gè)聯(lián)盟，而把I中除去R后剩下元素全體記作I/R看成是另一個(gè)聯(lián)盟，然后構(gòu)造一個(gè)兩零和對(duì)策：

7.3對(duì)人對(duì)策

如果對(duì)策有值則把

看成是聯(lián)盟R的“得失”。假定對(duì)于任何子集而言，對(duì)策

的值都存在，記為

。然后我們假定（其中表示空集）。這樣我們就在

的一切子集上定義了一個(gè)函數(shù)，這個(gè)函數(shù)稱為對(duì)策P的特征函數(shù)。它必有如下的性質(zhì)：(1)(2)(3)

由性質(zhì)（3）可推得

特別有

光從特征函數(shù)來討論可能成立什么聯(lián)盟還為時(shí)過早，因?yàn)殡m然結(jié)盟會(huì)增加共同贏得，但如果制定的分配共同贏得的方案不合適，也會(huì)引起聯(lián)盟的破裂。所以又引入了分配的概念。7.3對(duì)人對(duì)策在零和對(duì)策中，局中人如何結(jié)盟呢？這主要取決于分配對(duì)局中人的影響，所謂分配乃是指滿足下列條件的n個(gè)實(shí)數(shù)d=(a1,a2,……,an).對(duì)于一個(gè)分配a=(a1,a2……,an)而言，要使某個(gè)聯(lián)盟有可能形成，必須要這個(gè)條件如果滿足，則稱聯(lián)盟R對(duì)分配a有效。設(shè)為兩個(gè)分配，如果存在聯(lián)盟，R對(duì)分配a有效，且使得對(duì)一切

而言，ai>bi

那么說分配α優(yōu)于分配β，記為α>β。顯然當(dāng)α>β時(shí)，聯(lián)盟R必至少包含有兩個(gè)局中人。因?yàn)槿鬜只包含一個(gè)局中人i，那么由

但β乃是一個(gè)分配，所以bi>U(i)必成立。從而ai>U(i)，但已假設(shè)R對(duì)分配a有效，即必須成立，從而矛盾。7.3對(duì)人對(duì)策

引入這些概念之后，有人給出如下的解的概念。定義：命W是某些分配組成的集合，如果（1）對(duì)于任何

,α>β和β>α都不成立（2）對(duì)任何，必存在

使得

成立。

那么W就叫做對(duì)策P的一個(gè)解。下面舉一個(gè)多人對(duì)策的例子。此多人對(duì)策的樹狀圖為7.3對(duì)人對(duì)策這是一個(gè)全信息多人陣地對(duì)策。如果1,2合作，則上面陣地對(duì)策等價(jià)于如下的陣地對(duì)策（見圖4-3）（-1,1）（1,0）由于最后一步都是③的步；因此在這步上③一定選擇對(duì)他有利的擇路，也即絕不會(huì)選使他一無所得的擇路。但第一，二步是①、②聯(lián)盟的步，他們也一定選擇使他們總收入最大的擇路?，F(xiàn)在分析一下如果第一步選了右邊的擇路，最后肯定①、②只得到1而③可得到3.那么如果第一步選了左邊的擇路，而第二步分兩種情況：（1）如果選右邊的擇路，則①②可得1，而③只可得0。（2）如果選左邊的擇路，則①②可得-1，而③可得1。因此①②為了自己多得，也為了不讓③有所得，他們必須是第一步選左邊的擇路。所以①②聯(lián)盟時(shí)①②的總收入是1記作U(1,2)，而③的收入是0，記作U(3)。也即

U(1,2)=1;U(3)=0

同樣的方法分析后可得

U(1,3)=3;U(2)=1U(2,3)=2;U(1)=07.3對(duì)人對(duì)策

如果①，②，③結(jié)成聯(lián)盟時(shí)，等價(jià)于一人對(duì)策

顯然此時(shí)第一步必走右邊的擇路，最后總收入是4，記作U(1,2,3)=4。然后令U(V)=0。如此得到了定義在局中人集合I的一切子集上的一個(gè)函數(shù)（但與前述特征函數(shù)不太一樣，因?yàn)榇藭r(shí)對(duì)策不是零和的）。從此函數(shù)可以看到任何局中人不結(jié)盟總是一無所得的，但是哪樣的結(jié)盟會(huì)實(shí)現(xiàn)呢，這就與結(jié)盟時(shí)商定的總收入如何在盟員之間分配的協(xié)定有關(guān)了。例如三個(gè)人一起合作時(shí)，總收入4該如何分配呢，如果照樹梢上寫的支付函數(shù)分配，肯定有一人沒收入因而不滿意而退出聯(lián)盟。所以討論多人對(duì)策中的結(jié)盟問題，必須要涉及結(jié)盟后如何分配（也即有所謂“邊支付”）的問題。07.4微分對(duì)策7.4微分對(duì)策在追蹤對(duì)策中追趕雙方是在空間或地面運(yùn)動(dòng)的。這里逃的一方有時(shí)不是單純逃，而是企圖在被追到以前達(dá)到某種目的。而追的一方就要在逃方達(dá)到目的之前追到他。

設(shè)想有一只老鼠在園形的湖邊碰上了貓，它想回洞已來不及，只好跳入湖中企圖逃走。但貓?jiān)诎渡吓艿乃俣缺仁笤诤杏蔚乃俣瓤斓枚?，例如是鼠速?倍。粗看起來，老鼠沒有好辦法，只有束手就擒。但是，仔細(xì)研究一下，老鼠還是可以跑掉的。我們將老鼠所跑路線的奧妙介紹如下：

圖4-5中大圓表示圓湖其半徑設(shè)為R，取1/4R為半徑作一同心小圓K于是老鼠跳入湖中后，先游到小圓K內(nèi)，然后轉(zhuǎn)圈游，貓?jiān)诎渡习垂潭ǖ穆肪€跟著老鼠；但用同樣的時(shí)間，老鼠在圓k內(nèi)轉(zhuǎn)圈所轉(zhuǎn)過的角度比貓沿湖岸轉(zhuǎn)圈轉(zhuǎn)過的角度要大。所以老鼠可以游到和貓不在同一半徑，而在同一直徑的圓K的邊界點(diǎn)*的位置上去，然后沿此直徑游向湖岸。因?yàn)?點(diǎn)到湖岸的最短距離是3/4R，設(shè)鼠的速度為V,則鼠由*點(diǎn)到湖岸所需的時(shí)間是3R/4V，由于貓的位置同*點(diǎn)不在同一半徑上，所以貓的到達(dá)同一地點(diǎn)的路程正好是半圓周，即。那么，貓的速度是鼠的4倍（即4V），但貓所需時(shí)間是

所以鼠先上岸，且有時(shí)間迅速跑入附近的鼠洞而溜掉。貓鼠貓鼠貓鼠7.4微分對(duì)策

追蹤問題也存在對(duì)策現(xiàn)象所共有的根本要素：1.局中人此時(shí)局中人就是迫者與逃者，例如在空戰(zhàn)中一方的殲擊機(jī)和另一方的轟炸機(jī)，在空防中是攻方的轟炸機(jī)和守方的高射炮，在導(dǎo)彈戰(zhàn)中是一方的導(dǎo)彈和另一方的反導(dǎo)彈等等。2．策略追逃雙方都有自己的可選擇的行動(dòng)方案，例如轟炸機(jī)可選擇飛行路線和投彈方式等，殲擊機(jī)可選擇攻擊時(shí)間，飛行路線和攻擊方式等，高射炮可選擇發(fā)射角度等等。不過在追蹤問題中局中人的完整的行動(dòng)方案(所謂策略)比以前介紹的矩陣對(duì)策中的完整的行動(dòng)方案要復(fù)雜得多了。因?yàn)樵谧粉檰栴}中，局中人例如殲擊機(jī)必須每時(shí)每刻都掌握對(duì)方相對(duì)位置和某些情況以便跟蹤追擊。同時(shí)轟炸機(jī)也得每時(shí)每刻都能掌握雙方的相對(duì)位置和某些情況以便躲過攻擊，飛達(dá)轟炸目標(biāo)。所以用數(shù)學(xué)描述追蹤對(duì)策中的策略，也必須要反映出這種連續(xù)動(dòng)態(tài)的決策過程，這就得借助微分方程的理論。因此這類對(duì)策理論稱為微分對(duì)策。在微分對(duì)策中，通常用向量X(t)表示時(shí)刻t時(shí)各方為繼續(xù)進(jìn)行對(duì)策所必須知道的雙方的狀況變量。例如空戰(zhàn)中雙方飛機(jī)的相對(duì)位置和機(jī)頭所指方向等等，因此X(t)也被稱為狀況變量。7.4微分對(duì)策同時(shí)，各局中人都有控制自己運(yùn)動(dòng)路線的手段，例如飛機(jī)駕駛員可以做改變機(jī)速和使機(jī)頭拐彎等操作，于是機(jī)速和機(jī)頭拐彎的曲率半徑等是屬于局中人直接可控制的量，這些量的改變就能引起前述狀況變量的改變，并且這些量將怎么變，對(duì)方是不知道的，所以這些向量稱做控制量。于是局中人的一個(gè)策略就是決定一個(gè)連續(xù)控制的規(guī)律，即對(duì)任意狀況