  We study a class of procurement auctions with a budget constraint, where an
auctioneer is interested in buying resources or services from a set of agents.
Ideally, the auctioneer would like to select a subset of the resources so as to
maximize his valuation function, without exceeding a given budget. As the
resources are owned by strategic agents however, our overall goal is to design
mechanisms that are truthful, budget-feasible, and obtain a good approximation
to the optimal value. Budget-feasibility creates additional challenges, making
several approaches inapplicable in this setting. Previous results on
budget-feasible mechanisms have considered mostly monotone valuation functions.
In this work, we mainly focus on symmetric submodular valuations, a prominent
class of non-monotone submodular functions that includes cut functions. We
begin first with a purely algorithmic result, obtaining a
$\frac{2e}{e-1}$-approximation for maximizing symmetric submodular functions
under a budget constraint. We view this as a standalone result of independent
interest, as it is the best known factor achieved by a deterministic algorithm.
We then proceed to propose truthful, budget feasible mechanisms (both
deterministic and randomized), paying particular attention on the Budgeted Max
Cut problem. Our results significantly improve the known approximation ratios
for these objectives, while establishing polynomial running time for cases
where only exponential mechanisms were known. At the heart of our approach lies
an appropriate combination of local search algorithms with results for monotone
submodular valuations, applied to the derived local optima.
