Worst-Case Mechanism Design via Bayesian Analysis
Date of Issue2017
School of Physical and Mathematical Sciences
Budget feasible mechanism design is the study of procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize her valuation function on a subset of purchased 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 to the social optimum?” Singer [Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions have a constant approximation mechanism. Dobzinski, Papadimitriou, and Singer [Proceedings of the 12th ACM Conference on Electronic Commerce, ACM, New York, 2011, pp. 273--282] gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that “A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions.” In this paper, we give an affirmative answer to this question. To this end we relax the prior-free mechanism design framework to the Bayesian mechanism design framework (these are two standard approaches from computer science and economics, respectively). Then we convert our results in the Bayesian setting back to the prior-free framework by employing Yao's minimax principle. Along the way, we obtain the following results: (i) a polynomial time constant approximation for XOS valuations (a.k.a. fractionally subadditive valuations, a superset of submodular functions), (ii) a polynomial time $O(\log n / \log \log n)$-approximation for general subadditive valuations, (iii) a constant approximation for general subadditive functions in the Bayesian framework---we allow correlation in the distribution of sellers' costs and provide a universally truthful mechanism, (iv) the existence of a prior-free constant approximation mechanism via Yao's minimax principle.
SIAM Journal on Computing
© 2017 Society for Industrial and Applied Mathematics (SIAM). This paper was published in SIAM Journal on Computing and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics (SIAM). The published version is available at: [http://dx.doi.org/10.1137/16M1067275]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.