On the approximability of budget feasible mechanisms

TLDR

Budget‑feasible mechanisms, introduced by Singer (FOCS 2010), adapt algorithmic mechanism design to settings with a hard budget constraint. The authors aim to design truthful budget‑feasible mechanisms for monotone submodular functions—including the knapsack problem—and to improve their approximation guarantees. They obtain randomized and deterministic approximation ratios of 7.91 and 8.34 for general submodular functions, 3 and 2 + √2 for knapsack, extend these results to heterogeneous‑item knapsacks, and prove unconditional lower bounds of 2 for randomized and 1 + √2 for deterministic 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 monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7.91 (improving on the previous best-known result 233.83), and a deterministic mechanism with an approximation ratio of 8.34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results 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 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions.