Truthful Mechanisms for Multi Agent Self-interested Correspondence Selection

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationThe Semantic Web – ISWC 2019
Subtitle of host publication18th International Semantic Web Conference, Proceedings, Part I
EditorsChiara Ghidini, Olaf Hartig, Maria Maleshkova, Vojtěch Svátek, Isabel Cruz, Aidan Hogan, Jie Song, Maxime Lefrançois, Fabien Gandon
PublisherSpringer, Cham
Pages733-750
ISBN (Electronic)978-3-030-30793-6
ISBN (Print)978-3-030-30792-9
Publication statusPublished - Oct 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11778 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title18th International Semantic Web Conference, ISWC 2019
PlaceNew Zealand
CityAuckland
Period26 - 30 October 2019

Abstract

In the distributed ontology alignment construction problem, two agents agree upon a meaningful subset of correspondences that map between their respective ontologies. However, an agent may be tempted to manipulate the negotiation in favour of a preferred alignment by misrepresenting the weight or confidence of the exchanged correspondences. Therefore such an agreement can only be meaningful if the agents can be incentivised to be honest when revealing information. We examine this problem and model it as a novel mechanism design problem on an edge-weighted bipartite graph, where each side of the graph represents each agent’s private entities, and where each agent maintains a private set of valuations associated with its candidate correspondences. The objective is to find a matching (i.e. injective or one-to-one correspondences) that maximises the agents’ social welfare. We study implementations in dominant strategies, and show that they should be solved optimally if truthful mechanisms are required. A decentralised version of the greedy allocation algorithm is then studied with a first-price payment rule, proving tight bounds on the Price of Anarchy and Stability.

Research Area(s)

  • Decentralised Ontology Alignment, Multi-agent systems

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)

Truthful Mechanisms for Multi Agent Self-interested Correspondence Selection. / Zhi, Nan; Payne, Terry R.; Krysta, Piotr; Li, Minming.

The Semantic Web – ISWC 2019 : 18th International Semantic Web Conference, Proceedings, Part I. ed. / Chiara Ghidini; Olaf Hartig; Maria Maleshkova; Vojtěch Svátek; Isabel Cruz; Aidan Hogan; Jie Song; Maxime Lefrançois; Fabien Gandon. Springer, Cham, 2019. p. 733-750 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11778 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)