# Impartial Selection with Additive Guarantees via Iterated Deletion

arXiv: https://arxiv.org/abs/2205.08979 · HTML: https://mlsanity.com/paper/2205.08979/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2022.

## Built on by (most cited first, 2 of 2)

- [Manipulation and Peer Mechanisms: A Survey](https://mlsanity.com/paper/2210.01984/) (2022)
- [Impartial Selection with Predictions](https://mlsanity.com/paper/2510.19002/) (2025)

## Abstract (arXiv)

Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. For this problem, we give a deterministic mechanism with an additive performance guarantee of O(n(1+kappa)/2) in a setting with n individuals where each individual casts O(nkappa) nominations, where kappa∈[0,1]. For kappa=0, i.e., when each individual casts at most a constant number of nominations, this bound is O(√n). This matches the best-known guarantee for randomized mechanisms and a single nomination. For kappa=1 the bound is O(n). This is trivial, as even a mechanism that never selects provides an additive guarantee of n-1. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.