Optimal collusion-resistant mechanisms with verification

• 成果类型: Article
• 署名作者: Penna, Paolo; Ventre, Carmine
• 署名单位: University of Salerno; University of Teesside
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2012.09.002
• 发表日期: 2014
• 页码: 491-509
• 关键词: Game theory; Algorithmic mechanism design; Transferable utilities

摘要

We present the first general positive result on the construction of collusion-resistant mechanisms, that is, mechanisms that guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments). This is a much stronger solution concept as compared to truthful or even group strategyproof mechanisms, and only impossibility results were known for this type of mechanisms in the classical model. We describe collusion-resistant mechanisms with verification that return optimal solutions for a wide class of mechanism design problems (which includes utilitarian ones as a special case). Note that every collusion-resistant mechanism without verification must have an unbounded approximation factor and, in general, optimal solutions cannot be obtained even if we content ourselves with truthful (non-collusion-resistant) mechanisms. All these results apply to problems that have been extensively studied in the algorithmic mechanism design literature like, for instance, task scheduling and inter-domain routing. (C) 2012 Elsevier Inc. All rights reserved.