Impartial selection, additive approximation guarantees, and priors

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 modelled 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 behaviour 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.

Recent progress has identified impartial selection rules with optimal approximation ratios. It was noted though that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of quality. We present randomized impartial selection mechanisms with additive approximation guarantees of o(n), where n is the number of nodes in the input graph.

We furthermore demonstrate that prior information on voters’ preferences can be useful in the design of simple (deterministic) impartial selection mechanisms with good additive approximation guarantees. In this direction, we consider different models of prior information and analyze the performance of a natural selection mechanism that we call approval voting with default (AVD).

The talk is based on joint work with George Christodoulou and Nicos Protopapas. No advanced mathematical background (besides basic knowledge on graphs and probability) is required to follow the talk.

Bio: Ioannis Caragiannis joined the Department of Computer Science of Aarhus University as a professor in August 2020. Before, he was a faculty member at the Department of Computer Engineering and Informatics of the University of Patras (since 2006), where he served as Director of its Division of Foundations and Applications of Computer Science (2017-2020). His research interests include design and analysis of algorithms, economics and computation, and foundations of machine learning and artificial intelligence. He has published 160 papers in conference proceedings, scientific journals, and books, and has participated in basic research projects funded by the European Commission and the Greek state. He regularly serves as a program committee member in conferences at the interface of theoretical computer science, artificial intelligence, and economics, such as ACM Conference on Economics and Computation (EC) and the International Joint Conference on Artificial Intelligence (IJCAI). Recently, he was program co-chair of the 15th International Conference on Web and Internet Economics (WINE 2019). Ioannis Caragiannis is a member of the Association for Computing Machinery (ACM, SIGACT, SIGECOM), the Association for the Advancement of Artificial Intelligence (AAAI), and the European Association for Theoretical Computer Science (EATCS).