ECCC-Report TR06-074https://eccc.weizmann.ac.il/report/2006/074Comments and Revisions published for TR06-074en-usSun, 18 Jun 2006 21:37:26 +0300
Paper TR06-074
| Approximations by Computationally-Efficient VCG-Based Mechanisms |
Shahar Dobzinski,
Noam Nisan
https://eccc.weizmann.ac.il/report/2006/074We 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.
Sun, 18 Jun 2006 21:37:26 +0300https://eccc.weizmann.ac.il/report/2006/074