Impartial selection with prior information

We study the problem of em impartial selection, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular individual among a set of community members. The input can be modeled as a directed graph, where each node represents an individual, and a directed edge indicates nomination or approval of a community member to another. An em impartial mechanism is robust to potential selfish behavior of the individuals and provides appropriate incentives to voters to report their true preferences by ensuring that the chance of a node to become a winner does not depend on its outgoing edges. The goal is to design impartial mechanisms that select a node with an in-degree that is as close as possible to the highest in-degree. We measure the efficiency of such a mechanism by the difference of these in-degrees, known as its em additive approximation. In particular, we study the extent to which prior information on voters' preferences could be useful in the design of efficient deterministic impartial selection mechanisms with good additive approximation guarantees. We consider three models of prior information, which we call the em opinion poll, the em a prior popularity, and the em uniform model. We analyze the performance of a natural selection mechanism that we call em approval voting with default (AVD) and show that it achieves a O(√nlnn) additive guarantee for opinion poll and a O(ln2n) for a priori popularity inputs, where n is the number of individuals. We consider this polylogarithmic bound as our main technical contribution. We complement this last result by showing that our analysis is close to tight, showing an Omega(lnn) lower bound. This holds in the uniform model, which is the simplest among the three models.