Research map / Learning theory and algorithms / Submodular and game algorithms
Computing Voting Rules with Improvement Feedback
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.
Characterizes which positional scoring rules and Condorcet-consistent rules can be computed from t-improvement feedback (where users return a higher-ranked candidate within t positions), showing plurality is learnable but most other rules, including Condorcet winners, are not.
Problem
Aggregating preferences when voters can only give incremental improvement feedback rather than full rankings or pairwise comparisons; which voting rules can be computed from such feedback.
Approach
Introduces t-improvement feedback, where a queried candidate is returned with some probability as a better candidate within its t-above neighborhood, and uses t-indistinguishable profile constructions (swap-based) to prove impossibilities for positional scoring rules and Condorcet-consistent rules, while showing plurality and a t-dependent scoring rule are learnable.
Key results
- Plackett-Luce and Mallows simulations show pairwise and improvement feedback trade off depending on the underlying ranking distribution (m=20, t=5)
- Plurality is learnable under t-improvement feedback, and only plurality, the t-specific scoring rule and their linear combinations are learnable among positional scoring rules for t <= m/2-2
- No randomized algorithm identifies the Condorcet winner with probability above 1/m under uniform t-improvement feedback for m>=13
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use t-improvement feedback instead of pairwise comparison queries | Borda · Impartial culture (IC) | approximation ratio of optimal Borda score | No clear effect |
| Use t-improvement feedback instead of pairwise comparison queries | Copeland · Impartial culture (IC) | approximation ratio of optimal Copeland score | No clear effect |
| Use t-improvement feedback instead of pairwise comparison queries | Borda · Plackett-Luce (PL) model | approximation ratio of optimal Borda score | Hurt |
| Use t-improvement feedback instead of pairwise comparison queries | Copeland · Plackett-Luce (PL) model | approximation ratio of optimal Copeland score | Hurt |
| Use t-improvement feedback instead of pairwise comparison queries | Borda · Mallows model | approximation ratio of optimal Borda score | Helped |
| Use t-improvement feedback instead of pairwise comparison queries | Copeland · Mallows model | approximation ratio of optimal Copeland score | Helped |
| Use linear-decay or exponential-decay improvement feedback instead of uniform improvement feedback | Borda and Copeland winner estimation · IC, PL, and Mallows models | approximation ratio of optimal score | No clear effect |
| Vary t from the reported setting | Borda and Copeland winner estimation · IC, PL, and Mallows models | approximation ratio of optimal score | No clear effect |
Surprising findings
- Under the Mallows and Plackett-Luce simulations, improvement feedback beats pairwise feedback in some regimes despite worst-case theory
- Under the impartial culture model, the two feedback types behave identically in simulations
Limitations
- Results rely on idealized access to exact feedback probabilities
- Negative results for general t-improvement distributions and t > m/2-2 are not fully resolved
- Condorcet impossibility has an exception for one specific distribution family
Experimental setup
Benchmarks: simulated preference profiles (IC, Mallows, Plackett-Luce)
Metrics: approximation ratio of Borda and Copeland score
Baselines: pairwise comparison feedback
Builds on: pairwise comparison impossibility results t-wise comparison characterization of scoring rules
Closest papers by meaning
- Voting with Preference Intensities (AAAI 2023 · similarity 0.88)
- Modelling Iterative Judgment Aggregation (AAAI 2018 · similarity 0.87)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.86)
- Selective Preference Aggregation (ICML 2025 · similarity 0.85)
- Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion (AAAI 2024 · similarity 0.85)
- Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction (NeurIPS 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.