Optimal collusion-resistant mechanisms with verification

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).

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.