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 |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.529.3300 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.529.3300 2023-05-15T18:13:07+02:00 Setting lower bounds on truthfulness Michael Schapira The Pennsylvania State University CiteSeerX Archives application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.529.3300 http://leibniz.cs.huji.ac.il/tr/871.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.529.3300 http://leibniz.cs.huji.ac.il/tr/871.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://leibniz.cs.huji.ac.il/tr/871.pdf text ftciteseerx 2016-01-08T10:29:48Z 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 our techniques by exhibiting a lower bound of 2 − 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 7 4 truthful upper bound for the case of two machines. No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We also prove that no affine maximizer (including VCG mechanisms) achieves an approximation ratio better than m for the scheduling problem. This is a first step towards proving the conjecture of Nisan and Ronen that no truthful deterministic mechanism has an approximation ratio better than m. In addition, we apply 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, Papadim-itriou, Sami, and Shenker. Finally, we exploit the same methods to further investigate the problem of fairly allocating indivisible items, posed by Lipton, Markakis, Mossel, and Saberi. We prove lower bounds on the approximability of truthful mechanisms for both notions of fairness considered for this problem: envy minimization and Max-Min fairness. Text sami Unknown Ronen ENVELOPE(16.100,16.100,68.767,68.767) |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
description |
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 our techniques by exhibiting a lower bound of 2 − 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 7 4 truthful upper bound for the case of two machines. No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We also prove that no affine maximizer (including VCG mechanisms) achieves an approximation ratio better than m for the scheduling problem. This is a first step towards proving the conjecture of Nisan and Ronen that no truthful deterministic mechanism has an approximation ratio better than m. In addition, we apply 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, Papadim-itriou, Sami, and Shenker. Finally, we exploit the same methods to further investigate the problem of fairly allocating indivisible items, posed by Lipton, Markakis, Mossel, and Saberi. We prove lower bounds on the approximability of truthful mechanisms for both notions of fairness considered for this problem: envy minimization and Max-Min fairness. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Michael Schapira |
spellingShingle |
Michael Schapira Setting lower bounds on truthfulness |
author_facet |
Michael Schapira |
author_sort |
Michael Schapira |
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 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.529.3300 http://leibniz.cs.huji.ac.il/tr/871.pdf |
long_lat |
ENVELOPE(16.100,16.100,68.767,68.767) |
geographic |
Ronen |
geographic_facet |
Ronen |
genre |
sami |
genre_facet |
sami |
op_source |
http://leibniz.cs.huji.ac.il/tr/871.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.529.3300 http://leibniz.cs.huji.ac.il/tr/871.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766185606653673472 |