土木系統(tǒng)工程

土木系統(tǒng)工程第一頁，共四十六頁，編輯于2023年，星期五對策行為在日常生活中，經常會看到一些相互之間具有斗爭或競爭性質的行為，如下棋、打牌、體育比賽等。還比如戰(zhàn)爭活動中的雙方，都力圖選取對自己最有利的策略，千方百計去戰(zhàn)勝對手。在政治方面，國際間的談判，各種政治力量之間的斗爭，各國際集團之間的斗爭等無一不具有斗爭的性質。在經濟活動中，各國之間、各公司企業(yè)之間的經濟談判，企業(yè)之間為爭奪市場而進行的競爭等，舉不勝舉。具有競爭或對抗性質的行為稱為對策行為2第二頁，共四十六頁，編輯于2023年，星期五博弈論1、博弈論的概念和演變

博弈論(GameTheory)又稱對策論或競賽論，是研究具有競爭或比賽性質的數(shù)學理論和方法，屬于運籌學的一個分支，也是土木系統(tǒng)工程的理論基礎之一。博弈論研究對抗的雙方在競爭過程中是否存在自己制勝對方的最優(yōu)策略，由于其處理問題的方法有著明顯特色，所以正日益得到廣泛應用。對策論發(fā)展的歷史并不長，但由于它研究的問題與政治、經濟、軍事活動乃至一般的日常生活等有著密切聯(lián)系，所以日益引起廣泛注意。3第三頁，共四十六頁，編輯于2023年，星期五

博弈論歷史悠久，但直至20世紀20年代才引人“最優(yōu)策略”的概念。4O年代以來，由于生產和戰(zhàn)爭的需要，特別是戰(zhàn)爭中兵力調動、兵種步署、監(jiān)視對方、偵察活動等迫切要求戰(zhàn)爭指揮者拿出最好策略，用已有的條件去取得較大的勝利或較小的失敗，于是對策論的數(shù)學模型很快就形成了。各參戰(zhàn)國組織了大批科學家參加這項研究工作，1944年，這一工作被提高到一個新水平，馮·諾依曼和摩根斯頓出版了《對策論與經濟行為》，從此，對策論的研究才演變?yōu)橄到y(tǒng)化的理論化。4第四頁，共四十六頁，編輯于2023年，星期五20世紀50年代，納什（Nash）建立了非合作博弈的“納什均衡”理論，標志著博弈的新時代開始，是納什在經濟博弈論領域劃時代的貢獻，是繼馮·諾依曼之后最偉大的博弈論大師之一。1994年納什獲得了諾貝爾經濟學獎。他提出的著名的納什均衡概念在非合作博弈理論中起著核心作用。5第五頁，共四十六頁，編輯于2023年，星期五博弈論的典型例子之一：齊王賽馬

戰(zhàn)國時期，有一天齊王提出要與田忌賽馬，雙方約定從各自的上、中、下三個等級的馬中各選一匹參賽，每匹馬均只能參賽一次，每一次比賽雙方各出一匹馬，負者要付給勝者千金。已經知道，在同等級的馬中，田忌的馬不如齊王的馬，而如果田忌的馬比齊王的馬高一等級，則田忌的馬可取勝。當時，田忌手下的一個謀士給他出了個主意:每次比賽時先讓齊王牽出他要參賽的馬，然后來用下馬對齊王的上馬，用中馬對齊王的下馬，用上馬對齊王的中馬。比賽結果，田忌二勝一負，奪得千金。由此看來，兩個人各采取什么樣的出馬次序對勝負是至關重要的。6第六頁，共四十六頁，編輯于2023年，星期五

