Mechanisms for Complement-Free Procurement

摘要

We study procurement auctions when the buyer has complenient-free (subadditive) objectives in the budget (feasibility model [18]. For general subadditive functions we give a randomized universally truthful mechanism which is an O(log~2 n) approximation, and an O(log~3 n) deterministic truthful approximation mechanism; both mechanisms are in the demand oracle model. For cut functions, an interesting case of nonincreas-ing objectives, we give both randomized and deterministic truthful and budget feasible approximation mechanisms that achieve a constant, approximation factor.