A truthful mechanism consists of an algorithm augmented with a suitable payment function which guarantees that "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 [STOC 1999]. We first show how to obtain mechanisms that, for single-parameter domains, are resistant to coalitions of colluding agents even in the case in which compensation among members of the coalition is allowed (i.e., n-truthful mechanisms). Based on this technique 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 mechanisms with verification.
展开▼
