Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-074 | 24th April 2006 00:00

Approximations by Computationally-Efficient VCG-Based Mechanisms

RSS-Feed




TR06-074
Authors: Shahar Dobzinski, Noam Nisan
Publication: 18th June 2006 21:37
Downloads: 1562
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