On the approximability of budget feasible mechanisms

Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mech-anism 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 random-ized 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+ 2 approximation deterministic mechanism (improv-ing 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 + 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.