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 tight. We also show that this bound holds for a variation of the Vickrey-Clark-Groves mechanism. Finally we point out implementation issues of the optimal mechanism.

José R. Correa

Nicolás Figueroa