Research map / Learning theory and algorithms / Prediction and decision losses
Active Ranking and Matchmaking, with Perfect Matchings
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 an algorithm for active ranking of noisy pairwise comparisons where every round is a perfect matching, built on AKS sorting networks and bandit-style gap estimation, achieving near-optimal sample/time complexity and matchmaking cost.
Problem
Actively ranking players from noisy pairwise comparisons when every round must pair all players (perfect matching), while minimizing the cost of unbalanced pairings (matchmaking).
Approach
Uses the AKS-Paterson sorting network as a black box with a confidence-aware COMPARE subroutine to get an (epsilon,delta)-PAC ranking in O(log N) parallel rounds, refines it via cascading phases to an exact ranking, then learns the epsilon*-adjacency graph with a LIL-UCB-style elimination to output a min-cost perfect matching.
Key results
- Achieves (epsilon,delta)-PAC ranking in O(eps^-2 log^3 N log(N/delta)) rounds, matching the lower bound up to log^3 N factor.
- Exact ranking in O(log^3 N log(N/delta)/min_i Delta_i^2) rounds (plus log log terms).
- Optimal-matching regret upper bound matches a lower bound up to log^3 terms, with the lower bound from a 4-vertex construction duplicated N/4 times.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AKS-Paterson sorting with COMPARE for parallel comparisons | AKS(ε, δ) · (ε, δ)-PAC ranking | rounds: O(ε−2 log3 (N) log (N/δ)) rounds | Helped |
| Use AKS-Paterson sorting with COMPARE | AKS(ε, δ) · (ε, δ)-PAC ranking | comparisons: O(ε−2N log3 (N) log (N/δ)) comparisons; lower bound Ω(N/ε2 log (N/δ)) | Mixed |
| Refine the estimated ranking in successive phases | CASCADINGAKS · Exact ranking | rounds: O( log3(N) log(N/δ) / mini ∆2 i ) | Helped |
| Use the learned exact ranking to estimate the ε*-adjacency graph | CASCADINGAKS + GAPESTIMATION · Optimal matching | regret: O(∑ i∈[N−1]:∆i>ε∗ 1/∆2 ε∗,i log(N/δ log 1/∆2 ε∗,i) + ∑ i∈[N−1] 1/∆2 i log(N/δ log 1/∆2 i)) | Helped |
| Use combinatorial bandit algorithms instead of the proposed ranking-and-matching approach | Ranking from matching · Optimal matching | regret: O(N2 log(1/δ) / ∆2 min); O(N log(1/δ) / ∆2 0) | Hurt |
Surprising findings
- Exact ranking is sometimes necessary to find an optimal matching: an (eps*/2)-correct ranking is not always sufficient.
Limitations
- Time complexity is optimal only up to a log^3 N factor.
- AKS sorting network has a large hidden constant D, which makes it impractical.
- Assumes fixed known threshold eps* and independent comparison outcomes.
Experimental setup
Metrics: sample complexity time complexity (rounds) cumulative regret
Baselines: Falahatgar et al. 2017 active ranking Ren et al. 2019 binary insertion sort ranking Batcher sorting network combinatorial semi-bandit algorithms
Builds on: AKS sorting network LIL-UCB Bradley-Terry-Luce model
Closest papers by meaning
- Fairness in Repeated Matching: A Maximin Perspective (AAAI 2026 · similarity 0.88)
- Blind, Greedy, and Random: Algorithms for Matching and Clustering Using Only Ordinal Information (AAAI 2016 · similarity 0.88)
- An Analysis of Elo Rating Systems via Markov Chains (NeurIPS 2024 · similarity 0.86)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.86)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.85)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · 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.