Researcher profile

Niclas Boehmer

Niclas Boehmer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
15works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2026arXiv

The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions

AI alignment and participatory design motivate a new democratic design problem: how to collectively choose a decision rule to use repeatedly. We study this problem for linear ranking rules, which repeatedly rank items $x_j$ within batches $X=(x_1,\dots,x_m)\in(\mathbb{R}^d)^m$, where each item's ranking is dictated by its score $\langle θ^*,x_j\rangle$ according to a fixed scoring vector $θ^*$. Given voters' preferred scoring vectors $θ^{(1)},\dots,θ^{(n)}$ and their population fractions $α^{(1)},\dots,α^{(n)}$, we ask how to choose a collective vector $θ^*$ satisfying individual proportionality (IP): every voter type $i$ should agree with the resulting rankings to an $α^{(i)}$-proportional degree, either on average over time (long-run IP) or even within each batch (per-batch IP). The default rule, the arithmetic mean of the $θ^{(i)}$, has been shown to be severely majoritarian; more generally, it is not clear that any fixed linear rule can balance many voters' disparate opinions. Our main result is that, surprisingly, there is a simple rule that does satisfy long-run IP: the angular mean, the spherical analog of the arithmetic mean. We then show that exact per-batch IP is impossible for fixed linear rules, but that the gap between per-batch and long-run IP shrinks quickly with batch size. Experiments on three real-world preference datasets show that all rules perform similarly when voters' preferences are homogeneous, while the angular mean substantially improves proportionality in high-disagreement regimes.

preprint2023arXiv

Collecting, Classifying, Analyzing, and Using Real-World Elections

We present a collection of $7582$ real-world elections divided into $25$ datasets from various sources ranging from sports competitions over music charts to survey- and indicator-based rankings. We provide evidence that the collected elections complement already publicly available data from the PrefLib database, which is currently the biggest and most prominent source containing $701$ real-world elections from $36$ datasets. Using the map of elections framework, we divide the datasets into three categories and conduct an analysis of the nature of our elections. To evaluate the practical applicability of previous theoretical research on (parameterized) algorithms and to gain further insights into the collected elections, we analyze different structural properties of our elections including the level of agreement between voters and election's distances from restricted domains such as single-peakedness. Lastly, we use our diverse set of collected elections to shed some further light on several traditional questions from social choice, for instance, on the number of occurrences of the Condorcet paradox and on the consensus among different voting rules.

preprint2023arXiv

Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning

We use the ``map of elections'' approach of Szufa et al. (AAMAS-2020) to analyze several well-known vote distributions. For each of them, we give an explicit formula or an efficient algorithm for computing its frequency matrix, which captures the probability that a given candidate appears in a given position in a sampled vote. We use these matrices to draw the ``skeleton map'' of distributions, evaluate its robustness, and analyze its properties. Finally, we develop a general and unified framework for learning the distribution of real-world preferences using the frequency matrices of established vote distributions.

preprint2022arXiv

A Map of Diverse Synthetic Stable Roommates Instances

Focusing on Stable Roommates (SR) instances, we contribute to the toolbox for conducting experiments for stable matching problems. We introduce a polynomial-time computable pseudometric to measure the similarity of SR instances, analyze its properties, and use it to create a map of SR instances. This map visualizes 460 synthetic SR instances (each sampled from one of ten different statistical cultures) as follows: Each instance is a point in the plane, and two points are close on the map if the corresponding SR instances are similar to each other. Subsequently, we conduct several exemplary experiments and depict their results on the map, illustrating the map's usefulness as a non-aggregate visualization tool, the diversity of our generated dataset, and the need to use instances sampled from different statistical cultures. Lastly, to demonstrate that our framework can also be used for other matching problems under preference, we create and analyze a map of Stable Marriage instances.

preprint2022arXiv

A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners

Contributing to the toolbox for interpreting election results, we evaluate the robustness of election winners to random noise. We compare the robustness of different voting rules and evaluate the robustness of real-world election winners from the Formula 1 World Championship and some variant of political elections. We find many instances of elections that have very non-robust winners and numerous delicate robustness patterns that cannot be identified using classical and simpler approaches.

