Τίτλος: Impartial selection, additive approximation guarantees, and priors
Ομιλητής: Γιάννης Καραγιάννης, Professor, Aarhus University, Denmark (on leave from CEID)
Ημερομηνία-χώρος: Παρασκευή 23 Απριλίου, 3-5μμ
Περίληψη: 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).
Σχετικά με τον ομιλητή: Ioannis Caragiannis is Professor in the Department of Computer Science at Aarhus University and member of the Algorithms and Data Structures group. Before coming to Aarhus, he spent approximately three decades in the University of Patras, getting his Diploma (1996) and PhD (2002), and serving as a faculty member (2004-2020) at the Department of Computer Engineering and Informatics. He is doing research on algorithm design and analysis, with a current focus on computational problems of economic nature. In particular, his research lies at the interface of Computer Science (theoretical computer science and foundations of AI) and Economics (mainly game theory and microeconomics).