Truthful Mechanisms for Multi Agent Self-interested Correspondence Selection

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.