Concordance and the Smallest Covering Set of Preference Orderings
This work addresses the need for efficient and meaningful analysis of preference orderings in domains like group decision making and machine learning, though it appears incremental in its algorithmic improvements.
The paper tackles the problem of representing and quantifying agreement in sets of preference orderings, proposing a new algorithm for calculating common subsequences with time complexity O(Nn^2) and space complexity O(min{Nn, n^2}), and introduces a method to find the smallest covering set of preferences.
Preference orderings are orderings of a set of items according to the preferences (of judges). Such orderings arise in a variety of domains, including group decision making, consumer marketing, voting and machine learning. Measuring the mutual information and extracting the common patterns in a set of preference orderings are key to these areas. In this paper we deal with the representation of sets of preference orderings, the quantification of the degree to which judges agree on their ordering of the items (i.e. the concordance), and the efficient, meaningful description of such sets. We propose to represent the orderings in a subsequence-based feature space and present a new algorithm to calculate the size of the set of all common subsequences - the basis of a quantification of concordance, not only for pairs of orderings but also for sets of orderings. The new algorithm is fast and storage efficient with a time complexity of only $O(Nn^2)$ for the orderings of $n$ items by $N$ judges and a space complexity of only $O(\min\{Nn,n^2\})$. Also, we propose to represent the set of all $N$ orderings through a smallest set of covering preferences and present an algorithm to construct this smallest covering set. The source code for the algorithms is available at https://github.com/zhiweiuu/secs