兩個嫌犯受到指控，但除非至少一個招認，否則警方不能將二人判有罪。警察把二人分別帶到不同的房間，告之后果：如果二人均不坦白，將被判入獄一年。如果雙方均坦白，將被判入獄5年。如果一方坦白，另一方不坦白，坦白一方立即釋放，另一方判入獄8年。博弈論的典型例子之二：囚徒困境囚徒2囚徒1不坦白坦白不坦白－1，－1－8，0坦白0，－8－5，－57第七頁，共四十六頁，編輯于2023年，星期五2、對策行為的三個基本要素1）局中人在一個對策行為(或一局對策)中，有權決定自己行動方案的對策參加者，稱為局中人。一般要求一個對策中至少要有兩個局中人。如在“齊王賽馬”的例子中，局中人是齊王和田忌。局中人可以是個人或組織。對我們來說，只要在一個博弈中統(tǒng)一決策，統(tǒng)一行動、統(tǒng)一承擔結果，不管一個組織有多大，哪怕是一個國家，甚至是由許多國有組成的聯(lián)合國，都可以作為博弈中的一個參加方。并且，在博弈的規(guī)則確定之后，各參加方都是平等的，大家都必須嚴格按照規(guī)則辦事。8第八頁，共四十六頁，編輯于2023年，星期五2）策略集一局對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略。參加對策的每一局中人，都有自己的策略集。一般，每一個局中人的策略集中至少應包括兩個策略。在“齊王賽馬”的例子中，如果用(上，中，下)表示以上馬、中馬、下馬依次參賽這樣一個次序，這就是一個完整的行動方案，即為一個策略?？梢?，局中人齊王和田忌各自都有6個策略：(上，中，下)、(上，下，中)、(中，上，下)、(中，下，上)、(下，中，上)、(下，上，中)。9第九頁，共四十六頁，編輯于2023年，星期五3）贏得函數(shù)(支付函數(shù))

在一局對策中，各局中人選定的策略形成的策略組稱為一個局勢S。當一個局勢出現(xiàn)后，對策的結果也就確定了。也就是說，對任一局勢S，局中人i可以得到一個贏得值Hi。顯然，Hi是局勢S的函數(shù)，稱為第i個局中人的贏得函數(shù)。在“齊王賽馬”的例子中，齊王的策略集：田忌的策略集：一個局勢：令：則贏得函數(shù)：10第十頁，共四十六頁，編輯于2023年，星期五相互依存與理性行為

一提到博弈，人們都會想到擲骰子與對弈，但二者有本質的區(qū)別。擲骰子的得失純粹依賴于機遇；而一局棋的勝負則取決于雙方所采取的策略。相互依存：通常是指博弈中的任何一個局中人受到其他局中人的行為的影響，反過來，他的行為也影響到其他局中人。局中人理性地采取或選擇自己的策略行為，在相互制約相互影響的依存關系中，盡可能的提高自己的利益所得，這樣，博弈論就是關于包含相互依存情況中理性行為的研究。11第十一頁，共四十六頁，編輯于2023年，星期五納什均衡如果存在一個策略組合，其中每一個參與者的選擇都是他的最優(yōu)選擇，此時的策略組合就是一個納什均衡（Nashequilibrium）組合。納什均衡的特征：博弈方預測到均衡，博弈方預測到其他博弈方預測到均衡，等等。如果所有博弈方預測到一個特定的納什均衡將會出現(xiàn)，那么，沒有人有興趣作不同的選擇。納什均衡是一種非合作博弈均衡，在現(xiàn)實中非合作的情況要比合作情況普遍。并不意味著納什均衡一定是一個好的預測。12第十二頁，共四十六頁，編輯于2023年，星期五囚徒困境囚徒2囚徒1拒供坦白拒供－1，－1－8，0坦白0，－8－5，－5每個囚徒都會發(fā)現(xiàn)如果對方拒供，則自己坦白便可立即獲得釋放，而自己拒供則會被判1年，因此坦白是較好的選擇。如果對方坦白，則自己坦白將被判5年，而自己拒供則會被判8年，因此坦白是較好的選擇。由于每個囚徒都發(fā)現(xiàn)坦白是自己更好的選擇，因此，博弈的穩(wěn)定結果是兩個囚徒都會選擇坦白。這就是博弈的納什均衡。13第十三頁，共四十六頁，編輯于2023年，星期五

