On the strategyproof allocation of items under a budget constraint

• 成果类型: Article
• 署名作者: Cembrano, Javier; Klimm, Max; Knaack, Martin
• 署名单位: Universidad de Chile; Technical University of Berlin
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2026.08.003
• 发表日期: 2026
• 关键词: Knapsack

摘要

We study a mechanism-design-without-money setting in which a designer is interested in selecting items with maximum total value under a budget constraint. The items, however, are controlled by strategic agents who aim to maximize the total value of their selected items. This setting arises naturally when agencies select projects for funding, retailers choose products to stock, or hospitals schedule MRI scans. A mechanism governing the selection is strategyproof if no agent can benefit by hiding items they control from the mechanism. We are interested in mechanisms that are strategyproof and alpha-approximate, meaning that they always achieve at least an alpha-fraction of the optimal value for some alpha [0,1]. First, we give a deterministic mechanism that is 1/phi(2)-approximate, where 1/phi(2) approximate to 0.382 is the inverse of the square of the golden ratio. For the special case where all items have unit density, we design a deterministic 1/phi(2)-approximate mechanism, where 1/phi(2) approximate to 0.618. This result is tight as we show that no deterministic strategyproof mechanism with a better approximation exists. We further give randomized mechanisms with approximation guarantees of 1/2 for the general case and 2/3 for the unit-density case. For both the general and the unit-density settings, no randomized mechanism that is strategyproof in expectation can achieve an approximation guarantee better than 1/(5 phi(2) - 7) approximate to 0.917.