An Impossibility Result for Equal-cost Mechanism Design with Monitoring for Binary Covering Problems

16^th January 2019, 13:00
Piotr Krysta
University of Liverpool

Abstract

We apply the equal-cost mechanism design paradigm with monitoring to the class of problems which are binary covering problems with the objective function of minimising the social cost. This class contains many natural network design problems, for instance, minimum cost Steiner tree problem, minimum cost 2-edge-connected spanning subgraph problem, etc. We prove that no deterministic b-approximation algorithm for any problem in this class is an equal-cost truthful mechanism with monitoring for any b > 1, even if agents are single-dimensional. This is an unconditional impossibility result. On the other hand, we also show that any such b-approximation algorithm implies an equal-cost b-truthful mechanism with monitoring for any such problem.

This is joint work with Dimitris Fotakis and Carmine Ventre.