Arrow Research search

Author name cluster

Dorothea Baumeister

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.

25 papers
2 author rows

Possible papers

25

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

  • Dorothea Baumeister
  • Ratip Emin Berker
  • Niclas Boehmer
  • Sylvain Bouveret
  • Andreas Darmann
  • Piotr Faliszewski
  • Martin Lackner
  • Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

PDF

AAMAS Conference 2023 Conference Paper

Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner Elections

  • Dorothea Baumeister
  • Linus Boes
  • Christian Laußmann
  • Simon Rey

Approval ballots have been celebrated for many voting scenarios [16], in particular because of the low cognitive burden they put on the voters. This however, comes at the cost of expressiveness that can be problematic when voters have sophisticated preferences. We consider voters who, in addition to usual approval, may wish to express incompatibilities, dependencies, and/or substitution effects between the alternatives. We introduce, and evaluate a new type of ballot—bounded approval ballots—which captures these effects while being almost as easy as regular approval ballots to cast.

PDF

AAMAS Conference 2023 Conference Paper

Distortion in Attribute Approval Committee Elections

  • Dorothea Baumeister
  • Linus Boes

In attribute approval elections, the task is to select sets of winning candidates, while each candidate satisfies a variety of attributes in different categories (e. g. , academic degree, work experience, location). Every voter specifies, which attributes in each category are desirable for a candidate, whereas each candidate might satisfy only some of the attributes. In this paper, we study questions of distortion in attribute approval committee elections. We introduce different methods to derive approval ballots, ordinal preferences, or cardinal preferences from a given attribute approval ballot. Then for a given voting method, assuming only a derived preference is provided, we compute the ratio of the voters’ satisfaction for the worst possible committee, with the satisfaction of the actual winning committee, given the attribute approval ballots.

PDF

AAMAS Conference 2022 Conference Paper

On the Average-Case Complexity of Predicting Round-Robin Tournaments

  • Dorothea Baumeister
  • Tobias Hogrebe

Round-robin tournaments are, besides single-elimination tournaments, by far the most prominent and widely used tournament format in sports and other competitions. We study the average-case complexity of two problems related to the prediction of roundrobin tournaments, namely first the problem of calculating the championship probability of a team and second the well-known sports elimination problem where one has to decide whether a team still has the possibility to become champion. We show that, under certain assumptions, these problems are solvable in expected polynomial time for a distribution which, for the algorithm used, seems to dominate the distribution of real instances in terms of complexity, despite their computational worst-case hardness.

PDF

IJCAI Conference 2022 Conference Paper

Time-Constrained Participatory Budgeting Under Uncertain Project Costs

  • Dorothea Baumeister
  • Linus Boes
  • Christian Laußmann

In participatory budgeting the stakeholders collectively decide which projects from a set of proposed projects should be implemented. This decision underlies both time and monetary constraints. In reality it is often impossible to figure out the exact cost of each project in advance, it is only known after a project is finished. To reduce risk, one can implement projects one after the other to be able to react to higher costs of a previous project. However, this will increase execution time drastically. We generalize existing frameworks to capture this setting, study desirable properties of algorithms for this problem, and show that some desirable properties are incompatible. Then we present and analyze algorithms that trade-off desirable properties.

PDF Details DOI

AIJ Journal 2021 Journal Article

Acceptance in incomplete argumentation frameworks

  • Dorothea Baumeister
  • Matti Järvisalo
  • Daniel Neugebauer
  • Andreas Niskanen
  • Jörg Rothe

argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis—especially computational complexity—and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i. e. , present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Σ 3 p. In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP.

Details DOI

FLAP Journal 2021 Journal Article

Collective Acceptability in Abstract Argumentation.

  • Dorothea Baumeister
  • Daniel Neugebauer
  • Jörg Rothe

This chapter highlights the collective acceptability problem in multiagent argumentation, which is related to the problem of collective decision making in the field of computational social choice at the intersection of social choice theory, theoretical computer science, and artificial intelligence. Specifically, the chapter surveys various approaches to collective acceptability and showcases useful methods for structural aggregation of argumentation frameworks and their properties.

Details

AAMAS Conference 2021 Conference Paper

Complexity of Scheduling and Predicting Round-Robin Tournaments

  • Dorothea Baumeister
  • Tobias Alexander Hogrebe

Tournaments are commonly used to identify winners, for example in sports. We study the computational complexity of problems related to scheduling the matches in a tournament and predicting the outcome with a special focus on round-robin tournaments, which is the most prominent tournament type used in sports. Besides the general financial and intrinsically motivated interest of various agents in tournament prediction, the recently very relevant winner determination for suddenly discontinued tournaments is a strong motivation. We show the immense theoretical complexity of predicting the winners in round-robin tournaments even under the assumption that only three matchdays remain to be played. On the other hand, we present an FPT algorithm and analyze its practical complexity using experiments on real-world and generated data, showing the applicability of the algorithm in praxis. To the best of our knowledge, this is the first exact and not purely brute-force oriented approach for predicting round-robin tournaments.

