Arrow Research search

Author name cluster

Jörg Rothe

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.

67 papers
2 author rows

Possible papers

67

NeurIPS Conference 2025 Conference Paper

Clustering via Hedonic Games: New Concepts and Algorithms

  • Gergely Csáji
  • Alexander Gundert
  • Jörg Rothe
  • Ildikó Schlotter

We study fundamental connections between coalition formation games and clustering, illustrating the cross-disciplinary relevance of these concepts. We focus on graphical hedonic games where agents' preferences are compactly represented by a friendship graph and an enemy graph. In the context of clustering, friendship relations naturally align with data point similarities, whereas enmity corresponds to dissimilarities. We consider two stability notions based on single-agent deviations: local popularity and local stability. Exploring these concepts from an algorithmic viewpoint, we design efficient mechanisms for finding locally stable or locally popular partitions. Besides gaining theoretical insight into the computational complexity of these problems, we perform simulations that demonstrate how our algorithms can be successfully applied in clustering and community detection. Our findings highlight the interplay between coalition formation games and data-driven clustering techniques, offering fresh perspectives and applications in both areas.

PDF Details

JAIR Journal 2025 Journal Article

Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games

  • Joanna Kaczmarek
  • Jörg Rothe
  • Nimrod Talmon

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only sufficiently connected coalitions are taken into consideration for calculating the players' power indices. Focusing on the probabilistic Penrose-Banzhaf index (which Dubey and Shapley proposed in 1979 as an alternative to the normalized Penrose-Banzhaf index) and the Shapley-Shubik index, we study control of these games by an agent who can add edges to or delete edges from the given graph. We determine upper and lower bounds on how much such control actions can change a distinguished player's power and we study the computational complexity of the related problems.

PDF Details DOI

ECAI Conference 2025 Conference Paper

Control by Deleting Players from Weighted Voting Games Is NP PP -Complete for the Penrose-Banzhaf Power Index

  • Joanna Kaczmarek 0001
  • Jörg Rothe

Weighted voting games are a popular class of coalitional games that are widely used to model real-life situations of decision-making. They can be applied, for instance, to analyze legislative processes in parliaments or voting in corporate structures. Various ways of tampering with these games have been studied, among them merging or splitting players, fiddling with the quota, and controlling weighted voting games by adding or deleting players. While the complexity of control by adding players to such games so as to change or maintain a given player’s power has been recently settled, the complexity of control by deleting players from such games (with the same goals) remained open. We show that when the players’ power is measured by the probabilistic Penrose–Banzhaf index, some of these problems are complete for NPPP—the class of problems solvable by NP machines equipped with a PP (“probabilistic polynomial time”) oracle. Our results optimally improve the currently known lower bounds of hardness for much smaller complexity classes, thus providing protection against SAT-solving techniques in practical applications.

Details

IJCAI Conference 2025 Conference Paper

Control in Computational Social Choice

  • Jiehua Chen
  • Joanna Kaczmarek
  • Paul Nüsken
  • Jörg Rothe
  • Ildikó Schlotter
  • Tessa Seeger

We survey the notion of control in various areas of computational social choice (COMSOC) such as voting, fair allocation, cooperative game theory, matching under preferences, and group identification. In all these scenarios, control can be exerted, for instance, by adding or deleting agents with the goal of influencing the outcome. We conclude by briefly covering control in some other COMSOC areas including participatory budgeting, judgment aggregation, and opinion diffusion.

PDF Details DOI

ECAI Conference 2025 Conference Paper

District-Limited Bribery in Multidistrict Apportionment Elections with Threshold

  • Joanna Kaczmarek 0001
  • Jörg Rothe
  • Tessa Seeger

Apportionment methods allocate a fixed number of seats in a parliament to parties based on their vote counts. In many countries, parliamentary elections are organized by first holding separate elections in several districts and then putting the single results together. We call such elections multidistrict apportionment elections. Moreover, many countries have an additional general electoral threshold, i. e. , a minimum number of votes a party must receive to win any seats in a parliament. For such methods, we study the complexity of bribery problems where an external agent seeks to increase the number of seats for a distinguished party by bribing voters within a given budget. Specifically, we investigate how adding either a general electoral threshold, or district limits for the budget, or both influences the complexity of bribery. District limits—which the external agent must adhere to while still respecting the overall budget—denote a maximum budget for each district, each to be spent for changing the votes only in that district. We show that adding a general electoral threshold, with or without district limits, makes the problems NP-complete for the largest-remainder method and all divisor sequence methods (including the prominent D’Hondt and Sainte-Laguë apportionment methods). We also study parameterized complexity and domain restrictions of these problems.

Details

TARK Conference 2025 Conference Paper

Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments

  • Laryssa Horn
  • Paul Nüsken
  • Jörg Rothe
  • Tessa Seeger

The Skating System, which originated from the scrutineering system in dance sport tournaments, can be formulated as a voting system: We introduce and formalize the Skating System Single (SkS, for short), a new voting system embedded into the framework of computational social choice. Although SkS has similarities with Bucklin voting, it differs from it because it is subject to additional constraints when determining the election winners. Through an analysis of the axiomatic properties of SkS and of its vulnerability to manipulative and electoral control attacks, we compare SkS with Bucklin voting and provide insights into its potential strengths and weaknesses. In particular, we show that SkS satisfies nondictatorship as well as the majority criterion, positive responsiveness, monotonicity, and citizens' sovereignty but violates the Condorcet criterion, strong monotonicity, independence of clones, consistency, participation, resoluteness, and strategy-proofness. Further, we study manipulation, i. e. , where (groups of) voters vote strategically to improve the outcome of an election in their favor, showing that the constructive coalitional weighted manipulation problem for SkS is NP-complete, while the destructive variant can be solved in polynomial time. Lastly, we initiate the study of electoral control, where an external agent attempts to change the election outcome by interfering with the structure of the election. Here, we show NP-completeness for constructive and destructive control by deleting candidates as well as for constructive control by adding voters, whereas we show that the problem of destructive control by adding voters can be solved in polynomial time.

