What to Verify for Optimal Truthful Mechanisms without Money

Diodato Ferraioli, Paolo Serafino, Carmine Ventre

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

4 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems
PublisherACM
Pages68-76
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

Conference

Conference15th International Conference on Autonomous Agents and Multiagent Systems
Abbreviated titleAAMAS2016
CountrySingapore
Period9/05/1613/05/16

Fingerprint

Costs

Cite this

Ferraioli, D., Serafino, P., & Ventre, C. (2016). What to Verify for Optimal Truthful Mechanisms without Money. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (pp. 68-76). ACM.
Ferraioli, Diodato ; Serafino, Paolo ; Ventre, Carmine. / What to Verify for Optimal Truthful Mechanisms without Money. Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems . ACM, 2016. pp. 68-76
@inproceedings{ddbd18a39523406f90700df4ab97d4c5,
title = "What to Verify for Optimal Truthful Mechanisms without Money",
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.",
author = "Diodato Ferraioli and Paolo Serafino and Carmine Ventre",
year = "2016",
month = "5",
day = "9",
language = "English",
pages = "68--76",
booktitle = "Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems",
publisher = "ACM",

}

Ferraioli, D, Serafino, P & Ventre, C 2016, What to Verify for Optimal Truthful Mechanisms without Money. in 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.

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems . ACM, 2016. p. 68-76.

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

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 -

Ferraioli D, Serafino P, Ventre C. What to Verify for Optimal Truthful Mechanisms without Money. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems . ACM. 2016. p. 68-76