Аннотация:We consider computationally-efficient incentive-compatiblemechanisms that use the VCG payment scheme, and study how well theycan approximate the social welfare in auction settings. We present anovel technique for setting lower bounds on the approximation ratioof this type of mechanisms. Specifically, for combinatorial auctionsamong submodular (and thus also subadditive) bidders we prove an Ω(m1/6) lower bound, which is close to the knownupper bound of O(m1/2), and qualitatively higher than theconstant factor approximation possible from a purely computationalpoint of view.
