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