Research map / Multi-agent systems and games / Games and equilibria
Impartial Selection with Predictions
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.
Studies impartial mutual-nomination selection when a predicted top set is available, giving consistency-robustness trade-offs for 1-, 2- and k-selection via permutation-based mechanisms.
Problem
Impartial selection of agents based on mutual nominations, where mechanisms have been limited to weak approximation guarantees; the question is how much a prediction of the top-indegree set can improve them while remaining robust to bad predictions.
Approach
Extends permutation-based impartial mechanisms by placing predicted vertices at fixed positions (e.g., end of permutation or at position rho, or both ends) so their incoming edges are likely observed, giving consistency-robustness trade-offs that are near-optimal and tight for several settings.
Key results
- For 1-selection, the rho-permutation mechanism is rho-consistent and (1-rho)-robust for rho in [1/2,1], and this trade-off is shown best possible.
- For k-selection, the rho-partition mechanism with rho=1/2 achieves consistency 1-1/(2k) and robustness approaching 1-1/e as k grows; with rho=1 it is 1-consistent.
- For plurality graphs, the 1-permutation mechanism is 1-consistent and 1/2-robust; the bidirectional variant for 2-selection is 1-consistent and 1/2-robust.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Place the predicted vertex last in the permutation | Uniform permutation mechanism on plurality graphs · Plurality graphs, 1-selection | consistency: \frac{2}{3} -> 1 | Helped |
| Place the predicted vertex last in the permutation | Uniform permutation mechanism on plurality graphs · Plurality graphs, 1-selection | robustness: \frac{2}{3} -> \frac{1}{2} | Hurt |
| Place the predicted vertex at both ends across the forward and reverse permutations | Bidirectional permutation mechanism · General approval voting, 2-selection | consistency: \frac{1}{2} -> 1 | Helped |
| Place the predicted vertex at both ends across the forward and reverse permutations | Bidirectional permutation mechanism · General approval voting, 2-selection | robustness: \frac{1}{2} -> \frac{1}{2} | No clear effect |
| Place one predicted vertex in each partition and bias its position to ρ | k-partition mechanism · General approval voting, k-selection | consistency: 1-\frac{1- ho}{k} | Helped |
| Place one predicted vertex in each partition and bias its position to ρ | k-partition mechanism · General approval voting, k-selection | robustness: \bigl(1-\frac{2\rho}{k+1}\bigr) \bigl(1-\bigl(\frac{k-1}{k}\bigr)^k\bigr) | Mixed |
| Use the ρ-partition mechanism with ρ=1 instead of ρ=\frac{1}{2} (ablation) | ρ-partition mechanism · General approval voting, k-selection | consistency: 1-\frac{1}{2k} -> 1 | Helped |
| Use the ρ-partition mechanism with ρ=1 instead of ρ=\frac{1}{2} (ablation) | ρ-partition mechanism · General approval voting, k-selection | robustness: \frac{1}{2} -> \frac{1}{4} (k=2); \frac{19}{36} -> \frac{19}{54} (k=3); \frac{35}{64} -> \frac{105}{256} (k=4) | Hurt |
| Use the ρ-partition mechanism with ρ=\frac{1}{2} instead of ρ=1 (ablation) | ρ-partition mechanism · General approval voting, k-selection | robustness: \frac{1}{4} -> \frac{1}{2} (k=2); \frac{19}{54} -> \frac{19}{36} (k=3); \frac{105}{256} -> \frac{35}{64} (k=4) | Helped |
Surprising findings
- The baseline lottery between a predicted-vertex mechanism and the uniform permutation mechanism achieves the same trade-off for 1-selection but fails basic unanimity fairness, which the rho-permutation mechanism satisfies.
Limitations
- Gaps remain between upper and lower bounds in most settings (k>=3 and plurality cases).
- Results are theoretical; mechanisms are not tested in practical applications such as LLM output aggregation.
Experimental setup
Metrics: consistency robustness approximation ratio of indegree sum
Baselines: uniform permutation mechanism bidirectional permutation mechanism k-partition mechanism with permutation baseline lottery mechanism
Builds on: permutation mechanism bidirectional permutation mechanism k-partition mechanism with permutation robustness-consistency framework
Closest papers by meaning
- Joint Scoring Rules: Competition Between Agents Avoids Performative Prediction (AAAI 2025 · similarity 0.85)
- Manipulation-Robust Selection of Citizens’ Assemblies (AAAI 2024 · similarity 0.85)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.83)
- Select to Perfect: Imitating desired behavior from large multi-agent data (ICLR 2024 · similarity 0.83)
- Fair Secretaries with Unfair Predictions (NeurIPS 2024 · similarity 0.83)
- Attack Selection In Agentic AI Control Evaluations Meaningfully Decreases Safety (NeurIPS 2026 · similarity 0.82)
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.