PRAGMA Project
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:
- 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).
- 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
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)
Stanisław Szufa (Jul 2021 – present)
Former Team Members
Andrzej Kaczmarczyk (Nov 2021 – Sep 2024)
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
· The Complexity of Subelection Isomorphism Problems, P. Faliszewski, K. Sornat, S. Szufa, Journal of Artificial Intelligence Research, Vol. 80, 2024
· A Map of Diverse Synthetic Stable Matching Instances, N. Boehmer, K. Heeger, S. Szufa, Journal of Artificial Intelligence Research, Vol. 79, 2024
Conferences
· The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, H. Aziz, J. Gan, G. Lisowski, A. Pourmiri, SAGT-2024 (The Netherlands, Amsterdam)
· An O(loglog n)-Approximation for Submodular Facility Location, F.Abbasi, M. Adamczyk, M. Bosch-Calvo, J. Byrka, F. Grandoni, K. Sornat, A. Tinguely, ICALP-2024 (Accepted for publication)
· Aggregation of Continuous Preferences in One Dimension, A. Del Pia, D. Knop, A. Lassota, K. Sornat and N. Talmon, IJCAI-2024 (South Korea, Jeju)
· Selecting the Most Conflicting Pair of Candidates, T. Delemazure, Ł. Janeczko, A. Kaczmarczyk, S. Szufa, IJCAI-2024 (South Korea, Jeju)
· Nonparametric Detection of Gerrymandering in Multiparty Plurality Elections, D. Stolicki, W. Słomczyński, S. Szufa, IJCAI-2024 (South Korea, Jeju)
· Evaluation of Project Performance in Participatory Budgeting, N. Boehmer, P. Faliszewski, Ł. Janeczko, D. Peters, G. Pierczyński, Š. Schierreich, P. Skowron, S. Szufa, IJCAI-2024 (South Korea, Jeju)
· Guide to Numerical Experiments on Elections in Computational Social Choice, N. Boehmer, P. Faliszewski, Ł. Janeczko, A.Kaczmarczyk, G. Lisowski, G. Pierczyński, S. Rey, D. Stolicki, S. Szufa, T. Wąs, IJCAI-2024 (South Korea, Jeju)
· Discovering Consistent Subelections, Ł. Janeczko, J. Lang, G. Lisowski, S. Szufa, AAMAS-2024 (New Zealand, Auckland)
· Single-Winner Voting with Alliances: Avoiding the Spoiler Effect, G. Pierczyński, S. Szufa, AAMAS-2024 (New Zealand, Auckland)
· Strategic Cost Selection in Participatory Budgeting. Extended Abstract, P. Faliszewski, Ł. Janeczko, A. Kaczmarczyk, G. Lisowski, P. Skowron, S. Szufa, AAMAS-2024 (New Zealand, Auckland)
· Selecting Representative Bodies: An Axiomatic View (Blue-Sky Ideas Track), 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 (Poland, Kraków)
· 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 (Germany, Düsseldorf; Best Paper Runner-Up)
· Robustness of Greedy Approval Rules, P. Faliszewski, G. Gawron, B. Kusek, EUMAS-2022 (Germany, Düsseldorf)
· Using Multiwinner Voting to Search for Movies, P. Faliszewski, G. Gawron, EUMAS-2022 (Germany, Düsseldorf)
· 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