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: | Text |
Language: | unknown |
Published: |
2015
|
Subjects: | |
Online Access: | http://arxiv.org/abs/1507.08708 |
id |
ftarxivpreprints:oai:arXiv.org:1507.08708 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:1507.08708 2023-09-05T13:22:56+02:00 Setting Lower Bounds on Truthfulness Mu'alem, Ahuva Schapira, Michael 2015-07-30 http://arxiv.org/abs/1507.08708 unknown http://arxiv.org/abs/1507.08708 Computer Science - Computer Science and Game Theory text 2015 ftarxivpreprints 2023-08-16T13:43:09Z 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. Text sami ArXiv.org (Cornell University Library) Ronen ENVELOPE(16.100,16.100,68.767,68.767) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Computer Science and Game Theory |
spellingShingle |
Computer Science - Computer Science and Game Theory Mu'alem, Ahuva Schapira, Michael Setting Lower Bounds on Truthfulness |
topic_facet |
Computer Science - Computer Science and Game Theory |
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 |
Text |
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 |
publishDate |
2015 |
url |
http://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_relation |
http://arxiv.org/abs/1507.08708 |
_version_ |
1776203500532793344 |