高级检索

    一种边际效用递减组合拍卖的胜者决定算法

    A Winner Determine Algorithm for Combinatorial Auctions with Decreasing Marginal Utilities

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

       

      Abstract: Auctions are important mechanisms for resource and task allocation in multi-agent systems (MAS). Auction methods have explicit rules, require less agent abilities and achieve fast and efficient mutual agreements. In most microeconomic theories, consumers are assumed to exhibit decreasing marginal utilities. Aimed at the CAP in combinatorial auction with decreasing marginal utilities, the 1-UNT (1 unit cannot transfer) condition and k-UNT (k unit cannot transfer) condition of allocations are presented. A 1-UNT check based iterative algorithm is developed. The result of 1-UNT check based algorithm is proved with the effective rate of at least 0.5. Experiment study shows that the combination of 1-UNT algorithm and greedy algorithm can achieve better allocation in less time. A k-UNT check based algorithm is also presented proving that even in the simple case of CAP of 2 buyers, the k-UNT check based algorithm can not guarantee higher effective rate of 0.5. The 1-UNT check based algorithm partially improves the work of Benny Lehmann.

       

    /

    返回文章
    返回