Felix Brandt

AAMAS Conference 2026 Conference Paper

Majoritarian Assignment Rules

• Felix Brandt
• Haoyuan Chen
• Chris Dong
• Patrick Lederer
• Alexander Schlenga

A central problem in multiagent systems is the fair assignment of objects to agents. In this paper, we initiate the analysis of classic majoritarian social choice functions in assignment. Exploiting the special structure of the assignment domain, we show a number of surprising results with no counterparts in general social choice. In particular, we establish a near one-to-one correspondence between preference profiles and majority graphs. This correspondence implies that key properties of assignments—such as Pareto-optimality, least unpopularity, and mixed popularity—can be determined solely by the associated majority graph. We further show that all Paretooptimal assignments are semi-popular and belong to the top cycle. Elements of the top cycle can thus easily be found via serial dictatorships. Our main result is a complete characterization of the top cycle, which implies the top cycle can only consist of one, two, all but two, all but one, or all assignments. By contrast, we find that the uncovered set contains only very few assignments.

AAAI Conference 2025 Conference Paper

Weak Strategyproofness in Randomized Social Choice

• Felix Brandt
• Patrick Lederer

An important - but very demanding - property in collective decision-making is strategyproofness, which requires that voters cannot benefit from submitting insincere preferences. Gibbard (1977) has shown that only rather unattractive rules are strategyproof, even when allowing for randomization. However, Gibbard's theorem is based on a rather strong interpretation of strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for at least one utility function consistent with his ordinal preferences. In this paper, we study weak strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for all utility functions consistent with his ordinal preferences. We show how to systematically design attractive, weakly strategyproof social decision schemes (SDSs) and explore their limitations for both strict and weak preferences. In particular, for strict preferences, we show that there are weakly strategyproof SDSs that are either ex post efficient or Condorcet-consistent, while neither even-chance SDSs nor pairwise SDSs satisfy both properties and weak strategyproofness at the same time. By contrast, for the case of weak preferences, we discuss two sweeping impossibility results that preclude the existence of appealing weakly strategyproof SDSs.

JAIR Journal 2024 Journal Article

On the Convergence of Swap Dynamics to Pareto-Optimal Matchings

• Felix Brandt
• Anaëlle Wilczynski

We study whether Pareto-optimal stable matchings can be reached via pairwise swaps in one-to-one matching markets with initial assignments. We consider housing markets, marriage markets, and roommate markets as well as three different notions of swap rationality. Our main results are as follows. While it can be efficiently determined whether a Pareto-optimal stable matching can be reached when defining swaps via blocking pairs, checking whether this is the case for all such sequences is computationally intractable. When defining swaps such that all involved agents need to be better off, even deciding whether a Pareto-optimal stable matching can be reached via some sequence is intractable. This confirms and extends a conjecture made by Damamme, Beynier, Chevaleyre, and Maudet (2015) who have shown that convergence to a Pareto-optimal matching is guaranteed in housing markets with single-peaked preferences. We prove that in marriage and roommate markets, single-peakedness is not sufficient for this to hold, but the stronger restriction of one-dimensional Euclidean preferences is.

AIJ Journal 2024 Journal Article

Stability based on single-agent deviations in additively separable hedonic games

• Felix Brandt
• Martin Bullinger
• Leo Tappe

Coalition formation is a central concern in multiagent systems. A common desideratum for coalition structures is stability, defined by the absence of beneficial deviations of single agents. Such deviations require an agent to improve her utility by joining another coalition. On top of that, the feasibility of deviations may also be restricted by demanding consent of agents in the welcoming and/or the abandoned coalition. While most of the literature focuses on deviations constrained by unanimous consent, we also study consent decided by majority vote and introduce two new stability notions that can be seen as local variants of another solution concept called popularity. We investigate stability in additively separable hedonic games by pinpointing boundaries to computational complexity depending on the type of consent and friend-oriented utility restrictions. The latter restrictions shed new light on well-studied classes of games based on the appreciation of friends or the aversion to enemies. Many of our positive results follow from a new combinatorial observation that we call the Deviation Lemma and that we leverage to prove the convergence of simple and natural single-agent dynamics under fairly general conditions. Our negative results, in particular, resolve the complexity of contractual Nash stability in additively separable hedonic games.

AAMAS Conference 2023 Conference Paper

Strategyproof Social Decision Schemes on Super Condorcet Domains

• Felix Brandt
• Patrick Lederer
• Sascha Tausch

