Arrow Research search

Author name cluster

Robert Bredereck

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

57 papers
2 author rows

Possible papers

57

AAAI Conference 2026 Conference Paper

Putting Fair Division on the Map

  • Paula Böhm
  • Robert Bredereck
  • Paul Gölz
  • Andrzej Kaczmarczyk
  • Stanisław Szufa

The fair division of indivisible goods is not only a subject of theoretical research, but also an important problem in practice, with solutions being offered on several online platforms. Little is known, however, about the characteristics of real-world allocation instances and how they compare to synthetic instances. Using dimensionality reduction, we compute a map of allocation instances: a 2-dimensional embedding such that an instance's location on the map is predictive of the instance's origin and other key instance features. Because the axes of this map closely align with the utility matrix's two largest singular values, we define a second, explicit map, which we theoretically characterize.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Computing Efficient Envy-Free Partial Allocations of Indivisible Goods

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Junjie Luo
  • Bin Sun

Envy-freeness is one of the most prominent fairness concepts in the allocation of indivisible goods. Even though trivial envy-free allocations always exist, rich literature shows this is not true when one additionally requires some efficiency concept (e. g. , completeness, Pareto-efficiency, or social welfare maximization). In fact, in such case even deciding the existence of an efficient envy-free allocation is notoriously computationally hard. In this paper, we explore the limits of efficient computability by relaxing standard efficiency concepts and analyzing how this impacts the computational complexity of the respective problems. Specifically, we allow partial allocations (where not all goods are allocated) and impose only very mild efficiency constraints, such as ensuring each agent receives a bundle with positive utility. Surprisingly, even such seemingly weak efficiency requirements lead to a diverse computational complexity landscape. We identify several polynomial-time solvable or fixed-parameter tractable cases for binary utilities, yet we also find NP-hardness in very restricted scenarios involving ternary utilities.

PDF

AIJ Journal 2025 Journal Article

Drawing a map of elections

  • Stanisław Szufa
  • Niclas Boehmer
  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier
  • Piotr Skowron
  • Arkadii Slinko
  • Nimrod Talmon

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i. e. , collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e. g. , the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

Details DOI

IJCAI Conference 2025 Conference Paper

How to Resolve Envy by Adding Goods

  • Matthias Bentert
  • Robert Bredereck
  • Eva Deltl
  • Pallavi Jain
  • Leon Kellerhals

We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomial-time algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists—an aspect that is both theoretically interesting and far from trivial.

PDF Details DOI

ECAI Conference 2025 Conference Paper

Properties of Egalitarian Sequences of Committees: Theory and Experiments

  • Paula Böhm
  • Robert Bredereck
  • Till Fluschnik

We study the task of electing egalitarian sequences of τ committees given a set of agents with additive utilities for candidates available on each of τ levels. We introduce several rules for electing an egalitarian committee sequence as well as properties for such rules. We settle the computational complexity of finding a winning sequence for our rules and classify them against our properties. Additionally, we transform sequential election data from existing election data from the literature. Using this data set, we compare our rules empirically and test them experimentally against our properties.

Details

JAAMAS Journal 2024 Journal Article

Multivariate algorithmics for eliminating envy by donating goods

  • Niclas Boehmer
  • Robert Bredereck
  • Junjie Luo

Abstract 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-encoded 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.

Details DOI

IJCAI Conference 2023 Conference Paper

Algorithmics of Egalitarian versus Equitable Sequences of Committees

  • Eva Michelle Deltl
  • Till Fluschnik
  • Robert Bredereck

We study the election of sequences of committees, where in each of tau levels (e. g. modeling points in time) a committee consisting of k candidates from a common set of m candidates is selected. For each level, each of n agents (voters) may nominate one candidate whose selection would satisfy her. We are interested in committees which are good with respect to the satisfaction per day and per agent. More precisely, we look for egalitarian or equitable committee sequences. While both guarantee that at least x agents per day are satisfied, egalitarian committee sequences ensure that each agent is satisfied in at least y levels while equitable committee sequences ensure that each agent is satisfied in exactly y levels. We analyze the parameterized complexity of finding such committees for the parameters n, m, k, tau, x, and y, as well as combinations thereof.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Bribery Can Get Harder in Structured Multiwinner Approval Election

  • Bartosz Kusek
  • Robert Bredereck
  • Piotr Faliszewski
  • Andrzej Kaczmarczyk
  • Dušan Knop

