Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5071721 | Games and Economic Behavior | 2014 | 19 Pages |
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.