One of the central economic paradigms in multi-agent systems is that agents should not be better off by acting dishonestly. In the context of collective decision-making, this axiom is known as strategyproofness and turns out to be rather prohibitive, even when allowing for randomization. In particular, Gibbard’s random dictatorship theorem shows that only rather unattractive social decision schemes (SDSs) satisfy strategyproofness on the full domain of preferences. In this paper, we obtain more positive results by investigating strategyproof SDSs on the Condorcet domain, which consists of all preference profiles that admit a Condorcet winner. In more detail, we show that, if the number of voters 𝑛 is odd, every strategyproof and non-imposing SDS on the Condorcet domain can be represented as a mixture of dictatorial SDSs and the Condorcet rule (which chooses the Condorcet winner with probability 1). Moreover, we prove that the Condorcet domain is a maximal connected domain that allows for attractive strategyproof SDSs if 𝑛 is odd as only random dictatorships are strategyproof and nonimposing on any sufficiently connected superset of it. We also derive analogous results for even 𝑛 by slightly extending the Condorcet domain. Finally, we also characterize the set of group-strategyproof and non-imposing SDSs on the Condorcet domain and its supersets. These characterizations strengthen Gibbard’s random dictatorship theorem and establish that the Condorcet domain is essentially a maximal domain that allows for attractive strategyproof SDSs.

JAIR Journal 2022 Journal Article

Finding and Recognizing Popular Coalition Structures

• Felix Brandt
• Martin Bullinger

An important aspect of multi-agent systems concerns the formation of coalitions that are stable or optimal in some well-defined way. The notion of popularity has recently received a lot of attention in this context. A partition is popular if there is no other partition in which more agents are better off than worse off. In this paper, we study popularity, strong popularity, and mixed popularity (which is particularly attractive because existence is guaranteed by the Minimax Theorem) in a variety of coalition formation settings. Extending previous work on marriage games, we show that mixed popular partitions in roommate games can be found efficiently via linear programming and a separation oracle. This approach is quite universal, leading to efficient algorithms for verifying whether a given partition is popular and for finding strongly popular partitions (resolving an open problem). By contrast, we prove that both problems become computationally intractable when moving from coalitions of size 2 to coalitions of size 3, even when preferences are strict and globally ranked. Moreover, we show that finding popular, strongly popular, and mixed popular partitions in symmetric additively separable hedonic games and symmetric fractional hedonic games is NP-hard. Together, these results indicate strong boundaries to the tractability of popularity in both ordinal and cardinal models of hedonic games.

IJCAI Conference 2022 Conference Paper

Incentives in Social Decision Schemes with Pairwise Comparison Preferences

• Felix Brandt
• Patrick Lederer
• Warut Suksompong

Social decision schemes (SDSs) map the preferences of individual voters over multiple alternatives to a probability distribution over the alternatives. In order to study properties such as efficiency, strategyproofness, and participation for SDSs, preferences over alternatives are typically lifted to preferences over lotteries using the notion of stochastic dominance (SD). However, requiring strategyproofness or strict participation with respect to this preference extension only leaves room for rather undesirable SDSs such as random dictatorships. Hence, we focus on the natural but little understood pairwise comparison (PC) preference extension, which postulates that one lottery is preferred to another if the former is more likely to return a preferred outcome. In particular, we settle three open questions raised by Brandt in Rolling the dice: Recent results in probabilistic social choice (2017): (i) there is no Condorcet-consistent SDS that satisfies PC-strategyproofness; (ii) there is no anonymous and neutral SDS that satisfies PC-efficiency and PC-strategyproofness; and (iii) there is no anonymous and neutral SDS that satisfies PC-efficiency and strict PC-participation. All three impossibilities require m>=4 alternatives and turn into possibilities when m<=3.

JAIR Journal 2022 Journal Article

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

• Felix Brandt
• Martin Bullinger
• Patrick Lederer

