2015/07/30 by Ahuva Mu’alem, Michael Schapira, Mu'alem, Ahuva +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1507.08708
openalex publication_date 2015/07/30 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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-(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) (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.