Budget Feasible Mechanism for a k-submodular Function in the Clock Auction Model
摘要
Due to its numerous applications in social marketing and crowdsourcing, the classical topic of designing a budget-feasible mechanism for a submodular valuation function has been well-studied. In this paper, we consider a generalization of this topic: budget-feasible mechanism design for a k-submodular function in the clock auction model. In our problem, each agent has a private cost, and the auctioneer, composed of k departments, attempts to maximize his k-submodular valuation subject to a budget constraint. For the monotone objective, we propose a randomized mechanism with an approximation ratio of \(\frac{1}{5+\sqrt{13}}\) . Additionally, the randomized mechanism can also achieve an approximation ratio of \(\frac{2}{15+3\sqrt{13}}\) for the non-monotone objective. Our mechanism only requires O(kn) value oracle queries, making it more practical.