We study the complexity of constructive bribery in the context of structured multiwinner approval elections. Given such an election, we ask whether a certain candidate can join the winning committee by adding, deleting, or swapping approvals, where each such action comes at a cost and we are limited by a budget. We assume our elections to either have the candidate interval or the voter interval property, and we require the property to hold also after the bribery. While structured elections usually make manipulative attacks significantly easier, our work also shows examples of the opposite behavior. We conclude by presenting preliminary insights regarding the destructive variant of our problem.

PDF

ECAI Conference 2023 Conference Paper

Efficiently Computing Smallest Agreeable Sets

  • Robert Bredereck
  • Till Fluschnik
  • Nimrod Talmon

We study the computational complexity of identifying a small agreeable subset of items. A subset of items is agreeable if every agent does not prefer its complement set. We study settings in which agents either can assign arbitrary utilities to the items; can approve or disapprove the items; or can rank the items (in which case we consider Borda utilities). We prove that deciding whether an agreeable set exists is NP-hard for all variants; and we perform a parameterized analysis regarding the following natural parameters: the number of agents, the number of items, and the upper bound on the size of the agreeable set in question.

Details

JAAMAS Journal 2023 Journal Article

Fine-grained view on bribery for group identification

  • Niclas Boehmer
  • Robert Bredereck
  • Junjie Luo