preprint2022arXiv

A Refined Complexity Analysis of Fair Districting over Graphs

We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for "fair districts" without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters, including treewidth, and problem-specific parameters, including, the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hard, and para-NP-hard).

preprint2022arXiv

Equilibria in Schelling Games: Computational Hardness and Robustness

In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

preprint2022arXiv

Multivariate Algorithmics for Eliminating Envy by Donating Goods

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

preprint2022arXiv

Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences

We study stable matching problems where agents have multilayer preferences: There are $\ell$ layers each consisting of one preference relation for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, establishing four multilayer adaptions of classical notions of stability. We follow up on their work by analyzing the computational complexity of stable matching problems with multilayer approval preferences. We consider eleven stability notions derived from three well-established stability notions for stable matchings with ties and the four adaptions proposed by Chen et al. For each stability notion, we show that the problem of finding a stable matching is either polynomial-time solvable or NP-hard. Furthermore, we examine the influence of the number of layers and the desired "degree of stability" on the problems' complexity. Somewhat surprisingly, we discover that assuming approval preferences instead of strict preferences does not considerably simplify the situation (and sometimes even makes polynomial-time solvable problems NP-hard).

preprint2022arXiv

The Complexity of Finding Fair Many-to-One Matchings

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side 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. Assuming that each vertex from the left side has one color modeling its attribute, we study two fairness criteria. In one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. To establish the correctness of our integer programs, we prove a new separation result, inspired by Frank's separation theorem [Frank, Discrete Math. 1982], which may also be of independent interest. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

preprint2022arXiv

Who won? Winner Determination and Robustness in Liquid Democracy

Liquid democracy is a decision-making paradigm in which each agent can either vote directly for some alternative or (transitively) delegate its vote to another agent. To mitigate the issue of delegation cycles or the concentration of power, delegating agents might be allowed to specify multiple delegation options. Then, a (cycle-free) delegation is selected in which each delegating agent has exactly one representative. We study the winner determination problem for this setting, i.e., whether we can select a delegation such that a given alternative wins (or does not win). Moreover, we study the robustness of winning alternatives in two ways: First, we consider whether we can make a limited number of changes to the preferences cast by the agents such that a given alternative becomes a winner in one/in all delegations, and second, whether we can make a limited number of changes to a selected delegation to make a given alternative a winner.

preprint2021arXiv

A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas

In the Hospital Residents problem with lower and upper quotas ($HR-Q^U_L$), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero [Biró et al., TCS 2010]. We analyze this problem from a parameterized perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, we present a polynomial-time algorithm that finds a stable matching if it exists on instances with maximum lower quota two. Alongside $HR-Q^U_L$, we also consider two closely related models of independent interest, namely, the special case of $HR-Q^U_L$ where each hospital has only a lower quota but no upper quota and the variation of $HR-Q^U_L$ where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas. Lastly, we investigate how the parameterized complexity of these three models changes if preferences may contain ties.

preprint2021arXiv

Selecting Matchings via Multiwinner Voting: How Structure Defeats a Large Candidate Space

Given a set of agents with approval preferences over each other, we study the task of finding $k$ matchings fairly representing everyone's preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of all possible matchings and agents' preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that proportional approval voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our positive computational results extend to other types of compactly representable elections with an exponential candidate space.

preprint2020arXiv

Line-Up Elections: Parallel Voting with Shared Candidate Pool

We introduce the model of line-up elections which captures parallel or sequential single-winner elections with a shared candidate pool. The goal of a line-up election is to find a high-quality assignment of a set of candidates to a set of positions such that each position is filled by exactly one candidate and each candidate fills at most one position. A score for each candidate-position pair is given as part of the input, which expresses the qualification of the candidate to fill the position. We propose several voting rules for line-up elections and analyze them from an axiomatic and an empirical perspective using real-world data from the popular video game FIFA.

preprint2020arXiv

Stable Roommate Problem with Diversity Preferences

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents' preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.