Details DOI

TARK Conference 2025 Conference Paper

Solving Four Open Problems about Core Stability in Altruistic Hedonic Games

  • Jörg Rothe
  • Ildikó Schlotter

Hedonic games -- at the interface of cooperative game theory and computational social choice -- are coalition formation games in which the players have preferences over the coalitions they can join. Kerkmann et al. [13] introduced altruistic hedonic games where the players' utilities depend not only on their own but also on their friends' valuations of coalitions. The complexity of the verification problem for core stability has remained open in four variants of altruistic hedonic games: namely, for the variants with average- and minimum-based "equal-treatment" and "altruistic-treatment" preferences. We solve these four open questions by proving the corresponding problems coNP-complete; our reductions rely on rather intricate gadgets in the related networks of friends.

Details DOI

ECAI Conference 2024 Conference Paper

Complexity and Approximation Schemes for Social Welfare Maximization in the High-Multiplicity Setting

  • Trung Thanh Nguyen 0004
  • Khaled M. Elbassioni
  • Jörg Rothe

We study the social welfare maximization problem in the high-multiplicity setting where agents and/or items are available in multiple types, provided that the numbers of types are small. We focus on the egalitarian and Nash social welfare maximization problems, and show that they are NP-hard even when the number of item types is a constant. Furthermore, we present two polynomial-time approximation schemes (PTAS), one for egalitarian social welfare with two item types, and one for Nash social welfare with any constant number of agent types. The first PTAS can be applied to the unrelated machine scheduling problem, thus partially solving an open question raised by Jansen and Maack in 2019. The second PTAS significantly improves upon the existing PTAS for identical agents.

Details

ECAI Conference 2024 Conference Paper

Control by Adding Players to Change or Maintain the Shapley-Shubik or the Penrose-Banzhaf Power Index in Weighted Voting Games Is Complete for NP PP

  • Joanna Kaczmarek 0001
  • Jörg Rothe

Weighted voting games are a well-known and useful class of succinctly representable simple games that have many real-world applications, e. g. , to model collective decision-making in legislative bodies or shareholder voting. Among the structural control types being analyzing, one is control by adding players to weighted voting games, so as to either change or to maintain a player’s power in the sense of the (probabilistic) Penrose–Banzhaf power index or the Shapley–Shubik power index. For the problems related to this control, the best known lower bound is PP-hardness, where PP is “probabilistic polynomial time, ” and the best known upper bound is the class NP, i. e. , the class NP with a PP oracle. We optimally raise this lower bound by showing NPPP-hardness of all these problems for the Penrose–Banzhaf and the Shapley–Shubik indices, thus establishing completeness for them in that class. Our proof technique may turn out to be useful for solving other open problems related to weighted voting games with such a complexity gap as well.

Details

AAMAS Conference 2024 Conference Paper

NP PP -Completeness of Control by Adding Players to Change the Penrose-Banzhaf Power Index in Weighted Voting Games

  • Joanna Kaczmarek
  • Jörg Rothe

Weighted voting games are an important class of simple games that can be compactly represented and have many real-world applications. Rey and Rothe [14] introduced the notion of structural control by adding players to or deleting them from weighted voting games, with the goal to either change or maintain a given player’s power in a given game with respect to the (probabilistic) Penrose– Banzhaf power index [4] or the Shapley–Shubik power index [17]. For control by adding players, they showed PP-hardness as the best known lower bound and an upper bound of NPPP, where PP is “probabilistic polynomial time. ” We optimally improve their results by establishing NPPP-hardness (and thus NPPP-completeness) of all problems related to the Penrose–Banzhaf index and for the problem of maintaining the Shapley–Shubik index when players are added.

PDF

JAAMAS Journal 2024 Journal Article

The complexity of verifying popularity and strict popularity in altruistic hedonic games

  • Anna Maria Kerkmann
  • Jörg Rothe

Abstract We consider average- and min-based altruistic hedonic games and study the problem of verifying popular and strictly popular coalition structures. While strict popularity verification has been shown to be coNP-complete in min-based altruistic hedonic games, this problem has been open for equal- and altruistic-treatment average-based altruistic hedonic games. We solve these two open cases of strict popularity verification and then provide the first complexity results for popularity verification in (average- and min-based) altruistic hedonic games, where we cover all three degrees of altruism.

Details DOI

IJCAI Conference 2024 Conference Paper

Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections

  • Cynthia Maushagen
  • David Niclaus
  • Paul Nüsken
  • Jörg Rothe
  • Tessa Seeger

Both Schulze and ranked pairs are voting rules that satisfy many natural, desirable axioms. Many standard types of electoral control (with a chair seeking to change the outcome of an election by interfering with the election structure) have already been studied. However, for control by replacing candidates or voters and for (exact) multimode control that combines multiple standard attacks, many questions remain open. We solve a number of these open cases for Schulze and ranked pairs. In addition, we fix a flaw in the reduction of Menton and Singh showing that Schulze is resistant to constructive control by deleting candidates and re-establish a vulnerability result for destructive control by deleting candidates. In some of our proofs, we study variants of s-t vertex cuts in graphs that are related to our control problems.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Complexity of Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games

  • Joanna Kaczmarek 0001
  • Jörg Rothe
  • Nimrod Talmon

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only connected coalitions are taken into consideration for calculating the players’ power indices. We focus on the probabilistic Penrose–Banzhaf index [5] and the Shapley–Shubik index [18] and study the computational complexity of manipulating these games by an external agent who can add edges to or delete edges from the graph. For the problems modeling such scenarios, we raise some of the lower bounds obtained by Kaczmarek and Rothe [9] from NP- or DP-hardness to PP-hardness, where PP is probabilistic polynomial time. We also solve one of their open problems by showing that it is a coNP-hard problem to maintain the Shapley–Shubik index of a given player in a graph-restricted weighted voting game when edges are deleted.

