Limitations of VCG-based mechanisms

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 62 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.