PDF

AAMAS Conference 2021 Conference Paper

Complexity of Sequential Rules in Judgment Aggregation

  • Dorothea Baumeister
  • Linus Boes
  • Robin Weishaupt

The task in judgment aggregation is to find a collective judgment set based on the views of individual judges about a given set of propositional formulas. One way of guaranteeing consistent outcomes is the use of sequential rules. In each round, the decision on a single formula is made either because the outcome is entailed by the already obtained judgment set, or, if this is not the case, by some underlying rule, e. g. the majority rule. Such rules are especially useful for cases, where the agenda is not fixed in advance, and formulas are added one by one. This paper investigates the computational complexity of winner determination under a family of sequential rules, and the manipulative influence of the processing order on the final outcome.

PDF

EUMAS Conference 2021 Conference Paper

On the Complexity of Predicting Election Outcomes and Estimating Their Robustness

  • Dorothea Baumeister
  • Tobias Hogrebe

Abstract When dealing with election data it is reasonable to assume that the votes are incomplete or noisy. The reasons are manifold and range from cost-intensive elicitation to manipulation. We study the problems of evaluating elections with incomplete data and determining the robustness of elections with noisy data from a computational point of view. To capture a wide variety of motivations, we consider three different models for the distribution of preferences: the uniform distribution over the completions of incomplete preferences inspired by the possible winner problem, the dispersion around complete preferences, also called Mallows noise model, and a model in which the distribution over the votes of each voter is explicitly given. We consider both approval vector preferences and linear order preferences and show that the complexity of the problems can vary greatly depending on the voting rule, the distribution model, and the parameterization. We investigate the problems both in terms of counting complexity as well as decision complexity and discuss the effects of the winner model and tie-breaking on the results.

Details

AAAI Conference 2019 Conference Paper

Generalized Distance Bribery

  • Dorothea Baumeister
  • Tobias Hogrebe
  • Lisa Rey

The bribery problem in elections asks whether an external agent can make some distinguished candidate win or prevent her from winning, by bribing some of the voters. This problem was studied with respect to the weighted swap distance between two votes by Elkind et al. (2009). We generalize this definition by introducing a bound on the distance between the original and the bribed votes. The distance measures we consider include a restriction of the weighted swap distance and variants of the footrule distance, which capture some realworld models of influence an external agent may have on the voters. We study constructive and destructive variants of distance bribery for scoring rules and obtain polynomial-time algorithms as well as NP-hardness results. For the case of element-weighted swap and element-weighted footrule distances, we give a complete dichotomy result for the class of pure scoring rules.

PDF Details

IJCAI Conference 2019 Conference Paper

How Hard Is the Manipulative Design of Scoring Systems?

  • Dorothea Baumeister
  • Tobias Hogrebe

In an election, votes are often given as ordered lists over candidates. A common way of determining the winner is then to apply some scoring system, where each position is associated with a specific score. This setting is also transferable to other situations, such as sports tournaments. The design of such systems, i. e. , the choice of the score values, may have a crucial influence on the outcome. We study the computational complexity of two related decision problems. In addition, we provide a case study of data from Formula 1 using ILP formulations. Our results show that under some mild conditions there are cases where the actual scoring system has no influence, whereas in other cases very small changes may lead to a different winner. This may be seen as a measure of robustness of the winning candidate.

PDF Details

AAMAS Conference 2019 Conference Paper

Manipulative Design of Scoring Systems

  • Dorothea Baumeister
  • Tobias Hogrebe

Scoring systems give points to candidates according to their positions and are, for example, used in elections and sports tournaments. We study the influence that the design of such systems has on the outcome by introducing two related decision problems. The problem Scoring System Existence asks whether for a given set of profiles there exists a scoring system that makes some distinguished candidate win, whereas Closest Scoring System bounds the choice of an alternative scoring system by some given distance.

PDF

AAAI Conference 2018 Conference Paper

Complexity of Verification in Incomplete Argumentation Frameworks

  • Dorothea Baumeister
  • Daniel Neugebauer
  • Jörg Rothe
  • Hilmar Schadrack

Abstract argumentation frameworks are a well-established formalism to model nonmonotonic reasoning processes. However, the standard model cannot express incomplete or conflicting knowledge about the state of a given argumentation. Previously, argumentation frameworks were extended to allow uncertainty regarding the set of attacks or the set of arguments. We combine both models into a model of general incompleteness, complement previous results on the complexity of the verification problem in incomplete argumentation frameworks, and provide a full complexity map covering all three models and all classical semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Σp 2-completeness when allowing uncertainty about either attacks or arguments, or both.

