Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders

• 成果类型: Article
• 署名作者: Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
• 署名单位: Cornell University; Hebrew University of Jerusalem; Yale University; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0436
• 发表日期: 2010
• 页码: 1-13
• 关键词: Complexity

摘要

In a combinatorial auction m heterogenous indivisible items are sold to n bidders. This paper considers settings in which the valuation functions of the bidders are known to be complement free (a.k.a. subadditive). We provide several approximation algorithms for the social-welfare maximization problem in such settings. First, we present a logarithmic upper bound for the case that the access to the valuation functions is via demand queries. For the weaker value queries model we provide a tight O(root m) approximation. Unlike the other algorithms we present, this algorithm is also incentive compatible. Finally, we present two approximation algorithms for the more restricted class of XOS valuations: A simple deterministic algorithm that provides an approximation ratio of two and an optimal e/(e - 1) approximation achieved via randomized rounding. We also present optimal lower bounds for both the demand oracles model and the value oracles model.