Social choice functions (SCFs) map the preferences of a group of agents over some set of alternatives to a non-empty subset of alternatives. The Gibbard-Satterthwaite theorem has shown that only extremely restrictive SCFs are strategyproof when there are more than two alternatives. For set-valued SCFs, or so-called social choice correspondences, the situation is less clear. There are miscellaneous -- mostly negative -- results using a variety of strategyproofness notions and additional requirements. The simple and intuitive notion of Kelly-strategyproofness has turned out to be particularly compelling because it is weak enough to still allow for positive results. For example, the Pareto rule is strategyproof even when preferences are weak, and a number of attractive SCFs (such as the top cycle, the uncovered set, and the essential set) are strategyproof for strict preferences. In this paper, we show that, for weak preferences, only indecisive SCFs can satisfy strategyproofness. In particular, (i) every strategyproof rank-based SCF violates Pareto-optimality, (ii) every strategyproof support-based SCF (which generalize Fishburn's C2 SCFs) that satisfies Pareto-optimality returns at least one most preferred alternative of every voter, and (iii) every strategyproof non-imposing SCF returns the Condorcet loser in at least one profile. We also discuss the consequences of these results for randomized social choice.

AAMAS Conference 2022 Conference Paper

Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes

• Felix Brandt
• Patrick Lederer
• René Romen

Social decision schemes (SDSs) map the preferences of a group of voters over some set of 𝑚 alternatives to a probability distribution over the alternatives. A seminal characterization of strategyproof SDSs by Gibbard implies that there are no strategyproof Condorcet extensions and that only random dictatorships satisfy ex post efficiency and strategyproofness. The latter is known as the random dictatorship theorem. We relax Condorcet-consistency and ex post efficiency by introducing a lower bound on the probability of Condorcet winners and an upper bound on the probability of Pareto-dominated alternatives, respectively. We then show that the SDS that assigns probabilities proportional to Copeland scores is the only anonymous, neutral, and strategyproof SDS that can guarantee the Condorcet winner a probability of at least 2/𝑚. Moreover, no strategyproof SDS can exceed this bound, even when dropping anonymity and neutrality. Secondly, we prove a continuous strengthening of Gibbard’s random dictatorship theorem: the less probability we put on Pareto-dominated alternatives, the closer to a random dictatorship is the resulting SDS. Finally, we show that the only anonymous, neutral, and strategyproof SDSs that maximize the probability of Condorcet winners while minimizing the probability of Pareto-dominated alternatives are mixtures of the uniform random dictatorship and the randomized Copeland rule.

AAAI Conference 2022 Conference Paper

Single-Agent Dynamics in Additively Separable Hedonic Games

• Felix Brandt
• Martin Bullinger
• Leo Tappe

The formation of stable coalitions is a central concern in multiagent systems. A considerable stream of research defines stability via the absence of beneficial deviations by single agents. Such deviations require an agent to improve her utility by joining another coalition while possibly imposing further restrictions on the consent of the agents in the welcoming as well as the abandoned coalition. While most of the literature focuses on unanimous consent, we also study consent decided by majority vote, and introduce two new stability notions that can be seen as local variants of popularity. We investigate these notions in additively separable hedonic games by pinpointing boundaries to computational complexity depending on the type of consent and restrictions on the utility functions. The latter restrictions shed new light on well-studied classes of games based on the appreciation of friends or the aversion to enemies. Many of our positive results follow from the Deviation Lemma, a general combinatorial observation, which can be leveraged to prove the convergence of simple and natural single-agent dynamics under fairly general conditions.

AAMAS Conference 2021 Conference Paper

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

• Felix Brandt
• Martin Bullinger
• Patrick Lederer

Social choice functions (SCFs) map the preferences of a group of agents over some set of alternatives to a non-empty subset of alternatives. The Gibbard-Satterthwaite theorem has shown that only extremely unattractive single-valued SCFs are strategyproof when there are more than two alternatives. For set-valued SCFs, or so-called social choice correspondences, the situation is less clear. There are miscellaneous—mostly negative—results using a variety of strategyproofness notions and additional requirements. The simple and intuitive notion of Kelly-strategyproofness has turned out to be particularly compelling because it is weak enough to still allow for positive results. For example, the Pareto rule is strategyproof even when preferences are weak, and a number of attractive SCFs (such as the top cycle, the uncovered set, and the essential set) are strategyproof for strict preferences. In this paper, we show that, for weak preferences, only indecisive SCFs can satisfy strategyproofness. In particular, (i) every strategyproof rank-based SCF violates Pareto-optimality, (ii) every strategyproof support-based SCF (which generalize Fishburn’s C2 SCFs) that satisfies Paretooptimality returns at least one most preferred alternative of every voter, and (iii) every strategyproof non-imposing SCF returns a Condorcet loser in at least one profile.

AAAI Conference 2021 Conference Paper

Reaching Individually Stable Coalition Structures in Hedonic Games

• Felix Brandt
• Martin Bullinger
• Anaëlle Wilczynski

The formal study of coalition formation in multiagent systems is typically realized using so-called hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has received little attention. In this paper, we study the convergence of simple dynamics leading to stable partitions in a variety of classes of hedonic games, including anonymous, dichotomous, fractional, and hedonic diversity games. The dynamics we consider is based on individual stability: an agent will join another coalition if she is better off and no member of the welcoming coalition is worse off. We identify conditions for convergence, provide elaborate counterexamples of existence of individually stable partitions, and study the computational complexity of problems related to the coalition formation dynamics. In particular, we settle open problems suggested by Bogomolnaia and Jackson (2002), Brandl, Brandt, and Strobel (2015), and Boehmer and Elkind (2020).

AAMAS Conference 2019 Conference Paper

Exploring the No-Show Paradox for Condorcet Extensions Using Ehrhart Theory and Computer Simulations

• Felix Brandt
• Johannes Hofbauer
• Martin Strobel

Results from voting theory are increasingly used when dealing with collective decision making in computational multiagent systems. An important and surprising phenomenon in voting theory is the No-Show Paradox (NSP), which occurs if a voter is better off by abstaining from an election. While it is known that certain voting rules suffer from this paradox in principle, the extent to which it is of practical concern is not well understood. We aim at filling this gap by analyzing the likelihood of the NSP for six Condorcet extensions (Black’s rule, Baldwin’s rule, Nanson’s rule, MaxiMin, Tideman’s rule, and Copeland’s rule) under various preference models using Ehrhart theory as well as extensive computer simulations. We find that, for few alternatives, the probability of the NSP is rather small (less than 4% for four alternatives and all considered preference models, except for Copeland’s rule). As the number of alternatives increases, the NSP becomes much more likely and which rule is most susceptible to abstention strongly depends on the underlying distribution of preferences.

JAIR Journal 2019 Journal Article

Strategic Abstention based on Preference Extensions: Positive Results and Computer-Generated Impossibilities

• Florian Brandl
• Felix Brandt
• Christian Geist
• Johannes Hofbauer

Voting rules allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly's and Fishburn's preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives and seven agents, every Pareto-optimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn's extension. This is achieved by reducing the statement to a finite - yet very large - problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly's extension and give examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.

IJCAI Conference 2018 Conference Paper

An Analytical and Experimental Comparison of Maximal Lottery Schemes

• Florian Brandl
• Felix Brandt
• Christian Stricker

Randomized voting rules are gaining increasing attention in computational and non-computational social choice. A particularly interesting class of such rules are maximal lottery (ML) schemes, which were proposed by Peter Fishburn in 1984 and have been repeatedly recommended for practical use. However, the subtle differences between different ML schemes are often ignored. Two canonical subsets of ML schemes are C1-ML schemes (which only depend on unweighted majority comparisons) and C2-ML schemes (which only depend on weighted majority comparisons). We prove that C2-ML schemes are the only Pareto efficient---but also among the most manipulable---ML schemes. Furthermore, we evaluate the frequency of manipulable preference profiles and the degree of randomization of ML schemes via extensive computer simulations. In general, ML schemes are rarely manipulable and often do not randomize at all, especially when there are only few alternatives. For up to 21 alternatives, the average support size of ML schemes lies below 4 under reasonable assumptions. The average degree of randomization (in terms of Shannon entropy) of C2-ML schemes is significantly lower than that of C1-ML schemes.

AAMAS Conference 2018 Conference Paper

Voting with Ties: Strong Impossibilities via SAT Solving

• Felix Brandt
• Christian Saile
• Christian Stricker

Voting rules allow groups of agents to aggregate their preferences in order to reach joint decisions. The Gibbard-Satterthwaite theorem, a seminal result in social choice theory, implies that, when agents have strict preferences, all anonymous, Pareto-optimal, and single-valued voting rules can be strategically manipulated. In this paper, we consider multi-agent voting when there can be ties in the preferences as well as in the outcomes. These assumptions are extremely natural—especially when there are large numbers of alternatives—and enable us to prove much stronger results than in the overly restrictive setting of strict preferences. In particular, we show that (i) all anonymous Pareto-optimal rules where ties are broken according to the preferences of a chairman or by means of even-chance lotteries are manipulable, and that (ii) all pairwise Pareto-optimal rules are manipulable, no matter how ties are broken. These results are proved by reducing the statements to finite—yet very large—problems, which are encoded as formulas in propositional logic and then shown to be unsatisfiable by a SAT solver. We also extracted human-readable proofs from minimal unsatisfiable cores of the formulas in question, which were in turn verified by an interactive higher-order theorem prover.

AAMAS Conference 2017 Conference Paper

Majority Graphs of Assignment Problems and Properties of Popular Random Assignments

• Felix Brandt
• Johannes Hofbauer
• Martin Suderland

Randomized mechanisms for assigning objects to individual agents have received increasing attention by computer scientists as well as economists. In this paper, we study a property of random assignments, called popularity, which corresponds to the well-known notion of Condorcet-consistency in social choice theory. Our contribution is threefold. First, we define a simple condition that characterizes whether two assignment problems induce the same majority graph and which can be checked in polynomial time. Secondly, we analytically and experimentally investigate the uniqueness of popular random assignments. Finally, we prove that popularity is incompatible with very weak notions of both strategyproofness and envy-freeness. This settles two open problems by Aziz et al. [3] and reveals an interesting tradeoff between social and individual goals in random assignment. General Terms Economics, Theory

AAMAS Conference 2017 Conference Paper

Random Assignment with Optional Participation

• Florian Brandl
• Felix Brandt
• Johannes Hofbauer

A central problem in multiagent systems concerns the fair assignment of objects to agents. We initiate the study of randomized assignment rules with optional participation and investigate whether agents always benefit from participating in the assignment mechanism. Our results are largely positive, irrespective of the strategyproofness of the considered rules. In particular, random serial dictatorship, the probabilistic serial rule, and the Boston mechanism strictly incentivize single agents to participate, no matter what their underlying utility functions are. Random serial dictatorship and the probabilistic serial rule also cannot be manipulated by groups of agents who abstain strategically. These results stand in contrast to results for the more general domain of voting where many rules suffer from the so-called “no-show paradox”. We also show that rules that return popular random assignments may disincentivize participation for some (but never all) utility representations consistent with the agents’ ordinal preferences. General Terms Economics, Theory

AAMAS Conference 2016 Conference Paper

Analyzing the Practical Relevance of Voting Paradoxes via Ehrhart Theory, Computer Simulations, and Empirical Data

• Felix Brandt
• Christian Geist
• Martin Strobel

Results from social choice theory are increasingly used to argue about collective decision making in computational multiagent systems. A large part of the social choice literature studies voting paradoxes in which seemingly mild properties are violated by common voting rules. In this paper, we investigate the likelihood of the Condorcet Loser Paradox (CLP) and the Agenda Contraction Paradox (ACP) using Ehrhart theory, computer simulations, and empirical data. We present the first analytical results for the CLP on four alternatives and show that our experimental results, which go well beyond four alternatives, are in almost perfect congruence with the analytical results. It turns out that the CLP—which is often cited as a major flaw of some Condorcet extensions such as Dodgson’s rule, Young’s rule, and MaxiMin—is of no practical relevance. The ACP, on the other hand, frequently occurs under various distributional assumptions about the voters’ preferences. The extent to which it is real threat, however, strongly depends on the voting rule, the underlying distribution of preferences, and, somewhat surprisingly, the parity of the number of voters.

JAIR Journal 2016 Journal Article

Finding Strategyproof Social Choice Functions via SAT Solving

• Felix Brandt
• Christian Geist

A promising direction in computational social choice is to address research problems using computer-aided proving techniques. In particular with SAT solvers, this approach has been shown to be viable not only for proving classic impossibility theorems such as Arrow's Theorem but also for finding new impossibilities in the context of preference extensions. In this paper, we demonstrate that these computer-aided techniques can also be applied to improve our understanding of strategyproof irresolute social choice functions. These functions, however, requires a more evolved encoding as otherwise the search space rapidly becomes much too large. Our contribution is two-fold: We present an efficient encoding for translating such problems to SAT and leverage this encoding to prove new results about strategyproofness with respect to Kelly's and Fishburn's preference extensions. For example, we show that no Pareto-optimal majoritarian social choice function satisfies Fishburn-strategyproofness. Furthermore, we explain how human-readable proofs of such results can be extracted from minimal unsatisfiable cores of the corresponding SAT formulas.

AAMAS Conference 2016 Conference Paper

Optimal Bounds for the No-Show Paradox via SAT Solving

• Felix Brandt
• Christian Geist
• Dominik Peters

Voting rules allow multiple agents to aggregate their preferences in order to reach joint decisions. Perhaps one of the most important desirable properties in this context is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result in social choice theory by Moulin [28] has shown that Condorcetconsistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin’s result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.

IJCAI Conference 2016 Conference Paper

Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving

• Florian Brandl
• Felix Brandt
• Christian Geist

Two important requirements when aggregating the preferences of multiple agents are that the outcome should be economically efficient and the aggregation mechanism should not be manipulable. In this paper, we provide a computer-aided proof of a sweeping impossibility using these two conditions for randomized aggregation mechanisms. More precisely, we show that every efficient aggregation mechanism can be manipulated for all expected utility representations of the agents' preferences. This settles a conjecture by Aziz et al. [2013b] and strengthens a number of existing theorems, including statements that were shown within the special domain of assignment. Our proof is obtained by formulating the claim as a satisfiability problem over predicates from real-valued arithmetic, which is then checked using an SMT (satisfiability modulo theories) solver. To the best of our knowledge, this is the first application of SMT solvers in computational social choice.

JAIR Journal 2015 Journal Article

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

• Felix Brandt
• Markus Brill
• Edith Hemaspaandra
• Lane A. Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates---single-peaked preferences---those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems---including those for Kemeny and Llull elections---fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

IJCAI Conference 2015 Conference Paper

Strategic Abstention Based on Preference Extensions: Positive Results and Computer-Generated Impossibilities

• Florian Brandl
• Felix Brandt
• Christian Geist
• Johannes Hofbauer

Voting rules are powerful tools that allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly’s and Fishburn’s preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives, every Paretooptimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn’s extension. This is achieved by reducing the statement to a finite—yet very large—problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly’s extension. We conclude by giving examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.

AAAI Conference 2014 Conference Paper

Extending Tournament Solutions

• Felix Brandt
• Markus Brill
• Paul Harrenstein

An important subclass of social choice functions, so-called majoritarian (or C1) functions, only take into account the pairwise majority relation between alternatives. In the absence of majority ties—e. g. , when there is an odd number of agents with linear preferences—the majority relation is antisymmetric and complete and can thus conveniently be represented by a tournament. Tournaments have a rich mathematical theory and many formal results for majoritarian functions assume that the majority relation constitutes a tournament. Moreover, most majoritarian functions have only been defined for tournaments and allow for a variety of generalizations to unrestricted preference profiles, none of which can be seen as the unequivocal extension of the original function. In this paper, we argue that restricting attention to tournaments is justified by the existence of a conservative extension, which inherits most of the commonly considered properties from its underlying tournament solution.

AAAI Conference 2014 Conference Paper

On the Incompatibility of Efficiency and Strategyproofness in Randomized Social Choice

• Haris Aziz
• Florian Brandl
• Felix Brandt

Efficiency—no agent can be made better off without making another one worse off—and strategyproofness—no agent can obtain a more preferred outcome by misrepresenting his preferences—are two cornerstones of economics and ubiquitous in important areas such as voting, auctions, or matching markets. Within the context of random assignment, Bogomolnaia and Moulin have shown that two particular notions of efficiency and strategyproofness based on stochastic dominance are incompatible. However, there are various other possibilities of lifting preferences over alternatives to preferences over lotteries apart from stochastic dominance. In this paper, we give an overview of common preference extensions, propose two new ones, and show that the abovementioned incompatibility can be extended to various other notions of strategyproofness and efficiency in randomized social choice.

AIJ Journal 2013 Journal Article

Computing desirable partitions in additively separable hedonic games

• Haris Aziz
• Felix Brandt
• Hans Georg Seedig

An important aspect in systems of multiple autonomous agents is the exploitation of synergies via coalition formation. Additively separable hedonic games are a fundamental class of coalition formation games in which each player has a value for any other player and the value of a coalition to a particular player is simply the sum of the values he assigns to the members of his coalition. In this paper, we consider a number of solution concepts from cooperative game theory, welfare theory, and social choice theory as criteria for desirable partitions in hedonic games. We then conduct a detailed computational analysis of computing, checking the existence of, and verifying stable, fair, optimal, and popular partitions for additively separable hedonic games.

TCS Journal 2011 Journal Article

Equilibria of graphical games with symmetries

• Felix Brandt
• Felix Fischer
• Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetry in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in general for all four types. Using a characterization of games with pure equilibria in terms of even cycles in the neighborhood graph, as well as a connection to a generalized satisfiability problem, we identify tractable subclasses of the games satisfying the most restrictive type of symmetry. Hardness for a different subclass leads us to identify a satisfiability problem that remains NP-hard in the presence of a matching, a result that may be of independent interest. Finally, games with symmetries of two of the four types are shown to possess a symmetric mixed equilibrium which can be computed in polynomial time. We thus obtain a natural class of games where the pure equilibrium problem is computationally harder than the mixed equilibrium problem, unless P=NP.

IJCAI Conference 2011 Conference Paper

Group-Strategyproof Irresolute Social Choice Functions

• Felix Brandt

An important problem in voting is that agents may misrepresent their preferences in order to obtain a more preferred outcome. Unfortunately, this phenomenon has been shown to be inevitable in the case of resolute, i. e. , single-valued, social choice functions. In this paper, we introduce a variant of Maskin-monotonicity that completely characterizes the class of pairwise irresolute social choice functions that are group-strategyproof according to Kelly's preference extension. The class is narrow but contains a number of appealing Condorcet extensions such as the minimal covering set and the bipartisan set, thereby answering a question raised independently by Barbera (1977) and Kelly (1977). These functions furthermore encourage participation and thus do not suffer from the no-show paradox (under Kelly's extension).

