I am a fourth-year PhD student at TU Berlin supervised by Prof. Rolf Niedermeier and Prof. Markus Brill. I work on collective decision-making problems such as voting and stable matching with a focus on (parameterized) computational complexity theory and experimental works. Two recurring themes in my research are incorporating the dynamic nature of reality into collective decision-making problems and enriching the toolbox to conduct meaningful experiments.

Prior to my PhD, I obtained a master's degree in Computer Science at the University of Oxford and a bachelor's degree in Computer Science at the RWTH Aachen University.

niclas.boehmer [at] tu-berlin.de | dblp | Google Scholar | CV | research summary (10/2022)

Publications

Working Papers

Adapting Stable Matchings to Forced and Forbidden Pairs [arxiv]
Niclas Boehmer, Klaus Heeger
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.


Who won? Winner Determination and Robustness in Liquid Democracy [arxiv]
Matthias Bentert, Niclas Boehmer, Maciej Rymar, Henri Tannenberg
TL;DR: We study the complexity of the winner determination problem for liquid democracy where delegating agents specify multiple delegation options and study the robustness of winning alternatives.

2023

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)
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
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.


A Map of Diverse Synthetic Stable Roommates Instances [arxiv]
Niclas Boehmer,
Klaus Heeger, Stanisław Szufa
[
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.


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.


Collecting, Classifying, Analyzing, and Using Real-World Elections [arxiv] [collected elections]
Niclas Boehmer, Nathan Schaar
[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.


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)
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.

Community Service

Referring Journals

Algorithmica, Information Processing Letters (IPL), Journal of Artificial Intelligence Research (JAIR), Journal of Computer and System Sciences (JCSS), ACM Transactions on Economics and Computation (TEAC)

Referring Conferences and Workshops

AAAI 2023 (PC member), AAMAS 2023, AAMAS 2022, ICALP 2022, IJCAI 2022 (PC member), IWOCA 2022, MATCH-UP 2022, MFCS 2022, AAAI 2021 (PC member), CSR 2021, AAMAS 2020, ECAI 2020, ESA 2020, MOTOR 2020, SAGT 2020

Teaching

During my PhD, I contributed to the following courses:

  • Advanced Algorithmics (WS 20/21, WS 21/22)

  • Algorithm Engineering (WS 21/22)

  • Economics and Computation (SS 20)

  • Research in Teams (WS 21/22)

  • Seminar on Current Research in Algorithms and Complexity (WS 19/20, WS 20/21, SS 21, WS 21/22, SS 22)

Moreover, I (co)-supervised the following bachelor and master theses:

  • Competitive Diffusion Games on Graphs Made Temporal (bachelor thesis)

  • Algorithm Engineering for Dodgson Voting (bachelor thesis)

  • On Equilibria in Schelling Games: Robustness and Multimodality (bachelor thesis)

  • Towards Faster Algorithms for Stable Matching Problems under Structured Preferences (master thesis)

  • Algorithmic Aspects of Electing Multiple Committees with Restricted Candidate Availability (bachelor thesis)

  • Fair Allocation of Indivisible Resources to Agents with Multimodal Preferences (bachelor thesis)

  • Structure and Complexity of Occupation Games on Graphs (master thesis)

  • Fair Division of Indivisible Goods under Multimodal Preferences: Algorithms and Computational Complexity (master thesis)

Awards and Scholarships

  • Best Paper and Best Student Paper Award at the 16th Conference on Web and Internet Economics awarded for the paper "A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas" (authored together with Klaus Heeger)

  • Hoare Prize for the best overall performance in the MSc in Computer Science at the University of Oxford

  • Hoare Prize for the best dissertation in the MSc in Computer Science at the University of Oxford

  • Bachelor Award by the Department of Computer Science of the RWTH Aachen University awarded for an outstanding bachelor thesis and an exceptional overall performance in the BSc Computer Science (once per year)

  • Scholarship of the German Academic Scholarship Foundation between 2015 and 2019