论文部分内容阅读
作为一种协商手段，拍卖方法是多Agent系统（MAS）的重要问题之一，组合拍卖是其中的研究热点．提出了物品分配方案的k—UNT条件，并给出了一种基于1-UNT检查的求边际效用递减组合拍卖的近似算法，证明了1-UNT算法的解的效用率不低于0．5．实验表明，将1-UNT算法和贪心算法结合可在较短的时间内求得较优解．还给出了基于k—UNT检查的胜者决定算法，证明了即使在2人组合拍卖的简单情况下，基于k—UNT检查的胜者决定算法都不可能保证解的效用率大于0．5．1-UNT算法部分改进了Lehmann等人的工作．