Efficient Constrained Combinatorial Auctions

The seminal work by Green and Laffont [(1977) characterization of satisfactory mechanisms for the revelation of preferences for public goods, Econometrica 45, 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 k nonidentical items and n 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.