Budget feasible mechanism design : from prior-free to Bayesian

• Main Authors: Bei, Xiaohui, Chen, Ning, Gravin, Nick, Lu, Pinyan
• Other Authors: School of Physical and Mathematical Sciences
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/98770; http://hdl.handle.net/10220/12821
• Institution: Nanyang Technological University

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(log 2n) 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." In this paper, we address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis, which are two standard approaches from computer science and economics, respectively. • For the prior-free framework, we use a linear program (LP) that describes the fractional cover of the valuation function; the LP is also connected to the concept of approximate core in cooperative game theory. We provide a mechanism for subadditive functions whose approximation is O(I), via the worst case integrality gap I of this LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, as well as for valuations having a constant integrality gap. XOS valuations are an important class of functions and lie between the submodular and the subadditive classes of valuations. We further give another polynomial time O(log n/log log n) sub-logarithmic approximation mechanism for subadditive functions. Both of our mechanisms improve the best known approximation ratio O(log 2 n). • For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.