Details

IJCAI Conference 2023 Conference Paper

Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey

  • Trung Thanh Nguyen
  • Jörg Rothe

Fair allocation of indivisible goods is a central topic in many AI applications. Unfortunately, the corresponding problems are known to be NP-hard for many fairness concepts, so unless P = NP, exact polynomial-time algorithms cannot exist for them. In practical applications, however, it would be highly desirable to find exact solutions as quickly as possible. This motivates the study of algorithms that—even though they only run in exponential time—are as fast as possible and exactly solve such problems. We present known complexity results for them and give a survey of important techniques for designing such algorithms, mainly focusing on four common fairness notions: max-min fairness, maximin share, maximizing Nash social welfare, and envy-freeness. We also highlight the most challenging open problems for future work.

PDF Details DOI

AIJ Journal 2023 Journal Article

Fair and efficient allocation with few agent types, few item types, or small value levels

  • Trung Thanh Nguyen
  • Jörg Rothe

In fair division of indivisible goods, allocations that satisfy fairness and efficiency simultaneously are highly desired but may not exist or, even if they do exist, are computationally hard to find. Conditions under which such allocations, or allocations satisfying specific levels of fairness and efficiency simultaneously, can be efficiently found have thus been explored. Following this line of research, this study is concerned with the problem in a high-multiplicity setting where instances come with certain parameters, including agent types, item types, and value levels. Particularly, we address two computational problems. First, we wish to compute fair and Pareto-optimal allocations, w. r. t. any of the common fairness criteria: proportionality, maximin share, and max-min fairness. Second, we seek to find a max-min fair allocation that is efficient in the sense of maximizing utilitarian social welfare. We show that the first problem is tractable for most of the fairness criteria when the number of item types is fixed, or when at least two of the three parameters are fixed. For the second problem, we model it as a bi-criteria optimization problem that is solved approximately by determining an approximate Pareto set of bounded size. Our results are obtained based on dynamic programming and linear programming approaches. Our techniques strengthen known methods and can be potentially applied to other notions of fairness and efficiency.

Details DOI

JAIR Journal 2022 Journal Article

Altruistic Hedonic Games

  • Anna Maria Kerkmann
  • Nhan-Tam Nguyen
  • Anja Rey
  • Lisa Rey
  • Jörg Rothe
  • Lena Schend
  • Alessandra Wiechers

Hedonic games are coalition formation games in which players have preferences over the coalitions they can join. For a long time, all models of representing hedonic games were based upon selfish players only. Among the known ways of representing hedonic games compactly, we focus on friend-oriented hedonic games and propose a novel model for them that takes into account not only the players’ own preferences but also their friends’ preferences. Depending on the order in which players look at their own or their friends’ preferences, we distinguish three degrees of altruism: selfish-first, equal-treatment, and altruistic-treatment preferences. We study both the axiomatic properties of these games and the computational complexity of problems related to various common stability concepts.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Popularity and Strict Popularity in Altruistic Hedonic Games and Minimum-Based Altruistic Hedonic Games

  • Anna Maria Kerkmann
  • Jörg Rothe

We consider average-based and min-based altruistic hedonic games and study the problem of verifying popular and strictly popular coalition structures. While strict popularity verification has been shown to be coNP-complete in min-based altruistic hedonic games, this problem has been open for equal-treatment and altruistictreatment average-based altruistic hedonic games. We solve these two open cases of strict popularity verification and then provide the first complexity results for popularity verification in (both averageand min-based) altruistic hedonic games, where we cover all three degrees of altruism.

PDF

AAMAS Conference 2022 Conference Paper

Voting for Centrality

  • Ulrik Brandes
  • Christian Laußmann
  • Jörg Rothe

In network science, centrality indices are used to determine important nodes by virtue of their position in a network. In social choice theory, voting rules are used to aggregate preferences of voters to determine the winners of an election. Exploiting parallels between these two fields, we propose a novel approach to define network centrality indices based on voting rules. Since formal properties of voting rules have been studied in much greater depth, this will not only lead to new applications of social choice theory but also facilitate a deeper understanding of centrality in networks.

PDF

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

AIJ Journal 2021 Journal Article

Control complexity in Borda elections: Solving all open cases of offline control and some cases of online control

  • Marc Neveling
  • Jörg Rothe

Borda Count is one of the earliest and most important voting rules and has been central to many applications in artificial intelligence. We study the problem of control in Borda elections where an election chair seeks to either make a designated candidate win (constructive case), or prevent her from winning (destructive case), via actions such as adding, deleting, or partitioning either candidates or voters. These scenarios have been studied for many voting rules and the related control problems have been classified in terms of their computational complexity. However, for one of the most prominent natural voting rules, the Borda Count, complexity results have been known for only half of these cases until recently. We settle the complexity for all missing cases, focusing on the unique-winner model. We also exhibit two of the very rare cases where the complexity of control problems differs depending on the winner model chosen: For destructive control by partition and by run-off partition of candidates when ties promote, Borda is resistant in the unique-winner model (i. e. , these two control problems are NP-hard), yet is vulnerable in the nonunique-winner model (i. e. , one can decide in polynomial time whether control is possible). Finally, we turn to the model of online control in sequential elections that was recently proposed by Hemaspaandra et al. [62, 61]. We show that sequential Borda elections are vulnerable to constructive and destructive online control by adding or deleting candidates, whereas we obtain coNP-hardness results for all types of online voter control in sequential Borda elections.

Details DOI

