Improved lower bounds for non-utilitarian truthfulness

We study the limitations imposed by truthfulness for two non-utilitarian multi-parameter optimization problems. The first is the workload minimization in inter-domain routing problem, and the other is the unrelated machines scheduling problem. Our main findings can be briefly summarized as follows: 1.We prove that any truthful deterministic mechanism and any universal truthful randomized mechanism for workload minimization in inter-domain routing cannot achieve approximation ratio better than 2. These results improve the current lower bounds of and due to Mu’alem and Schapira [A. Mu’alem, M. Schapira, Setting lower bounds on truthfulness, in: Proceedings 18th annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1143–1152].2.We establish a lower bound of on the achievable approximation guarantee of any truthful deterministic mechanism for unrelated machines scheduling when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [G. Christodoulou, E. Koutsoupias, A. Vidali, A lower bound for scheduling mechanisms, in: Proceedings 18th annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1163–1170].