Characterizing the Vickrey combinatorial auction by induction

This note studies the allocation of heterogeneous commodities to agents whose private values for combinations of these commodities are monotonic by inclusion. This setting can accommodate the presence of complementarity and substitutability among the heterogeneous commodities. By using induction logic, we provide an alternative proof of Holmstrom’s (Econometrica 47:1137–1144, 1979) characterization of the Vickrey combinatorial auction as the unique efficient, strategy-proof, and individually rational allocation rule on a smoothly connected domain of value profiles. Our approach is elementary, not involving smoothness, and intuitive in the sense that familiar properties of the single-item second-price auction provide the first step in our induction on the number of auctioned items. Moreover, our method of proof can be applied to domains which may not be smoothly connected, including nonconvex ones. The authors acknowledge the helpful comments of anonymous referee. Serizawa greatly benefited from discussion with Rajat Deb.