The Budget-Feasible Mechanisms on Non-Monotone k-Submodular Objectives for the Offline and Online Procurement Auctions

Many application areas such as influence maximization with [Formula: see text] topics, sensor placement with [Formula: see text] type sensors, multi-cooperative games, et al. are captured by maximizing [Formula: see text]-submodular objectives under a knapsack constraint. Assuming that the items in the ground set are strategic agents with private costs, a natural model of procurement auctions may be generated. Within the budget constraint, an auctioneer consisting of [Formula: see text] departments strives to maximize his valuation function. Using the simultaneous greedy technique, we investigate the case of non-monotone [Formula: see text]-submodular valuation functions and propose truthful, budget-feasible, and [Formula: see text]-approximation mechanisms in polynomial time for both online and offline procurement auctions.