Efficient Truthful Scheduling and Resource Allocation through Monitoring

We study the power and limitations of the Vickrey-Clarke-Groves mechanism with monitoring (VCG^mon) for cost minimization problems with objective functions that are more general than the social cost. We identify a simple and natural sufficient condition for VCG^mon to be truthful for general objectives. As a consequence, we obtain that for any cost minimization problem with non-decreasing objective µ, VCG^mon is truthful, if the allocation is Maximal-in-Range and µ is 1-Lipschitz (e.g., µ can be the Lp-norm of the agents’ costs, for any p = 1 or p = 8). We apply VCG^mon to scheduling on restricted-related machines and obtain a polynomial-time truthful-in-expectation 2-approximate (resp. O(1)-approximate) mechanism for makespan (resp. Lp-norm) minimization. Moreover, applying VCG^mon, we obtain polynomial-time truthful O(1)-approximate mechanisms for some fundamental bottleneck network optimization problems with single-parameter agents. On the negative side, we provide strong evidence that VCG^mon could not lead to computationally efficient truthful mechanisms with reasonable approximation ratios for binary covering social cost minimization problems. However, we show that VCG^mon results in computationally efficient approximately truthful mechanisms for binary covering problems.