博弈論算法講義

1、博弈論算法一、博弈的戰(zhàn)略式表述及納什均衡的定義在博弈論里，一個(gè)博弈可以用兩種不同的方式來表述：一種是戰(zhàn)略式表述(strategic form representation)，另一種是擴(kuò)展式表述(或譯為“展開式表述”)(extensive form representation)o 1 1 從分弈的角戰(zhàn)膈式表述?更適合于靜態(tài)博弈，而擴(kuò)展式表述更適合于討論動(dòng)態(tài)博弈。戰(zhàn)略式表述又稱為標(biāo)準(zhǔn)式表述(normalform representation)o在這種表述中，所參與人同時(shí)選擇各自 的戰(zhàn)略，所有參與人選擇的戰(zhàn)略一起決定每個(gè)參與人的支付。戰(zhàn)略式表述給出：1.博弈的參與人集合：i m,r = (1,2,

2、 ,n)o,n o,s ), i = 1,2, , n ok 2 n)代表戰(zhàn)略式表述博弈。每個(gè)參與人的戰(zhàn)略空間：S.,i = 1,2,I每個(gè)參與人的支付函數(shù)：七(七叩 我們用 G = (S , , S ; u , 1 n 1 n例如在兩個(gè)寡頭產(chǎn)量博弈里，企業(yè)是參與人，產(chǎn)量是戰(zhàn)略空間，利潤(rùn)是支付;戰(zhàn)略式表述博弈為:G = q 0, q 0；兀(q , q ),兀(q , q )j12112212這里q、丸別表示第7個(gè)企業(yè)的產(chǎn)量和利潤(rùn)。1.2納什均衡的定義有n個(gè)參與人的戰(zhàn)略式表述博弈G = (% ,Sju，un)，戰(zhàn)略組合s* = 什均衡。如果對(duì)于每一個(gè)i、s；是給定其他參與人選擇S；. =；,

3、,S,S,(1.1),S；是一個(gè)納；,S*,S ；的情況下第個(gè)參與人 n的最優(yōu)戰(zhàn)略，即(1.2)(1.3) u (s*, s* ) u (s , s* ), Vs g S , Vii i -ii i -i i . J. . .或者用另一種表述方式，s；是下述最大化問題的解：s* g argmax u (s*,., s* , s , s* ,., s*), i = 1,2,., n ; s g Sii 1i-1 i i+1ni i來檢查一個(gè)特定的戰(zhàn)略組合是否是一個(gè)納什均衡。兩個(gè)嫌疑犯作案后補(bǔ)警察抓住，被分別關(guān)在不同的房間里審訊。警察知道兩人有罪，但缺乏足夠的證 據(jù)定罪，除非兩人當(dāng)中至少有一個(gè)人坦

4、白。警察告訴每個(gè)人：如果兩個(gè)都不承認(rèn)，每個(gè)人都以輕微的犯罪 判刑1年；如果兩人都坦白，各判刑8年；如果兩人中一個(gè)人坦白另一個(gè)人抵賴，坦白的釋放出去，抵賴 的判刑10年。這樣，每一個(gè)嫌疑犯面臨四個(gè)可能的后果：獲釋(自己坦白同伙抵賴)被判刑1年(自己 抵賴同伙也抵賴)；被判刑8年(自己坦白同伙也坦白)；被判刑10年(自己抵賴但同伙坦白)。囚徒困境囚犯B表1 坦白 抵賴坦白 (-8,-8)(0,-10)囚犯A抵賴(-10,0)(-1,-1)在這個(gè)博弈中，每個(gè)囚徒都有兩種可選擇的戰(zhàn)略：坦白或抵賴。顯然，不論同伙選擇什么戰(zhàn)略，每個(gè) 囚徒的最優(yōu)戰(zhàn)略是“坦白”，比如說，如果B選擇坦白，A選擇坦白時(shí)支付為-8

5、,選擇抵賴時(shí)的支付為-10， 因而坦白比抵賴好；如果B選擇抵賴，A坦白時(shí)的支付為0，抵賴時(shí)的支付為-1，因而坦白還是比抵賴好。 就是說，“坦白”是囚徒A的占優(yōu)戰(zhàn)略。類似的，“坦白”也是B的占優(yōu)戰(zhàn)略。在囚徒困境里，(坦白，坦白)是一個(gè)納什均衡，而(抵賴，抵賴)不是一個(gè)納什么均衡，因?yàn)榻o定 同伙選擇抵賴，自己選擇抵賴時(shí)得外1，選擇坦白時(shí)得到0，因而抵賴不是自己的最優(yōu)戰(zhàn)略，類似的，(坦 二抵賴殖陣胃對(duì)坦茴也不是納什均衡。2.1純零和對(duì)策矩陣對(duì)策也叫零和對(duì)策，是一類特殊的對(duì)策問題。在這類對(duì)策中，只有兩名局中人，每個(gè)局中人都只 有有限個(gè)策略可供選擇。在任一純局勢(shì)下，兩個(gè)局中人的贏得之和總是等于零，即雙方

6、和利益是激烈對(duì)抗 的。設(shè)局中人I、II的策略集分別為： TOC o 1-5 h z HYPERLINK l bookmark29 o Current Document S =a , ,a , S =p , , p (2,1)11 m 21 n當(dāng)局中人I選定策略.和局中人II選定策略七后，就形成了一個(gè)局勢(shì)(氣,P ?，可見這樣的局勢(shì)共有 mn個(gè)，對(duì)任一局勢(shì)(氣，p，記局中人I的贏得值為七，并稱aaaaaaA =21222na a： a：1 C Am1m 2 . . . mn為局中人I贏得矩陣(或?yàn)榫种腥薎I的支付矩陣)。由于假定對(duì)策為零和的，故局中人II的贏得矩陣就是A。當(dāng)局中人I、II和策略集

7、S1、S2及局中人I的贏得矩陣A確定后，一個(gè)零和對(duì)策就給定了，零和對(duì) 策又可稱為矩陣對(duì)策，并可簡(jiǎn)記成：G = SS2; A雙方都應(yīng)考慮到對(duì)方有使自己損失最大的動(dòng)機(jī)。定義1鞍點(diǎn)設(shè)/3 y)為一個(gè)定義在工e A及e B上的實(shí)值函數(shù)，如果存在了* G A, y* G B使得一切X e A和 G B，有f (x, y*) f (x*, y*) f (x*, y)(2.2)則稱(x*, y*)為函數(shù)f的一個(gè)鞍點(diǎn)。Mathematica畫圖說明鞍點(diǎn)定義2贏得矩陣的鞍點(diǎn)設(shè)G = s ,S ; a為矩陣對(duì)策，其中S=a,a ,a,S =p,p , ,p,A =(a)。若等式12112 m 212 nij nx

8、mmax min a = min max a = a(23)i j ij j i iji* j*( . )成立，記匕二%*，則稱匕為對(duì)策G的值，使(2.3)式成.立的純局勢(shì)(a.*，p為對(duì)策G鞍點(diǎn)或穩(wěn)定解，贏 得矩陣中與%*，p相對(duì)應(yīng)的元素ai*廣稱為贏得矩陣的鞍點(diǎn)，a i*和七*分別稱為局中人I與II的最優(yōu)純 策略。定理1極大極小原理設(shè)G = S ,S ;A，記日=maxmina，v= minmaxa，則必有p+v 0, i = 1, ,m;1mis* = (y , , y )T I y 0, j = 1, ,n; TOC o 1-5 h z 1nj定義4混合策略對(duì)策問題的鞍點(diǎn)(2.4)(2

9、.5)若存在m維概率向量x和n維向量y，使得對(duì)一切m維向量x和n維向量y有 xt Ay = max xt Ay = min xTAy_ _xy則稱(x, y)為混合策略對(duì)策問題的鞍點(diǎn)。定理3鞍點(diǎn)的判定設(shè)X e S * , y e S *，則(x, y)為G = s , s ；A的解的充要條件是： 1212V工 a y xTAy, i = 1,2, , m 廣1 j j XTAy, j = 1,2, ,nij i虹i=1定理4鞍點(diǎn)的存在性任意混合策略對(duì)策問題必存在鞍點(diǎn)，即必存在概率向量X和y，使得：XTAy = max xt Ay = min XTAyxy下面是三個(gè)關(guān)于零和對(duì)策解集的定理，設(shè)零和

10、對(duì)策G的解集為T (G)定理5加法律設(shè)兩個(gè)零和對(duì)策G =s , s ；A ,G =s ,s ；A ，其中A =a , A =a +切,L為任一常數(shù)。則112121221 ij 2 ijV = V + LT(G ) =1T(G ) TOC o 1-5 h z HYPERLINK l bookmark89 o Current Document 定理6乘法律12設(shè)兩個(gè)零和對(duì)策G =s ,s ; A,G =s ,s ;a A，其中a 0為任一常數(shù)。貝ij11221V =aVT(2G ) = 1(G ) HYPERLINK l bookmark103 o Current Document 定理7對(duì)稱律1

11、2設(shè)G = s1, s2; A為一零和對(duì)策，且A = - AT為反對(duì)稱矩陣(亦稱這種對(duì)策為對(duì)稱對(duì)策)。則V = 0GT(G) = T(G)其中T(G)和T (G)為局中人I和II的最優(yōu)策略集。2.3零和對(duì)策的線性規(guī)劃解法當(dāng)m 2且n 2時(shí)，通常采用線性規(guī)劃方法求解零和對(duì)策問題 局中人I選擇混合策略元的目的是使得xTAy = max min xt Ay = max min xtA( y e ) = max min E yx yx yj=1 x y j=1 j j其中e,為只有第j個(gè)分量為1而其余分量均為零的單位向量，E = xTAe。記u三E = minE jjjk j于 y = 1jine.y

12、.在yk = 1，yj = 0(j豐k)時(shí)達(dá)到最小值u，故x應(yīng)為線性規(guī)劃問題。max umin一yj=i a x u, j = 1,2, , n(即 E E )ij ij ki=1=1i=1x 0, i = 1,2, , m解。_同理，y應(yīng)為線性規(guī)劃max va y 0, j = 1,2, ,n由線性規(guī)劃知識(shí)，(2.6)和(2.7)兩個(gè)互為對(duì)偶線性規(guī)劃，它們具有相同的最優(yōu)目標(biāo)函數(shù)值。 TOC o 1-5 h z 不妨設(shè)u 0，對(duì)(2.6)變換x =-襯,i = 1,2, mi u則線性規(guī)劃問題(2.6)化為min x，ii=1a x : 1, j = 1,2, , ni = 1x 0, i =

13、 1,2, , mi同理，對(duì)(2.7)作變換.yj = % ,j = 1,2,，n(2.6)(2.7)(2.8)則線性規(guī)劃問題(2.7)化為三、雙矩陣對(duì)策max 工 yi i=1Eq y 0, jj = 1,2, , n(2.9)雙矩陣對(duì)策又叫二人非常數(shù)和對(duì)策。所謂常數(shù)和對(duì)策是指局中人I和局中人II所贏得的值之和為一常數(shù)。顯然，二人零和對(duì)策是二人常數(shù) 和對(duì)策的特例，即常數(shù)為零。對(duì)于二人常數(shù)和對(duì)策，有純策略對(duì)策和混合策略對(duì)策，其求解方法與二人零和對(duì)策是相同的。二人非 常數(shù)和對(duì)騷稱為雙矩陣對(duì)策。也有純策略對(duì)策和混合策略對(duì)策兩種策略。囚徒困境是一個(gè)典型的二人非常數(shù)和對(duì)策，每人的贏得矩陣是不相同的。其

14、中局中人I有m個(gè)策略%，%，對(duì)于一般純策略問題，局中人I、II的贏得矩陣如表2所示。局中人II有n個(gè)策略%， ，Bn，分別記為S =a , ,a , S =P ,11m 21C1 = (Cj )mxn為局中.人I的贏得矩陣，C 2 =(門)mxn為局中人II的贏得矩陣。因此，雙矩陣對(duì)策記為G = *, S 2, C1, C 2表2定義5雙矩陣對(duì)策的Nash平衡點(diǎn)設(shè)G = SS 2, C1, C 2是一雙矩陣對(duì)策，若等式c1 = min max c1,c2 = min max c2(3 1)i j* j i iji j* j i ijt .)成立，則記，=%*，并稱為局中人I的贏得值，記，并袖2

15、為局中人II的贏得值，稱(%，*)為 G在純策略下的解(或Nash平衡點(diǎn))，稱a產(chǎn)和七*分別為局中人I，II的最優(yōu)純策略。實(shí)際上，定義5也同時(shí)給出了純策略問題的求解方法。因此，對(duì)于囚徒困境的例子，(1,0),(1,0)是Nash平衡點(diǎn)，這里(1,0)表示以概率1取第一個(gè)策略， 也就是說，坦白是他們的最佳策略。如果不存在使式(3.1)成立的對(duì)策，則需要求混合對(duì)策。類似于二人零和對(duì)策情況，需要給出混合對(duì)策 的最優(yōu)解?；旌蠈?duì)策問題的基本概念定義6非合作平衡點(diǎn)在對(duì)策G = S ,S ,C1,C2中若存在策略對(duì)無e S*, y e S*使得1212(3.2)I xtCiy xtCiy, Vx e S*|

16、 XtC2y xtC2y, Vy e S*t2對(duì)稱(x, y)為g的一個(gè)非合作平衡點(diǎn)。記七=xtCiy,七=xtC2y,則稱七,七分別為局中人i , ii的 贏得值。對(duì)于混合對(duì)策問題有以下三個(gè)定理。定理8雙矩陣對(duì)策非合作平衡點(diǎn)的存在性每個(gè)雙矩陣對(duì)策至少存在一個(gè)非合作平衡點(diǎn)。定理9雙矩陣對(duì)策非合作平衡點(diǎn)的判定混合策略(X, y)為對(duì)策G = S1,S2,C1,C2的平衡點(diǎn)的充分必要條件是 cy. xtC1 y,i = 1,2,，m(3.3) j=iEc2X xtC2y,j = 1,2,nij i、-i=1混合對(duì)策問題的求解方法由定義6可知，求解混合對(duì)策就是求非合作對(duì)策的平衡點(diǎn)，進(jìn)一步由定理8得到

17、，求解非合作對(duì)策的 平衡點(diǎn)，就是求解滿足不等式約束(3.3)的可行點(diǎn)。因此，混合對(duì)策問題的求解問題就轉(zhuǎn)化為求不等式約束 (2.6)的可行點(diǎn)，而LINGO軟件可很容易做到這一點(diǎn)。舉例：對(duì)抗賽有甲、乙兩支游泳隊(duì)舉行包括三個(gè)項(xiàng)目的對(duì)抗賽。這兩支游泳隊(duì)各有一名健將級(jí)運(yùn)動(dòng)員(甲隊(duì)為李， 乙隊(duì)為王)，在三個(gè)項(xiàng)目中成績(jī)都很突出，但規(guī)則準(zhǔn)許他們每人只能參加兩項(xiàng)比賽，每隊(duì)的其他兩名運(yùn)動(dòng) 員可參加全部三項(xiàng)比賽。已知各運(yùn)動(dòng)員平時(shí)成績(jī)(秒)見表3。表3甲隊(duì)乙隊(duì)趙錢李王張孫100米蝶泳59.763.257.758.661.464.8100米仰泳67.268.463.261.564.766.5100米蛙泳74.175.5

18、70.372.673.476.9假定各運(yùn)動(dòng)員在比賽中都發(fā)揮正常水平，又比賽第一名得5分，第二名得3分，第三名得1分，問教 練員應(yīng)決定讓自己隊(duì)健將參加哪兩項(xiàng)比賽，使本隊(duì)得分最多？(各隊(duì)參加比賽名單互相保密，定下來后不 準(zhǔn)變動(dòng))解 分別用、a2和a3表示甲隊(duì)中李姓健將不參加蝶泳、仰泳、蛙泳比賽的策略， 分別用約、七和P3表示乙隊(duì)中王姓健將不參加蝶泳、仰泳、蛙泳比賽的策略。當(dāng)甲隊(duì)采用策略a 1，乙隊(duì)采用策略P1時(shí)，在100米蝶泳中，甲隊(duì)中趙獲第一、錢獲第三得6分，乙隊(duì)中張獲第二，得3分；在100米仰泳中，甲隊(duì)中李獲第二，得3分，乙隊(duì)中王獲第一、張獲第三，得6分；在100米蛙泳中，甲隊(duì)中李獲第一，得5

19、分，乙隊(duì)中王獲第二、張獲第三，得4分。也就是說，對(duì)應(yīng)于策略(a1, P2)甲、乙兩隊(duì)各自的得分為(14,13)。表4給出了在全部策略下各隊(duì)的得分。策略aaPPP123(14,13)(13,14)(12,15)(13,14)(12,15)(12,15)(12,15)(12,15)(13,14)表4計(jì)算支付矩陣的Matlab程序，運(yùn)彳亍按照定理8，求最優(yōu)混合策略，就是求不等式約束(3.3)的可行解，求解最優(yōu)混合策略的LINGO程序。求得甲隊(duì)米用的策略是、氣方案各占50%，乙隊(duì)米用的策略是P2、P3方案各占 50%，甲隊(duì)的平均得分為12.5分，乙隊(duì)的平均得分為14.5分。如表5所示。表5策略p 1

20、0.0p 2 0.5七0.5aQB1(14,13)(13,14)(12,15)a 2(13,14)(12,15)(12,15)a3(12,15)(12,15)(13,14)N人合作博弈五、博弈的擴(kuò)展式表述和動(dòng)態(tài)博弈51博弈論的擴(kuò)展式表述具體來講，博弈的擴(kuò)展式表述包括以下要素：參與人集合：i = 1，n，此外，我們將用N來表示虛擬參與人“自然”；參與人的行動(dòng)順序：誰在什么時(shí)候行動(dòng)；參與人的行動(dòng)空間：在每次行動(dòng)時(shí)，參與人有些什么選擇；參與人的信息集：每次行動(dòng)時(shí)，參與人知道些什么；參與人的支付函數(shù)：在行動(dòng)結(jié)束之后，每個(gè)參與人得到些什么(支付是所有行動(dòng)的函數(shù))5 2外博弈樹牛自構(gòu)造選擇)的概率分布。設(shè)

