An Efficient Algorithm To Compute Distance Between Lexicographic Preference Trees

An Efficient Algorithm To Compute Distance Between Lexicographic Preference Trees

Minyi Li, Borhan Kazimipour

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1898-1904. https://doi.org/10.24963/ijcai.2018/262

Very often, we have to look into multiple agents' preferences, and compare or aggregate them. In this paper, we consider the well-known model, namely, lexicographic preference trees (LP-trees), for representing agents' preferences in combinatorial domains. We tackle the problem of calculating the dissimilarity/distance between agents' LP-trees. We propose an algorithm LpDis to compute the number of disagreed pairwise preferences between agents by traversing their LP-trees. The proposed algorithm is computationally efficient and allows agents to have different attribute importance structures and preference dependencies. 
Keywords:
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Preference Modelling and Preference-Based Reasoning
Knowledge Representation and Reasoning: Knowledge Representation and Game Theory ; Social Choice
Agent-based and Multi-agent Systems: Computational Social Choice