TCS Journal 2021 Journal Article

Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints

  • Trung Thanh Nguyen
  • Jörg Rothe

We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p i, j time units and incurs a cost c i, j, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [1], we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints.

Details DOI

TCS Journal 2021 Journal Article

Local fairness in hedonic games via individual threshold coalitions

  • Anna Maria Kerkmann
  • Nhan-Tam Nguyen
  • Jörg Rothe

Hedonic games are coalition formation games where players only specify preferences over coalitions they are part of. We introduce and systematically study three local fairness notions in hedonic games called max-min fairness, grand-coalition fairness, and min-max fairness. To this end, we define suitable threshold coalitions for these three concepts. A coalition structure (i. e. , a partition of the players into coalitions) is considered locally fair if all players' coalitions in this structure are each at least as good as their threshold coalitions. Based on this approach, we then introduce three specific notions of local fairness by suitably adapting fairness notions from fair division. We show that they form a proper hierarchy and how they are related to previously studied solution concepts in hedonic games. We also study the computational aspects of finding threshold coalitions and of deciding whether fair coalition structures exist in additively separable hedonic games, and we investigate the related price of local fairness.

Details DOI

AAAI Conference 2021 Conference Paper

Thou Shalt Love Thy Neighbor as Thyself When Thou Playest: Altruism in Game Theory

  • Jörg Rothe

Game theory is typically used to model the interaction among (software) agents in multiagent systems and, therefore, is a key topic at leading AI conferences. Game-theoretic models, however, are often based on the assumption that agents are perfectly rational and narrowly selfish and are interested only in maximizing their own gains, no matter what the costs to the other agents are. This summary paper presents various ways of introducing certain notions of altruism into existing game-theoretic models in both noncooperative and cooperative games, in the hope that simulating altruistic behavior in AI systems will make AI better suit real-world applications— and thus may make the real world a better place.

PDF Details

IJCAI Conference 2020 Conference Paper

Altruism in Coalition Formation Games

  • Anna Maria Kerkmann
  • Jörg Rothe

Nguyen et al. [2016] introduced altruistic hedonic games in which agents’ utilities depend not only on their own preferences but also on those of their friends in the same coalition. We propose to extend their model to coalition formation games in general, considering also the friends in other coalitions. Comparing the two models, we argue that excluding some friends from the altruistic behavior of an agent is a major disadvantage that comes with the restriction to hedonic games. After introducing our model, we additionally study some common stability notions and provide a computational analysis of the associated verification and existence problems.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Approximate Pareto Set for Fair and Efficient Allocation: Few Agent Types or Few Resource Types

  • Trung Thanh Nguyen
  • Jörg Rothe

In fair division of indivisible goods, finding an allocation that satisfies fairness and efficiency simultaneously is highly desired but computationally hard. We solve this problem approximately in polynomial time by modeling it as a bi-criteria optimization problem that can be solved efficiently by determining an approximate Pareto set of bounded size. We focus on two criteria: max-min fairness and utilitarian efficiency, and study this problem for the setting when there are only a few item types or a few agent types. We show in both cases that one can construct an approximate Pareto set in time polynomial in the input size, either by designing a dynamic programming scheme, or a linear-programming algorithm. Our techniques strengthen known methods and can be potentially applied to other notions of fairness and efficiency as well.

PDF Details DOI

ECAI Conference 2020 Conference Paper

Complexity of Possible and Necessary Existence Problems in Abstract Argumentation

  • Kenneth Skiba
  • Daniel Neugebauer
  • Jörg Rothe

This work focuses on generalizing the existence problems for extensions in abstract argumentation to incomplete argumentation frameworks. In this extended model, incomplete or conflicting knowledge about the state of the arguments and attacks are allowed. We propose possible and necessary variations of the existence and nonemptiness problems, originally defined for (complete) argumentation frameworks, to extend these problems to incomplete argumentation frameworks. While the computational complexity of existence problems is already known for the standard model, we provide a full analysis of the complexity for incomplete argumentation frameworks using the most prominent semantics, namely, the conflict-free, admissible, complete, grounded, preferred, and stable semantics. We show that the complexity rises from NP-completeness to ∏ p 2 -completeness for most “necessary” problem variants when uncertainty is allowed.

Details

AAAI Conference 2020 Conference Paper

Deciding Acceptance in Incomplete Argumentation Frameworks

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

Expressing incomplete knowledge in abstract argumentation frameworks (AFs) through incomplete AFs has recently received noticeable attention. However, algorithmic aspects of deciding acceptance in incomplete AFs are still underdeveloped. We address this current shortcoming by developing algorithms for NP-hard and coNP-hard variants of acceptance problems over incomplete AFs via harnessing Boolean satisfiability (SAT) solvers. Focusing on nonempty conflict-free or admissible sets and on stable extensions, we also provide new complexity results for a refined variant of skeptical acceptance in incomplete AFs, ranging from polynomial-time computability to hardness for the second level of the polynomial hierarchy. Furthermore, central to the proposed SAT-based counterexample-guided abstraction re- finement approach for the second-level problem variants, we establish conditions for redundant atomic changes to incomplete AFs from the perspective of preserving extensions. We show empirically that the resulting SAT-based approach for incomplete AFs scales at least as well as existing SAT-based approaches to deciding acceptance in AFs.

PDF Details

JAIR Journal 2020 Journal Article

Hedonic Games with Ordinal Preferences and Thresholds

  • Anna Maria Kerkmann
  • Jérôme Lang
  • Anja Rey
  • Jörg Rothe
  • Hilmar Schadrack
  • Lena Schend

