King's College London

Research portal

Truthfulness on a budget: trading money for approximation through monitoring

Research output: Contribution to journalArticlepeer-review

Paolo Serafino, Carmine Ventre, Angelina Vidali

Original languageEnglish
Article number5
JournalAutonomous Agents and Multi-Agent Systems
Issue number1
Early online date4 Dec 2019
Accepted/In press25 Nov 2019
E-pub ahead of print4 Dec 2019
PublishedApr 2020


King's Authors


Albeit a pervasive desideratum when computing 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 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 two well-studied problems outside of this class, namely facility location and obnoxious facility location, we draw a novel picture about the relationship between (additive) approximation and frugality. While for optimal mechanisms we prove that the social cost is always a sufficient and necessary budget for both problems, for approximate mechanisms we do have a dichotomy: for the facility location problem (i.e., agents want to be close to the facilities) we show that “good” approximations still need a budget equal to the social cost; on the contrary, for the obnoxious facility location problem (i.e. agents want to be as far away from the facilities as possible) we show that it is possible to trade approximation for frugality, thus obtaining truthfulness with a lower budget.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454