PRAGMA Project

AGH · Kraków · Poland

Pragmatics of Multiwinner Voting: Algorithms and Preference Data Analysis

Multiwinner voting deals with the problem of selecting a group of candidates (referred to as the committee) that, in some sense, collectively represent the views of a group of agents (the voters). While in recent years the researchers working within (computational) social choice theory have made great progress regarding both the analysis of the properties of multiwinner voting rules and the design of algorithms for computing winning committees, their results remain fairly abstract. In this project we take a more pragmatic approach and aim to bridge the gap between what we know about committee elections and what we would like to use them for. The proposal is based on the following two guiding ideas:

  1. The theory of multiwinner voting provides an excellent abstract basis for group decision making, but it is missing principled means of extending and adapting its results (algorithms, computational complexity results, axiomatic analysis, etc.) to particular needs of specific applications, which often require novel approaches and ideas (such as new languages of representing voters’ preferences or requiring different properties from the algorithms and voting rules).
  2. Currently, the understanding of preference data—for elections in general and for multiwinner elections in particular—is very limited. While there is a repository of real-life election data [PrefLib] and there are numerous models of generating synthetic data, it is quite unclear what data and what preference models should be used in what contexts (thus, researchers often make their choices ad hoc).

The proposed vision is to enable the use of fair, efficient, explainable multiwinner voting mechanisms, whose performance can both be guaranteed theoretically and verified experimentally, on truly relevant data. From the perspective of computational social choice, our goal is to obtain deeper understanding of the theory and pragmatics of multiwinner voting. From the broader point of view, our goal is to provide a set of mathematical and computational tools that can be used for group decision-making in as many areas of science—and other human activities—as possible.

The PRAGMA project has received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854).

Team

Principal Investigator

  Piotr Faliszewski

Team Members

  Krzysztof Sornat (May 2024 – present, Jun 2021 - Nov 2022)

  Grzegorz Pierczyński (Sep 2023 – present)

  Grzegorz Lisowski (Mar 2023 – present)

  Łukasz Janeczko (Jan 2022 – present)

  Andrzej Kaczmarczyk (Nov 2021 – present)

  Stanisław Szufa (Jul 2021 – present)

Former Team Members

  Tomasz Wąs (Mar 2022 – Aug 2022)

Seminars

Group Seminar

Each Monday at 4 p.m. [room='Online']

Joint Seminar with the University of Warsaw (Faculty of Mathematics, Informatics, and Mechanics)

First Thursday each month at 12 p.m. [room='Online']
Official website of the seminar

Publications

PhD Theses

· Map of Elections, S. Szufa, 2024

2024

Journals

· A Map of Diverse Synthetic Stable Matching Instances, N. Boehmer, K. Heeger, S. Szufa, Journal of Artificial Intelligence Research, Vol. 79, 2024

Conferences

· Discovering Consistent Subelections, Ł. Janeczko, J. Lang, G. Lisowski, S. Szufa, AAMAS-2024 (Accepted for publication)

· Single-Winner Voting with Alliances: Avoiding the Spoiler Effect, G. Pierczyński, S. Szufa, AAMAS-2024 (Accepted for publication)

· Strategic Cost Selection in Participatory Budgeting. Extended Abstract, P. Faliszewski, Ł. Janeczko, A. Kaczmarczyk, G. Lisowski, P. Skowron, S. Szufa, AAMAS-2024 (Accepted for publication)

· Selecting Representative Bodies: An Axiomatic View. Blue-Sky Ideas, M. Revel, N. Boehmer, R. Colley, M. Brill, P. Faliszewski, E. Elkind, AAMAS-2024 (Accepted for publication)

· Fine-Grained Liquid Democracy for Cumulative Ballots, M. Köppe, M. Koutecký, K. Sornat, N. Talmon, AAMAS-2024 (Accepted for publication)

2023

Journals

· Improving Resource Allocations by Sharing in Pairs, R. Bredereck, A. Kaczmarczyk, J. Luo, R. Niedermeier, F. Sachse, Journal of Artificial Intelligence Research, Vol. 78, 2023

· Justifying Groups in Multiwinner Approval Voting, E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin, W. Suksompong, Theoretical Computer Science, Vol. 969, 2023

Conferences

· High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming, R. Bredereck, A. Kaczmarczyk, D. Knop, R. Niedermeier, ECAI-2023 (Kraków, Poland)

· Robustness of Participatory Budgeting Outcomes: Complexity and Experiments, N. Boehmer, P. Faliszewski, A. Kaczmarczyk, Ł. Janeczko, SAGT-2023 (United Kingdom, London)

