Analysis proposes budget-feasible mechanisms for procurement auctions using non-monotone k-submodular objectives, suggesting strategies for multiple agents.
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.
No takes yet. Share an insight, caveat, or question.
Zhang et al. (2025) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: