Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/98770
Title: Budget feasible mechanism design : from prior-free to Bayesian
Authors: Bei, Xiaohui
Chen, Ning
Gravin, Nick
Lu, Pinyan
Issue Date: 2012
Source: Bei, X., Chen, N., Gravin, N., & Lu, P. (2012). Budget feasible mechanism design: from prior-free to bayesian. Proceedings of the 44th symposium on Theory of Computing - STOC '12, 449-458.
Conference: Symposium on Theory of Computing (44th : 2012)
Abstract: 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.
URI: https://hdl.handle.net/10356/98770
http://hdl.handle.net/10220/12821
DOI: 10.1145/2213977.2214020
Schools: School of Physical and Mathematical Sciences 
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Conference Papers

SCOPUSTM   
Citations 10

52
Updated on Mar 27, 2024

Page view(s) 10

846
Updated on Mar 27, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.