We propose a new representation setting for hedonic games, where each agent partitions the set of other agents into friends, enemies, and neutral agents, with friends and enemies being ranked. Under the assumption that preferences are monotonic (respectively, antimonotonic) with respect to the addition of friends (respectively, enemies), we propose a bipolar extension of the responsive extension principle, and use this principle to derive the (partial) preferences of agents over coalitions. Then, for a number of solution concepts, we characterize partitions that necessarily or possibly satisfy them, and we study the related problems in terms of their complexity.

PDF Details DOI

ECAI Conference 2020 Conference Paper

The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections

  • Cynthia Maushagen
  • Jörg Rothe

One of the key topics of computational social choice is electoral control, which models certain ways of how an election chair can seek to influence the outcome of elections via structural changes such as adding, deleting, or partitioning either candidates or voters. Faliszewski and Rothe [13] have surveyed the rich literature on control, giving an overview of previous results on the complexity of the associated problems for the most important voting rules. Among those, only a few results were known for two quite prominent voting rules: Borda Count and maximin voting (a. k. a. the Simpson–Kramer rule). Neveling and Rothe [26, 25] recently settled the remaining open cases for Borda. In this paper, we solve all remaining open cases for the complexity of control in maximin elections all of which concern control by partition of either candidates or voters.

Details

AAAI Conference 2019 Conference Paper

Borda Count in Collective Decision Making: A Summary of Recent Results

  • Jörg Rothe

Borda Count is one of the earliest and most important voting rules. Going far beyond voting, we summarize recent advances related to Borda in computational social choice and, more generally, in collective decision making. We first present a variety of well known attacks modeling strategic behavior in voting—including manipulation, control, and bribery—and discuss how resistant Borda is to them in terms of computational complexity. We then describe how Borda can be used to maximize social welfare when indivisible goods are to be allocated to agents with ordinal preferences. Finally, we illustrate the use of Borda in forming coalitions of players in a certain type of hedonic game. All these approaches are central to applications in artificial intelligence.

PDF Details

AAMAS Conference 2019 Conference Paper

Stability in FEN-Hedonic Games for Single-Player Deviations

  • Anna Maria Kerkmann
  • Jörg Rothe

Hedonic games model how players form coalitions based on their preferences about the coalitions they can join. Lang et al. [17] introduced FEN-hedonic games where each player partitions the other players into friends, enemies, and neutral players and ranks her friends and enemies. They then use bipolar responsive extensions to derive preferences over coalitions, and since such preferences can be incomplete, they consider possible and necessary stability for various stability notions and study the related verification and existence problems in terms of computational complexity. However, in their complexity analysis they left a number of cases open. We settle several of these open problems for stability concepts based on single-player deviations: We show that possible verification can be solved in polynomial time for Nash stability, individual stability, and contractually individual stability. Yet, necessary existence is an NP-complete problem for individual stability while possible existence is easy for contractually individual stability.

PDF

TARK Conference 2019 Conference Paper

The Complexity of Online Bribery in Sequential Elections (Extended Abstract)

  • Edith Hemaspaandra
  • Lane A. Hemachandra
  • Jörg Rothe

Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all voters' votes. But neither of those assumptions always holds. In many real-world settings, votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to bribe/alter a given vote, and at the time of making that decision, the briber may not know what votes remaining voters are planning on casting. In this paper, we introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is polynomial-time computable, an online, sequential setting may vastly increase the complexity of bribery, in fact jumping the problem up to completeness for high levels of the polynomial hierarchy or even PSPACE. On the other hand, we show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems in the online, sequential setting.

Details DOI

JAAMAS Journal 2018 Journal Article

Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of indivisible goods

  • Tobias Heinen
  • Nhan-Tam Nguyen
  • Jörg Rothe

Abstract This paper is concerned with various types of allocation problems in fair division of indivisible goods, aiming at maximin share, proportional share, and minimax share allocations. However, such allocations do not always exist, not even in very simple settings with two or three agents. A natural question is to ask, given a problem instance, what is the largest value c for which there is an allocation such that every agent has utility of at least c times her fair share. We first prove that the decision problem of checking if there exists a minimax share allocation for a given problem instance is \(\mathrm {NP}\) -hard when the agents’ utility functions are additive. We then show that, for each of the three fairness notions, one can approximate c by a polynomial-time approximation scheme, assuming that the number of agents is fixed. Next, we investigate the restricted cases when utility functions have values in \(\{0, 1\}\) only or are defined based on scoring vectors (Borda and lexicographic vectors), and we obtain several tractability results for these cases. Interestingly, we show that maximin share allocations can always be found efficiently with Borda utilities, which cannot be guaranteed for general additive utilities. In the nonadditive setting, we show that there exists a problem instance for which there is no c -maximin share allocation, for any constant c. We explore a class of symmetric submodular utilities for which there exists a tight \(\frac{1}{2}\) -maximin share allocation, and show how it can be approximated to within a factor of \(\nicefrac {1}{4}\).

Details DOI

JAIR Journal 2018 Journal Article

Bounds on the Cost of Stabilizing a Cooperative Game

  • Yoram Bachrach
  • Edith Elkind
  • Enrico Malizia
  • Reshef Meir
  • Dmitrii Pasechnik
  • Jeffrey S. Rosenschein
  • Jörg Rothe
  • Michael Zuckerman

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core---the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.

PDF Details DOI

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

TCS Journal 2017 Journal Article

The complexity of controlling candidate-sequential elections

  • Edith Hemaspaandra
  • Lane A. Hemaspaandra
  • Jörg Rothe

Candidate control of elections is the study of how adding or removing candidates can affect the outcome. However, the traditional study of the complexity of candidate control is in the model in which all candidates and votes are known up front. This paper develops a model for studying online control for elections where the structure is sequential with respect to the candidates, and in which the decision regarding adding and deleting must be irrevocably made at the moment the candidate is presented. We show that great complexity—PSPACE-completeness—can occur in this setting, but we also provide within this setting polynomial-time algorithms for the most important of election systems, plurality.