Abstract Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of agents. Social qualification depends on the specific rule used to aggregate individual qualifications. The classical bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome in a certain way. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific agents socially qualified) or destructive (aiming at making specific agents socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, nonunit prices for different bribery actions, and a more general bribery goal that combines the constructive and destructive setting.

Details DOI

ECAI Conference 2023 Conference Paper

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

  • Robert Bredereck
  • Andrzej Kaczmarczyk 0001
  • Dusan Knop
  • Rolf Niedermeier

Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter “number of agents” plus “number of item types. ” Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.

Details

JAIR Journal 2023 Journal Article

Improving Resource Allocations by Sharing in Pairs

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Junjie Luo
  • Rolf Niedermeier
  • Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to a higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. More precisely, our model allows agents to form pairs which then may share a limited number of resources. Sharing a resource can come at some costs or loss in utility. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Rank Aggregation Using Scoring Rules

  • Niclas Boehmer
  • Robert Bredereck
  • Dominik Peters

To aggregate rankings into a social ranking, one can use scoring systems such as Plurality, Veto, and Borda. We distinguish three types of methods: ranking by score, ranking by repeatedly choosing a winner that we delete and rank at the top, and ranking by repeatedly choosing a loser that we delete and rank at the bottom. The latter method captures the frequently studied voting rules Single Transferable Vote (aka Instant Runoff Voting), Coombs, and Baldwin. In an experimental analysis, we show that the three types of methods produce different rankings in practice. We also provide evidence that sequentially selecting winners is most suitable to detect the "true" ranking of candidates. For different rules in our classes, we then study the (parameterized) computational complexity of deciding in which positions a given candidate can appear in the chosen ranking. As part of our analysis, we also consider the Winner Determination problem for STV, Coombs, and Baldwin and determine their complexity when there are few voters or candidates.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Combating Collusion Rings Is Hard but Possible

  • Niclas Boehmer
  • Robert Bredereck
  • André Nichterlein

A recent report of Littmann published in the Communications of the ACM outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem CYCLE-FREE REVIEWING that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit. We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that CYCLE-FREE REVIEWING is NP-hard in various restricted cases (i. e. , when every author is qualified to review all papers and one wants to prevent that authors review each other’s or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.

PDF Details

AIJ Journal 2022 Journal Article

Envy-free allocations respecting social networks

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist and determining whether they exist is computationally hard even under highly restricted settings. Classical envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since the agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a “more local” concept of envy-freeness. We also consider a “strong” variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classical and the parameterized complexity of finding allocations that are complete and, at the same time, envy-free with respect to one of the variants of our new concept. To this end, we study different restrictions of the agents' preferences and of the social network structure. We identify cases that become easier (from Σ 2 P -hard or NP-hard to polynomial-time solvable) and cases that become harder (from polynomial-time solvable to NP-hard) when comparing classical envy-freeness with our graph envy-freeness. Furthermore, we spot cases where graph envy-freeness is easier to decide than strong graph envy-freeness, and vice versa. On the route to one of our fixed-parameter tractability results, we also establish a connection to a directed and colored variant of the classical Subgraph Isomorphism problem, thereby extending a known fixed-parameter tractability result for the latter.

Details DOI

NeurIPS Conference 2022 Conference Paper

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

  • Niclas Boehmer
  • Robert Bredereck
  • Edith Elkind
  • Piotr Faliszewski
  • Stanisław Szufa

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. We further develop a general and unified framework for learning the distribution of real-world preferences using the frequency matrices of established vote distributions.

PDF Details

AAMAS Conference 2022 Conference Paper

Multivariate Algorithmics for Eliminating Envy by Donating Goods

  • Niclas Boehmer
  • Robert Bredereck
  • Klaus Heeger
  • Dušan Knop
  • Junjie Luo

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.

PDF

AAAI Conference 2022 Conference Paper

On Improving Resource Allocations by Sharing

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Junjie Luo
  • Rolf Niedermeier
  • Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and treelike (hierarchical) social networks.

PDF Details

IJCAI Conference 2022 Conference Paper

Single-Peaked Opinion Updates

  • Robert Bredereck
  • Anne-Marie George
  • Jonas Israel
  • Leon Kellerhals

We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study of preserving single-peakedness. We identify voting rules that, when given a single-peaked profile, output at least one ranking that is single peaked w. r. t. a single-peaked axis of the input. For such voting rules we show convergence to a stable state of the diffusion process that uses the voting rule as the agents' update rule. Further, we establish an efficient algorithm that maximises the spread of extreme opinions.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

When Votes Change and Committees Should (Not)

  • Robert Bredereck
  • Till Fluschnik
  • Andrzej Kaczmarczyk

Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce two time-dependent multistage models based on simple scoring-based voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be "easier" than being conservative.

PDF Details DOI

AAAI Conference 2021 Conference Paper

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem

  • Matthias Bentert
  • Robert Bredereck
  • Péter Györgyi
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

The NP-hard MATERIAL CONSUMPTION SCHEDULING PROBLEM and related problems have been thoroughly studied since the 1980’s. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewable resources. We focus on the singlemachine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized computational complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational complexity. Thereby, we get a deepened understanding of this fundamental scheduling problem.

PDF Details

JAIR Journal 2021 Journal Article

Bribery and Control in Stable Marriage

  • Niclas Boehmer
  • Robert Bredereck
  • Klaus Heeger
  • Rolf Niedermeier

We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

High-Multiplicity Fair Allocation Made More Practical

  • Robert Bredereck
  • Aleksander Figiel
  • Andrzej Kaczmarczyk
  • Dušan Knop
  • Rolf Niedermeier

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC 2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for “high-multiplicity fair allocation”, exploiting parameters such as number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We “engineer” their work towards practical usefulness, thereby being able to solve all realworld instances from the state-of-art online platform “spliddit. org for provably fair solutions”. Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e. g. , allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain “solution paths” which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

PDF

JAAMAS Journal 2021 Journal Article

On coalitional manipulation for multiwinner elections: shortlisting

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

Abstract Shortlisting of candidates—selecting a group of “best” candidates—is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, \(\ell \) -Bloc (every voter approves \(\ell \) candidates). In particular, we investigate the influence of several different group evaluation functions (e. g. , egalitarian versus utilitarian) and tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other things, we conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computational complexity landscape of this scenario.

Details DOI

IJCAI Conference 2021 Conference Paper

Putting a Compass on the Map of Elections

  • Niclas Boehmer
  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier
  • Stanisław Szufa

In their AAMAS 2020 paper, Szufa et al. presented a "map of elections" that visualizes a set of 800 elections generated from various statistical cultures. While similar elections are grouped together on this map, there is no obvious interpretation of the elections' positions. We provide such an interpretation by introducing four canonical “extreme” elections, acting as a compass on the map. We use them to analyze both a dataset provided by Szufa et al. and a number of real-life elections. In effect, we find a new parameterization of the Mallows model, based on measuring the expected swap distance from the central preference order, and show that it is useful for capturing real-life scenarios.

PDF Details DOI

AIJ Journal 2021 Journal Article

Robustness among multiwinner voting rules

  • Robert Bredereck
  • Piotr Faliszewski
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier
  • Piotr Skowron
  • Nimrod Talmon

We investigate how robust the results of committee elections are with respect to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member might be replaced, or (2) it is possible that the whole committee will be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically NP-hard, but there are natural FPT algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

Details DOI

IJCAI Conference 2021 Conference Paper

Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

  • Niclas Boehmer
  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier

We study the parameterized complexity of counting variants of Swap- and Shift-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that Swap-Bribery offers a new approach to the robustness analysis of elections.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Adapting Stable Matchings to Evolving Preferences

  • Robert Bredereck
  • Jiehua Chen
  • Dušan Knop
  • Junjie Luo
  • Rolf Niedermeier

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of STABLE MARRIAGE and STABLE ROOMMATES. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of INCREMENTAL STA- BLE MARRIAGE and INCREMENTAL STABLE ROOMMATES. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference pro- file) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

PDF Details

AAAI Conference 2020 Conference Paper

Electing Successive Committees: Complexity and Algorithms

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

We introduce successive committees elections. The point is that our new model additionally takes into account that “committee members” shall have a short term of office possibly over a consecutive time period (e. g. , to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e. g. , for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a “best possible” series of committees representing the electorate. We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases.

PDF Details

IJCAI Conference 2020 Conference Paper

Fine-Grained View on Bribery for Group Identification

  • Niclas Boehmer
  • Robert Bredereck
  • Dušan Knop
  • Junjie Luo

Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks

  • Robert Bredereck
  • Lilian Jacobs
  • Leon Kellerhals

We consider the setting of asynchronous opinion diffusion with majority threshold: given a social network with each agent assigned to one opinion, an agent will update its opinion if more than half of its neighbors agree on a different opinion. The stabilized final outcome highly depends on the sequence in which agents update their opinion. We are interested in optimistic sequences---sequences that maximize the spread of a chosen opinion. We complement known results for two opinions where optimistic sequences can be computed in time and length linear in the number of agents. We analyze upper and lower bounds on the length of optimistic sequences, showing quadratic bounds in the general and linear bounds in the acyclic case. Moreover, we show that in networks with more than two opinions determining a spread-maximizing sequence becomes intractable; surprisingly, already with three opinions the intractability results hold in highly restricted cases, e. g. , when each agent has at most three neighbors, when looking for a short sequence, or when we aim for approximate solutions.

PDF Details DOI

TCS Journal 2020 Journal Article

Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting

  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier
  • Piotr Skowron
  • Nimrod Talmon

A classic result of Lenstra [Math. Oper. Res. 1983] says that an integer linear program can be solved in fixed-parameter tractable ( FPT ) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic NP -hard computational problems. In particular, we prove that Weighted Set Multicover is in FPT when parameterized by the number of elements to cover, and that there exists an FPT -time approximation scheme for Multiset Multicover for the same parameter—this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e. g. , problems related to bribery and control in elections) are in FPT when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known XP -memberships to FPT -memberships.

Details DOI

AAAI Conference 2020 Conference Paper

Parameterized Algorithms for Finding a Collective Set of Items

  • Robert Bredereck
  • Piotr Faliszewski
  • Andrzej Kaczmarczyk
  • Dušan Knop
  • Rolf Niedermeier

We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

PDF Details

JAAMAS Journal 2020 Journal Article

Stable roommates with narcissistic, single-peaked, and single-crossing preferences

  • Robert Bredereck
  • Jiehua Chen
  • Rolf Niedermeier

Abstract The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigate Stable Roommates with complete (i. e. , every agent can be matched with any other agent) or incomplete preferences, with ties (i. e. , two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms for Stable Roommates that are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity— Stable Roommates remains NP-complete.

Details DOI

IJCAI Conference 2020 Conference Paper

Strategic Campaign Management in Apportionment Elections

  • Robert Bredereck
  • Piotr Faliszewski
  • Michal Furdyna
  • Andrzej Kaczmarczyk
  • Martin Lackner

In parliamentary elections, parties compete for a limited, typically fixed number of seats. We study the complexity of the following bribery-style problem: Given the distribution of votes among the parties, what is the smallest number of voters that need to be convinced to vote for our party, so that it gets a desired number of seats. We also run extensive experiments on real-world election data and measure the effectiveness of our method.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

An Experimental View on Committees Providing Justified Representation

  • Robert Bredereck
  • Piotr Faliszewski
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

We provide an experimental study of committees that achieve (proportional/extended) justified representation (JR/PJR/EJR). In particular, we ask how many such committees exist and how varied they are in terms of voter satisfaction and coverage. We find that under many natural distributions of preferences a large fraction of randomly selected JR committees also provide PJR and EJR. Further, we find that the sets of JR committees for our elections are very varied and include both high-quality ones and not-so-appealing ones.

PDF Details

AAMAS Conference 2019 Conference Paper

Complexity of Manipulation in Premise-Based Judgment Aggregation with Simple Formulas

  • Robert Bredereck
  • Junjie Luo

Judgment aggregation is a framework to aggregate individual opinions on multiple, logically connected issues into a collective outcome. It is open to manipulative attacks such as Manipulation where judges cast their judgments strategically. Previous works have shown that most computational problems corresponding to these manipulative attacks are NP-hard. This desired computational barrier, however, often relies on formulas that are either of unbounded size or of complex structure. We revisit the computational complexity for a large class of Manipulation problems in judgment aggregation, now focusing on simple and realistic formulas. We restrict all formulas to be clauses that are (positive) monotone, Horn-clauses, or have bounded length. For basic variants of Manipulation, we show that these restrictions make several variants, which were in general known to be NP-hard, polynomial-time solvable. Moreover, we provide a P vs. NP dichotomy for a large class of clause restrictions (generalizing monotone and Horn clauses) by showing a close relationship between variants of Manipulation and variants of Satisfiability. For Hamming distance based Manipulation, we show that NPhardness even holds for positive monotone clauses of length three, but the problem becomes polynomial-time solvable for positive monotone clauses of length two.

PDF

AAMAS Conference 2019 Conference Paper

Hedonic Diversity Games

  • Robert Bredereck
  • Edith Elkind
  • Ayumi Igarashi

We consider a coalition formation setting where each agent belongs to one of the two types, and agents’ preferences over coalitions are determined by the fraction of the agents of their own type in each coalition. This setting differs from the well-studied Schelling’s model in that some agents may prefer homogeneous coalitions, while others may prefer to be members of a diverse group, or a group that mostly consists of agents of the other type. We model this setting as a hedonic game and investigate the existence of stable outcomes using hedonic games solution concepts. We show that a core stable outcome may fail to exist and checking the existence of core stable outcomes is computationally hard. On the other hand, we propose an efficient algorithm to find an individually stable outcome under the natural assumption that agents’ preferences over fractions of the agents of their own type are single-peaked.

PDF

AAMAS Conference 2018 Conference Paper

Envy-Free Allocations Respecting Social Networks

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and finding them can be a computationally hard task. Classic envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a “more local” concept of envyfreeness. We also consider a strong variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classic and the parameterized complexity of finding allocations that are envy-free with respect to one of the variants of our new concept, and that either are complete, are Paretoefficient, or optimize the utilitarian social welfare. To this end, we study different restrictions of the agents’ preferences and of the social network structure. We identify cases that become easier (from ΣP 2-hard or NP-hard to P) and cases that become harder (from P to NP-hard) when comparing classic envy-freeness with our graphbased envy-freeness. Furthermore, we spot cases where graph envyfreeness is easier to decide than strong graph envy-freeness, and vice versa.

PDF

AAAI Conference 2018 Conference Paper

Multiwinner Elections With Diversity Constraints

  • Robert Bredereck
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Martin Lackner
  • Piotr Skowron

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e. g. , Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e. g. , of the form “at least 30% of the committee members are junior candidates and at least 40% are females”). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NPhardness results. We focus on several natural classes of voting rules and diversity constraints.

PDF Details

TCS Journal 2018 Journal Article

Parameterized complexity of team formation in social networks

  • Robert Bredereck
  • Jiehua Chen
  • Falk Hüffner
  • Stefan Kratsch

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree Δ. We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining Δ with either b or l yields fixed-parameter tractability.

Details DOI

IJCAI Conference 2017 Conference Paper

Manipulating Opinion Diffusion in Social Networks

  • Robert Bredereck
  • Edith Elkind

We consider opinion diffusion in binary influence networks, where at each step one or more agents update their opinions so as to be in agreement with the majority of their neighbors. We consider several ways of manipulating the majority opinion in a stable outcome, such as bribing agents, adding/deleting links, and changing the order of updates, and investigate the computational complexity of the associated problems, identifying tractable and intractable cases.

PDF Details

IJCAI Conference 2017 Conference Paper

On Coalitional Manipulation for Multiwinner Elections: Shortlisting

  • Robert Bredereck
  • Andrzej Kaczmarczyk
  • Rolf Niedermeier

Shortlisting of candidates—selecting a group of “best” candidates—is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the most natural and simple voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e. g. pessimistic versus optimistic) and group evaluation functions (e. g. egalitarian versus utilitarian) and conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. We provide a fairly comprehensive picture of the computational complexity landscape of this neglected scenario.

