IJCAI-ECAI-2018 Tutorial


Table of Contents

  1. Presenters
  2. Abstract
  3. Presenters' short bio's
  4. Tutorial Outline
  5. Tutorial Notes and Materials



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!


Piotr 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

  phone: +48 510-295-166 
Piotr 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


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



  1. Introduction
    • high-level overview of multiwinner voting and its applications (individual excellence, diversity, proportionality)
    • formal model of elections (hints on extensions)
    • formal presentation of the main issues (normative properties, computational complexity of winner determination, etc.)
  2. Overview of Interesting Multiwinner Rules
    • committee scoring rules
    • STV
    • approval-based rules
    • Condorcet-inspired rules
  3. Applications, Axioms, and Algorithms
    • individual excellence (committee enlargement monotonicity, noncrossing monotonicity, weakly-separable rules, Gehrlein-consistent rules)
    • diversity (applications, Chamberlin--Courant, axioms and characterizations, algorithms and complexity)
    • proportional representation (intuitions, formal axioms, STV, Monroe, PAV, justified representation, algorithms and complexity)
  4. Generalizations
    • participatory budgeting
    • proportional rankings and search engines
    • rules with variable number of winners
  5. Summary


Slides: Many of the ideas presented in the tutorial are also covered in the following chapter on multiwinner elections:
  • Multiwinner Voting: A New Challenge for Social Choice Theory, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon, In U. Endriss, editor, Trends in Computational Social Choice, 2017