Setting Lower Bounds on Truthfulness
We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we demonstrate the strength of our techniques by e...
| Main Authors: | , |
|---|---|
| Format: | Report |
| Language: | unknown |
| Published: |
arXiv
2015
|
| Subjects: | |
| Online Access: | https://dx.doi.org/10.48550/arxiv.1507.08708 https://arxiv.org/abs/1507.08708 |