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 |
id |
ftdatacite:10.48550/arxiv.1507.08708 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.1507.08708 2023-05-15T18:12:42+02:00 Setting Lower Bounds on Truthfulness Mu'alem, Ahuva Schapira, Michael 2015 https://dx.doi.org/10.48550/arxiv.1507.08708 https://arxiv.org/abs/1507.08708 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Computer Science and Game Theory cs.GT FOS Computer and information sciences Preprint Article article CreativeWork 2015 ftdatacite https://doi.org/10.48550/arxiv.1507.08708 2022-04-01T12:13:44Z 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 exhibiting a lower bound of $2-\frac{1}{m}$ for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). Moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms -- i.e., truthfulness in expectation. This lower bound nearly matches the known $\frac{7}{4}$ (randomized) truthful upper bound for the case of two machines (a non-truthful FPTAS exists). No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We show an application of our techniques to the workload-minimization problem in networks. We prove our lower bounds for this problem in the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we discuss several notions of non-utilitarian "fairness" (Max-Min fairness, Min-Max fairness, and envy minimization). We show how our techniques can be used to prove lower bounds for these notions. Report sami DataCite Metadata Store (German National Library of Science and Technology) Ronen ENVELOPE(16.100,16.100,68.767,68.767) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Computer Science and Game Theory cs.GT FOS Computer and information sciences |
spellingShingle |
Computer Science and Game Theory cs.GT FOS Computer and information sciences Mu'alem, Ahuva Schapira, Michael Setting Lower Bounds on Truthfulness |
topic_facet |
Computer Science and Game Theory cs.GT FOS Computer and information sciences |
description |
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 exhibiting a lower bound of $2-\frac{1}{m}$ for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). Moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms -- i.e., truthfulness in expectation. This lower bound nearly matches the known $\frac{7}{4}$ (randomized) truthful upper bound for the case of two machines (a non-truthful FPTAS exists). No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We show an application of our techniques to the workload-minimization problem in networks. We prove our lower bounds for this problem in the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we discuss several notions of non-utilitarian "fairness" (Max-Min fairness, Min-Max fairness, and envy minimization). We show how our techniques can be used to prove lower bounds for these notions. |
format |
Report |
author |
Mu'alem, Ahuva Schapira, Michael |
author_facet |
Mu'alem, Ahuva Schapira, Michael |
author_sort |
Mu'alem, Ahuva |
title |
Setting Lower Bounds on Truthfulness |
title_short |
Setting Lower Bounds on Truthfulness |
title_full |
Setting Lower Bounds on Truthfulness |
title_fullStr |
Setting Lower Bounds on Truthfulness |
title_full_unstemmed |
Setting Lower Bounds on Truthfulness |
title_sort |
setting lower bounds on truthfulness |
publisher |
arXiv |
publishDate |
2015 |
url |
https://dx.doi.org/10.48550/arxiv.1507.08708 https://arxiv.org/abs/1507.08708 |
long_lat |
ENVELOPE(16.100,16.100,68.767,68.767) |
geographic |
Ronen |
geographic_facet |
Ronen |
genre |
sami |
genre_facet |
sami |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.1507.08708 |
_version_ |
1766185194749952000 |