Efficient Constrained Combinatorial Auctions
Abstract
The seminal work by Green and Laffont [(1977) characterization of satisfactory mechanisms for the revelation of preferences for public goods, Econometrica45, 427–438] shows that efficient mechanisms with Vickrey–Clarke–Groves prices satisfy the properties of dominant-strategy incentive compatible (DSIC) and individually rational in the quasilinear utilities model. Nevertheless in many real-world situations some players have a gap between their willingness to pay and their ability to pay, i.e., a budget. We show that once budgets are integrated into the model then Green and Laffont’s theorem ceases to apply. More specifically, we show that even if only a single player has budget constraints then there is no deterministic efficient mechanism that satisfies the individual rationality and DSIC properties. Furthermore, in a quasilinear utilities model with kk nonidentical items and nn players with multidimensional types, we characterize the sufficient and necessary conditions under which Green and Laffont’s theorem holds in the presence of budget-constrained players. Interestingly our characterization is similar in spirit to that of Maskin [(2000) Auctions, development and privatization: Efficient auctions with liquidity-constrained buyers, Eur. Econ. Rev.44, 667–681] for Bayesian single-item constrained-efficiency auctions.
