Budget Feasible Mechanism Design: From Prior-Free to Bayesian

Details Budget Feasible Mechanism Design: From Prior-Free to Bayesian Budget Feasible Mechanism Design: From Prior-Free to Bayesian

2012-03-20

arxiv.org/abs/1203.4455v1

Computer Science

Computer Science and Game Theory

to appear in STOC 2012

Scientific paper

Budget feasible mechanism design studies procurement combinatorial auctions where 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 showed that additive and submodular functions have such constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an O(log^2 n)-approximation mechanism for subadditive functions; they also remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions." We address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis. For the prior-free framework, we use an LP that describes the fractional cover of the valuation function; it is also connected to the concept of approximate core in cooperative game theory. We provide an O(I)-approximation mechanism for subadditive functions, via the worst case integrality gap I of LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, and for valuations with a constant I. XOS valuations are an important class of functions that lie between submodular and subadditive classes. We give another polynomial time O(log n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations. 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.

Affiliated with

Also associated with

No associations

Rating

Budget Feasible Mechanism Design: From Prior-Free to Bayesian does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Budget Feasible Mechanism Design: From Prior-Free to Bayesian, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Budget Feasible Mechanism Design: From Prior-Free to Bayesian will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495322