MULTIWINNER ELECTIONS: APPLICATIONS, AXIOMS, ALGORITHMS, AND GENERALIZATIONS (HALF-DAY)
Table of Contents
Multiwinner elections have a broad area of applications in AI and multiagent systems, ranging from shortlisting tasks, through supporting various business decision, to choosing representative committees and parliaments. We present the area in general, discuss its recent, rapid progress, and concentrate on emerging future research directions.
In the standard model of multiwinner elections, the goal is to select a group of k individuals (the committee) based on the preferences of a number of agents (voters). While the most prominent example of multiwinner elections comes from the world of politics (parliamentary elections held in almost all modern democracies), they are widely present and include settings such as choosing other representative bodies (e.g., working groups to deal with particular issues), making various business decisions (e.g., choosing products for an Internet store to put on its homepage, choosing movies to put on a transatlantic flight), and shortlisting tasks (e.g., shortlisting applicants for a given academic position).
In this tutorial we will present several emerging applications of multiwinner voting (including those mentioned above, but also, e.g., their use in genetic algorithms), a number of multiwinner voting rules, and a number of algorithms for computing them (there is a large research corpus on coping with the computational intractability of most rules). Based on their axiomatic properties and on simulation results, we will argue which rules are best-suited for each application. We will discuss other models of multiwinner elections and their generalizations, such as selecting committees with variable number of winners, producing proportional rankings, and participatory budgeting.
No prior knowledge of computational social choice (i.e., COMSOC) is assumed. The attendees interested in COMSOC will learn cutting-edge results and interesting techniques. Multiagent systems designers will learn a new set of tools. Everyone will enjoy a fresh perspective on voting and democracy!
PRESENTERS' SHORT BIOSPiotr Faliszewski is an associate professor at the AGH University of Science and Technology in Krakow, Poland. He has obtained his PhD at the University of Rochester, USA, under the supervision of Prof. Lane A. Hemaspaandra. His main interests regard computational social choice, with focus on algorithms for, complexity of, and axiomatic properties of voting mechanisms. So far, he has written over 35 journal papers and 70 conference papers (including a runner-up for AAMAS-2013 best-paper award), several surveys and bookchapters. He was a visiting professor at the University of Auckland (New Zealand) and Universite Paris Dauphine (France), and was a Mercator Fellow with the group of Prof. Rolf Niedermeier at Technische Universität Berlin (Germany). At AGH, he is teaching courses on Algorithms and Data Structures, Computational Complexity Theory, and Algorithmic Game Theory. He has received the 2013 Polityka Research Award (anually granted to five Polish scientists across all areas of science).
Piotr Faliszewski AGH University of Science and Technology al. Mickiewicza 30 30-059 Krakow Poland phone: +48 510-295-166 email@example.comPiotr Skowron is an assistant professor at the University of Warsaw. Previously he was a postdoctoral fellow at the University of Oxford and at Technische Universtiät Berlin (where he held a Humboldt fellowship). He obtained his PhD at the University of Warsaw, Poland, under the supervision of Prof. Piotr Faliszewski and Prof. Krzysztof Rzadca. He is interested in algorithmic game theory, multiwinner elections, and scheduling. Piotr was a runner up for the Victor Lesser Distinguished Thesis Award for year 2015. He is an author of eight journal papers and over 30 conference papers.
Piotr Skowron University of Warsaw ul. Banacha 2, 02-097 Warsaw Poland firstname.lastname@example.org
Nimrod Talmon is a lecturer (assistant professor) at the Ben-Gurion University of the Negev. Previously he was a postdoctoral fellow at the Weizmann Institute of Science. He obtained his PhD at Technische Universität Berlin, Germany, under the supervision of Prof. Rolf Niedermeier. He is interested in algorithmic game theory and computational social choice, with a focus on combinatorial issues in voting (e.g., combinatorial control problems and multiwinner voting). He is an author of 10 journal papers and over 30 conference papers. He has received an award for the best PhD thesis of Faculty IV of the Technische Universität Berlin. Nimrod is also a professional musician.
Nimrod Talmon Ben-Gurion University of the Negev P.O.B. 653 Beer-Sheva Israel email@example.com
TUTORIAL NOTES AND MATERIALSSlides: