Abstract
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.
Introduction
In fields ranging from voting theory to consumer marketing, quantifying the consensus among a group of "judges" regarding a set of items is a fundamental challenge. Traditionally, researchers have relied on metrics like the Length of the Longest Common Subsequence (llcs) or various edit distances to measure this "concordance."
However, these traditional metrics possess significant theoretical flaws. First, the longest common subsequence is often not unique, leading to an incomplete picture of shared preferences. Second, and more critically, the llcs metric can fail to capture the reduction in agreement when diverse rankings are added to a set. This paper addresses these shortcomings by proposing a more robust measure based on all common subsequences and introducing a novel descriptive tool called the Smallest Covering Set (SCS).
Methods
The authors approach preference orderings through a subsequence-based feature space, treating sequences as vectors in a high-dimensional space where each dimension represents a possible subsequence.
1. Efficient Concordance Calculation
The "concordance" of a set of rankings is defined as the Number of All Common Subsequences (nacs), which acts as a generalized inner product in the feature space. To overcome the computational cost of counting every possible common subsequence, the paper introduces an algorithm with a time complexity of $O(Nn^2)$ and a space complexity of $O(\min\{Nn, n^2\})$. This efficiency is achieved through a specialized indicator-array and truth-table approach, making it significantly faster than previous dynamic programming methods.
2. The Smallest Covering Set (SCS)
The SCS is the paper's primary conceptual contribution. It is defined as the minimal set of sequences such that every common subsequence found in the data is a subsequence of at least one member of the SCS. While a single concordance score provides a numerical summary, the SCS offers a human-readable "summary" of the specific patterns of items that the group actually agrees upon.
Key Insights and the Axiom of Concordance
A central argument of the paper is that a valid measure of agreement $C(X)$ must satisfy the property $C(X) \geq C(X \cup Y)$. Intuitively, if more diverse opinions are added to a group, the total agreement should either decrease or remain stable. The authors argue that nacs satisfies this axiom more robustly than llcs because it accounts for the entire density of shared patterns.
As shown in the table above, while the llcs might remain constant when taking the union of two sets $X$ and $Y$, the actual set of longest common subsequences (lcs's) can shrink significantly. Focusing solely on the "longest" patterns ignores the wealth of information contained in shorter, shared subsequences. The nacs metric captures this "density" of agreement more effectively by counting all shared subsequences.
Results and Applications
The proposed framework offers both computational and theoretical advantages:
- Efficiency: The $O(Nn^2)$ algorithm allows for rapid concordance calculation across large groups of judges.
- Descriptive Power: The SCS "opens the black box" of concordance scores. For example, if the SCS contains the sequence
(apple, orange), it indicates that every judge in the set preferred apple over orange, regardless of their other rankings. - Flexibility: The framework includes "bucket strings" to handle "weak orderings," allowing for ties where a judge might view two items as equal.
Limitations and Future Work
While mathematically sound, the current SCS algorithm is optimized for sequences where each item appears exactly once. Future research aims to extend this to domains like peptide analysis or web browsing, where symbols frequently repeat. Additionally, empirical validation on large-scale, noisy real-world datasets is needed to further compare these metrics against traditional methods like Kendall’s Tau. For very large item sets, the authors also suggest investigating "approximate" or "top-k" covering sets to maintain human interpretability.
Summary updated