### 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.

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 | Singapore |

Period | 9/05/16 → 13/05/16 |

### Fingerprint

### Cite this

*Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems*(pp. 68-76). ACM.

}

*Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems .*ACM, pp. 68-76, 15th International Conference on Autonomous Agents and Multiagent Systems, Singapore, 9/05/16.

**What to Verify for Optimal Truthful Mechanisms without Money.** / Ferraioli, Diodato; Serafino, Paolo; Ventre, Carmine.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research

TY - GEN

T1 - What to Verify for Optimal Truthful Mechanisms without Money

AU - Ferraioli, Diodato

AU - Serafino, Paolo

AU - Ventre, Carmine

PY - 2016/5/9

Y1 - 2016/5/9

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 68

EP - 76

BT - Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

PB - ACM

ER -