PDF Details

AIJ Journal 2018 Journal Article

Verification in incomplete argumentation frameworks

  • Dorothea Baumeister
  • Daniel Neugebauer
  • Jörg Rothe
  • Hilmar Schadrack

We tackle the problem of expressing incomplete knowledge in abstract argumentation frameworks originally introduced by Dung [26]. In applications, incomplete argumentation frameworks may arise as intermediate states in an elicitation process, or when merging different beliefs about an argumentation framework's state, or in cases where complete information cannot be obtained. We consider two specific models of incomplete argumentation frameworks, one focusing on attack incompleteness and the other on argument incompleteness, and we also provide a general model of incomplete argumentation framework that subsumes both specific models. In these three models, we study the computational complexity of variants of the verification problem with respect to six common semantics of argumentation frameworks: the conflict-free, admissible, stable, complete, grounded, and preferred semantics. We provide a full complexity map covering all three models and these six semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Σ 2 p -completeness when allowing uncertainty about either attacks or arguments, or both.

Details DOI

ECAI Conference 2016 Conference Paper

Minisum and Minimax Committee Election Rules for General Preference Types

  • Dorothea Baumeister
  • Toni Böhnlein
  • Lisa Rey
  • Oliver Schaudt
  • Ann-Kathrin Selker

In committee elections it is often assumed that voters only (dis)approve of each candidate or that they rank all candidates, as it is common for single-winner elections. We suggest an intermediate approach, where the voters rank the candidates into a fixed number of groups. This allows more diverse votes than approval votes, but leaves more freedom than in a linear order. A committee is then elected by applying the minisum or minimax approach to minimize the voters' dissatisfaction. We study the axiomatic properties of these committee election rules as well as the complexity of winner determination and show fixed-parameter tractability for our minimax rules.

Details

JAAMAS Journal 2016 Journal Article

Positional scoring-based allocation of indivisible goods

  • Dorothea Baumeister
  • Sylvain Bouveret
  • Abdallah Saffidine

Abstract We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents’ preferences over sets of goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vector \(s = (s_1, \ldots, s_m)\) consists of m nonincreasing, nonnegative weights, where \(s_i\) is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function \(\star \) such as, typically, \(+\) or \(\min \). The rule associated with s and \(\star \) maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.

Details DOI

IJCAI Conference 2015 Conference Paper

Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods

  • Nhan-Tam Nguyen
  • Dorothea Baumeister
  • J
  • ouml; rg Rothe

We study resource allocation in a model due to Brams and King [2005] and further developed by Baumeister et al. [2014]. Resource allocation deals with the distribution of resources to agents. We assume resources to be indivisible, nonshareable, and of single-unit type. Agents have ordinal preferences over single resources. Using scoring vectors, every ordinal preference induces a utility function. These utility functions are used in conjunction with utilitarian social welfare to assess the quality of allocations of resources to agents. Then allocation correspondences determine the optimal allocations that maximize utilitarian social welfare. Since agents may have an incentive to misreport their true preferences, the question of strategyproofness is important to resource allocation. We assume that a manipulator has a strictly monotonic and strictly separable linear order on the power set of the resources. We use extension principles (from social choice theory, such as the Kelly and the Gärdenfors extension) for preferences to study manipulation of allocation correspondences. We characterize strategy-proofness of the utilitarian allocation correspondence: It is Gärdenfors/Kellystrategy-proof if and only if the number of different values in the scoring vector is at most two or the number of occurrences of the greatest value in the scoring vector is larger than half the number of goods.

PDF Details

ECAI Conference 2014 Conference Paper

Scoring Rules for the Allocation of Indivisible Goods

  • Dorothea Baumeister
  • Sylvain Bouveret
  • Jérôme Lang
  • Nhan-Tam Nguyen
  • Trung Thanh Nguyen 0004
  • Jörg Rothe

We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of goods are additive, but that the input is ordinal: each agent simply ranks single goods. Similarly to (positional) scoring rules in voting, a scoring vector s = (s1, .. ., sm) consists of m nonincreasing nonnegative weights, where siis the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function ★ such as, typically, + or min. The rule associated with s and ★ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.

Details

AAMAS Conference 2012 Conference Paper

Campaigns for Lazy Voters: Truncated Ballots

  • Dorothea Baumeister
  • Piotr Faliszewski
  • eacute; r
  • ocirc; me Lang
  • J
  • ouml; rg Rothe