囚徒困境反映了個人理性和集體理性的矛盾。如果兩個囚徒都選擇不坦白，各判刑１年，顯然比都選擇坦白各判刑８年好得多，顯然最好的策略是雙方都不坦白。當然，兩個囚徒可以在被警察抓到之前訂立一個“攻守同盟”，但是這可能不會有用，因為每個人都擔心對方背棄盟約，沒有人有積極性遵守這個協(xié)定。囚徒的困境博弈的重要意義，在于類似的情況在社會經濟活動中具有很大的普遍性，在市場競爭的各個領域和方面，在資源利用和環(huán)境保護，以及政治、軍事和法律等各種領域的問題中，都存在類似囚徒的困境的現(xiàn)象。如：貿易戰(zhàn)14第十四頁，共四十六頁，編輯于2023年，星期五對策分類（1）根據局中人個數(shù)，分為二人對策和多人對策；（2）根據各局中人的贏得函數(shù)的代數(shù)和是否為0，分為零和對策與非零和對策；（3）根據各局中人間是否允許合作，分為合作對策和非合作對策；（4）根據局中人的策略集中的策略個數(shù)，分為有限對策和無限對策；（5）根據策略的選擇是否與時間有關，分為靜態(tài)對策和動態(tài)對策；（6）根據對策模型的數(shù)學特征，分為矩陣對策、連續(xù)對策、微分對策等在眾多對策模型中，占有重要地位的是二人有限零和對策，又稱為矩陣對策。15第十五頁，共四十六頁，編輯于2023年，星期五3、矩陣對策

二人有限零和對策就是矩陣對策，是指只有兩個參加對策的局中人，每個局中人都只有有限個策略可供選擇。在任一局勢下，兩個局中人的贏得之和總是等于零，即雙方的利益是激烈對抗的?！褒R王賽馬”就是一個矩陣對策的例子，齊王和田忌各有6個策略，一局對策結束后，齊王的所得必為田忌的所失，反之亦然。16第十六頁，共四十六頁，編輯于2023年，星期五（1）矩陣對策的數(shù)學模型

在矩陣對策中，一般用Ⅰ、Ⅱ分別表示兩個局中人，并設局中人Ⅰ有m個純策略(以與后面的混合策略區(qū)別)，局中人Ⅱ有n個純策略，局中人Ⅰ、Ⅱ的策略集分別為：當局中人Ⅰ選定純策略ai，和局中人Ⅱ選定純策略后bj，就形成了一個純局勢(ai，bj)，可見這樣的純局勢共有m×n個。17第十七頁，共四十六頁，編輯于2023年，星期五對任一純局勢純局勢(ai，bj)，局中人Ⅰ的贏得值為aij，稱為局中人Ⅰ的贏得矩陣(或為局中人Ⅱ的支付矩陣)。由于假定對策為零和的，故局中人Ⅱ的贏得矩陣就是-A，通常，將一個矩陣對策記成或18第十八頁，共四十六頁，編輯于2023年，星期五如齊王賽馬：

S1={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}S２={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}19第十九頁，共四十六頁，編輯于2023年，星期五（2）最優(yōu)純策略例：對于一個矩陣對策其中求雙方的最優(yōu)策略。20第二十頁，共四十六頁，編輯于2023年，星期五解：由A可以看出，局中人Ⅰ的最大贏得是7，就是說局中人Ⅰ十分希望自己取得7，就會出a1加入博弈。然而，局中人Ⅱ也在考慮，因為局中人Ⅰ有出a1的心理狀態(tài)，于是局中人Ⅱ就想出b2

進行博弈，這樣不僅使Ⅰ得不到7，反而要輸3(即贏得-3)。同樣，Ⅰ也會這樣想，Ⅱ有出b2的心理狀態(tài)，于是Ⅰ就會出a3，結果Ⅱ不但得不到3，反而要輸2。這樣，如果Ⅰ出a3，則Ⅱ會出b2，使Ⅰ的贏得達到最小2。而對于Ⅰ來說，如果Ⅱ出b2，Ⅰ的最優(yōu)策略仍然是a3，可獲得最大贏得值2。于是a3和b2分別是雙方的最優(yōu)策略。21第二十一頁，共四十六頁，編輯于2023年，星期五

如果雙方都不想冒險都不存在僥幸心理，而是考慮到對方必然會設法使自己的所得最少這一點，就應該從各自可能出現(xiàn)的最不利的情形中選擇一種最有利的情形作為決策的依據，這就是所謂的“理智行為”，也是對策雙方實際上都能接受的一種穩(wěn)妥的方法。22第二十二頁，共四十六頁，編輯于2023年，星期五

