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