ECCC-Report TR09-068https://eccc.weizmann.ac.il/report/2009/068Comments and Revisions published for TR09-068en-usTue, 01 Sep 2009 23:34:07 +0300
Paper TR09-068
| Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms |
Dave Buchfuhrer,
Chris Umans
https://eccc.weizmann.ac.il/report/2009/068Many 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 a previous bound on the achievable social welfare of polynomial time maximal-in-range mechanisms of $2n/(n+1)$ for constant $n$. Our bound is tight, as a $\min(n,2m^{1/2})$ approximation of the social welfare is achievable.Tue, 01 Sep 2009 23:34:07 +0300https://eccc.weizmann.ac.il/report/2009/068