  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.
