TR06-074 Authors: Shahar Dobzinski, Noam Nisan

Publication: 18th June 2006 21:37

Downloads: 1736

Keywords:

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.