Publications
2024
Guide to Numerical Experiments on Elections in Computational Social Choice [arxiv]
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko, Andrzej Kaczmarczyk, Grzegorz Lisowski, Grzegorz Pierczynski, Simon Rey, Dariusz Stolicki, Stanisław Szufa, Tomasz Wąs
[Conference] 33rd International Joint Conference on Artificial Intelligence: Survey Track (IJCAI 2024)
TL;DR: We analyze how numerical experiments regarding elections were conducted within the computational social choice literature and provide recommendations for the design and analysis of such experiments.
Evaluation of Project Performance in Participatory Budgeting [arxiv]
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko, Dominik Peters, Grzegorz Pierczynski, Simon Schierreich, Piotr Skowron, Stanisław Szufa
[Conference] 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024)
TL;DR: We study ways of evaluating the performance of losing projects in participatory budgeting (PB) elections, thereby contributing to an increased transparency of PB algorithms.
Selecting Representative Bodies: An Axiomatic View [arxiv]
Manon Revel, Niclas Boehmer, Rachael Colley, Markus Brill, Piotr Faliszewski and Edith Elkind
[Conference] 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2024)
TL;DR: We argue for the importance of an axiomatic analysis of different mechanisms for selecting representative bodies within a single framework.
Approval-Based Committee Voting in Practice: A Case Study of (Over-)Representation in the Polkadot Blockchain [arxiv]
Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein, Luis Sánchez-Fernández, Ulrike Schmidt-Kraepelin
[Conference] Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI 2024)
TL;DR: We provide the first large-scale data collection of real-world approval-based committee elections. We conduct an in-depth study of application-relevant questions, including a quantitative and qualitative analysis of the degree of (over)-representation in outcomes returned by different voting rules.
2023
Application-Oriented Collective Decision Making: Experimental Toolbox and Dynamic Environments
Niclas Boehmer
[PhD Thesis] Technische Universität Berlin; Won Chorafas Prize and 2023 Victor Lesser Distinguished Dissertation Award
Robustness of Participatory Budgeting Outcomes: Complexity and Experiments [arxiv]
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko, Andrzej Kaczmarczyk
[Conference] 16th International Symposium on Algorithmic Game Theory (SAGT 2023)
TL;DR: We analyze the robustness of funding decisions in participatory budgeting to random noise. We find that computing the funding probabilities of a project in case votes are randomly perturbed is computationally intractable. Using sampling, we identify many non-robust funding decisions in real-world participatory budgeting elections.
Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist
Niclas Boehmer, Piotr Faliszewski, Sonja Kraiczy
[Conference] Fortieth International Conference on Machine Learning (ICML 2023)
[Workshop] 9th International Workshop on Computational Social Choice (COMSOC 2023)
TL;DR: We analyze how the properties of rankings sampled from the Mallows model change when increasing the number of alternatives. We find that real-world data behaves differently than the Mallows model and issue several warnings about using the model.
Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions [arxiv]
Niclas Boehmer, L. Elisa Celis, Lingxiao Huang, Anay Mehrotra, Nisheeth K Vishnoi
[Conference] Fortieth International Conference on Machine Learning (ICML 2023)
TL;DR: We study subset selection from multiple rankings in the presence of bias. We show that requiring the subset to satisfy fairness constraints can mitigate biases but different aggregation functions need a very different number of rankings to do so.
Adapting Stable Matchings to Forced and Forbidden Pairs [arxiv]
Niclas Boehmer, Klaus Heeger
[Conference] 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023); Nominated for Best Paper Award
TL;DR: We study the (parameterized) complexity of minimally changing a given stable matching to a stable matching including a given set of forced and excluding a given set of forbidden pairs.
A Map of Diverse Synthetic Stable Roommates Instances [arxiv]
Niclas Boehmer, Klaus Heeger, Stanisław Szufa
[Conference] 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023); Won Best Student Paper Award
[Workshop] 6th International Workshop on Matching Under Preferences (MATCH-UP 2022)
TL;DR: We introduce a distance measure for Stable Roommates (SR) instances, analyze its properties, and use it to create a map of SR instances, which visualizes 460 synthetic SR instances sampled from ten different statistical cultures as points in two-dimensional space.
Collecting, Classifying, Analyzing, and Using Real-World Elections [arxiv] [collected elections]
Niclas Boehmer, Nathan Schaar
[Conference] 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023)
[Workshop] [Video] 4th Games, Agents, and Incentives Workshop (GAIW 2022)
[Poster] 2nd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO 2022)
TL;DR: We present a collection of 7582 real-world elections divided into 25 datasets. Among others, we analyze different structural properties of our elections including the level of agreement between voters and election’s distances from restricted domains.
Causes of Stability in Dynamic Coalition Formation [arxiv]
Niclas Boehmer, Martin Bullinger, Anna Maria Kerkmann
[Conference] Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2023)
[Workshop] 9th International Workshop on Computational Social Choice (COMSOC 2023)
TL;DR: We study the formation of stable outcomes via simple dynamics in cardinal hedonic games, where the utilities of agents change over time depending on the history of the coalition formation process.
Properties of Position Matrices and Their Elections [arxiv]
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Zheliang Fan, Łukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Wąs
[Conference] Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2023)
TL;DR: We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a given number of voters).
Rank Aggregation Using Scoring Rules [arxiv]
Niclas Boehmer, Robert Bredereck, Dominik Peters
[Conference] Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2023)
TL;DR: We experimentally and algorithmically study three types of scoring-based methods to aggregate rankings into a social ranking.
2022
Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [arxiv]
Niclas Boehmer, Robert Bredereck, Edith Elkind, Piotr Faliszewski, Stanisław Szufa
[Conference] Thirty-Sixth Conference on Neural Information Processing Systems (NeurIPS 2022)
TL;DR: We show how to compute frequency matrices of vote distributions, which simplifies a "map of elections" and can be used for preference learning.
A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners [arxiv]
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier
[Conference] [Video] 2nd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO 2022)
TL;DR: Contributing to the toolbox for interpreting election results, we evaluate the robustness of real-world election winners to random noise. We find many instances of elections that have very non-robust winners.
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences [arxiv]
Matthias Bentert, Niclas Boehmer, Klaus Heeger, Tomohiro Koana
[Conference] 15th International Symposium on Algorithmic Game Theory (SAGT 2022)
TL;DR: We study the complexity of finding a stable matching of a set of agents with multilayer approval preferences over each other for different multilayer adaptions of classical stability notions.
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems [arxiv]
Niclas Boehmer, Klaus Heeger, Rolf Niedermeier
[Conference] 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
TL;DR: We study the parameterized complexity of adapting a given stable matching to change considering, among others, the number of changes and the degree of similarity of the agents' preferences as parameters.
Understanding Distance Measures Among Elections [arxiv]
Niclas Boehmer, Piotr Faliszewski, Rolf Niedermeier, Stanisław Szufa, Tomasz Wąs
[Conference] 31st International Joint Conference on Artificial Intelligence (IJCAI 2022)
TL;DR: We analyze the theoretical/axiomatic and practical properties of six distance measures among elections.
The Complexity of Finding Fair Many-to-One Matchings [arxiv]
Niclas Boehmer, Tomohiro Koana
[Conference] 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022)
TL;DR: We analyze the (parameterized) complexity of "fair" bipartite many-to-one matching, where each vertex from the left side has a color and is matched to exactly one vertex and each vertex from the right side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices.
Multivariate Algorithmics for Eliminating Envy by Donating Goods [arxiv]
Niclas Boehmer, Robert Bredereck, Klaus Heeger, Dusan Knop, Junjie Luo
[Conference] [Video (Junjie)] 21th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
TL;DR: We study the parameterized complexity of deleting some items from a given allocation of indivisible items to make it envy-free.
Equilibria in Schelling Games: Computational Hardness and Robustness [arxiv]
Luca Kreisel, Niclas Boehmer, Vincent Froese, Rolf Niedermeier
[Conference] [Video (Luca)] 21th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
TL;DR: We prove that deciding the existence of an equilibrium in Schelling’s game of segregation on a graph is NP-hard. We introduce two measures for the robustness of equilibria in these games.
Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences [arxiv]
Niclas Boehmer, Markus Brill, Ulrike Schmidt-Kraepelin
[Conference] [Poster] 21th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
[Workshop] 8th International Workshop on Computational Social Choice (COMSOC 2021)
My co-author Markus ranked first in the poll on the best poster presentation at COMSOC.
TL;DR: We apply the proportionality ideal from multiwinner voting to find a set of k matchings of agents with approval preferences over each other fairly representing everyone's preferences.
A Refined Complexity Analysis of Fair Districting over Graphs [arxiv]
Niclas Boehmer, Tomohiro Koana, Rolf Niedermeier
[Conference (Extended Abstract)] [Poster] 21th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
[Journal] Autonomous Agents and Multi-Agent Systems (JAAMAS)
TL;DR: Motivated by the task to divide voters into "fair" voting districts, we analyze the (parameterized) complexity of partitioning a vertex-colored graph into connected components so that in each component the most frequent color occurs at most a given number of times more often than the second most frequent color.
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets [arxiv]
Niclas Boehmer, Klaus Heeger, Rolf Niedermeier
[Conference] [Poster] 36th AAAI Conference on Artificial Intelligence (AAAI 2022)
TL;DR: We contribute theoretical and empirical insights into minimally adapting a given stable two-sided matching to change.
Combating Collusion Rings is Hard but Possible [arxiv] [code]
Niclas Boehmer, Robert Bredereck, André Nichterlein
[Conference] [Poster] 36th AAAI Conference on Artificial Intelligence (AAAI 2022)
TL;DR: We observe that cycles often occur in review assignments and that finding a cycle-free review assignment is NP-hard, yet admits an efficient heuristic, which we show to be of excellent quality in practice.
2021
Two Influence Maximization Games on Graphs Made Temporal [arxiv]
Niclas Boehmer, Vincent Froese, Julia Henkel, Yvonne Lasars, Rolf Niedermeier, Malte Renken
[Conference] [Poster] 30st International Joint Conference on Artificial Intelligence (IJCAI 2021)
TL;DR: We generalize competitive diffusion games and Voronoi games from static to temporal graphs and investigate the existence of Nash equilibria on different graph classes.
Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments [arxiv]
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier
[Conference] [Poster] 30st International Joint Conference on Artificial Intelligence (IJCAI 2021)
[Workshop] 8th International Workshop on Computational Social Choice (COMSOC 2021)
TL;DR: We study the parameterized complexity of counting variants of Swap- and Shift-Bribery. We show experimentally that Swap-Bribery offers a new approach to estimating the robustness of election winners to random noise that is different from classical approaches such as the score difference between the winner and the runner-up.
Putting a Compass on the Map of Elections [arxiv]
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Stanisław Szufa
[Conference] [Poster] 30st International Joint Conference on Artificial Intelligence (IJCAI 2021)
[Workshop] 8th International Workshop on Computational Social Choice (COMSOC 2021)
My co-author Piotr ranked first in the poll on the best oral presentation at COMSOC.
TL;DR: We provide an interpretation of elections' position on the "map of elections" by introducing four canonical "extreme" elections, acting as a compass. We use this framework to analyze real-life elections and find a new variant of the Mallows model.
Broadening the Research Agenda for Computational Social Choice: Multiple Preference Profiles and Multiple Solutions
Niclas Boehmer, Rolf Niedermeier
[Conference] [Video] Blue Sky Ideas Track: 21th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021)
TL;DR: We argue that one possibility to incorporate the changing and ambivalent nature of reality into collective decision-making problems is to allow for multiple preference profiles and multiple solutions. We systematically review different types of arising settings and point out how classical problems and solution concepts can be generalized.
Finding Small Multi-Demand Set Covers with Ubiquitous Elements and Large Sets is Fixed-Parameter Tractable [arxiv]
Niclas Boehmer, Robert Bredereck, Dusan Knop, Junjie Luo
TL;DR: We show different variants of Set Cover to be fixed-parameter tractable with respect to the maximum number of elements missing in one set plus the number of sets in which an element does not occur.
2020
A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas [arxiv]
Niclas Boehmer, Klaus Heeger
[Journal] ACM Transactions on Economics and Computation (TEAC) invited to the Special Issue of WINE 2020
[Conference] [Video] 16th Conference on Web and Internet Economics (WINE 2020); Winner of the Best Paper and Best Student Paper Award
TL;DR: We study the (parameterized) complexity of finding a stable matching of residents to hospitals, where the number of residents matched to a hospital is between its given lower and upper quota or zero.
Fine-Grained View on Bribery for Group Identification [arxiv]
Niclas Boehmer, Robert Bredereck, Dušan Knop, Junjie Luo
[Conference] [Long Video] [Short Video] [Poster] 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)
TL;DR: We provide a comprehensive picture of the parameterized computational complexity landscape of different bribery variants for group identification.
Stable Roommate Problem with Diversity Preferences [arxiv]
Niclas Boehmer, Edith Elkind
[Conference] [Long Video] [Short Video] [Poster] 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)
[Conference (Extended Abstract)] 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020)
TL;DR: We study the complexity of finding good allocations in the multidimensional stable roommates problem where agents have diversity preferences: Each agent belongs to one type and only cares about the fraction of agents of its type in its room.
Bribery and Control in Stable Marriage [arxiv]
Niclas Boehmer, Robert Bredereck, Klaus Heeger, Rolf Niedermeier
[Journal] Journal of Artificial Intelligence Research (JAIR)
[Conference] 13th International Symposium on Algorithmic Game Theory (SAGT 2020)
TL;DR: We initiate the study and investigate the complexity of external manipulations in Stable Marriage by considering several manipulative actions and goals, such as deleting agents to make a given agent pair part of at least one stable matching.
Line-Up Elections: Parallel Voting with Shared Candidate Pool [arxiv]
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Rolf Niedermeier
[Conference] 13th International Symposium on Algorithmic Game Theory (SAGT 2020)
TL;DR: We introduce line-up elections which capture parallel single-winner elections with a shared candidate pool where each candidate can win at most one election. We propose several voting rules and analyze them from an axiomatic and an empirical perspective.
Individual-Based Stability in Hedonic Diversity Games [arxiv]
Niclas Boehmer, Edith Elkind
[Conference] [Poster] 34th AAAI Conference on Artificial Intelligence (AAAI 2020)
TL;DR: We study the complexity of finding Nash or individually stable outcomes in hedonic diversity games, where each agent belongs to one type and only cares about the fraction of agents of its type in its coalition.
Entropic quadrature for moment approximations of the Boltzmann-BGK equation
Niclas Boehmer, Manuel Torrilhon
[Journal] Journal of Computational Physics
TL;DR: We combine the maximum-entropy approach with the quadrature method of moments (QMOM) to introduce the "Entropic Quadrature" (EQ) closure for moment transport equations of kinetic equations.