PDF Details

AAMAS Conference 2017 Conference Paper

On Parameterized Complexity of Group Activity Selection Problems on Social Networks

  • Ayumi Igarashi
  • Robert Bredereck
  • Edith Elkind

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the form (activity, group size); moreover, a group of players can only engage in the same activity if the members of the group form a connected subset of the underlying communication structure. We study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter ‘number of activities’, we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i. e. , for classic GASP); similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star. For the parameter ‘number of players’, all problems we consider are in XP for arbitrary social networks; on the other hand, we prove W[1]-hardness results with respect to the parameter ‘number of players’ for the case where the social network is a clique (i. e. , for classic GASP).

PDF

JAIR Journal 2017 Journal Article

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

  • Robert Bredereck
  • Jiehua Chen
  • Rolf Niedermeier
  • Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. They work in multiple stages where the result of each stage may influence the result of the next stage. Both procedures proceed according to a given linear order of the alternatives, an agenda. We obtain the following results for both voting procedures: On the one hand, deciding whether one can make a specific alternative win by reporting insincere preferences by the fewest number of voters, the Manipulation problem, or whether there is a suitable ordering of the agenda, the Agenda Control problem, takes polynomial time. On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters' preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure.

PDF Details DOI

AAAI Conference 2017 Conference Paper

