A Winner Determine Algorithm for Combinatorial Auctions with Decreasing Marginal Utilities

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.