Abstract:
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.