IJCAI Conference 2011 Conference Paper

On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions

• Felix Brandt
• Markus Brill
• Hans Georg Seedig

Tournament solutions, i. e. , functions that associate with each complete and asymmetric relation on a set of alternatives a non-empty subset of the alternatives, play an important role within social choice theory and the mathematical social sciences at large. Laffond et al. have shown that various tournament solutions satisfy composition-consistency, a structural invariance property based on the similarity of alternatives. We define the decomposition degree of a tournament as a parameter that reflects its decomposability and show that computing any composition-consistent tournament solution is fixed-parameter tractable with respect to the decomposition degree. Furthermore, we experimentally investigate the decomposition degree of two natural distributions of tournaments and its impact on the running time of computing the tournament equilibrium set.

IJCAI Conference 2011 Conference Paper

Optimal Partitions in Additively Separable Hedonic Games

• Haris Aziz
• Felix Brandt
• Hans Georg Seedig

We conduct a computational analysis of fair and optimal partitions in additively separable hedonic games. We show that, for strict preferences, a Pareto optimal partition can be found in polynomial time while verifying whether a given partition is Pareto optimal is coNP-complete, even when preferences are symmetric and strict. Moreover, computing a partition with maximum egalitarian or utilitarian social welfare or one which is both Pareto optimal and individually rational is NP-hard. We also prove that checking whether there exists a partition which is both Pareto optimal and envy-free is &Sigma; 2p-complete. Even though an envy-free partition and a Nash stable partition are both guaranteed to exist for symmetric preferences, checking whether there exists a partition which is both envy-free and Nash stable is NP-complete.