We study elections in which voters may submit partial ballots consisting of truncated lists: each voter ranks some of her top candidates (and possibly some of her bottom candidates) and is indifferent among the remaining ones. Holding elections with such votes requires adapting classical voting rules (which expect complete rankings as input) and these adaptations create various opportunities for candidates who want to increase their chances of winning. We provide complexity results regarding planning various kinds of campaign in such settings, and we study the complexity of the possible winner problem for the case of truncated votes.

PDF

AAMAS Conference 2012 Conference Paper

Computational Complexity in Three Areas of Computational Social Choice: Possible Winners, Unidirectional Covering Sets, and Judgment Aggregation

  • Dorothea Baumeister

This thesis studies the computational complexity of different problems from three areas of social choice. The first one is voting, and especially the problem of determining whether a distinguished candidate can be a winner in an election with some kind of incomplete information. The second setting is in the broader sense related to the problem of determining winners. Here the computational complexity of problems related to minimal upward and downward covering sets are studied. The last area is judgment aggregation, where judges have to report their judgments over a set of possibly interconnected propositions and a collective judgment set is determined by some aggregation procedure. In contrast to the problems mentioned above we do not study the complexity of some kind of 'winner'-problem, but the complexity of two forms of influencing the outcome, namely manipulation and bribery.

PDF

ECAI Conference 2012 Conference Paper

The Possible Winner Problem with Uncertain Weights

  • Dorothea Baumeister
  • Magnus Roos
  • Jörg Rothe
  • Lena Schend
  • Lirong Xia

The original possible winner problem is: Given an unweighted election with partial preferences and a distinguished candidate c, can the preferences be extended to total ones such that c wins? We introduce a novel variant of this problem in which not some of the voters' preferences are uncertain but some of their weights. Not much has been known previously about the weighted possible winner problem. We present a general framework to study this problem, both for integer and rational weights, with and without upper bounds on the total weight to be distributed, and with and without ranges to choose the weights from. We study the complexity of these problems for important voting systems such as scoring rules, Copeland, ranked pairs, plurality with runoff, and (simplified) Bucklin and fall-back voting.

Details

AAMAS Conference 2011 Conference Paper

( PcWNA ) problem, which asks, given an election with strict preferences over the candidates, is it possible to make a designated candidate win the election by adding a limited number of new candidates to the election? In the case of unweighted voters we show NP-completeness of PcWNA for a broad class of pure scoring rules. We will also briefly study the case of weighted voters. The second type of possible winner problem we study is Possible Winner/co-Winner under Uncertain Voting System ( PWUVS and PcWUVS ). Here, uncertainty is present not in the votes but in the election rule itself. For example, PcWUVS is the problem of whether, given a set C of candidates, a list of votes over C, a distinguished candidate c ı n C, and a class of election rules, there is at least one election rule from this class under which c wins the election. We study these two problems for a class of systems based on approval voting, the family of Copeland ^α elections, and a certain class of scoring rules. Our main result is that it is NP-complete to determine whether there is a scoring vector that makes c win the election, if we restrict the set of possible scoring vectors for an m-candidate election to those of the form (α _1, .. ., α _{m-4}, x_1, x_2, x_3, 0), with x_i = 1 for at least one i ı n {1, 2, 3}. Computational Complexity of Two Variants of the Possible Winner Problem

  • Dorothea Baumeister
  • Magnus Roos
  • J
  • ouml; rg Rothe

A possible winner of an election is a candidate that has, in some kind of incomplete-information election, the possibility to win in a complete extension of the election. The first type of problem we study is the Possible co-Winner with respect to the Addition of New Candidates

PDF

ECAI Conference 2010 Conference Paper

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules

  • Dorothea Baumeister
  • Jörg Rothe

The POSSIBLE WINNER problem asks, given an election where the voters' preferences over the candidates are specified only partially, whether a designated candidate can be made win. Betzler and Dorn [1] proved a result that is only one step away from a full dichotomy of this problem for the important class of pure scoring rules in the case of unweighted voters and an unbounded number of candidates: POSSIBLE WINNER is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule with vector ( 2, 1, … ,1, 0) , but is solvable in polynomial time for plurality and veto. We take the final step to a full dichotomy by showing that POSSIBLE WINNER is NP-complete also for the scoring rule with vector ( 2, 1, … ,1, 0) .

Details

I&C Journal 2009 Journal Article

The three-color and two-color Tantrix™ rotation puzzle problems are NP-complete via parsimonious reductions

  • Dorothea Baumeister
  • Jörg Rothe

Holzer and Holzer [M. Holzer, W. Holzer, Tantrix™ rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] proved that the Tantrix™ rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we study the three-color and two-color Tantrix™ rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix™ tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer [M. Holzer, W. Holzer, Tantrix™ rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.

Details DOI
v2026.09.13