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 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