Research map / Bandits and online learning / Multi-armed bandits
Eliciting Kemeny Rankings
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.
Frames eliciting voter preferences for a Kemeny ranking as a dueling bandits problem and derives PAC sample complexities (with and without replacement) plus confidence-interval pruning and look-ahead adaptive sampling, evaluated on synthetic data.
Problem
Eliciting pairwise preferences from a population of voters efficiently enough to approximate a Kemeny ranking, without requiring complete preference profiles.
Approach
Treats pairwise voter comparisons as dueling-bandit feedback over a preference matrix, derives confidence-interval-based approximation bounds on Kemeny score (and shows Kendall tau approximation is impossible via sampling), gives PAC algorithms for sampling with and without replacement (hypergeometric), and prunes intervals using preference-matrix properties (symmetry, triangle inequality) with lo
Key results
- Sampling without replacement needs fewer samples than with replacement for the same approximation guarantee (theoretical comparison; e.g., theoretical sample complexity 6576 for sampling with replacement in the k=4 experiment).
- Look-ahead adaptive methods (optimistic, pessimistic, realistic) sometimes outperform uniform and opportunistic sampling for many samples in the without-replacement setting, while opportunistic sampling has much lower computational cost.
- Kendall tau approximation can be maximal even with arbitrarily small matrix error, so no PAC guarantee for Kendall tau distance from sample means.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| sample without replacement instead of with replacement | KemenyEl uniform sampling · Synthetic preference matrices | sample complexity | Helped |
| prune confidence intervals after each sample | Uniform sampling without replacement · Synthetic preference matrices | samples to reach approximation bound | Helped |
| use adaptive sampling instead of uniform sampling | Sampling without replacement with pruned confidence intervals · Synthetic preference matrices | sample complexity | Helped |
| use opportunistic sampling rather than uniform sampling | Sampling without replacement with pruning · Synthetic preference matrices | samples to reach approximation bound | Helped |
| use optimistic, pessimistic, or realistic look-ahead sampling rather than opportunistic sampling | Sampling without replacement with pruning · Synthetic preference matrices, larger sample counts | samples to reach approximation bound | Helped |
| use optimistic or realistic look-ahead rather than pessimistic look-ahead | Sampling without replacement with pruning · Synthetic preference matrices | sample complexity | Helped |
| use look-ahead sampling rather than uniform sampling | Sampling with replacement and pruned confidence intervals · Synthetic preference matrices | samples to reach approximation bound | Hurt |
| use uniform or opportunistic sampling rather than look-ahead sampling | Sampling with replacement and pruned confidence intervals · Synthetic preference matrices | samples to reach approximation bound: 6576 samples | Helped |
| prune confidence intervals | Uniform and opportunistic sampling with replacement · Synthetic preference matrices | samples to reach approximation bound | No clear effect |
| estimate the Kemeny ranking from sampled pairwise comparisons | Kemeny ranking elicitation · Preference matrices with winning probabilities near 0.5 | Kendall tau distance: d_Kt(τ, τ̂) = (k - 1)k/2 | No clear effect |
Surprising findings
- With replacement, uniform and opportunistic sampling behave identically and pruning appears to have no effect in tested instances.
- Look-ahead methods often get stuck sampling the same pairs in the with-replacement setting, including pessimistic sampling which should be conservative.
Limitations
- Experiments limited to small numbers of arms (up to 9) and 10 voters due to NP-hard Kemeny computation
- Results only on synthetic data
- Approximation bounds are loose compared to actual Kemeny score gaps
Experimental setup
Metrics: Kemeny score approximation gap confidence interval bound length number of samples
Baselines: uniform sampling opportunistic sampling
Builds on: dueling bandits Hoeffding inequality Kemeny rule
Closest papers by meaning
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.87)
- Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.87)
- The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits (NeurIPS 2026 · similarity 0.86)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.86)
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.86)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.86)
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.