2012/03/20 by Xiaohui Bei, Ning Chen, Nick Gravin +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Approximation algorithm #Auction Theory and Applications #Combinatorial auction #Combinatorics #Common value auction #Discrete mathematics #Economics #Game Theory and Voting Systems #Law, Economics, and Judicial Systems #Mathematical economics #Mathematical optimization #Mathematics #Matroid #Mechanism design #Subadditivity #Submodular set function #Valuation (finance) #cs.GT
paper · pdf · doi:10.1145/2213977.2214020
published as Proceedings of STOC 2012 · to appear in STOC 2012
arxiv created 2012/03/20 · openalex publication_date 2012/05/19 · arxiv updated 2012/11/09 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/29
Budget feasible mechanism design studies procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)?" Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log2n) approximation mechanism for subadditive functions; further, they remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions."