Negotiating over Ontological Correspondences with Asymmetric and Incomplete Knowledge

Effective communication is dependent on agents correctly interpreting the messages exchanged, based on the entities (or vocabulary) within the messages, and their ontological definitions. As agents are not guaranteed to share the same vocabulary, correspondences (i.e. mappings between corresponding entities in different ontologies) should be selected that provide a (logically) coherent alignment between the agents' ontologies. In this paper, we show how two agents, each possessing incomplete sets of private, heterogeneous (and typically ambiguous) correspondences, can each disclose a subset of these to facilitate agreement on the construction of an unambiguous alignment. We formally present an inquiry dialogue and illustrate how agents negotiate by exchanging their beliefs of the utilities of each correspondence. We empirically demonstrate how our distributed approach can still identify solutions that are typically 95% of the optimal solution (found centrally with complete information). Compared to reference alignments, our approach increases the precision of the resulting alignment by up to 40% whilst only slightly affecting recall, with each agent disclosing on average only 16.76% of its individual correspondences.