博弈論模型和線性規(guī)劃課件

博弈論模型和線性規(guī)劃幽默來自智慧，惡語來自無能第07章對策論模型ModelsofGameTheory71矩陣對策模型7.2雙矩陣對策模型73n人合作對策初步71矩陣對策模型例71田忌賽馬問題戰(zhàn)國時期,齊國國王齊王提出要與田忌賽馬,雙方約定從各自的上、中、下三個等級的馬中各選一匹參賽,每匹馬都只能參賽一次,每次比賽雙方各出一匹馬,負(fù)者要付給勝者千金。已經(jīng)知道,在同等級別的馬中,田忌的馬不如齊王的馬,而如果田忌的馬比齊王的馬高等級,則田忌的馬可取勝。當(dāng)時,田忌手下的一個謀士給他出了一個主意:每次比賽時先讓齊王牽出他要參賽的馬,然后來用下馬對齊王的上馬,用中馬對齊王的下馬,用上馬對齊王的中馬。比賽結(jié)果,田忌二勝一負(fù),奪得千金。對策模型的種類可以千差萬別,但本質(zhì)上都必須包括以下三個基本要素口局中人,是指參與對抗的各方,可以是一個人,也可以是一個集團(tuán)在例71中的齊王和田忌就是局中人口策略,是指局中人所擁有的對付其他局中人的手段、方案的集合如例71中田忌共有(上、中、下)、(上、下、中)、(中、上下)、(中、下、上)、(下、中、上)和(下、上、中)六種策略口支付函數(shù)(或收益函數(shù)),是指一局對策后各局中人的得與失,通常用正數(shù)表示局中人的得,用負(fù)數(shù)表示局中人的失。例如,在例71的局中人齊王的支付函數(shù)如表7-1所示。表7-1田忌的策略齊王的策略、(上,中下)(上,下中)(中,上,下)(中下,上)(下中,上)(下,上中)(上中,下3a2(上,下,中)a(中,上,下)11111a4(中,下,上)a(下,中,上)113111111131a。(下,上,中)當(dāng)局中人得失總和為零時,稱這類對策為零和對策;否則稱為非零和對策當(dāng)局中人只有兩個,且對策得失總和為零,則稱為二人零和對策;若得失總和為常數(shù),則稱為二人常數(shù)和對策;若得失總和是非常數(shù),則稱為二人非常數(shù)和對策。若二人對策雙方的得失是用矩陣形式表示,則稱支付函數(shù)為支付矩陣,相應(yīng)的對策稱為矩陣對策。通常,支付矩陣表示局中人A的支付函數(shù)。71.1對策的基本策略鞍點對策例72設(shè)A,B兩人對策,各自擁有三個策略a1a2a3和b1b2b3,局中人A的支付(收益)矩陣如表7-2所示。試求A,B各自的最優(yōu)策略。表7-2bin63545b9729max8從直觀上來看,局中人A應(yīng)該出策略a1,因為這樣選擇,他有可能得到9但局中人B看到了這一點,他出策略b,這樣局中人A不能得到9,而只能得到1。因此,局中人A也充分認(rèn)識到這一點,他應(yīng)當(dāng)出策略a3,這樣做,就有可能得到8,而這種情況下局中人B就要出策略b,局中人A也只能得到2這樣做下來,局中人A只能選擇策略a2,而局中人B也只能選擇策略b,大家達(dá)到平衡,最后局中人A贏得的值為5,局中人B輸?shù)舻闹禐?。從上面的分析可以看出,無論局中mn人A選擇什么策略,他贏得的值總是小于等于5,而無論局中人B選擇什么策略,他輸?shù)舻闹悼偸谴骯于等于5,5就是支付矩陣的鞍點。688354597292max假設(shè)局中人I有m個策略a1,a2,…,an,局中人Ⅱ有n個策略,B2,…,Bn,分別記為S2={B1,B2,…,BA=(an)mn為局中人I的支付矩陣,而-4為局中人Ⅱ的支付矩陣,矩陣對策記為G=A,B;S,S,;A)AG=S,S2;A)定義7設(shè)G={S,S2;A}是一矩陣對策,若等式maxmiinai-minmaxai=((7-1)成立,則記并稱vc為對策G的值。稱使式71成立的純局勢(a月)為在純策略下的解(或平衡局勢),稱a1和B分別為局中人Ⅰ、Ⅱ的最優(yōu)純策略。由定義7.1可知,在矩陣對策中兩局中人都采取最優(yōu)純策略(如果最優(yōu)純策略存在)才是理智的行動例73求解矩陣對策G={S,S2;A},其中435A15-2-4解:根據(jù)矩陣A,有-406BB2B3mIn435306-4maxnai1536maxmina=minmaxa=a=3va=3,G的解為(a2/B2),a2和2分別是局中人I和Ⅱ的最優(yōu)純策略從例73可以看出,矩陣A的元素a2既是其所在行的最小元素又是其所在列的最大元素,即a2≤a2≤a2i=1,2,34;j=1,2,3。將這事實推廣到一般矩陣對策,可得如下定理。定理71矩陣對策G={S1,S2;A}在純策略意義下有解的充分必要條件是:存在純局勢(x,B)使得≤a.,≤a,i=1,2,n(7-2)為了便于對更廣泛的對策情形進(jìn)行分析,引進(jìn)關(guān)于二元函數(shù)鞍點的概念定義72設(shè)∫(xy)為一個定義在x∈A及y∈B上的實值函數(shù),若存在x∈A,y∈B,使得f(x,y*)≤f(x米,y*)≤f(x,y),Vx∈A,y∈B(7-3)則稱(x,y)為函數(shù)f(x,y)的一個鞍點當(dāng)矩陣對策的最優(yōu)解不惟一時,有如下定理。定理72(無差別性)若(a1,廂和(a3,B是矩陣對策的兩個解,則定理73(可交換性)若(a1,B1)和(a2,B2)是矩陣對策的兩個解,則(a4,B2)和(a2,B)也是矩陣對策的解6565例74設(shè)矩陣對策G={S1,S2;A},其中,142-1S1={a,a2,∝1,c1},S2={A,B2,B,B}。支付矩陣A如下,試求對策的解857526、要使整個人生都過得舒適、愉快，這是不可能的，因為人類必須具備一種能應(yīng)付逆境的態(tài)度。——盧梭

27、只有把抱怨環(huán)境的心情，化為上進(jìn)的力量，才是成功的保證?！?/p>