Name
Abstract | ||
|---|---|---|
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 ) for any constant < 1=2 and run in polynomial time, unless NP 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;2m1=2) approximation of the social welfare is achievable. |
Year | Venue | Keywords |
|---|---|---|
2009 | Electronic Colloquium on Computational Complexity (ECCC) | polynomial time,social welfare |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Time complexity,Mathematics,Social Welfare | Journal | 16 |
Citations | PageRank | References |
3 | 0.41 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Buchfuhrer | 1 | 20 | 2.18 |
| Christopher Umans | 2 | 879 | 55.36 |