Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions

12 years 11 months ago
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
A truthful mechanism consists of an algorithm augmented with a suitable payment function which guarantees that the "players" cannot improve their utilities by "cheating". Mechanism design approaches are particularly appealing for designing "protocols" that cannot be manipulated by rational players. We present new constructions of so called mechanisms with verification introduced by Nisan and Ronen [NR01]. We first show how to obtain mechanisms that, for single-parameter domains, are resistant to coalitions of colluding agents even if they can exchange compensations. Based on this result we derive a class of exact truthful mechanisms with verification for arbitrary bounded domains. This class of problems includes most of the problems studied in the algorithmic mechanism design literature and for which exact solutions cannot be obtained with truthful mechanisms without verification. This result improves over all known previous constructions of exact mechani...
Paolo Penna, Carmine Ventre
Added 19 Oct 2010
Updated 19 Oct 2010
Type Conference
Year 2008
Where ESA
Authors Paolo Penna, Carmine Ventre
Comments (0)