Teams in Online Scheduling Polls: Game-Theoretic Aspects

  • Robert Bredereck
  • Jiehua Chen
  • Rolf Niedermeier
  • Svetlana Obraztsova
  • Nimrod Talmon

Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team would like to maximize its relative attendance (i. e. the proportional number of its team members attending the meeting). We introduce a corresponding game, where each team can declare a lower total availability in the scheduling poll in order to improve its relative attendance—the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.

PDF Details

IJCAI Conference 2016 Conference Paper

Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

  • Bernhard Bliem
  • Robert Bredereck
  • Rolf Niedermeier

We study the problem of finding a Pareto-efficient and envy-free allocation of a set of indivisible resources to a set of agents with monotonic preferences, either dichotomous or additive. Motivated by results of Bouveret and Lang [JAIR 2008], we provide a refined computational complexity analysis by studying the influence of three natural parameters: the number n of agents, the number m of resources, and the number z of different numbers occurring in utility-based preferences of the agents. On the negative side, we show that small values for n and z alone do not significantly lower the computational complexity in most cases. On the positive side, devising fixed-parameter algorithms we show that all considered problems are tractable in case of small m. Furthermore, we develop a fixed-parameter algorithm indicating that the problem with additive preferences becomes computationally tractable in case of small n and small z.

PDF Details

