Kavli Affiliate: Felix Fischer
| First 5 Authors: Javier Cembrano, Felix Fischer, Max Klimm, ,
| Summary:
We give new bounds for the single-nomination model of impartial selection, a
problem proposed by Holzman and Moulin (Econometrica, 2013). A selection
mechanism, which may be randomized, selects one individual from a group of $n$
based on nominations among members of the group; a mechanism is impartial if
the selection of an individual is independent of nominations cast by that
individual, and $alpha$-optimal if under any circumstance the expected number
of nominations received by the selected individual is at least $alpha$ times
that received by any individual. In a many-nominations model, where individuals
may cast an arbitrary number of nominations, the so-called permutation
mechanism is $1/2$-optimal, and this is best possible. In the single-nomination
model, where each individual casts exactly one nomination, the permutation
mechanism does better and prior to this work was known to be $67/108$-optimal
but no better than $2/3$-optimal. We show that it is in fact $2/3$-optimal for
all $n$. This result is obtained via tight bounds on the performance of the
mechanism for graphs with maximum degree $Delta$, for any $Delta$, which we
prove using an adversarial argument. We then show that the permutation
mechanism is not best possible; indeed, by combining the permutation mechanism,
another mechanism called plurality with runner-up, and some new ideas,
$2105/3147$-optimality can be achieved for all $n$. We finally give new upper
bounds on $alpha$ for any $alpha$-optimal impartial mechanism. They improve
on the existing upper bounds for all $ngeq 7$ and imply that no impartial
mechanism can be better than $76/105$-optimal for all $n$; they do not preclude
the existence of a $(3/4-varepsilon)$-optimal impartial mechanism for
arbitrary $varepsilon>0$ if $n$ is large.
| Search Query: ArXiv Query: search_query=au:”Felix Fischer”&id_list=&start=0&max_results=3