Abstract
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.
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 language | English |
---|---|
Title of host publication | Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems |
Publisher | ACM |
Pages | 68-76 |
ISBN (Electronic) | 978-1-4503-4239-1 |
Publication status | Published - 9 May 2016 |
Event | 15th International Conference on Autonomous Agents and Multiagent Systems - Grand Copthorne Waterfront Hotel, Singapore Duration: 9 May 2016 → 13 May 2016 Conference number: 15 |
Conference
Conference | 15th International Conference on Autonomous Agents and Multiagent Systems |
---|---|
Abbreviated title | AAMAS2016 |
Country/Territory | Singapore |
Period | 9/05/16 → 13/05/16 |