AAAI Conference 2016 Conference Paper

Complexity of Shift Bribery in Committee Elections

  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier
  • Nimrod Talmon

We study the (parameterized) complexity of SHIFT BRIBERY for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin–Courant rules, as well as on approximate variants of the Chamberlin–Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin–Courant rule sometimes affects the complexity of SHIFT BRIBERY.

PDF Details

TCS Journal 2016 Journal Article

Finding large degree-anonymous subgraphs is hard

  • Cristina Bazgan
  • Robert Bredereck
  • Sepp Hartung
  • André Nichterlein
  • Gerhard J. Woeginger

A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k − 1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym V-Del and Anonym E-Del. We present a variety of hardness results, most of them hold for both problems. The two variants are intractable from the parameterized as well as from the approximation point of view. In particular, we show that both variants remain NP-hard on very restricted graph classes like trees even if k = 2. We further prove that both variants are W[1]-hard with respect to the combined parameter solutions size s and anonymity level k. With respect to approximability, we obtain hardness results showing that neither variant can be approximated in polynomial time within a factor better than n 1 2 (unless P = NP ). Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k, this inapproximability result even holds if we allow a running time of f ( s ) ⋅ n O ( 1 ) for any computable function f. On the positive side, we classify both problem variants as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree Δ.

Details DOI

