betaFeedback

WorksComputer Science

On the Approximability of Budget Feasible Mechanisms

Abstract

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.917.91 (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio 8.348.34. Further we study the knapsack problem, which is special submodular function, give a 2+22+\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+21+\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.

Paper details

vlnc:W_2jps93g4
Version
v1 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…