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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Budget Feasible Mechanism for a k-submodular Function in the Clock Auction Model

  • Hongyang Zhang,
  • Wenchang Luo

摘要

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.