Research map / Learning theory and algorithms / Prediction and decision losses
The Surprising Effectiveness of SP Voting with Partial Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes scalable surprisingly popular (SP) voting variants (Partial-SP and Aggregated-SP) that elicit only partial preferences over size-k subsets, validated by a 432-person MTurk study and a concentric Mallows model with sample-complexity bounds.
Problem
Recovering the ground-truth ranking over many alternatives when eliciting full rankings and full prediction distributions is too costly; standard vote aggregation fails when experts are a minority.
Approach
Extend surprisingly popular voting to partial preferences by eliciting votes and predictions over overlapping k-subsets (Top, Approval(t), Rank formats), then either run SP per subset and aggregate the partial rankings (Partial-SP) or aggregate votes first and run pairwise SP on aggregated scores (Aggregated-SP).
Key results
- Rank-Rank and Approval(3)-Rank elicitation formats give the highest correlation with ground truth; Partial-SP significantly outperforms Aggregated-SP.
- Both SP variants significantly outperform Borda, Copeland, Maximin on Kendall-Tau and Spearman's rho, with Schulze matching Aggregated-SP.
- Approval(2)-Approval(2) performs on par with Rank-Rank for Partial-SP while imposing lower cognitive load.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Partial-SP instead of common vote aggregation rules | Partial-SP · MTurk study, averaged across geography, movies, and paintings | Kendall-Tau correlation | Helped |
| Use Partial-SP instead of Aggregated-SP | SP voting · MTurk study, averaged across geography, movies, and paintings | Kendall-Tau correlation | Helped |
| Add prediction information to Copeland vote aggregation | Partial-SP · Approval(2)-Approval(2), MTurk study | Pairwise hit rate | Helped |
| Use Rank-Rank instead of less expressive elicitation formats | SP voting · MTurk study, averaged across three domains | Kendall-Tau correlation | Helped |
| Use Approval(3)-Rank instead of less expressive elicitation formats | SP voting · MTurk study, averaged across three domains | Spearman's ρ | Helped |
| Use Approval(2)-Approval(2) instead of Rank-Rank | Partial-SP · MTurk study, averaged across three domains | Kendall-Tau correlation | No clear effect |
| Use Top-Rank instead of Rank-Top | Aggregated-SP · MTurk study, averaged across three domains | Kendall-Tau correlation | Mixed |
| Add information to the vote or prediction format | Partial-SP · MTurk study, averaged across three domains | Kendall-Tau correlation | Helped |
| Use Aggregated-SP instead of common vote aggregation rules | Aggregated-SP · Schulze comparison across domains | Kendall-Tau correlation | No clear effect |
| Use Partial-SP instead of common aggregation rules | Partial-SP · Paintings | Spearman's ρ | Helped |
| Increase subset size and widen inter-alternative gaps | Partial-SP and Aggregated-SP · Ground-truth ranking recovery | Accuracy | Helped |
Surprising findings
- Unordered approval-set elicitation for both votes and predictions is sufficient to recover ground truth, performing comparably to full rankings.
- Schulze matches the performance of Aggregated-SP on the domains tested.
Limitations
- Fixed subset size k and gap parameter; trade-off between subset size and accuracy left open.
- Sample-complexity analysis assumes concentric Mallows model and an assumption linking p, phi_E and phi_NE.
- Experiments limited to 36 alternatives in three domains with 432 MTurk participants.
Experimental setup
Datasets: UN population estimates for 36 countries box-office gross for 36 movies auction prices for 36 paintings
Benchmarks: MTurk crowdsourcing study (geography, movies, paintings)
Metrics: Kendall-Tau distance Spearman's rho pairwise hit rate top-t hit rate
Baselines: Borda Copeland Maximin Schulze Copeland on votes only
Builds on: surprisingly popular algorithm surprisingly popular voting Mallows model Condorcet
Closest papers by meaning
- Selective Preference Aggregation (ICML 2025 · similarity 0.86)
- Can We Predict the Election Outcome from Sampled Votes? (AAAI 2020 · similarity 0.86)
- Comparing Election Methods Where Each Voter Ranks Only Few Candidates (AAAI 2020 · similarity 0.86)
- Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling (ICLR 2026 · similarity 0.85)
- Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability (ICML 2021 · similarity 0.85)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.