On the Approximability of Budget Feasible Mechanisms

Details On the Approximability of Budget Feasible Mechanisms On the Approximability of Budget Feasible Mechanisms

2010-07-22

arxiv.org/abs/1007.3801v1

Computer Science

Computer Science and Game Theory

Scientific paper

Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for general submodular functions: we give a randomized mechanism with approximation ratio $7.91$ (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio $8.34$. Further we study the knapsack problem, which is special submodular function, give a $2+\sqrt{2}$ approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.

Affiliated with

Also associated with

No associations

Rating

On the Approximability of Budget Feasible Mechanisms 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 On the Approximability of Budget Feasible Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Approximability of Budget Feasible Mechanisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-611030