Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-074 | 24th April 2006 00:00

#### Approximations by Computationally-Efficient VCG-Based Mechanisms

TR06-074
Authors: Shahar Dobzinski, Noam Nisan
Publication: 18th June 2006 21:37
Keywords:

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.

ISSN 1433-8092 | Imprint