论文部分内容阅读
该文旨在对集合对策的解的性质及结构做深入的研究,得到了系统深刻的结果,建立了完善的理论体系,其目的就是为了方便有效地使用高性能计算机这一强有力的工具,实现大量集合之间的复杂运算,以利于快捷、及时、准确地得到对策的解,这在当今讯息万变的世界里,对经济、军事、政治、以及人类生活的各个方面都有着重要的现实意义.该文主要研究了集合对策及其解的计算复杂性.我们从定性的定量两个方面讨论了集合对策的解,在定性方面,我们提出了集合对策联盟力量值的概念,并给出了这个分配方案的公理化特征,证明了在集合对策的分配体系中,联盟力量值是唯一满足全局有效性、等价性和联盟力量单调性的分配方案.这个值是Aarts等人提出的边缘贡献值的一种推广,在单调集合对策中,这两个值是等价的.同时,我们也给出了集合对策的共享边缘贡献值,证明了共享边缘贡献值是唯一满足全局有效性、等价性和共享边缘单调性的分配方案,在证明过程中,我们使用了元素集合对策这一重要工具,它比Aarts等人所使用的方法更具普遍性.基于边缘贡献值、联盟力量值和共享边缘贡献值的共性,我们找到了集合对策的一类一般解.在证明这一类解的唯一性时,我们首次以简单集合对策为工具,使得证明得到简化.再者,我们将物理学中势的概念推广到集合对策中,以此为工具发现了集合对策一个新的值-Driessen-Sun值,并讨论了Driessen-Sun值在研究势性问题中的作用,同时利用限制性全局有效性、等价性和一种单调性对Driessen-Sun值进行了唯一性刻画.其次,我们证明了边缘贡献值具有分配方案的单调性,边缘贡献值及拟边缘贡献值均在集合对策的核心中.在定量方面,我们提出了集合对策的两种定量边缘解,并给出了两种解的公理化特征:有效性、对称性、哑元性、Banzhaf总和性和传递性;另外,我们将Shapley值与Banzhaf值推广到κ-维欧氏空间.最后,我们讨论了集合对策解的计算复杂性,首先将集合对策定量化,找出它一TU-对策解之间的关系,在此基础上,我们利用生成函数的方法得到了在一定条件下,某些特殊对策的解具有多项式算法,其计算量可达O(n<2>Cκ).