Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with auctions:
TR06-074 | 24th April 2006
Shahar Dobzinski, Noam Nisan

Approximations by Computationally-Efficient VCG-Based Mechanisms

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 ... more >>>

TR09-068 | 1st September 2009
Dave Buchfuhrer, Chris Umans

Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

ISSN 1433-8092 | Imprint