在本例中，局中人Ⅰ分析到出純策略a1,a2，a3，a4可能帶來的最少贏得(矩陣A中每行的最小元素)分別為:-3，-4，2，-6，在這些最少贏得(最不利的情形)中最好的結果(最有利的情形)是贏得為2。因此局中人Ⅰ以a3參加對策。同理，對局中人Ⅱ來說，各純策略b1，b2，b3可能帶來的最不利的結果(矩陣A中每列中最大元素)為7,2,5，在這些最不利的結果中最好的結果(輸?shù)米钌?也是2，因此局中人Ⅱ以b2參加對策。

a3和b2分別是雙方的最優(yōu)策略，a32=2稱為矩陣對策G的值。它是第3行中最小值，也正好是第2列中的最大值。23第二十三頁，共四十六頁，編輯于2023年，星期五定義：設為矩陣對策。其中若等式成立則稱為對策G的值。（也稱為鞍點）這時的純局勢為G在純策略下的解(或平衡局勢)，與分別稱為局中人I，II的最優(yōu)純策略。24第二十四頁，共四十六頁，編輯于2023年，星期五案例：俾斯麥海的海空對抗1943年2月，第二次世界大戰(zhàn)中的日本，在太平洋戰(zhàn)區(qū)已經處于劣勢。為扭轉局勢，日本統(tǒng)帥山本五十六大將統(tǒng)率下的一支艦隊策劃了一次軍事行動：由集結地——南太平洋的新不列顛群島的蠟包爾出發(fā)，穿過俾斯麥海，開往新幾內亞的萊城，支援困守在那里的日軍。當盟軍獲悉此情報后，盟軍統(tǒng)帥麥克阿梭命令太平洋戰(zhàn)區(qū)空軍司令肯尼將軍組織空中打擊。日本統(tǒng)帥山本五十六大將心里很明白：在日本艦隊穿過俾斯麥海的三天航行中，不可能躲開盟軍的空中打擊，他要策劃的是盡可能減少損失。

25第二十五頁，共四十六頁，編輯于2023年，星期五

日美雙方的指揮官及參謀人員都進行了冷靜的思考與全面的謀劃。自然條件對于雙方都是已知的。基本情況如下：從蠟包爾出發(fā)開往萊城的海上航線有南北兩條。通過時間均為3天。氣象預報表明：未來3天中，北線陰雨，能見度差；而南線天氣晴好，能見度好。肯尼將軍的轟炸機布置在南線的機場，偵察機全天候進行偵察，但有一定的搜索半徑。26第二十六頁，共四十六頁，編輯于2023年，星期五經測算，雙方均可得到如下估計：局勢1：盟軍的偵察機重點搜索北線，日本艦隊也恰好走北線。由于氣候惡劣，能見度差，盟軍只能實施兩天的轟炸。局勢2：盟軍的偵察機重點搜索北線，日本艦隊走南線。由于發(fā)現(xiàn)晚，盡管盟軍的轟炸機群在南線，但有效轟炸也只有兩天。局勢3：盟軍的偵察機重點搜索南線，而日本艦隊走北線。由于發(fā)現(xiàn)晚、盟軍的轟炸機群在南線，以及北線氣候惡劣，故有效轟炸只有一天。27第二十七頁，共四十六頁，編輯于2023年，星期五局勢4：盟軍的偵察機重點搜索南線，日本艦隊也恰好走南線。此時日本艦隊迅速被發(fā)現(xiàn)，盟軍的轟炸機群所需航程很短，加上天氣晴好，有效轟炸時間三天。解：局中人：盟軍、日軍對策集：贏得矩陣：純策略下的解為局勢1。a1(北)與b1(北)分別為盟軍、日軍的最優(yōu)純策略。28第二十八頁，共四十六頁，編輯于2023年，星期五歷史的實際情況是：局勢1成為現(xiàn)實?？夏釋④娒蠲塑姷膫刹鞕C重點搜索北線；而山本五十六大將命令日本艦隊取道北線航行。由于氣候惡劣，能見度差，盟軍飛機在一天后發(fā)現(xiàn)了日本艦隊，基地在南線的盟軍轟炸機群遠程航行，實施了兩天的有效轟炸，重創(chuàng)了日本艦隊，但未能全殲。29第二十九頁，共四十六頁，編輯于2023年，星期五例:求對策的解。設矩陣對策其中贏得矩陣為解:直接在A提供的贏得表上計算，有 故都是對策的解30第三十頁，共四十六頁，編輯于2023年，星期五性質1無差別性。即若和是對策G的兩個解，則性質2可交換性。即若和是對策G的兩個解，則和也是解。矩陣對策的解的兩個重要性質這兩條性質表明，矩陣對策的值是唯一的。31第三十一頁，共四十六頁，編輯于2023年，星期五（3）矩陣對策的混合策略由前面的討論可知，對矩陣對策來說，局中人Ⅰ有把握的至少贏得是局中人Ⅱ有把握的至多損失是一般，局中人Ⅰ的贏得值不會多于局中人Ⅱ的所失值，即總有當v1=v2

