English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online