Details DOI

AAMAS Conference 2016 Conference Paper

Altruistic Hedonic Games

  • Nhan-Tam Nguyen
  • Anja Rey
  • Lisa Rey
  • Jörg Rothe
  • Lena Schend

Hedonic games are coalition formation games in which players have preferences over the coalitions they can join. All models of representing hedonic games studied so far are based upon selfish players only. Among the known ways of representing hedonic games compactly, we focus on friend-oriented hedonic games and propose a novel model for them that takes into account not only a player’s own preferences but also her friends’ preferences under three degrees of altruism. We study both the axiomatic properties of these games and the computational complexity of problems related to various stability concepts.

PDF

ECAI Conference 2016 Conference Paper

Complexity of Control by Partitioning Veto and Maximin Elections and of Control by Adding Candidates to Plurality Elections

  • Cynthia Maushagen
  • Jörg Rothe

Control by partition refers to situations where an election chair seeks to influence the outcome of an election by partitioning either the candidates or the voters into two groups, thus creating two first-round subelections that determine who will take part in a final round. The model of partition-of-voters control attacks is remotely related to "gerrymandering" (maliciously resizing election districts). While the complexity of control by partition (and other control actions) has been studied thoroughly for many voting systems, there are no such results known for the important veto and maximin voting systems. We settle the complexity of control by partition for veto in a broad variety of models and for maximin with respect to destructive control by partition of candidates. We also observe that a reduction from the literature [8] showing the parameterized complexity of control by adding candidates to plurality elections, parameterized by the number of voters, is technically flawed by giving a counterexample, and we show how this reduction can be fixed.

Details

AAMAS Conference 2016 Conference Paper

Local Fairness in Hedonic Games via Individual Threshold Coalitions

  • Nhan-Tam Nguyen
  • Jörg Rothe

Hedonic games are coalition formation games where players only specify preferences over coalitions they are part of. We introduce and systematically study local fairness notions in hedonic games by suitably adapting fairness notions from fair division. In particular, we introduce three notions that assign to each player a threshold coalition that only depends on the player’s individual preferences. A coalition structure (i. e. , a partition of the players into coalitions) is considered locally fair if all players’ coalitions in this structure are each at least as good as their threshold coalitions. We relate our notions to previously studied concepts and show that our fairness notions form a proper hierarchy. We also study the computational aspects of finding threshold coalitions and of deciding whether fair coalition structures exist in additively separable hedonic games. At last, we investigate the price of fairness.

PDF

MFCS Conference 2016 Conference Paper

Structural Control in Weighted Voting Games

  • Anja Rey
  • Jörg Rothe

Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player's Shapley-Shubik or probabilistic Penrose-Banzhaf index in relation to the original game. We study the computational complexity of the problems of whether such structural changes can achieve the desired effect.

Details

AAMAS Conference 2016 Conference Paper

Structural Control in Weighted Voting Games (Extended Abstract)

  • Anja Rey
  • Jörg Rothe

Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player’s Shapley–Shubik power index in relation to the original game. We study the complexity of the problems of whether such structural changes can achieve the desired effect.

PDF

JAAMAS Journal 2016 Journal Article

The complexity of online voter control in sequential elections

  • Edith Hemaspaandra
  • Lane A. Hemaspaandra
  • Jörg Rothe

Abstract Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters’ preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is \(\mathrm {PSPACE}\) -complete, even if there are only two candidates. In addition, we obtain (by a new characterization of coNP in terms of weight-bounded alternating Turing machines) completeness for \({\mathrm {coNP}}\) in the deleting/adding cases with a bounded deletion/addition limit, and we obtain completeness for \({\mathrm {NP}}\) in the partition cases with an additional restriction. We also show that for plurality, online control by deleting or adding voters is in \({\mathrm {P}}\), and for partitioning voters is \({\mathrm {coNP}}\) -hard.

Details DOI

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

JAAMAS Journal 2013 Journal Article

Computational complexity and approximability of social welfare optimization in multiagent resource allocation

  • Nhan-Tam Nguyen
  • Trung Thanh Nguyen
  • Jörg Rothe

Abstract A central task in multiagent resource allocation, which provides mechanisms to allocate (bundles of) resources to agents, is to maximize social welfare. We assume resources to be indivisible and nonshareable and agents to express their utilities over bundles of resources, where utilities can be represented in the bundle form, the \(k\) -additive form, and as straight-line programs. We study the computational complexity of social welfare optimization in multiagent resource allocation, where we consider utilitarian and egalitarian social welfare and social welfare by the Nash product. Solving some of the open problems raised by Chevaleyre et al. ( 2006 ) and confirming their conjectures, we prove that egalitarian social welfare optimization is \(\mathrm{NP}\) -complete for the bundle form, and both exact utilitarian and exact egalitarian social welfare optimization are \(\mathrm{DP}\) -complete, each for both the bundle and the \(2\) -additive form, where \(\mathrm{DP}\) is the second level of the boolean hierarchy over \(\mathrm{NP}\). In addition, we prove that social welfare optimization by the Nash product is \(\mathrm{NP}\) -complete for both the bundle and the \(1\) -additive form, and that the exact variants are \(\mathrm{DP}\) -complete for the bundle and the \(3\) -additive form. For utility functions represented as straight-line programs, we show \(\mathrm{NP}\) -completeness for egalitarian social welfare optimization and social welfare optimization by the Nash product. Finally, we show that social welfare optimization by the Nash product in the \(1\) -additive form is hard to approximate, yet we also give fully polynomial-time approximation schemes for egalitarian and Nash product social welfare optimization in the \(1\) -additive form with a fixed number of agents.

Details DOI

AAMAS Conference 2013 Conference Paper

Envy-Ratio and Average-Nash Social Welfare Optimization in Multiagent Resource Allocation

  • Trung Thanh Nguyen
  • Jörg Rothe