· Map of Diverse Synthetic Stable Roommates Instances (recognized as Best Student Paper), N. Boehmer, K. Heeger, S. Szufa, AAMAS-2023 (United Kingdom, London)

· Bribery Can Get Harder in Structured Multiwinner Approval Election, B. Kusek, R. Bredereck, P. Faliszewski, A. Kaczmarczyk, D. Knop, AAMAS-2023 (United Kingdom, London)

· Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist, N. Boehmer, P. Faliszewski, S. Kraiczy, ICML-2023 (USA, Honolulu)

· Ties in Multiwinner Approval Voting, Ł. Janeczko, P. Faliszewski, IJCAI-2023 (China, Macao)

· Diversity, Agreement, and Polarization in Elections, T. Wąs, P. Faliszewski, A. Kaczmarczyk, K. Sornat, S. Szufa, IJCAI-2023 (China, Macao)

· An Experimental Comparison of Multiwinner Voting Rules on Approval Elections, P. Faliszewski, M. Lackner, K. Sornat, S. Szufa, IJCAI-2023 (China, Macao)

· Participatory Budgeting: Data, Tools and Analysis, P. Faliszewski, J. Flis, D. Peters, G. Pierczyński, P. Skowron, D. Stolicki, S. Szufa, N. Talmon, IJCAI-2023 (China, Macao)

· Properties of Position Matrices and Their Elections, N. Boehmer, J. Cai, P. Faliszewski, A. Z. Fan, Ł. Janeczko, A. Kaczmarczyk, T. Wąs, AAAI-2023 (USA, Washington DC)

2022

Conferences

· Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning, N. Boehmer, R. Bredereck, E. Elkind, P. Faliszewski, S. Szufa, NeurIPS-2022 (USA, New Orleans)

· Preserving Consistency for Liquid Knapsack Voting, P. Jain, K. Sornat, N. Talmon, EUMAS-2022 (Düsseldorf, Germany; Best Paper Runner-Up)

· Robustness of Greedy Approval Rules, P. Faliszewski, G. Gawron, B. Kusek, EUMAS-2022 (Düsseldorf, Germany)

· Using Multiwinner Voting to Search for Movies, P. Faliszewski, G. Gawron, EUMAS-2022 (Düsseldorf, Germany)

· Justifying Groups in Multiwinner Approval Voting, E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin, W. Suksompong, SAGT-2022 (UK, Colchester)

· A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners, N. Boehmer, R. Bredereck, P. Faliszewski, R. Niedermeier, EAAMO-2022 (USA, Washington DC)

· A Map of Diverse Synthetic Stable Roommates Instances, N. Boehmer, K. Heeger, S. Szufa, MATCH-UP-2022 (Austria, Vienna)

· Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules, K. Sornat, V. Vassilevska Williams, Y. Xu, IJCAI-2022 (Austria, Vienna)

· When Votes Change and Committees Should (Not), R. Bredereck, T. Fluschnik, A. Kaczmarczyk, IJCAI-2022 (Austria, Vienna)

· Understanding Distance Measures Among Elections, N. Boehmer, P. Faliszewski, R. Niedermeier, S. Szufa, T. Wąs, IJCAI-2022 (Austria, Vienna)

· How to Sample Approval Elections?, S. Szufa, P. Faliszewski, Ł. Janeczko, M. Lackner, A. Slinko, K. Sornat, N. Talmon, IJCAI-2022 (Austria, Vienna)

· The Price of Justified Representation, E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin, W. Suksompong, AAAI-2022 (Canada, Vancouver)

· The Complexity of Proportionality Degree in Committee Elections, Ł. Janeczko, P. Faliszewski, AAAI-2022 (Canada, Vancouver)

· The Complexity of Subelection Isomorphism Problems, P. Faliszewski, K. Sornat, S. Szufa, AAAI-2022 (Canada, Vancouver)

· On Improving Resource Allocations by Sharing, R. Bredereck, A. Kaczmarczyk, J. Luo, R. Niedermeier, F. Sachse, AAAI-2022 (Canada, Vancouver)

2021

Conferences

· Putting a Compass on the Map of Elections, N. Boehmer, R. Bredereck, P. Faliszewski, R. Niedermeier, S. Szufa, IJCAI-2021 (Canada, Montreal)

· Participatory Budgeting with Project Groups, P. Jain, K. Sornat, N. Talmon, M. Zehavi, IJCAI-2021 (Canada, Montreal)

· Fine-Grained Complexity and Algorithms for the Schulze Voting Method, K. Sornat, V. V. Williams, Y. Xu, EC-2021 (Hungary, Budapest)

Contact

Phone: (+48) 12 328-33-34

Email: faliszew@agh.edu.pl

Address ul. Kawiory 21 30-055 Kraków, Poland