21、想你是一家房地產(chǎn)開發(fā)商(為了討論方便，我們稱你為“開發(fā)商X”，正在考慮是否要在北京的某一 地段開發(fā)一棟新的寫字樓。你面臨的選擇是開發(fā)或不開發(fā)。如果決定開發(fā)，你必須投入1億資金；當(dāng)然， 如果決定不開發(fā)，你的資金投入為0。在做這個(gè)決定時(shí)，你關(guān)心的當(dāng)然是開發(fā)是否有利可圖。像房地產(chǎn)這樣的市場(chǎng)充滿了風(fēng)險(xiǎn)。風(fēng)險(xiǎn)首先來自市場(chǎng)需求的不確定性。需求可能大，也可能小。風(fēng)險(xiǎn) 的另一個(gè)來源是你的競(jìng)爭(zhēng)對(duì)手，房地產(chǎn)開發(fā)商B。讓我們假定開發(fā)商B也面臨與你同樣的決策問題：是否 投入1億資金開發(fā)一棟同樣的寫字樓。假定，如果市場(chǎng)上有兩棟樓出售，需求大時(shí)，每棟售價(jià)可達(dá)1.4億，需求小時(shí)，售價(jià)為7千萬；如果 市場(chǎng)上只有一棟樓出售，需

22、求大時(shí)售價(jià)為1.8億，需求小時(shí)為1.1億。這樣，有以下8種可能的結(jié)果：需求大，你開發(fā)，他不開發(fā)；你的利潤(rùn)為8千萬，他的利潤(rùn)為0。需求大，你不開發(fā)，他開發(fā)；你的利潤(rùn)為0，他的利潤(rùn)為8千萬。需求大，你開發(fā)，他也開發(fā)；你的利潤(rùn)為4千萬，他的利潤(rùn)為4千萬。需求大，你不開發(fā)，他也不開發(fā)；你和他的利潤(rùn)為都為0。需求小，你開發(fā)，他不開發(fā)；你的利潤(rùn)為1千萬，他的利潤(rùn)為0。需求小，你不開發(fā)，他開發(fā)；你的利潤(rùn)為0，他的利潤(rùn)為1千萬。需求小，你開發(fā)，他也開發(fā)；你的利潤(rùn)為-3千萬，他的利潤(rùn)為-3千萬。需求小，你不開發(fā)，他也不開發(fā)；你和他的利潤(rùn)為都為0。在這個(gè)例子中，無論開發(fā)商A還是開發(fā)商B，在決定是否開發(fā)時(shí)，不僅要考

23、慮市場(chǎng)需求的大小，而且 要考慮對(duì)方的行動(dòng)。我們假定該博弈的行動(dòng)順序如下：開發(fā)商A首先行動(dòng)，選擇開發(fā)或不開發(fā)；在A決策后，自然選擇市場(chǎng)需求的大?。婚_發(fā)商B在觀測(cè)到A的決策和市場(chǎng)需求后，決定開發(fā)或不開發(fā)。圖1房地產(chǎn)開發(fā)博弈I博弈樹的基本建筑材料包括結(jié)(nodes)、枝(branches)和信息集(information sets)。結(jié)(nodes)結(jié)包括決策結(jié)(decision nodes)和終點(diǎn)結(jié)(terminal nodes)兩類；決策結(jié)是參與人采取行動(dòng)的時(shí)點(diǎn)， 終點(diǎn)結(jié)是博弈行動(dòng)路徑的終點(diǎn)。一般地，我們用X來表示所有結(jié)的集合，x e X表示某個(gè)選定的結(jié)。用-.表示定義在X上的順序關(guān) 系(pre

24、cedence relation)： x x意味著x在x之前。定義P(x)為x之前的所有結(jié)的集合，簡(jiǎn)稱為x的前列集(the set of precedene)；定義T(x)為x之后的所有結(jié)點(diǎn)的集合，簡(jiǎn)稱為x的后續(xù)集(the set of successors)。如果 P(x) = 0,x 稱為初始結(jié)(initial nodes)如果T(x) = 0,x稱為終點(diǎn)結(jié)(terminal nodes)。除終點(diǎn)結(jié)之外的所有結(jié)都是決策結(jié)。每一個(gè)終點(diǎn)結(jié)完全決定了博弈樹的路徑，我們可以用函數(shù)，(z)表示對(duì)應(yīng)的博弈路徑所導(dǎo)致的第i個(gè)參 與人的支付函數(shù)。枝(branches)在博弈樹上，枝是從一個(gè)決策結(jié)到它的直接后續(xù)結(jié)的連線(有時(shí)用箭頭表述)，每一個(gè)枝代表參與人 的一個(gè)行動(dòng)選擇。一般地，對(duì)于一個(gè)給定的決策結(jié)，x e X，存在一個(gè)有限的行動(dòng)集合A(x)和一個(gè)一一對(duì)應(yīng)的函數(shù)a : t(x) A(x)，這里t(x)是x直接后續(xù)結(jié)的集合。信息集(information sets)博弈樹上的所有決策結(jié)分割