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 obtain a
2-approximation for multi-unit auctions, and show that this is
best possible, even though from a purely computational perspective
an FPTAS exists. For combinatorial auctions among submodular (or
subadditive) bidders, we prove an \Omega(m^{\frac 1 6}) lower
bound, which is close to the known upper bound of O(m^{\frac 1 2}), and qualitatively higher than the constant factor
approximation possible from a purely computational point of view.