Setting lower bounds on truthfulness
We present and discuss general techniques for proving inapproximability results for truthful mecha-nisms. We demonstrate the usefulness of these techniques by proving lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we illustrate the strength of...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.529.3300 http://leibniz.cs.huji.ac.il/tr/871.pdf |