Impartial selection with prior information

22^nd July 2020, 11:00
Nicos Protopapas

Abstract

We study the problem of 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 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 additive approximation.

Following the success in the design of auction and posted pricing mechanisms with good approximation guarantees for welfare and profit maximization, 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 opinion poll, the a priori popularity, and the uniform model. We analyze the performance of a natural selection mechanism that we call Approval Voting with Default (AVD) and show that it is $O(sqrt( ln(n) )-additive for opinion poll and O(ln(n)^2) 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(ln(n)) lower bound. This holds in the uniform model, which is the simplest among the three models.

Authors: Ioannis Caragiannis, Giorgos Christodoulou, Nicos Protopapas