Truthful optimization using mechanisms with verification

We study the question of whether optimization problems can be solved exactly in the presence of economic constraints, such as truthfulness of selfish agents. In general, imposing these extra constraints makes it impossible to optimize, even in exponential time. To reconcile optimization and economic incentives we focus on so-called mechanisms with verification and show that, under this general mechanism design paradigm, it is indeed possible to optimize and to be truthful. Our truthful mechanisms minimize any cost function that is monotone nondecreasing in agentsʼ costs under the technical hypothesis that the possible declarations of the selfish agents belong to a finite set. Our results also extend to the multidimensional scenario of compound agents; in the case in which the single dimensions are one-parameter, we also show how to implement truthfully and efficiently classical (approximation) algorithms for cost functions that behave smoothly in the presence of input rounding. Our results are applied to a number of very general scheduling problems to obtain the first truthful mechanisms for them. Finally, the issue of designing mechanisms with verification for infinite domains is studied showing the limitations that the imposition of the Taxation Principle yields.