Research map / Multi-agent systems and games / Games and equilibria
Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction
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.
Applies quantitative relative judgment aggregation (QRJA) from computational social choice to ranking prediction from race/contest results, giving almost-linear-time algorithms for l_p QRJA (p>=1), NP-hardness for p<1, and experiments showing competitive prediction on sports/contest datasets.
Problem
Predicting future contest rankings and relative performance of contestants from past race or contest results, where each race yields pairwise quantitative judgments that are noisy by race difficulty and sparse participation.
Approach
Treats race results as quantitative relative judgments (score differences between contestants) and aggregates them via l_p QRJA, a least-p-norm regression over pairwise differences, to obtain interpretable single-dimensional contestant strengths that account for common race difficulty and transitivity.
Key results
- l1 and l2 QRJA are always among the best algorithms in ordinal accuracy and quantitative loss across the four main datasets, performing comparably to matrix factorization.
- l_p QRJA is solvable in O(m^{1+o(1)}) time for p>=1 and NP-hard to approximate within (1+c/n^2) for p<1.
- Subsampling judgments with all-ones weights reduces the number of judgments to about 0.4 of the original on Chess with minor performance loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ℓ1 or ℓ2 QRJA instead of other tested algorithms | contest ranking prediction · Chess, F1, Marathon, Codeforces | ordinal accuracy | Helped |
| use ℓ1 or ℓ2 QRJA instead of other tested algorithms | contest ranking prediction · Chess, F1, Marathon, Codeforces | quantitative loss | Helped |
| use Matrix Factorization instead of QRJA | contest ranking prediction · Chess, F1, Marathon, Codeforces | ordinal accuracy | No clear effect |
| use Matrix Factorization instead of QRJA | contest ranking prediction · Chess, F1, Marathon, Codeforces | quantitative loss | No clear effect |
| use Mean or Median instead of QRJA | contest ranking prediction · F1 and Codeforces | ordinal accuracy | Hurt |
| use Mean or Median instead of QRJA | contest ranking prediction · Chess, F1, Marathon, Codeforces | quantitative loss | Hurt |
| use Borda or Kemeny-Young instead of QRJA | contest ranking prediction · F1 | ordinal accuracy | Mixed |
| reduce the number of judgments by subsampling at rate α ≥ 0.4 (ablation) | ℓ1 and ℓ2 QRJA · Chess | ordinal accuracy | No clear effect |
| reduce the number of judgments by subsampling at rate α ≥ 0.4 (ablation) | ℓ1 and ℓ2 QRJA · Chess | quantitative loss | No clear effect |
| use ℓ2 instead of ℓ1 QRJA (ablation) | QRJA · Chess and other subsampled datasets | robustness to subsampling | Helped |
| use ℓ2 instead of ℓ1 QRJA (ablation) | QRJA · F1-Full | ordinal accuracy and quantitative loss | Hurt |
| use ℓ2 instead of ℓ1 QRJA (ablation) | QRJA · F1-Full | quantitative loss | Hurt |
Surprising findings
- Borda and Kemeny-Young, using only rankings, perform very well on F1 and F1-Full despite not using numerical scores.
- Low-rank matrix factorization with rank 2 or 5 overfits and performs worse than rank 1 on several datasets.
Limitations
- General p>=1 almost-linear algorithm relies on galactic min-cost flow algorithms, so practical experiments use only l1 and l2.
- Kemeny-Young only scales to hundreds of contestants, so it is run on per-contest subsets.
- Assumes judgments are non-strategic and that a single latent quality per contestant suffices; no GPU/LLM component.
Experimental setup
Datasets: Tata Steel Chess Tournament results 1983-2023 Formula 1 race results 1950-2023 Boston and New York Marathon results 2000-2023 Codeforces Division 1 contest results 2010-2023 Cross-Tables tournament results 2000-2023 F1-Full Codeforces-Core
Benchmarks: Chess F1 Marathon Codeforces Cross-Tables F1-Full Codeforces-Core
Metrics: ordinal accuracy quantitative loss (normalized L1) L2 quantitative loss entrywise L1/L2 loss
Baselines: Mean Median Borda rule Kemeny-Young rule Matrix Factorization
Builds on: quantitative judgment aggregation minimum cost flow Kemeny-Young rule Borda rule Elo rating system
Closest papers by meaning
- Data-driven Rank Breaking for Efficient Rank Aggregation (ICML 2016 · similarity 0.86)
- Heterogeneous Judge-Aware Ranking with Sensitivity, Disagreement, and Confidence (NeurIPS 2026 · similarity 0.86)
- Selective Preference Aggregation (ICML 2025 · similarity 0.86)
- Computing Voting Rules with Improvement Feedback (ICML 2025 · similarity 0.85)
- Inherent Trade-Offs between Diversity and Stability in Multi-Task Benchmarks (ICML 2024 · similarity 0.84)
- ResponseRank: Data-Efficient Reward Modeling through Preference Strength Learning (NeurIPS 2025 · similarity 0.84)
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.