Impartial selection with additive guarantees via iterated deletion
研究了在群体中基于提名进行公正选择的问题，提出一种确定性机制，其加性性能保证为O(n^{(1+κ)/2})，并证明该界是最优的。
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+κ)/2) in a setting with n individuals where each individual casts O(nκ) nominations, where κ∈[0,1]. This bound is O(n) for κ=0 and O(n) for κ=1. The latter 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.