What to Verify for Optimal Truthful Mechanisms without Money

Diodato Ferraioli, Paolo Serafino, Carmine Ventre

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Downloads (Pure)


We aim at identifying a minimal set of conditions under which algorithms with good approximation guarantees are truthful without money. In line with recent literature, we wish to express such a set via verification assumptions, i.e., kind of agents' misbehavior that can be made impossible by the designer.

We initiate this research endeavour for the paradigmatic problem in approximate mechanism design without money, facility location. It is known how truthfulness imposes (even severe) losses and how certain notions of verification are unhelpful in this setting; one is thus left powerless to solve this problem satisfactorily in presence of selfish agents. We here address this issue and characterize the minimal set of verification assumptions needed for the truthfulness of optimal algorithms, for both social cost and max cost objective functions. En route, we give a host of novel conceptual and technical contributions ranging from topological notions of verification to a lower bounding technique for truthful mechanisms that connects methods to test truthfulness (i.e., cycle monotonicity) with approximation guarantee.
Original languageEnglish
Title of host publicationProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems
ISBN (Electronic)978-1-4503-4239-1
Publication statusPublished - 9 May 2016
Event15th International Conference on Autonomous Agents and Multiagent Systems - Grand Copthorne Waterfront Hotel, Singapore
Duration: 9 May 201613 May 2016
Conference number: 15


Conference15th International Conference on Autonomous Agents and Multiagent Systems
Abbreviated titleAAMAS2016


Dive into the research topics of 'What to Verify for Optimal Truthful Mechanisms without Money'. Together they form a unique fingerprint.

Cite this