No truthful mechanism can be better than n approximate for two natural problems

• 成果类型: Article
• 署名作者: Leucci, Stefano; Mamageishvili, Akaki; Penna, Paolo
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.05.003
• 发表日期: 2018
• 页码: 64-74
• 关键词: Mechanism design; Truthful mechanisms; Inapproximability; Non-utilitarian problems; Lower bounds

摘要

This work gives the first natural non-utilitarian problems for which the trivial n approximation via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than n approximate, where n is the number of agents. The problems we study are the min-max variant of the shortest path and the (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost. (C) 2018 Elsevier Inc. All rights reserved.