Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions

摘要

A truthful mechanism consists of an algorithm augmented with a suitable payment function that 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 [2001]. 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 is an improvement over all known previous constructions of exact mechanisms with verification.