Budget Feasible Mechanisms

TLDR

The basic class of mechanism design problems, which captures many common economic situations, has not been studied before and standard mechanisms like VCG are inapplicable. The study investigates a novel class of mechanism design problems where outcomes are constrained by payments. The authors analyze procurement auctions with private seller costs, aiming to maximize utility under a budget constraint, and characterize budget‑feasible mechanisms in other domains under restricted conditions. For general functions, budget constraints can make mechanisms arbitrarily ineffective, but for sub‑modular functions a bounded approximation ratio is achievable, with even better results for certain subclasses, and the authors characterize budget‑feasible mechanisms in other domains under restricted conditions.

Abstract

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of sub modular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the sub modular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.