Strongly polynomial-time truthful mechanisms in one shot

作     者：Penna, Paolo Proietti, Guido Widmayer, Peter 

作者机构：Univ Salerno Dipartimento Informat & Applicaz Renato M Capocel Salerno Italy ETH Inst Theoret Informat Zurich Switzerland Univ Aquila Dipartimento Informat I-67100 Laquila Italy CNR Ist Anal Sistemi & Informat A Ruberti Rome Italy 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2009年第410卷第17期

页      面：1607-1615页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Swiss BBW European Commission, EC, (COST 295) Ministero dell’Istruzione, dell’Università e della Ricerca, MIUR, (IST-15964) 

主　　题：Algorithmic game theory Mechanism design Design and analysis of algorithms Minimum diameter spanning tree 

摘      要：One of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic Solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain monotonicity properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity). We provide a general technique for building truthful mechanisms that provide optimal solutions in strongly polynomial time. We show that the entire mechanism can be obtained if one is able to express/write a strongly polynomial-time algorithm (for the corresponding optimization problem) as a suitable combination of simpler algorithms. This approach applies to a wide class of mechanism design graph problems, where each selfish agent corresponds to a weighted edge in a graph (the weight of the edge is the cost of using that edge). Our technique can be applied to several optimization problems which prior results cannot handle (e.g., MIN-MAX optimization problems). As an application, we design the first (strongly polynomial-time) truthful mechanism for the minimum diameter spanning tree problem, by obtaining it directly from an existing algorithm for solving this problem. For this non-utilitarian MIN-MAX problem, no truthful mechanism was known, even considering those running in exponential time (indeed, exact algorithms do not necessarily yield truthful mechanisms). Also, standard techniques for payment computations may result in a running time which is not polynomial in the size of the input graph. The overall running time of our mechanism, instead, is polynomial in the number n of nodes and in of edges, and it is only a factor O(n alpha(n, n)) away from the best known canonical centralized algorithm. (C) 2009 Elsevier B.V. All rights reserved.