JAIR Journal 2016 Journal Article

Large-Scale Election Campaigns: Combinatorial Shift Bribery

  • Robert Bredereck
  • Piotr Faliszewski
  • Rolf Niedermeier
  • Nimrod Talmon

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.

PDF Details DOI

IJCAI Conference 2015 Conference Paper

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

  • Robert Bredereck
  • Jiehua Chen
  • Rolf Niedermeier
  • Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or agenda controls is tractable for both procedures, our real-world experimental results indicate that most elections cannot be manipulated by a few voters and agenda control is typically impossible. If the voter preferences are incomplete, then finding possible winners is NP-hard for both procedures. Whereas finding necessary winners is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

PDF Details

TCS Journal 2015 Journal Article

The complexity of degree anonymization by vertex addition

  • Robert Bredereck
  • Vincent Froese
  • Sepp Hartung
  • André Nichterlein
  • Rolf Niedermeier
  • Nimrod Talmon

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results.

Details DOI

AAAI Conference 2014 Conference Paper

Prices Matter for the Parameterized Complexity of Shift Bribery

  • Robert Bredereck
  • Jiehua Chen
  • Piotr Faliszewski
  • André Nichterlein
  • Rolf Niedermeier

In the SHIFT BRIBERY problem, we are given an election (based on preference orders), a preferred candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters’ preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we must not exceed the given budget. We study the parameterized computational complexity of SHIFT BRIBERY with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize SHIFT BRIBERY by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin, and is W[1]-hard for Copeland. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that SHIFT BRIBERY tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.

PDF Details

IJCAI Conference 2013 Conference Paper

Are There Any Nicely Structured Preference Profiles Nearby?

  • Robert Bredereck
  • Jiehua Chen
  • Gerhard J. Woeginger

We investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile of a certain type, as for instance single-peaked, single-caved, singlecrossing, value-restricted, best-restricted, worstrestricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted so as to reach a nicely structured profile. Our results classify all considered problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial time solvable) and computationally intractable (NP-hard) questions.

PDF Details DOI

JAAMAS Journal 2013 Journal Article

Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation

  • Nadja Betzler
  • Robert Bredereck
  • Rolf Niedermeier

Abstract Kemeny Rank Aggregation is a consensus finding problem important in many areas ranging from classical voting over web search and databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a “median ranking”. We analyze efficient polynomial-time data reduction rules with provable performance bounds that allow us to find even all optimal median rankings. We show that our reduced instances contain at most candidates where \(d_a\) denotes the average Kendall’s tau distance between the input votes. On the theoretical side, this improves a corresponding result for a “partial problem kernel” from quadratic to linear size. In this context we provide a theoretical analysis of a commonly used data reduction. On the practical side, we provide experimental results with data based on web search and sport competitions, e. g. , computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds. Moreover, we perform experiments with randomly generated data based on two random distribution models for permutations.

Details DOI

AAAI Conference 2012 Conference Paper

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

  • Robert Bredereck
  • Jiehua Chen
  • Sepp Hartung
  • Rolf Niedermeier
  • Ondřej Suchý
  • Stefan Kratsch

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete LOBBYING problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of LOBBYING, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for LOB- BYING and introduce natural variants such as RESTRICTED LOBBYING and PARTIAL LOBBYING.

PDF Details

MFCS Conference 2011 Conference Paper

Pattern-Guided Data Anonymization and Clustering

  • Robert Bredereck
  • André Nichterlein
  • Rolf Niedermeier
  • Geevarghese Philip

Abstract A matrix M over a fixed alphabet is k -anonymous if every row in M has at least k − 1 identical copies in M. Making a matrix k -anonymous by replacing a minimum number of entries with an additional ⋆-symbol (called “suppressing entries”) is known to be NP-hard. This task arises in the context of privacy-preserving publishing. We propose and analyze the computational complexity of an enhanced anonymization model where the user of the k -anonymized data may additionally “guide” the selection of the candidate matrix entries to be suppressed. The basic idea is to express this by means of “pattern vectors” which are part of the input. This can also be interpreted as a sort of clustering process. It is motivated by the observation that the “value” of matrix entries may significantly differ, and losing one (by suppression) may be more harmful than losing the other, which again may very much depend on the intended use of the anonymized data. We show that already very basic special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results.

Details