On the strategyproof allocation of items under a budget constraint

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 α -approximate, meaning that they always achieve at least an α -fraction of the optimal value for some α ∈ [0, 1]. First, we give a deterministic mechanism that is 1/ ϕ 2 -approximate, where 1/ ϕ 2 ≈ 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/ ϕ -approximate mechanism, where 1/ ϕ ≈ 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 ϕ − 7 ) ≈ 0.917 .