AMAIDs的研究与应用

2006年第9期计算机系统应用AMAIDS的研究与应用The Research and Application of AMAIDs石黎(湖北经济学院计算机科学与技术学院武汉430205)林仙(云南省国家税务局昆明650051)摘要: AMAIDs是在MADs和ADs的基础上发展而来。本文首先研究了MADs和ADs表示求解博弈,然后在此基础上提出 AMAIDS,它是将MADs和ADS两者相融合得到了一种能有效的表示非对称博弈的模型,并使用一个实例来说明 AMAIDS的应用。关健词: AMAIDS非对称博弈 MAIDS AIDs1引言说,一个MAD可以简单的看作是一个影响图,但此时非对称博弈是一种普遍存在的博弈现象现实中影响图中的决策节点和效用节点不再是属于一个a大量的博弈都呈现出非对称的特性,如何表示和求解9em的而是属于多个ogen的,所以MADs中的每个非对称博弈就是一个急迫需要解决的问题了。MADS决策节点和效用节点都是和某一个ogem相关联的。对于对称博弈来说是一种很有效的表示方法,但是非MADs定义了非合作博弈的语义:一个MAD可以转换对称博弈的表示问题在MADS中却是一个难以解决的成一棵等价的博弈树。MADs能够以自然的表示形式问题而对于非对称单-ogen决策问题来说,ADs能来描述复杂的博弈并将变量级的相互作用结构清晰的对它进行有效的表示和求解,所以我们将MADs和表示出来而且,一般来说,MAD比起博弈树来说是一ADs两者相融合得到了一种能有效的表示非对称博弈种更加压缩的表示形式。就像贝叶斯网能够具体的表的模型:非对称多- agent影响图( Asymmetric M-示出概率变量之间的相互依赖关系一样,MADs能够agent Infiuence Diagrams, AMAIDs具体的表示出决策变量之间的依赖关系,从而给出了AMAIDs是在多-gen影响图(Mi- agent In-策略相关性的概念,策略相关性的概念使我们能够定nce Diagrams,MADs和非对称影响图(Asym义一个称为相关图的数据结构——个刻画MAD中metric Infiuence Diagrams,ADs)(2的基础上发展而来的决策变量间的依赖关系的有向图。利用相关图能够的,它继承了MADs在表示博弈时所具有的优点同时很自然的将一个复杂的博弈分解成多个相互作用的片又具备了有效的表示非对称博弈的特点。对于段并且在保证得到整个博弈的全局均衡的条件下求解AMDs的求解,我们首先采用ADs中分解非对称问各个子博弈,对于每个子博弈的求解方法是首先将它题的方法将待求解的 AMAIDS分解成多个MADs,然后转换成一棵博弈树,然后再利用标准的博弈求解方我们用求解MADs的方法分别对分解得到的各个法对其进行求解。该算法比标准的博弈论求解算法MADs进行求解最后综合各个MADs求解得到的结更加有效,包括一些在博弈树上直接进行求解的比较果以得出我们最终的结果有效的算法。用MADs来表示和求解博弈°YH中国煤化工对称单- agentKo|er和Mkh给出的多 agents影响图(MADs)CNMHG是对贝叶斯网(BN)和影响图(0s)4的扩展,它能够Nielsen和 Jensen12)提出了ADs来表示和求解非表示涉及多 agents的决策问题。实际上从结构上来对称决策问题。ADs建立在影响图Ds的基础之上Applied Technique应用技术57计算机系统应用2006年第9期他将决策问题的非对称性定性的在图形结构中表示出模型,它融合了MADs和ADs并同时继承了它们各自来,因此我们可以从ADS中直接获得决策问题的非对的优点。我们对 AMAIDs的求解:首先采用ADs中分解称信息。简单的说,一个AD就是一个带标记的有向非对称影响图的方法将待求解的非对称多-ogen影响图,它用一个约束弧集和一个标记集来表示决策问题的图分解成多个多 agent影响图;然后利用MADs中求非对称性,约束弧集是信息弧集的一个子集,一条约束解多- agent影响图的方法为每一个分解得到的多-0弧(X,D)由节点X指向一个决策节点D并用虚线来表gent影响图求解出一个均衡;最后合并求解结果,找到示,该弧表示D的可选行动集将根据Ⅹ取值的不同而不初始问題的均衡解。下面我们通过一个简单的例子来同。另外,标记集与一个所有节点和信息弧的子集相关看 AMAIDS是如何表示和求解非对称博弈的联,一个标记定义了在什么样的条件下与之相关联的节4.2应用实例点或信息弧才会在决策场景中出现。ADs的求解采用问题陈述:一个西方国家的某公司与其工会之间了“分而治之”的方法,将一个初始的菲对称决策问题分将就工资问题进行一场至多持续两个周期的谈判。首解成多个对称的子问题,也就是将一个非对称影响图分先假设工作是固定的,工会向公司提出工资价目然后解成多个影响图,然后再利用已有的求解影响图的方由公司来决定是否雇用工会成员,如果不被公司雇用,法来分别求解各个分解得到的影响图最后通过合并工会保留工资为0。公司的盈利以F表示,它是公司的每个影响图的结果最终得到决策问题的最优解。私人信息,也就是说只有公司知道F的值,而工会不知道F的值,设讨价还价的谈判至多持续两个周期。在4 AMAIDS的提出与应用第一个周期,工会根据对公司类型的先验信念开出4. 1 AMADs个工资价目W,假如公司接受这个开价,那么博弈宣在MADs中,作者指出了MADs和博弈树可相互布结束,工会盈利为W而公司的盈利为(F-W)。倘转换的关系,对对称的博弈来说,采用MAD表示方法若公司拒绝工会提出的W,那么博弈进入第二个周能比用博弈树在很大的程度上节省空间,可以说期在这个周期内,工会根据上一周期博弈的结果调整MADs是博弈的一种压缩的表示方法,但对于非对称对公司类型的信念并给出另一个工资开价W2,如果公博弈来说,情况就刚好相反了,此时,由于博弈树本身司接受W2,(考虑贴现)局中人盈利为:工会δW,公就具有非对称的特点所以它表示非对称博弈就会非常司6(P-W2)。如果公司拒绝工会的第二次开价,那么自然而简洁而MADs表示将会比博弈树表示占用更博弈结束,此时两者的盈利都等于0.在现实生活中,大的空间,用MADs来表示一个简单的非对称博弈就公司的类型F以及工会的开价W可以有许多种可能,有可能导致表示的爆炸。因此,需要对原有的MADs甚至可以在一个连续的区间上取值,这样的博弈表示进行扩展使之能够同样以一种压缩的方式来表示非对起来比较困难,为了将其离散化和讨论的方便,这里就称博弈,即兼有博弈树和MADs两者的优点。我们将只考虑一种它的最简形式:公司的类型只有两种:PhADs表示非对称决策问题的方法引入到MADs中两和P;工会的工资开价也只有两个W和Wh者融合得到了能够有效表示非对称博弈的 AMAIDs博弈树表示:如图1所示。个非对称多- agent影响图( AMAIDs)是一个带博弈树的每一个叶节点表示一种博弈的结局,每标记的有向图,与多-0gent影响图MAD对比,个结局对应着一个所有局中人的盈利向量。可以看AMAIDs除了具有MADs的结构特点外,在模型中加入出,在这个博弈树中,一共有一个随机节点和四个决策了约束弧和标记机制来表示博弈的非对称性;与非对节点每个节点都有两个取值那么所有节点的笛卡儿郑况和标况半表示题的半对称性的物远将有21个年在字中我们总共只ADs中的单- agent决策问题扩展成允许有多个a对称博CNMHGgents的博弈情况。可见, AMAIDs是一种既能够表示多AMAIDS表示:如图2所示,我们将公司在第一周ogen决策问题又能表示非对称决策问题的图形表示期的决策用节点D来表示,与图2的MAD相比,图3舟数捆Tohe2006年第9期计算机系统应用中的AMAD包含了两个标记并且它们都是D=R,即是其后继的随机节点也不再进行后验信念的修改在现实的博弈中,问题往往要复杂的多, AMAIDS的优越性也将更明显。AMAIDS的另一个优点是将一个较大的一王会1-2非对称博弈分解成多个对称博弈来求Wh解,有效的提高了博弈求解的效率。下面我们将图2的MADs分解成多个公司MADs的集合,分解后得到如图3所示的结果。图3(a)所示的MAD中,决策节点D被一个随机节点D所代替,并R1且该节点只有一个取值,即Dl=A,D工会貴王会1-q以概率1取到它的这个唯一值;在(b)所示的MAD中,决策节点D同样被一个只有一个取值的随机节点D2所代替,D2以概率1取D=R。对(a)和A2R2●A2。R2(b)所示的两个MADs,利用2中给出的方法分别进行求解可以得到两个均工会王会1-衡解,比较两者选出其中的最优者就得公司到了整个非对称博弈的解。5结论图1鉴于MADs只能有效的表示对称的多-gent决策问题,ADs只能表示非对称的单- agent决策D=R问题,本文在MADs和ADs的基础上提出了 AMAIDS,融合了这两者的优点同时克服了它们各自的D一工垒?公罚2缺点,是一种有效的表示非对称的多- agent决策问题的方法。在今后的研究中,我们将着力于N寻找更有效的求解 AMAIDS的方法以及博弈的多-均衡解处理问题等相关问题图2考文默在第一周期的博弈中,公司拒绝了工会提出的工资开1 D Koller and B Milch. Multi价W,两个标记分别与随机节点B2和决策节点“工会中国煤化工 Fence diagrams for2”相关联,也就是说,如果公司在第一周期就接受了工CN MH Genting and solving会的工资开价W的话,那么就没有必要形成信念B2,games. In UCAl, pages 1027同时“工会2"及其后继的决策节点都不再需要决策0342001算机系统应用006年第9期2 Nielsen. T. D. and F. v. jJenseng and solvitymmetric bayesian decisioartment of Computer ScienceDenmank. R-99-50103施锡铨、博弈论[M],上海上海aI D=A财经大学出版社,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页)技术,防火墙产品也是网络防护设备中最常用的防护4CMP隐蔽通道攻击穿透技术防范设备。在网络安全事件日益增多的今天,从防护者的CMP隐蔽通道攻击穿透技术本质上是针对CMP角度对网络攻击技术尤其是防火墙的攻击穿透技术进协议本身的特点而研究实现的一种防火墙攻击穿透技行研究,对于我们更好地保护好已方网络,更好地防止术,所以对该攻击穿透技术最好的防范方法是在网络网络安全事件的发生有重要意义。中禁止CMP协议的报文通过,当然,这样对网络管理和运行都会带来一定的不便。要很好地防范利用CMP隐蔽通道攻击穿透技术实现的网络攻击,就应对进1孟盂朝霞、吴展晖,CMP的应用、缺陷及防御,运城学出网络的数据包尤其是从外网到内网的CMP协议数院学报,NO.3,21-22,2003。据包进行监控和分析,一旦发现有异常的MP协议数2周炎涛、李立明,τPP协议下网络编程技术及其据包或本来不该有的CMP协议数据包出现,就要立即实现航空计算技术,No3,122-124,2002采取措施因为这很有可能就是利用CMP隐蔽通道攻3陈康荣,防火墙穿透方法初探,计算机安全,No.8,击穿透技术而实现的网络攻击报文。32-34,2003。4宋V口中国煤化工机理与防范,计算5结束语机CNMHG目前防火墙技术是网络安全防护技术中最常用的5宿洁、袁军鹏,防火墙技术及其进展,计算机工程与应用,No9,147-149,200460转捆 Technique