Setting lower bounds on truthfulness

• 成果类型: Article
• 署名作者: Mu'alem, Ahuva; Schapira, Michael
• 署名单位: Hebrew University of Jerusalem
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.02.001
• 发表日期: 2018
• 页码: 174-193
• 关键词: Algorithmic mechanism design; Scheduling; Bayesian Incentive-Compatible mechanisms; Truthfulness-in-expectation mechanisms; Randomized truthful mechanisms

摘要

This paper presents inapproximability results for paradigmatic multi-dimensional truthful mechanism design problems. We first show a lower bound of 2 - 1/n for the scheduling problem with n 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 universally-truthful randomized mechanisms, regardless of any computational assumptions on the running time of these mechanisms. Moreover, it holds even for the wider class of truthfulness in-expectation mechanisms. We then turn to Bayesian settings and show a lower bound of 1.2 for Bayesian Incentive Compatible (BIC) mechanisms. No lower bounds for truthful mechanisms in multidimensional settings which incorporate randomness were previously known. Next, we define the workload-minimization problem in networks. We prove lower bounds for the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we prove lower bounds for Max-Min fairness, Min-Max fairness, and envy minimization. (C) 2018 Elsevier Inc. All rights reserved.