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.

本文研究了一类采购拍卖问题，涉及到预算约束和非单调子模价值函数。我们提出了可行的机制来最大化拍卖者的估值函数，同时也满足诚实、可行和近似最优的要求，本文所提机制在增加了预算约束的条件下，显著改进了以往的方法。其中以最大割问题为重点，在此问题上，我们的结果显著提高了已知的近似比，同时为只有指数级机制的情况建立了多项式运行时间的结果。