In many settings, a procurer has a fixed budget to spend on projects that differ in their value and cost. Under full information, this problem is known as the knapsack problem: what is the value-maximizing way to pack a bag with a limited weight capacity when the available items differ in value and weight? This combinatorial problem dates back as far as 1897 and is one of the classical NP-hard problems. In a recent article, Felix Jarman (German Ministry of Finance) and BCCP fellow Vincent Meisner study a mechanism design variant of this problem in which the costs (the items' weights) are private information of the projects' managers. They derive a mechanism that maximizes the expected aggregate value of implemented projects under ex-post constraints. That is, a manager only has to implement her project if her costs are at least fully covered, it must be a dominant strategy to report these costs truthfully, and the sum of compensation payments must never exceed a fixed budget.
They find that the optimal allocation is implementable with a descending-clock auction: each manager faces a clock with a continuously decreasing price on it, and she indicates whether she is willing to implement the project for the price currently shown on the clock. The optimal allocation takes a simple form in the symmetric case, in which all projects have the same value and costs are drawn from the same distribution: all implemented projects obtain the same transfer and as many projects as the budget allows are implemented. This is implementable with a single price clock and projects drop out over time in order of their cost. However, when projects are asymmetric, in the optimal implementation, every project gets an individual clock. Clocks not only descend asynchronously, sometimes individual clocks have to stop. This is due to a quantity-quality tradeoff: the procurer not only prefers high-value projects over low-value projects, but also prefers more over fewer projects. Consequently, out of two rival projects sometimes only the inferior one is implemented. If the procurer did always greenlight the superior project, the properties of the allocation rule imply a reduced probability of implementing both projects together. This paper is one of the first that considers purely ex-post constrained mechanism design, and it is also one of the first that shows the optimality of clock auctions under complex constraints.
Read the full article (pay-walled) Ex-post optimal knapsack procurement, Journal of Economic Theory, June 2017 or the last working paper version.