AAMAS Conference 2011 Conference Paper

Stable Partitions in Additively Separable Hedonic Games

• Haris Aziz
• Felix Brandt
• Hans Georg Seedig

An important aspect in systems of multiple autonomous agents is the exploitation of synergies via coalition formation. In this paper, we solve various open problems concerning the computational complexity of stable partitions in additively separable hedonic games. First, we propose a polynomial-time algorithm to compute a contractually individually stable partition. This contrasts with previous results such as the NP-hardness of computing individually stable or Nash stable partitions. Secondly, we prove that checking whether the core or the strict core exists is NP-hard in the strong sense even if the preferences of the players are symmetric. Finally, it is shown that verifying whether a partition consisting of the grand coalition is contractual strict core stable or Pareto optimal is coNP-complete.

AAAI Conference 2010 Conference Paper

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

• Felix Brandt
• Markus Brill
• Edith Hemaspaandra
• Lane Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates—single-peaked preferences—those protections vanish. By using singlepeaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems—including those for Kemeny and Llull elections—fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partitionof-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θp 2-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

AAMAS Conference 2010 Conference Paper

Minimal Retentive Sets in Tournaments

• Felix Brandt
• Markus Brill
• Felix Fischer
• Paul Harrenstein

Many problems in multiagent decision making can be addressed using tournament solutions, i. e. , functions that associate with each completeand asymmetric relation on a set of alternatives a non-empty subset of the alternatives. For any given tournemant solution $S$, there is another tournament solution $\dot{S}$, which returns the union of all inclusion-minimal sets that satisfy S-retentiveness, a natural stability criterion with respect to S. Schwartz's tournament equilibrium set ($TEQ$) is then defined as $TEQ = T\dot{E}Q$. Due to this unwieldy recursive definition, preciously little is known about $TEQ$. Contingent on a well-known conjecture about $TEQ$, we show that $\dot{S}$ inherits a number of important and desirable properties from $S$. We thus obtain an infinite hierarchy of attractive and efficiently computable tournament solutions that "approximate" $TEQ$, which itself is intractable. This hierarchy contains well-known tournament solutions such as the top cycle ($TC$) and the minimal covering set ($MC$). We further pove a weaker version of the conjecture mentioned above, which establishes $\dot{T}C$ as an attractive new tournament solution.

