Abstract | ||
---|---|---|
We consider the fundamental mechanism design problem of approximate social welfare maximization under general cardinal preferences on a finite number of alternatives and without money. The well-known range voting scheme can be thought of as a non-truthful mechanism for exact social welfare maximization in this setting. With m being the number of alternatives, we exhibit a randomized truthful-in-expectation ordinal mechanism with approximation ratio Omega(m(-3/4)). On the other hand, we show that for sufficiently many agents, the approximation ratio of any truthful-in-expectation ordinal mechanism is O(m(-2/3)). We supplement our results with an upper bound for any truthful-in-expectation mechanism. We get tighter bounds for the natural special case of m = 3, and in that case furthermore obtain separation results concerning the approximation ratios achievable by natural restricted classes of truthful-in-expectation mechanisms. In particular, we show that the best cardinal truthful mechanism strictly outperforms all ordinal ones. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-319-13129-0_13 | WEB AND INTERNET ECONOMICS |
DocType | Volume | ISSN |
Journal | 8877 | 0302-9743 |
Citations | PageRank | References |
2 | 0.43 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aris Filos-Ratsikas | 1 | 76 | 18.29 |
Peter Bro Miltersen | 2 | 1146 | 94.49 |