The resource allocation problem deals with distributing a number of indivisible, nonshareable resources among a set of agents so as to optimizing social welfare. Assuming all agents to have additive utility functions and focusing on two particular measures of social welfare, envy-ratio and average-Nash product, we investigate the two resulting optimization problems. We give the first hardness of approximation result for a factor better than 3/2 for the problem of minimum envy-ratio, and we design an FPTAS for the case when the number of agents is fixed. For the special case when the number of agents and the number of resources are equal, we show that the problem is even solvable in polynomial time. Next, we propose the first approximation algorithm for maximizing the average-Nash product in the general case, and we prove that this problem admits a PTAS if all agents’ utility functions are the same. Finally, we study the problem of how hard it is to design a truthful mechanism for these two optimization problems.

PDF

TARK Conference 2013 Conference Paper

The Complexity of Online Manipulation of Sequential Elections

  • Edith Hemaspaandra
  • Lane A. Hemachandra
  • Jörg Rothe

Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing one’s voting rule. Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonuniquewinner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first PNP[1] completeness and PNP -completeness results in the field of computational social choice, in particular proving such completeness for, respectively, the complexity of 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.

Details

ECAI Conference 2012 Conference Paper

Controlling Candidate-Sequential Elections

  • Edith Hemaspaandra
  • Lane A. Hemachandra
  • Jörg Rothe

All previous work on "candidate-control" manipulation of elections has been in the model of full-information, simultaneous voting. This is a problem, since in quite a few real-world settings- from TV singing/dancing talent shows to university faculty-hiring processes-candidates are introduced, and appraised by the voters, in sequence. We provide a natural model for sequential candidate evaluation, a framework for evaluating the computational complexity of controlling the outcome within that framework, and some initial results on the range such complexity can take on. We hope our work will lead to further examination of temporally involved candidate control.

Details

ECAI Conference 2012 Conference Paper

Online Voter Control in Sequential Elections

  • Edith Hemaspaandra
  • Lane A. Hemachandra
  • Jörg Rothe

Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters' preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is PSPACE-complete, even if there are only two candidates. In addition, we obtain completeness for coNP in the deleting/adding cases with a bounded deletion/addition limit, and for NP in the partition cases with only one candidate. Finally, we show that for plurality, online control by deleting or adding voters is in P, and for partitioning voters is coNP-hard.

Details

ECAI Conference 2012 Conference Paper

Probabilistic Path-Disruption Games

  • Anja Rey
  • Jörg Rothe

Path-disruption games, recently introduced by Bachrach and Porat [1], are coalitional games played on graphs where one or multiple adversaries each seek to reach a given target vertex from a given source vertex and a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target, for each adversary. We expand their model by allowing uncertainty about the targets. In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it. We study the complexity of various problems related to such games.

Details

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

AAAI Conference 2011 Conference Paper

How to Calibrate the Scores of Biased Reviewers by Quadratic Programming

  • Magnus Roos
  • Jörg Rothe
  • Björn Scheuermann

Peer reviewing is the key ingredient of evaluating the quality of scientific work. Based on the review scores assigned by the individual reviewers to the submissions, program committees of conferences and journal editors decide which papers to accept for publication and which to reject. However, some reviewers may be more rigorous than others, they may be biased one way or the other, and they often have highly subjective preferences over the papers they review. Moreover, each reviewer usually has only a very local view, as he or she evaluates only a small fraction of the submissions. Despite all these shortcomings, the review scores obtained need to be aggregrated in order to globally rank all submissions and to make the acceptance/rejection decision. A common method is to simply take the average of each submission’s review scores, possibly weighted by the reviewers’ confidence levels. Unfortunately, the global ranking thus produced often suffers from a certain unfairness, as the reviewers’ biases and limitations are not taken into account. We propose a method for calibrating the scores of reviewers that are potentially biased and blindfolded by having only partial information. Our method uses a maximum likelihood estimator, which estimates both the bias of each individual reviewer and the unknown “ideal” score of each submission. This yields a quadratic program whose solution transforms the individual review scores into calibrated, globally comparable scores. We argue why our method results in a fairer and more reasonable global ranking than simply taking the average of scores. To show its usefulness, we test our method empirically using real-world data.

PDF Details

ECAI Conference 2010 Conference Paper

Complexity of Merging and Splitting for the Probabilistic Banzhaf Power Index in Weighted Voting Games

  • Anja Rey
  • Jörg Rothe

The Banzhaf power index is a prominent measure of a player's influence for coalition formation in weighted voting games, an important class of simple coalitional games that are fully expressive but compactly representable. For the normalized Banzhaf index, Aziz and Paterson [1] show that it is NP-hard to decide whether merging any coalition of players is beneficial, and that in unanimity games, merging is always disadvantageous, whereas splitting is always advantageous. We show that for the probabilistic Banzhaf index (which is considered more natural than the normalized Banzhaf index), the merging problem is in P for coalitions of size two, and is NP-hard for coalitions of size at least three. We also prove a corresponding result for the splitting problem. In unanimity games and for the probabilistic Banzhaf index (in strong contrast with the results for the normalized Banzhaf index), we show that splitting is always disadvantageous or neutral, whereas merging is neutral for size-two coalitions, yet advantageous for coalitions of size at least three.

Details

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

TCS Journal 2009 Journal Article

Generalized juntas and NP-hard sets

  • Gábor Erdélyi
  • Lane A. Hemaspaandra
  • Jörg Rothe
  • Holger Spakowski

We show that many NP-hard sets have heuristic polynomial-time algorithms with high probability weight of correctness with respect to generalizations of Procaccia and Rosenschein’s junta distributions.

Details DOI

TARK Conference 2009 Conference Paper