AAMAS Conference 2010 Conference Paper

Monotone cooperative games and their threshold versions

• Haris Aziz
• Felix Brandt
• Paul Harrenstein

Cooperative games provide an appropriate framework forfair and stable resource allocation in multiagent systems. This paper focusses on monotone cooperative games, a classwhich comprises a variety of games that have enjoyed specialattention within AI, in particular, skill games, connectivity games, flow games, voting games, and matching games. Given a threshold, each monotone cooperative game naturally corresponds to a simple game. The core of a thresholdversion may be empty, even if that is not the case in themonotonic game itself. For each of the subclasses of monotonic games mentioned above, we conduct a computationalanalysis of problems concerning some relaxations of the coresuch as the least-core and the cost of stability. It is shownthat threshold versions of monotonic games are generallyat least as hard to handle computationally. We also introduce the length of a simple game as the size of the smallestwinning coalition and study its computational complexityin various classes of simple games and its relationship withcomputing core-based solutions. A number of computationalhardness results are contrasted with polynomial time algorithms to compute the length of threshold matching gamesand the cost of stability of matching games, spanning connectivity games, and simple coalitional skill games with aconstant number of skills.

AAMAS Conference 2009 Conference Paper

Computational Aspects of Shapley's Saddles

• Felix Brandt
• Markus Brill
• Felix Fischer
• Paul Harrenstein

