金涬, 石纯一. 一种边际效用递减组合拍卖的胜者决定算法[J]. 计算机研究与发展, 2006, 43(7): 1142-1148.
 引用本文: 金涬, 石纯一. 一种边际效用递减组合拍卖的胜者决定算法[J]. 计算机研究与发展, 2006, 43(7): 1142-1148.
Jin Xing, Shi Chunyi. A Winner Determine Algorithm for Combinatorial Auctions with Decreasing Marginal Utilities[J]. Journal of Computer Research and Development, 2006, 43(7): 1142-1148.
 Citation: Jin Xing, Shi Chunyi. A Winner Determine Algorithm for Combinatorial Auctions with Decreasing Marginal Utilities[J]. Journal of Computer Research and Development, 2006, 43(7): 1142-1148.

## 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.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