In many collective decision-making scenarios—such as awarding a "Best Paper" prize at a conference, selecting a committee chair, or distributing research grants—the voters are also the candidates. This creates a fundamental incentive problem: a rational agent might withhold a vote from a strong competitor or vote for themselves to increase their own chances of winning.
Impartial selection is the study of mechanisms that are immune to such manipulation. A mechanism is impartial if an agent’s selection is entirely independent of their own nominations. While this sounds like a simple fairness requirement, it introduces a rigorous mathematical "tax" on accuracy.
The Failure of Deterministic Rules
The most intuitive way to pick a winner is to count the votes and take the person with the highest tally. However, if we want to ensure that no one can influence their own outcome, we must ignore an agent's vote when considering that specific agent.
Noga Alon, Felix Fischer, Ariel Procaccia, and Moshe Tennenholtz demonstrated in Sum of Us: Strategyproof Selection from the Selectors that deterministic rules are fundamentally limited. They proved that any deterministic impartial rule cannot guarantee a finite approximation of the maximum vote count. In fact, to remain impartial, a deterministic rule might be forced to select a candidate with zero votes even when a highly popular candidate exists.
This impossibility stems from the structural constraints of the "voting graph." As Javier Cembrano, Felix Fischer, and Max Klimm show in Optimal Impartial Correspondences, any deterministic rule must potentially include candidates who have at least one fewer vote than the maximum. This "1-min-additivity" is a hard theoretical ceiling on how precise a fair deterministic system can be.
The Partitioning Solution
To bypass the failures of deterministic rules, researchers turned to randomization. The most successful mechanism for achieving impartiality is partitioning.
The intuition is simple: split the set of candidates into two or more groups. To decide who wins from Group A, you only look at the votes cast by members of Group B. Because members of Group A cannot vote for themselves (their votes are only used to judge Group B), they have no way to influence their own selection.
However, this fairness comes at a cost. In Optimal Impartial Selection, Felix Fischer and Max Klimm proved a fundamental limit: no impartial mechanism can guarantee more than 50% of the maximum possible nominations in expectation. This is most obvious in a two-person race: if Agent A and Agent B vote for each other, an impartial mechanism must ignore A's vote for B and B's vote for A, essentially reducing the choice to a coin flip regardless of external support.
Quantifying the Impartiality Tax
The gap between the "true" winner (the person with the most votes) and the winner selected by an impartial mechanism is often called the impartiality tax.
Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas have extensively mapped this tax. In Impartial Selection with Additive Approximation Guarantees, they showed that even the best randomized mechanisms incur an additive error that scales with the square root of the population size ($\sqrt{n}$).
This means that as the group grows, the "error"—the number of votes the winner might be missing compared to the true most-popular person—inevitably increases. This error is not a flaw in the algorithm, but a mathematical necessity of maintaining manipulation-proofness.
Modern Frontiers: Constraints and Predictions
Recent research has moved beyond simple "pick the winner" scenarios to more complex environments:
- Combinatorial Constraints: In Impartial Selection Under Combinatorial Constraints, Javier Cembrano, Max Klimm, and Arturo Merino explored what happens when you have a budget (knapsack constraints) or structural requirements (matroids). They found that the "girth" of the system—the size of the smallest set that violates the constraints—is the key factor in determining how well an impartial mechanism can perform.
- Augmented Information: Can we reduce the impartiality tax if we have a little bit of extra help? Ioannis Caragiannis and colleagues explored using prior information about candidates to guide the selection. More recently, Javier Cembrano, Felix Fischer, and Max Klimm investigated Impartial Selection with Predictions. They demonstrated that using external advice (like an LLM's prediction of the winner) can significantly improve accuracy when the advice is good (consistency) without losing the safety net of impartiality if the advice is wrong (robustness).
By treating impartiality as a hard constraint, this field provides the blueprint for designing systems where the "best" can be chosen by their peers without the process devolving into a game of strategic sabotage.