Game-theoretic solution concepts, such as Nash equilibrium, are playing an ever increasing role in the study of systems of autonomous computational agents. A common criticism of Nash equilibrium is that its existence relies on the possibility of randomizing over actions, which in many cases is deemed unsuitable, impractical, or even infeasible. In work dating back to the early 1950s Lloyd Shapley proposed ordinal setvalued solution concepts for zero-sum games that he refers to as strict and weak saddles. These concepts are intuitively appealing, they always exist, and are unique in important subclasses of games. We initiate the study of computational aspects of Shapley’s saddles and provide polynomial-time algorithms for computing strict saddles in normal-form games and weak saddles in a subclass of symmetric zero-sum games. On the other hand, we show that certain problems associated with weak saddles in bimatrix games are NP-hard. Finally, we extend our results to mixed refinements of Shapley’s saddles introduced by Duggan and Le Breton.

AIJ Journal 2009 Journal Article

Ranking games

• Felix Brandt
• Felix Fischer
• Paul Harrenstein
• Yoav Shoham

The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann–Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.

AAAI Conference 2008 Conference Paper

A Computational Analysis of the Tournament Equilibrium Set

• Felix Brandt
• Paul Harrenstein

A recurring theme in AI and multiagent systems is how to select the “most desirable” elements given a binary dominance relation on a set of alternatives. Schwartz’s tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions proposed so far in this context. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive solution concept refining both the Banks set and Dutta’s minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard. Furthermore, we propose a heuristic that significantly outperforms the naive algorithm for computing TEQ. Early experimental results support the conjecture that TEQ is indeed monotonic.

IJCAI Conference 2007 Conference Paper

