In this paper we study a large class of resource allocation problems with an important complication, the utilization cost of a given resource is private information of a profit maximizing agent. After reviewing the characterization of the optimal bayesian mechanism, we study the informational cost introduced by the presence of private information. Our main result is to provide an upper bound for the ratio between the cost under asymmetric information and the cost of a fully informed designer, which is independent of the combinatorial nature of the problem and only depend on the statistical distribution of the resource costs. In particular our bounds evaluates to 2 when the utilization cost’s distributions are symmetric and unimodal and this is tight. We also show that this bound holds for a variation of the Vickrey-Clark-Groves mechanism, which always achieves an ex-post efficient allocation. Finally we point out implementation issues of the considered mechanisms.

Keywords: Mechanism Design, Information Cost