Introduction
In social choice theory and statistics, a recurring challenge is determining how well an external attribute—such as age, income, or education level—explains a set of ranked preferences. Traditional statistical methods often analyze alternatives in isolation, failing to capture the holistic structure of ordinal rankings. This research, originally presented at IJCAI-19, proposes a novel approach: using the "distance to single-crossing" as a correlation coefficient to measure the explanatory power of an attribute over a full preference profile.
The Single-Crossing Property as a Statistical Tool
A preference profile is considered single-crossing if, when voters are ordered by a specific attribute, any two alternatives change their relative rank at most once along that axis. This property represents a "perfect" explanation where the attribute dictates the evolution of preferences.
However, real-world data is rarely pristine. To use this concept as a statistical tool, one must calculate the minimum number of "edits"—such as swaps, deletions, or partitions—required to transform a noisy profile into a single-crossing one. Unlike previous work that allowed for arbitrary voter reordering, this study focuses on the fixed voter order imposed by the external attribute, which fundamentally alters the computational landscape.
Methodology and Distance Measures
The authors analyze several distance measures to quantify how far a profile is from being single-crossing:
- Swap-based distances: Measuring the total number of adjacent swaps (Global Swaps) or the maximum swaps required per voter (Local Swaps).
- Deletion-based distances: Identifying the minimum number of alternatives (Alternative Deletion) or voters (Voter Deletion) to remove to achieve the property.
- Partition-based distances: Dividing alternatives or voters into $k$ single-crossing groups.
- Voter Reordering: Determining the minimum swaps of voters needed to satisfy the property relative to the original attribute order.
To address the inherent difficulty of these problems, the researchers employ parameterized complexity. They investigate whether these measures can be computed efficiently when the distance ($k$) is small, categorizing them into Fixed-Parameter Tractable (FPT) or XP classes.
Computational Complexity and Results
The study provides a comprehensive map of the complexity for these problems under a fixed axis. A key insight is that while many problems are NP-hard, they often become tractable when the attribute provides a "good" explanation (i.e., the distance $k$ is small).
Notably, the authors found that Voter Deletion and Voter Reordering can be solved in polynomial time. In contrast, Alternative Deletion is NP-complete even for as few as four voters. For the NP-hard cases, the researchers developed algorithms that are FPT with respect to the distance $k$, ensuring that the "tractability of noise" allows for practical application when the correlation is high.
Conclusion and Future Directions
This work establishes the theoretical foundation for a new class of correlation coefficients based on structural properties of preferences. While the current focus is on ordinal data and computational feasibility, future research could extend these models to include cardinal information (preference intensity). The next step involves empirical validation, applying these measures to real-world survey data to compare their insights against traditional metrics like Kendall-tau correlations.
Summary updated