• Felix Brandt
• Felix Fischer
• Paul Harrenstein
• Yoav Shoham

This paper is a comparative study of game-theoretic solution concepts in strictly competitive multiagent scenarios, as commonly encountered in the context of parlor games, competitive economic situations, and some social choice settings. We model these scenarios as ranking games in which every outcome is a ranking of the players, with higher ranks being preferred over lower ones. Rather than confining our attention to one particular solution concept, we give matching upper and lower bounds for various comparative ratios of solution concepts within ranking games. The solution concepts we consider in this context are security level strategies (maximin), Nash equilibrium, and correlated equilibrium. Additionally, we also examine quasi-strict equilibrium, an equilibrium refinement proposed by Harsanyi, which remedies some apparent shortcomings of Nash equilibrium when applied to ranking games. In particular, we compute the price of cautiousness, i. e. , the worst-possible loss an agent may incur by playing maximin instead of the worst (quasi-strict) Nash equilibrium, the mediation value, i. e. , the ratio between the social welfare obtained in the best correlated equilibrium and the best Nash equilibrium, and the enforcement value, i. e. , the ratio between the highest obtainable social welfare and that of the best correlated equilibrium.

IJCAI Conference 2007 Conference Paper

• Felix Brandt
• Tuomas Sandholm
• Yoav Shoham

We study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize a convex combination of their own profit and their competitors' losses. The motivation for this assumption stems from inherent spitefulness or, for example, from competitive scenarios such as in closed markets where the loss of a competitor will likely result in future gains for oneself. We derive symmetric Bayes Nash equilibria for spiteful agents in first-price and second-price sealed-bid auctions. In first-price auctions, bidders become "more truthful" the more spiteful they are. Surprisingly, the equilibrium strategy in second-price auctions does not depend on the number of bidders. Based on these equilibria, we compare the revenue in both auction types. It turns out that expected revenue in second-price auctions is higher than expected revenue in first-price auctions in the case of even the most modestly spiteful agents, provided they still care at least at little for their own profit. In other words, revenue equivalence only holds for auctions in which all agents are either self-interested or completely malicious. We furthermore investigate the impact of common knowledge on spiteful bidding. Divulging the bidders' valuations reduces revenue in second-price auctions, whereas it has the opposite effect in first-price auctions.

AAMAS Conference 2007 Conference Paper

Commitment and Extortion

• Paul Harrenstein
• Felix Brandt
• Felix Fischer

Making commitments, e. g. , through promises and threats, enables a player to exploit the strengths of his own strategic position as well as the weaknesses of that of his opponents. Which commitments a player can make with credibility depends on the circumstances. In some, a player can only commit to the performance of an action, in others, he can commit himself conditionally on the actions of the other players. Some situations even allow for commitments on commitments or for commitments to randomized actions. We explore the formal properties of these types of (conditional) commitment and their interrelationships. So as to preclude inconsistencies among conditional commitments, we assume an order in which the players make their commitments. Central to our analyses is the notion of an extortion, which we define, for a given order of the players, as a profile that contains, for each player, an optimal commitment given the commitments of the players that committed earlier. On this basis, we investigate for different commitment types whether it is advantageous to commit earlier rather than later, and how the outcomes obtained through extortions relate to backward induction and Pareto efficiency.

AAAI Conference 2007 Conference Paper

Computational Aspects of Covering in Dominance Graphs

• Felix Brandt

Various problems in AI and multiagent systems can be tackled by finding the “most desirable” elements of a set given some binary relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Some particularly attractive solution sets are defined in terms of a covering relation—a transitive subrelation of the original relation. We consider three different types of covering (upward, downward, and bidirectional) and the corresponding solution concepts known as the uncovered set and the minimal covering set. We present the first polynomialtime algorithm for finding the minimal bidirectional covering set (an acknowledged open problem) and prove that deciding whether an alternative is in a minimal upward or downward covering set is NP-hard. Furthermore, we obtain various set-theoretical inclusions, which reveal a strong connection between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other hand. In particular, we show that every stable set is also a minimal upward covering set.

AAAI Conference 2006 Conference Paper

On Strictly Competitive Multi-Player Games

• Felix Brandt

We embark on an initial study of a new class of strategic (normal-form) games, so-called ranking games, in which the payoff to each agent solely depends on his position in a ranking of the agents induced by their actions. This definition is motivated by the observation that in many strategic situations such as parlor games, competitive economic scenarios, and some social choice settings, players are merely interested in performing optimal relative to their opponents rather than in absolute measures. A simple but important subclass of ranking games are single-winner games where in any outcome one agent wins and all others lose. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibria when there are more than two players and pure Nash equilibria when the number of players is unbounded. This dashes hope that multi-player ranking games can be solved efficiently, despite the structural restrictions of these games.

AAMAS Conference 2004 Conference Paper

(Im)Possibility of Unconditionally Privacy-Preserving Auctions

• Felix Brandt
• Tuomas Sandholm