時，矩陣對策G存在純策略意義下的解，然而，一般情形不總是如此，實際中出現(xiàn)的更多情形是v1<v2，這時，對策G不存在純策略意義下的解。32第三十二頁，共四十六頁，編輯于2023年，星期五例如，贏得矩陣為：

如果雙方仍然各自根據從最不利情形中選取最有利結果的原則選擇純策略，應分別選取a2和b1。此時局中人Ⅰ將贏得5，比其預期贏得v1=4還多，原因就在于局中人Ⅱ選擇了b1，使他的對手多得了原本不該得的贏得。故b1對局中人Ⅱ來說并不是最優(yōu)的，因而他會考慮出b2。局中人Ⅰ亦會采取相應的辦法，改出a1以使贏得為6，而局中人Ⅱ又可能仍取策略b1來對付局中人Ⅰ的策略a1。這樣，局中人Ⅰ出a1或a2的可能性及局中人Ⅱ出b1或b2的可能性都不能排除。33第三十三頁，共四十六頁，編輯于2023年，星期五定義：對給定的矩陣對策

G={S1,S2;A}其中S1={1,2…m}

S2={1,2…

n}A=(aij)mn把純策略集合對應的概率向量

X=(x1,x2…

xm)其中xi

0xi=1和

Y=(y1,

y2…

yn)其中yj

0yj=1分別稱為局中人Ⅰ和局中人Ⅱ的混合策略。若只進行一次對策，混合策略可設想成局中人對各純策略的偏愛程度。34第三十四頁，共四十六頁，編輯于2023年，星期五如果局中人Ⅰ選取的混合策略為X=(x1,x2

…

xm)，局中人Ⅱ選取的混合策略為Y=(y1,y2

…

yn)，則期望值稱為局中人Ⅰ期望贏得，而局勢（X，Y）稱為“混合局勢”，局中人Ⅰ，Ⅱ的混合策略集合記為S1*，S2*。這樣得到的新對策記成稱G*為對策G的混合擴充。純策略是混合策略的特例。35第三十五頁，共四十六頁，編輯于2023年，星期五

對于局中人Ⅰ，若采取混合策略X，則只能希望贏得：因此他應選取Y，使支出最小：因此他應選取X，使贏得最大：

對于局中人Ⅱ，若采取混合策略Y，則可能支出：36第三十六頁，共四十六頁，編輯于2023年，星期五定義：設G*={S1*,S2*;E}是對策G的混合擴充，如果有則稱這個值為對策G在混合意義下的值，記為VG，而達到VG

的混合局勢（X*，Y*）稱為對策G在混合策略意義下的解，而X*和Y*分別稱為局中人I，II的最優(yōu)混合策略。37第三十七頁，共四十六頁，編輯于2023年，星期五定理：任意一個給定的矩陣對策在混合策略意義下一定有解。矩陣對策的求解一般情況的矩陣對策可轉化為兩組線性規(guī)劃來求解1）如果有鞍點，則鞍點就是純策略下最優(yōu)解。2）2×2矩陣對策可直接代公式。3）m×2或2×n矩陣對策，可用圖解法求解4）事先知道解均不為零，則可將兩組不等式化成線性方程組來求解。5）出現(xiàn)優(yōu)超關系時，可降低矩陣階數(shù)求解。38第三十八頁，共四十六頁，編輯于2023年，星期五2×2矩陣對策的公式解法