Truthfulness on a Budget: Trading Money for Approximation through Monitoring

Albeit a pervasive desideratum when computing a novel paradigm wherein agents’ declarations can be partially checked against their actual costs. in the presence of selfish agents, truthfulness typically imposes severe limitations to what can be implemented. The price of these limitations is typically paid either economically , in terms of the financial resources needed to enforce truthfulness, or algorithmically , in terms of restricting the set of implementable objective functions, which often leads to renouncing optimality and resorting to approximate allocations. In this paper, with regards to utilitarian problems, we ask two fundamental questions: (i) what is the a minimum sufficient budget needed by optimal truthful mechanisms, and (ii) whether it is possible to sacrifice optimality in order to achieve truthfulness with a lower budget. To answer these questions, we connect two streams of work on mechanism design and look at monitoring – a paradigm wherein agents’ actual costs are bound to their declarations. In this setting, we prove that the social cost is always a sufficient budget, even for collusion-resistant mechanisms, and, under mild conditions, also a necessary budget for a large class of utilitarian problems that encompass set system problems. Furthermore, for facility location, a well-studied problem outside of this class, we draw a novel picture about the relationship between approximation and frugality.