2006年第9期計算機系統(tǒng)應(yīng)用AMAIDS的研究與應(yīng)用The Research and Application of AMAIDs石黎(湖北經(jīng)濟(jì)學(xué)院計算機科學(xué)與技術(shù)學(xué)院武漢430205)林仙(云南省國家稅務(wù)局昆明650051)摘要: AMAIDs是在MADs和ADs的基礎(chǔ)上發(fā)展而來。本文首先研究了MADs和ADs表示求解博弈,然后在此基礎(chǔ)上提出 AMAIDS,它是將MADs和ADS兩者相融合得到了一種能有效的表示非對稱博弈的模型,并使用一個實例來說明 AMAIDS的應(yīng)用。關(guān)健詞: AMAIDS非對稱博弈 MAIDS AIDs1引言說,一個MAD可以簡單的看作是一個影響圖,但此時非對稱博弈是一種普遍存在的博弈現(xiàn)象現(xiàn)實中影響圖中的決策節(jié)點和效用節(jié)點不再是屬于一個a大量的博弈都呈現(xiàn)出非對稱的特性,如何表示和求解9em的而是屬于多個ogen的,所以MADs中的每個非對稱博弈就是一個急迫需要解決的問題了。MADS決策節(jié)點和效用節(jié)點都是和某一個ogem相關(guān)聯(lián)的。對于對稱博弈來說是一種很有效的表示方法,但是非MADs定義了非合作博弈的語義:一個MAD可以轉(zhuǎn)換對稱博弈的表示問題在MADS中卻是一個難以解決的成一棵等價的博弈樹。MADs能夠以自然的表示形式問題而對于非對稱單-ogen決策問題來說,ADs能來描述復(fù)雜的博弈并將變量級的相互作用結(jié)構(gòu)清晰的對它進(jìn)行有效的表示和求解,所以我們將MADs和表示出來而且,一般來說,MAD比起博弈樹來說是一ADs兩者相融合得到了一種能有效的表示非對稱博弈種更加壓縮的表示形式。就像貝葉斯網(wǎng)能夠具體的表的模型:非對稱多- agent影響圖( Asymmetric M-示出概率變量之間的相互依賴關(guān)系一樣,MADs能夠agent Infiuence Diagrams, AMAIDs具體的表示出決策變量之間的依賴關(guān)系,從而給出了AMAIDs是在多-gen影響圖(Mi- agent In-策略相關(guān)性的概念,策略相關(guān)性的概念使我們能夠定nce Diagrams,MADs和非對稱影響圖(Asym義一個稱為相關(guān)圖的數(shù)據(jù)結(jié)構(gòu)——個刻畫MAD中metric Infiuence Diagrams,ADs)(2的基礎(chǔ)上發(fā)展而來的決策變量間的依賴關(guān)系的有向圖。利用相關(guān)圖能夠的,它繼承了MADs在表示博弈時所具有的優(yōu)點同時很自然的將一個復(fù)雜的博弈分解成多個相互作用的片又具備了有效的表示非對稱博弈的特點。對于段并且在保證得到整個博弈的全局均衡的條件下求解AMDs的求解,我們首先采用ADs中分解非對稱問各個子博弈,對于每個子博弈的求解方法是首先將它題的方法將待求解的 AMAIDS分解成多個MADs,然后轉(zhuǎn)換成一棵博弈樹,然后再利用標(biāo)準(zhǔn)的博弈求解方我們用求解MADs的方法分別對分解得到的各個法對其進(jìn)行求解。該算法比標(biāo)準(zhǔn)的博弈論求解算法MADs進(jìn)行求解最后綜合各個MADs求解得到的結(jié)更加有效,包括一些在博弈樹上直接進(jìn)行求解的比較果以得出我們最終的結(jié)果有效的算法。用MADs來表示和求解博弈°YH中國煤化工對稱單- agentKo|er和Mkh給出的多 agents影響圖(MADs)CNMHG是對貝葉斯網(wǎng)(BN)和影響圖(0s)4的擴展,它能夠Nielsen和 Jensen12)提出了ADs來表示和求解非表示涉及多 agents的決策問題。實際上從結(jié)構(gòu)上來對稱決策問題。ADs建立在影響圖Ds的基礎(chǔ)之上Applied Technique應(yīng)用技術(shù)57計算機系統(tǒng)應(yīng)用2006年第9期他將決策問題的非對稱性定性的在圖形結(jié)構(gòu)中表示出模型,它融合了MADs和ADs并同時繼承了它們各自來,因此我們可以從ADS中直接獲得決策問題的非對的優(yōu)點。我們對 AMAIDs的求解:首先采用ADs中分解稱信息。簡單的說,一個AD就是一個帶標(biāo)記的有向非對稱影響圖的方法將待求解的非對稱多-ogen影響圖,它用一個約束弧集和一個標(biāo)記集來表示決策問題的圖分解成多個多 agent影響圖;然后利用MADs中求非對稱性,約束弧集是信息弧集的一個子集,一條約束解多- agent影響圖的方法為每一個分解得到的多-0弧(X,D)由節(jié)點X指向一個決策節(jié)點D并用虛線來表gent影響圖求解出一個均衡;最后合并求解結(jié)果,找到示,該弧表示D的可選行動集將根據(jù)Ⅹ取值的不同而不初始問題的均衡解。下面我們通過一個簡單的例子來同。另外,標(biāo)記集與一個所有節(jié)點和信息弧的子集相關(guān)看 AMAIDS是如何表示和求解非對稱博弈的聯(lián),一個標(biāo)記定義了在什么樣的條件下與之相關(guān)聯(lián)的節(jié)4.2應(yīng)用實例點或信息弧才會在決策場景中出現(xiàn)。ADs的求解采用問題陳述:一個西方國家的某公司與其工會之間了“分而治之”的方法,將一個初始的菲對稱決策問題分將就工資問題進(jìn)行一場至多持續(xù)兩個周期的談判。首解成多個對稱的子問題,也就是將一個非對稱影響圖分先假設(shè)工作是固定的,工會向公司提出工資價目然后解成多個影響圖,然后再利用已有的求解影響圖的方由公司來決定是否雇用工會成員,如果不被公司雇用,法來分別求解各個分解得到的影響圖最后通過合并工會保留工資為0。公司的盈利以F表示,它是公司的每個影響圖的結(jié)果最終得到?jīng)Q策問題的最優(yōu)解。私人信息,也就是說只有公司知道F的值,而工會不知道F的值,設(shè)討價還價的談判至多持續(xù)兩個周期。在4 AMAIDS的提出與應(yīng)用第一個周期,工會根據(jù)對公司類型的先驗信念開出4. 1 AMADs個工資價目W,假如公司接受這個開價,那么博弈宣在MADs中,作者指出了MADs和博弈樹可相互布結(jié)束,工會盈利為W而公司的盈利為(F-W)。倘轉(zhuǎn)換的關(guān)系,對對稱的博弈來說,采用MAD表示方法若公司拒絕工會提出的W,那么博弈進(jìn)入第二個周能比用博弈樹在很大的程度上節(jié)省空間,可以說期在這個周期內(nèi),工會根據(jù)上一周期博弈的結(jié)果調(diào)整MADs是博弈的一種壓縮的表示方法,但對于非對稱對公司類型的信念并給出另一個工資開價W2,如果公博弈來說,情況就剛好相反了,此時,由于博弈樹本身司接受W2,(考慮貼現(xiàn))局中人盈利為:工會δW,公就具有非對稱的特點所以它表示非對稱博弈就會非常司6(P-W2)。如果公司拒絕工會的第二次開價,那么自然而簡潔而MADs表示將會比博弈樹表示占用更博弈結(jié)束,此時兩者的盈利都等于0.在現(xiàn)實生活中,大的空間,用MADs來表示一個簡單的非對稱博弈就公司的類型F以及工會的開價W可以有許多種可能,有可能導(dǎo)致表示的爆炸。因此,需要對原有的MADs甚至可以在一個連續(xù)的區(qū)間上取值,這樣的博弈表示進(jìn)行擴展使之能夠同樣以一種壓縮的方式來表示非對起來比較困難,為了將其離散化和討論的方便,這里就稱博弈,即兼有博弈樹和MADs兩者的優(yōu)點。我們將只考慮一種它的最簡形式:公司的類型只有兩種:PhADs表示非對稱決策問題的方法引入到MADs中兩和P;工會的工資開價也只有兩個W和Wh者融合得到了能夠有效表示非對稱博弈的 AMAIDs博弈樹表示:如圖1所示。個非對稱多- agent影響圖( AMAIDs)是一個帶博弈樹的每一個葉節(jié)點表示一種博弈的結(jié)局,每標(biāo)記的有向圖,與多-0gent影響圖MAD對比,個結(jié)局對應(yīng)著一個所有局中人的盈利向量?？梢钥碅MAIDs除了具有MADs的結(jié)構(gòu)特點外,在模型中加入出,在這個博弈樹中,一共有一個隨機節(jié)點和四個決策了約束弧和標(biāo)記機制來表示博弈的非對稱性;與非對節(jié)點每個節(jié)點都有兩個取值那么所有節(jié)點的笛卡兒鄭況和標(biāo)況半表示題的半對稱性的物遠(yuǎn)將有21個年在字中我們總共只ADs中的單- agent決策問題擴展成允許有多個a對稱博CNMHGgents的博弈情況?？梢? AMAIDs是一種既能夠表示多AMAIDS表示:如圖2所示,我們將公司在第一周ogen決策問題又能表示非對稱決策問題的圖形表示期的決策用節(jié)點D來表示,與圖2的MAD相比,圖3舟數(shù)捆Tohe2006年第9期計算機系統(tǒng)應(yīng)用中的AMAD包含了兩個標(biāo)記并且它們都是D=R,即是其后繼的隨機節(jié)點也不再進(jìn)行后驗信念的修改在現(xiàn)實的博弈中,問題往往要復(fù)雜的多, AMAIDS的優(yōu)越性也將更明顯。AMAIDS的另一個優(yōu)點是將一個較大的一王會1-2非對稱博弈分解成多個對稱博弈來求Wh解,有效的提高了博弈求解的效率。下面我們將圖2的MADs分解成多個公司MADs的集合,分解后得到如圖3所示的結(jié)果。圖3(a)所示的MAD中,決策節(jié)點D被一個隨機節(jié)點D所代替,并R1且該節(jié)點只有一個取值,即Dl=A,D工會貴王會1-q以概率1取到它的這個唯一值;在(b)所示的MAD中,決策節(jié)點D同樣被一個只有一個取值的隨機節(jié)點D2所代替,D2以概率1取D=R。對(a)和A2R2●A2。R2(b)所示的兩個MADs,利用2中給出的方法分別進(jìn)行求解可以得到兩個均工會王會1-衡解,比較兩者選出其中的最優(yōu)者就得公司到了整個非對稱博弈的解。5結(jié)論圖1鑒于MADs只能有效的表示對稱的多-gent決策問題,ADs只能表示非對稱的單- agent決策D=R問題,本文在MADs和ADs的基礎(chǔ)上提出了 AMAIDS,融合了這兩者的優(yōu)點同時克服了它們各自的D一工壘?公罰2缺點,是一種有效的表示非對稱的多- agent決策問題的方法。在今后的研究中,我們將著力于N尋找更有效的求解 AMAIDS的方法以及博弈的多-均衡解處理問題等相關(guān)問題圖2考文默在第一周期的博弈中,公司拒絕了工會提出的工資開1 D Koller and B Milch. Multi價W,兩個標(biāo)記分別與隨機節(jié)點B2和決策節(jié)點“工會中國煤化工 Fence diagrams for2”相關(guān)聯(lián),也就是說,如果公司在第一周期就接受了工CN MH Genting and solving會的工資開價W的話,那么就沒有必要形成信念B2,games. In UCAl, pages 1027同時“工會2"及其后繼的決策節(jié)點都不再需要決策0342001算機系統(tǒng)應(yīng)用006年第9期2 Nielsen. T. D. and F. v. jJenseng and solvitymmetric bayesian decisioartment of Computer ScienceDenmank. R-99-50103施錫銓、博弈論[M],上海上海aI D=A財經(jīng)大學(xué)出版社,2000年putation of equilibrium in fi-nite games. In Handbook of Com-工會1工會2pages 87-142. Elsevier Science,Amsterdam 19965 F Jensen, F V Jensen and S LDittmer. From infiuence diagrams[b) D=RUAl, pages 367-373, 7(上接第56頁)技術(shù),防火墻產(chǎn)品也是網(wǎng)絡(luò)防護(hù)設(shè)備中最常用的防護(hù)4CMP隱蔽通道攻擊穿透技術(shù)防范設(shè)備。在網(wǎng)絡(luò)安全事件日益增多的今天,從防護(hù)者的CMP隱蔽通道攻擊穿透技術(shù)本質(zhì)上是針對CMP角度對網(wǎng)絡(luò)攻擊技術(shù)尤其是防火墻的攻擊穿透技術(shù)進(jìn)協(xié)議本身的特點而研究實現(xiàn)的一種防火墻攻擊穿透技行研究,對于我們更好地保護(hù)好已方網(wǎng)絡(luò),更好地防止術(shù),所以對該攻擊穿透技術(shù)最好的防范方法是在網(wǎng)絡(luò)網(wǎng)絡(luò)安全事件的發(fā)生有重要意義。中禁止CMP協(xié)議的報文通過,當(dāng)然,這樣對網(wǎng)絡(luò)管理和運行都會帶來一定的不便。要很好地防范利用CMP隱蔽通道攻擊穿透技術(shù)實現(xiàn)的網(wǎng)絡(luò)攻擊,就應(yīng)對進(jìn)1孟盂朝霞、吳展暉,CMP的應(yīng)用、缺陷及防御,運城學(xué)出網(wǎng)絡(luò)的數(shù)據(jù)包尤其是從外網(wǎng)到內(nèi)網(wǎng)的CMP協(xié)議數(shù)院學(xué)報,NO.3,21-22,2003。據(jù)包進(jìn)行監(jiān)控和分析,一旦發(fā)現(xiàn)有異常的MP協(xié)議數(shù)2周炎濤、李立明,τPP協(xié)議下網(wǎng)絡(luò)編程技術(shù)及其據(jù)包或本來不該有的CMP協(xié)議數(shù)據(jù)包出現(xiàn),就要立即實現(xiàn)航空計算技術(shù),No3,122-124,2002采取措施因為這很有可能就是利用CMP隱蔽通道攻3陳康榮,防火墻穿透方法初探,計算機安全,No.8,擊穿透技術(shù)而實現(xiàn)的網(wǎng)絡(luò)攻擊報文。32-34,2003。4宋V口中國煤化工機理與防范,計算5結(jié)束語機CNMHG目前防火墻技術(shù)是網(wǎng)絡(luò)安全防護(hù)技術(shù)中最常用的5宿潔、袁軍鵬,防火墻技術(shù)及其進(jìn)展,計算機工程與應(yīng)用,No9,147-149,200460轉(zhuǎn)捆 Technique