Impartial Selection with Predictions

Javier Cembrano, Felix Fischer, Max KlimmNeurIPS 2025 · OpenReview

Introduction

Impartial selection is a fundamental problem in mechanism design where a group of agents must select one or more winners from among themselves based on nominations. The primary challenge is ensuring impartiality: an agent's own nomination should not influence their probability of being selected. Without this property, agents have a strong incentive for strategic voting—for example, withholding a vote from a strong competitor to improve their own chances.

Traditional impartial mechanisms face a significant "price of impartiality." For instance, the best possible randomized mechanism for selecting a single winner can only guarantee a winner with at least half as many votes as the most popular candidate. This paper explores whether external "predictions" (e.g., from an expert or an AI model) can be leveraged to improve performance without sacrificing impartiality.

Methods and Mechanisms

The authors introduce mechanisms that incorporate a prediction $\hat{i}$ about the potential winner. These mechanisms are evaluated based on two metrics:

  • Consistency ($\alpha$): The performance guarantee when the prediction is correct.
  • Robustness ($\beta$): The performance guarantee when the prediction is incorrect.

The core of their approach is the $\rho$-Permutation Mechanism. In a standard permutation mechanism, agents are ordered randomly, and a leader is updated as the list is traversed based on votes from preceding agents. By biasing this order—specifically, by placing the predicted winner at a specific position $\rho$—the mechanism can "see" more of their incoming votes while maintaining impartiality.

The ρ-permutation mechanism, which biases the selection order based on a predicted winner.

For selecting $k > 1$ winners, the authors propose more complex variations:

  • Fixed Bidirectional Permutation ($k=2$): Runs the mechanism in two directions, placing predicted winners at the ends of the sequence.
  • $\rho$-Partition Mechanism (General $k$): Partitions agents into $k$ sets, each containing one predicted winner, and applies biased permutations within each set.

Key Results and Theoretical Bounds

The paper establishes formal trade-offs between consistency and robustness across different voting models, such as approval voting (any number of nominations) and plurality voting (exactly one nomination).

Trade-offs between consistency (α) and robustness (β) for various selection mechanisms and values of k.

Key findings include:

  • Single Winner ($k=1$): There is a direct trade-off where $\alpha + \beta \le 1$. The $\rho$-permutation mechanism achieves $\alpha = \rho$ and $\beta = 1 - \rho$.
  • Plurality Voting Advantage: In plurality settings, the authors found a "free lunch" where one can achieve perfect consistency ($\alpha=1$) while maintaining the best possible robustness ($\beta=1/2$).
  • Scaling with $k$: As the number of winners increases, robustness approaches $1 - 1/e$ (approx. 0.632) while maintaining near-perfect consistency.

Conclusion

This work demonstrates that even fallible predictions can significantly enhance the performance of impartial selection mechanisms. By strategically positioning predicted winners in a selection sequence, it is possible to achieve high consistency when predictions are accurate without failing catastrophically when they are not. Future work remains to bridge the remaining mathematical gaps for $k \ge 3$ and to test these mechanisms in practical, real-world voting scenarios.

Summary updated

Abstract

We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to AI alignment. As agents both select and are selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is correct and robustness its performance when the prediction is incorrect. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.
BibTeX
@inproceedings{cembrano2025impartial,
  author = {Javier Cembrano and Felix Fischer and Max Klimm},
  title = {{Impartial Selection with Predictions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=vyI84ToW3q},
}
Figure