The shield that never was: societies with single-peaked preferences are more open to manipulation and control

  • Piotr Faliszewski
  • Edith Hemaspaandra
  • Lane A. Hemachandra
  • Jörg Rothe

Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having singlepeaked preferences, many existing NP-hardness results on manipulation and control evaporate.

Details

TCS Journal 2008 Journal Article

Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions

  • Lane A. Hemaspaandra
  • Jörg Rothe
  • Amitabh Saxena

Rabi and Sherman [M. Rabi, A. Sherman, An observation on associative one-way functions in complexity theory, Information Processing Letters 64 (5) (1997) 239–244; M. Rabi, A. Sherman, Associative one-way functions: A new paradigm for secret-key agreement and digital signatures, Tech. Rep. CS-TR-3183/UMIACS-TR-93-124, Department of Computer Science, University of Maryland, College Park, MD, 1993] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i. e. , p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to P ≠ NP. More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions—equivalently, stand or fall together with P ≠ NP. We look at the four attributes used in Rabi and Sherman’s seminal work on algebraic properties of one-way functions (see [M. Rabi, A. Sherman, An observation on associative one-way functions in complexity theory, Information Processing Letters 64 (5) (1997) 239–244; M. Rabi, A. Sherman, Associative one-way functions: A new paradigm for secret-key agreement and digital signatures, Tech. Rep. CS-TR-3183/UMIACS-TR-93-124, Department of Computer Science, University of Maryland, College Park, MD, 1993]) and subsequent papers–strongness (of noninvertibility), totality, commutativity, and associativity–and for each attribute, we allow it to be required to hold, required to fail, or “don’t care”. In this categorization there are 3 4 = 81 potential types of one-way functions. We prove that each of these 81 feature-laden types stands or falls together with the existence of (plain) one-way functions.

Details DOI

MFCS Conference 2008 Conference Paper

Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control

  • Gábor Erdélyi
  • Markus Nowak
  • Jörg Rothe

Abstract We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [8], with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters’ preference rankings with their approvals of candidates, and we adapt it here so as to keep its useful features with respect to approval strategies even in the presence of control actions. We prove that this system is computationally resistant (i. e. , the corresponding control problems are np -hard) to at least 16 out of 20 types of constructive and destructive control. Thus, for the 20 control types studied here, SP-AV has more resistances to control, by at least two, than is currently known for any other natural voting system with a polynomial-time winner problem.

Details

AIJ Journal 2007 Journal Article

Anyone but him: The complexity of precluding an alternative

  • Edith Hemaspaandra
  • Lane A. Hemaspaandra
  • Jörg Rothe

Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. In particular, we study the ability of an election's chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study—plurality, Condorcet, and approval voting—we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules.

Details DOI

TCS Journal 2006 Journal Article

If P ≠ NP then some strongly noninvertible functions are invertible

  • Lane A. Hemaspaandra
  • Kari Pasanen
  • Jörg Rothe

Rabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility, and show—via explicit cryptographic protocols for secret-key agreement (Rabi and Sherman attribute this protocol to Rivest and Sherman) and digital signatures (Rabi and Sherman)—that strongly noninvertible functions are very useful components in protocol design. Their definition of strong noninvertibility has a small twist (“respecting the argument given”) that is needed to ensure cryptographic usefulness. In this paper, we show that this small twist has a consequence: unless P = NP, some strongly noninvertible functions are invertible.

Details DOI

MFCS Conference 2005 Conference Paper

An Exact 2. 9416 n Algorithm for the Three Domatic Number Problem

  • Tobias Riege
  • Jörg Rothe

Abstract The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i. e. , sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3 n, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2. 9416 n. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.

Details

TCS Journal 2000 Journal Article

A second step towards complexity-theoretic analogs of Rice's Theorem

  • Lane A. Hemaspaandra
  • Jörg Rothe

Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan (1997) initiated the search for complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.

Details DOI

TCS Journal 2000 Journal Article

Characterizing the existence of one-way permutations

  • Lane A. Hemaspaandra
  • Jörg Rothe

We establish a condition necessary and sufficient for the existence of one-way permutations: One-way permutations exist if and only if there exist total one-one one-way functions whose range is P-rankable.

Details DOI

MFCS Conference 1998 Conference Paper

A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem

  • Lane A. Hemachandra
  • Jörg Rothe

Abstract Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan [BS97] initiated the search for circuit complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.

Details

TCS Journal 1998 Journal Article

Boolean operations, joins, and the extended low hierarchy

  • Lane A. Hemaspaandra
  • Zhigen Jiang
  • Jörg Rothe
  • Osamu Watanabe

We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the second level of the extended low hierarchy, EL2, yet their join is in EL2. That is, in terms of extended lowness, the join operator can lower complexity. Since in a strong intuitive sense the join does not lower complexity, our result suggests that the extended low hierarchy is unnatural as a complexity measure. We also study the closure properties of EL2 and prove that EL2 is not closed under certain Boolean operations. To this end, we establish the first known (and optimal) EL2 lower bounds for certain notions generalizing P-selectivity, which may be regarded as an interesting result in its own right.

Details DOI

MFCS Conference 1998 Conference Paper

Tally NP Sets and Easy Census Functions

  • Judy Goldsmith
  • Mitsunori Ogihara
  • Jörg Rothe

Abstract We study the question of whether every P set has an easy (i. e. , polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as \(\# P_1 \subseteq FP\), where #P 1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P PH 1 function can be computed in \(FP^{\# P_1 ^{\# P_1 } }\). Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption \(\# P_1 \subseteq FP\) implies P = BPP and \(PH \subseteq MOD_k P\) for each k ≥ 2, which provides further evidence that not all sets in P have an easy census function. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be n α -enumerated in time n β for fixed α and Β) than that it can be precisely computed in polynomial time.

Details