  The framework of budget-feasible mechanism design studies procurement
auctions where the auctioneer (buyer) aims to maximize his valuation function
subject to a hard budget constraint. We study the problem of designing truthful
mechanisms that have good approximation guarantees and never pay the
participating agents (sellers) more than the budget. We focus on the case of
general (non-monotone) submodular valuation functions and derive the first
truthful, budget-feasible and $O(1)$-approximate mechanisms that run in
polynomial time in the value query model, for both offline and online auctions.
Prior to our work, the only $O(1)$-approximation mechanism known for
non-monotone submodular objectives required an exponential number of value
queries.
  At the heart of our approach lies a novel greedy algorithm for non-monotone
submodular maximization under a knapsack constraint. Our algorithm builds two
candidate solutions simultaneously (to achieve a good approximation), yet
ensures that agents cannot jump from one solution to the other (to implicitly
enforce truthfulness). Ours is the first mechanism for the problem
where---crucially---the agents are not ordered with respect to their marginal
value per cost. This allows us to appropriately adapt these ideas to the online
setting as well.
  To further illustrate the applicability of our approach, we also consider the
case where additional feasibility constraints are present. We obtain
$O(p)$-approximation mechanisms for both monotone and non-monotone submodular
objectives, when the feasible solutions are independent sets of a $p$-system.
With the exception of additive valuation functions, no mechanisms were known
for this setting prior to our work. Finally, we provide lower bounds suggesting
that, when one cares about non-trivial approximation guarantees in polynomial
time, our results are asymptotically best possible.
