Limitations of VCG-Based Mechanisms

We consider computationally-efficient incentive-compatible mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We present a novel technique for setting lower bounds on the approximation ratio of this type of mechanisms. Specifically, for combinatorial auctions among sub-modular (and thus also subadditive) bidders we prove an Omega(m(1/6)) lower bound, which is close to the known upper bound of O(m(1/2)), and qualitatively higher than the constant factor approximation possible from a purely computational point of view.