Kavli Affiliate: Felix Fischer
| First 5 Authors: Javier Cembrano, Felix Fischer, David Hannon, Max Klimm,
| Summary:
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(n^{kappa})$ nominations, where $kappain[0,1]$. For $kappa=0$,
i.e., when each individual casts at most a constant number of nominations, this
bound is $O(sqrt{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.
| Search Query: ArXiv Query: search_query=au:”Felix Fischer”&id_list=&start=0&max_results=3