Paul Harrenstein

AAMAS Conference 2023 Conference Paper

k -Prize Weighted Voting Game

• Wei-Chen Lee
• David Hyland
• Alessandro Abate
• Edith Elkind
• Jiarui Gan
• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

We introduce a natural variant of weighted voting games, which we refer to as 𝑘-Prize Weighted Voting Games. Such games consist of 𝑛 players with weights, and 𝑘 prizes, of possibly differing values. The players form coalitions, and the 𝑖-th largest coalition (by the sum of weights of its members) wins the 𝑖-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

TARK Conference 2023 Conference Paper

On Imperfect Recall in Multi-Agent Influence Diagrams

• James Fox
• Matt MacDermott
• Lewis Hammond
• Paul Harrenstein
• Alessandro Abate
• Michael J. Wooldridge

Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. In some settings, MAIDs offer significant advantages over extensive-form game representations. Previous work on MAIDs has assumed that agents employ behavioural policies, which set independent conditional probability distributions over actions for each of their decisions. In settings with imperfect recall, however, a Nash equilibrium in behavioural policies may not exist. We overcome this by showing how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also analyse the computational complexity of key decision problems in MAIDs, and explore tractable cases. Finally, we describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.

AAMAS Conference 2022 Conference Paper

Computing Nash Equilibria for District-based Nominations

• Paul Harrenstein
• Paolo Turrini

We study political parties that strategically place their candidates in districts so to maximise the number of their nominees that get elected. In each district, voters rank the nominated candidates and elect the plurality winners. After studying equilibrium existence in restricted instances, we show that deciding the existence of pure Nash equilibria for these games is NP-complete if party size is bounded by a constant and ΣP 2 -complete for the general case. For the hardness part of the latter result we reduce from ∃∃! -3sat.

AAMAS Conference 2021 Conference Paper

A Hotelling-Downs Framework for Party Nominees

• Paul Harrenstein
• Grzegorz Lisowski
• Ramanujan Sridharan
• Paolo Turrini

We present a model for the strategic selection of party nominees, where competing groups choose their representatives based on the expected electoral returns. Technically, we look at a generalisation of the Hotelling-Downs model, where each nominee has a predefined position on the political spectrum and attracts the closest voters compared to all other representatives. Within this framework we explore the algorithmic properties of Nash equilibria, which are not guaranteed to exist even in two party competitions. We show that finding a Nash equilibrium is NP-complete for the general case. However, if there are only two competing parties, this can be achieved in linear time. The results readily extend to games with restricted positioning options for the players involved, such as facility location and Voronoi games.

JAIR Journal 2018 Journal Article

Efficient Computation of Semivalues for Game-Theoretic Network Centrality

• Mateusz K. Tarkowski
• Piotr L. Szczepański
• Tomasz P. Michalak
• Paul Harrenstein
• Michael Wooldridge

Some game-theoretic solution concepts such as the Shapley value and the Banzhaf index have recently gained popularity as measures of node centrality in networks. While this direction of research is promising, the computational problems that surround it are challenging and have largely been left open. To date there are only a few positive results in the literature, which show that some game-theoretic extensions of degree-, closeness- and betweenness-centrality measures are computable in polynomial time, i.e., without the need to enumerate the exponential number of all possible coalitions. In this article, we show that these results can be extended to a much larger class of centrality measures that are based on a family of solution concepts known as semivalues. The family of semivalues includes, among others, the Shapley value and the Banzhaf index. To this end, we present a generic framework for defining game-theoretic network centralities and prove that all centrality measures that can be expressed in this framework are computable in polynomial time. Using our framework, we present a number of new and polynomial-time computable game-theoretic centrality measures.

AAMAS Conference 2018 Conference Paper

Local Equilibria in Logic-Based Multi-Player Games

• Julian Gutierrez
• Paul Harrenstein
• Thomas Steeples
• Michael Wooldridge

Game theory provides a well-established framework for the analysis and verification of concurrent and multi-agent systems. Typically, the analysis of a multi-agent system involves computing the set of equilibria in the associated multi-player game representing the behaviour of the system. As systems grow larger, it becomes increasingly harder to find equilibria in the game – which represent the rationally stable behaviours of the multi-agent system (the solutions of the game). To address this issue, in this paper, we study the concept of local equilibria, which are defined with respect to (maximal) stable coalitions of agents for which an equilibrium can de found. We focus on the solutions given by the Nash equilibria of Boolean games and iterated Boolean games, two logic-based models for multi-agent systems, in which the players’ goals are given by formulae of propositional logic and LTL, respectively.

IJCAI Conference 2017 Conference Paper

Characterising the Manipulability of Boolean Games

• Paul Harrenstein
• Paolo Turrini
• Michael Wooldridge

The existence of (Nash) equilibria with undesirable properties is a well-known problem in game theory, which has motivated much research directed at the possibility of mechanisms for modifying games in order to eliminate undesirable equilibria, or induce desirable ones. Taxation schemes are a well-known mechanism for modifying games in this way. In the multi-agent systems community, taxation mechanisms for incentive engineering have been studied in the context of Boolean games with costs. These are games in which each player assigns truth-values to a set of propositional variables she uniquely controls in pursuit of satisfying an individual propositional goal formula; different choices for the player are also associated with different costs. In such a game, each player prefers primarily to see the satisfaction of their goal, and secondarily, to minimise the cost of their choice, thereby giving rise to lexicographic preferences over goal-satisfaction and costs. Within this setting, where taxes operate on costs only, however, it may well happen that the elimination or introduction of equilibria can only be achieved at the cost of simultaneously introducing less desirable equilibria or eliminating more attractive ones. Although this framework has been studied extensively, the problem of precisely characterising the equilibria that may be induced or eliminated has remained open. In this paper we close this problem, giving a complete characterisation of those mechanisms that can induce a set of outcomes of the game to be exactly the set of Nash Equilibrium outcomes.

AIJ Journal 2017 Journal Article

From model checking to equilibrium checking: Reactive modules for rational verification

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

KR Conference 2016 Conference Paper

Boolean Hedonic Games

• Haris Aziz
• Paul Harrenstein
• Jérôme Lang
• Michael Wooldridge

We study hedonic games with dichotomous preferences. Hedonic games are cooperative games in which players desire to form coalitions, but only care about the makeup of the coalitions of which they are members; they are indifferent about the makeup of other coalitions. The assumption of dichotomous preferences means that, additionally, each player’s preference relation partitions the set of coalitions of which that player is a member into just two equivalence classes: satisfactory and unsatisfactory. A player is indifferent between satisfactory coalitions, and is indifferent between unsatisfactory coalitions, but strictly prefers any satisfactory coalition over any unsatisfactory coalition. We develop a succinct representation for such games, in which each player’s preference relation is represented by a propositional formula. We show how solution concepts for hedonic games with dichotomous preferences are characterised by propositional formulas.

AAMAS Conference 2016 Conference Paper

Expressiveness and Nash Equilibrium in Iterated Boolean Games

• Julian Gutierrez
• Paul Harrenstein
• Giuseppe Perelli
• Michael Wooldridge

We introduce and investigate a novel notion of expressiveness for temporal logics that is based on game theoretic properties of multiagent systems. We focus on iterated Boolean games, where each agent i has a goal γi, represented using (a fragment of) Linear Temporal Logic (LTL). The goal γi captures agent i’s preferences: the models of γi represent system behaviours that would satisfy i, and each player is assumed to act strategically, taking into account the goals of other players, in order to bring about computations satisfying their goal. In this setting, we apply the standard gametheoretic concept of Nash equilibria: the Nash equilibria of an iterated Boolean game can be understood as a (possibly empty) set of computations, each computation representing one way the system could evolve if players chose strategies in Nash equilibrium. Such an equilibrium set of computations can be understood as expressing a temporal property—which may or may not be expressible within a particular LTL fragment. The new notion of expressiveness that we study is then as follows: what LTL properties are characterised by the Nash equilibria of games in which agent goals are expressed in fragments of LTL? We formally define and investigate this notion of expressiveness and some related issues, for a range of LTL fragments.

AAAI Conference 2016 Conference Paper

Rational Verification: From Model Checking to Equilibrium Checking

• Michael Wooldridge
• Julian Gutierrez
• Paul Harrenstein
• Enrico Marchioni
• Giuseppe Perelli
• Alexis Toumi

Rational verification is concerned with establishing whether a given temporal logic formula ϕ is satisfied in some or all equilibrium computations of a multi-agent system – that is, whether the system will exhibit the behaviour ϕ under the assumption that agents within the system act rationally in pursuit of their preferences. After motivating and introducing the framework of rational verification, we present formal models through which rational verification can be studied, and survey the complexity of key decision problems. We give an overview of a prototype software tool for rational verification, and conclude with a discussion and related work.

AAAI Conference 2015 Conference Paper

Efficient Computation of Semivalues for Game-Theoretic Network Centrality

• Piotr Szczepański
• Mateusz Tarkowski
• Tomasz Michalak
• Paul Harrenstein
• Michael Wooldridge

Solution concepts from cooperative game theory, such as the Shapley value or the Banzhaf index, have recently been advocated as interesting extensions of standard measures of node centrality in networks. While this direction of research is promising, the computation of game-theoretic centrality can be challenging. In an attempt to address the computational issues of game-theoretic network centrality, we present a generic framework for constructing game-theoretic network centralities. We prove that all extensions that can be expressed in this framework are computable in polynomial time. Using our framework, we present the first game-theoretic extensions of weighted and normalized degree centralities, impact factor centrality, distance-scaled and normalized betweenness centrality, and closeness and normalized closeness centralities.

JAIR Journal 2015 Journal Article

Possible and Necessary Winners of Partial Tournaments

• Haris Aziz
• Markus Brill
• Felix Fischer
• Paul Harrenstein
• Jerome Lang
• Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

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.

KR Conference 2014 Conference Paper

Reasoning about Equilibria in Game-like Concurrent Systems

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

the assumption that they act rationally and strategically in pursuit of their goals. In this paper, we present a branching time logic that is explicitly intended for this purpose. Specifically, we provide a logic for reasoning about the equilibrium properties of game-like concurrent systems. Equilibrium concepts are the best-known and most widely applied analytical tools in the game theory literature, and of these Nash equilibrium is the best-known (Osborne and Rubinstein 1994). A Nash equilibrium is an outcome that obtains because no player has a rational incentive to deviate from it. If we consider Nash equilibrium in the context of game-like concurrent systems, then it is natural to ask which computations (runs, histories,...) will be generated in equilibrium? In (Gutierrez, Harrenstein, and Wooldridge 2013), this question was investigated using the Iterated Boolean Games (iBG) model. In this model, each player is assumed to control a set of Boolean variables, and the game is played over an infinite sequence of rounds, where at each round every player chooses values for its variables. Each player has a goal, expressed as an LTL formula, and acts strategically in pursuit of this goal. Given this, some computations of a game can be identified as being the result of Nash equilibrium strategies, and (Gutierrez, Harrenstein, and Wooldridge 2013) suggested that the key questions in the strategic analysis of the system are whether a given LTL formula holds in some or all equilibrium computations. While the iBG model of (Gutierrez, Harrenstein, and Wooldridge 2013) is useful for the purposes of exposition, it is not a realistic model of concurrent programs. Moreover, (Gutierrez, Harrenstein, and Wooldridge 2013) provides no language for reasoning about the equilibria of systems: such reasoning must be carried out at the meta-level. This paper fills those gaps. First, we present a computational model that is more appropriate for modelling concurrent systems than the iBG model. In this model, the goals (and thus preferences) of players are given as temporal logic formulae that the respective player aspires to satisfy. After exploring some properties of this model, we introduce Equilibrium Logic (EL) as a formalism for reasoning about the equilibria of such systems. EL is a branching time logic that provides a new path quantifier [NE]ϕ, which asserts that ϕ holds on all Nash equilibrium computations of the system. Thus, EL supports reasoning about equilibria directly in the object language. We then investigate some properties of this logic. Our aim is to develop techniques for reasoning about gamelike concurrent systems, where the components of the system act rationally and strategically in pursuit of logicallyspecified goals. We first present a computational model for such systems, and investigate its properties. We then define and investigate a branching-time logic for reasoning about the equilibrium properties of such systems. The key operator in this logic is a path quantifier [NE]ϕ, which asserts that ϕ holds on all Nash equilibrium computations of the system.

LORI Conference 2013 Conference Paper

Boolean Games with Epistemic Goals

• Thomas Ågotnes
• Paul Harrenstein
• Wiebe van der Hoek
• Michael J. Wooldridge

Abstract We introduce and formally study games in which the goals of players relate to the epistemic states of players in the game. For example, one player might have a goal that another player knows a certain proposition, while another player might have as a goal that a certain player does not know some proposition. The formal model we use to study epistemic games is a variation of the increasingly popular Boolean games model in which each player controls a number of Boolean variables, but has limited ability to see the truth values of the overall set of formulae that hold in the game. Each player in an epistemic Boolean game has a goal, defined as a formula of modal epistemic logic. Using such a language for goals allows us to explicitly and compactly represent desirable epistemic states. After motivating and formally defining epistemic Boolean games as a concise representation of epistemic Kripke structures, we investigate their complexity and study their properties.

IJCAI Conference 2013 Conference Paper

Iterated Boolean Games

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

Iterated games are well-known in the game theory literature. We study iterated Boolean games. These are games in which players repeatedly choose truth values for Boolean variables they have control over. Our model of iterated Boolean games assumes that players have goals given by formulae of Linear Temporal Logic (LTL), a formalism for expressing properties of state sequences. In order to model the strategies that players use in such games, we use a finite state machine model. After introducing and formally defining iterated Boolean games, we investigate the computational complexity of their associated game-theoretic decision problems as well as semantic conditions characterising classes of LTL properties that are preserved by pure strategy Nash equilibria whenever they exist.

IS Journal 2013 Journal Article

The Joy of Matching

• Paul Harrenstein
• David Manlove
• Michael Wooldridge

Here, the authors discuss matching problems and how the Gale-Shapley algorithm solves them, while also explaining some matching techniques.

IJCAI Conference 2013 Conference Paper

Verifiable Equilibria in Boolean Games

• Thomas Ågotnes
• Paul Harrenstein
• Wiebe van der Hoek
• Michael Wooldridge

This work is motivated by the following concern. Suppose we have a game exhibiting multiple Nash equilibria, with little to distinguish them except that one of them can be verified while the others cannot. That is, one of these equilibria carries sufficient information that, if this is the outcome, then the players can tell that an equilibrium has been played. This provides an argument for this equilibrium being played, instead of the alternatives. Verifiability can thus serve to make an equilibrium a focal point in the game. We formalise and investigate this concept using a model of Boolean games with incomplete information. We define and investigate three increasingly strong types of verifiable equilibria, characterise the complexity of checking these, and show how checking their existence can be captured in a variant of modal epistemic logic.

AAMAS Conference 2012 Conference Paper

Individual-based Stability in Hedonic Games depending on the Best or Worst Players

• Haris Aziz
• Paul Harrenstein
• Evangelia Pyrga

We consider classes of hedonic games in which each player’s preferences over coalition structures are induced by the best player (B- and B-hedonic games) or the worst player (Wand W-hedonic games) in his coalition. For these classes, which allow for concise representation, we analyze the computational complexity of deciding the existence of and computing individually stable, Nash stable, and individually rational and contractually individually stable coalition partitions. We identify a key source of intractability in compact coalition formation games in which preferences over players are extended to preferences over coalitions.

AAMAS Conference 2012 Conference Paper

Possible and Necessary Winners of Partial Tournaments

• Haris Aziz
• Markus Brill
• Felix Fischer
• Paul Harrenstein
• J
• eacute; r
• ocirc; me Lang
• Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

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

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.

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.

TARK Conference 2007 Conference Paper

The computational complexity of choice sets

• Felix Brandt 0001
• Felix A. Fischer
• Paul Harrenstein

Social choice rules are often evaluated and compared by inquiring whether they fulfill certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets (a concept originally introduced in the context of cooperative game theory), the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity which allows us to obtain hardness results for entire classes of social choice rules. In contrast to most existing work, we do not impose any restrictions on individual preferences, apart from the indifference relation being reflexive and symmetric. This assumption is motivated by the fact that many realistic types of preferences in computational contexts such as incomplete or quasi-transitive preferences may lead to general pairwise majority relations that need not be complete.

ECAI Conference 2002 Conference Paper

On Modal Logic Interpretations of Games

• Paul Harrenstein
• Wiebe van der Hoek
• John-Jules Ch. Meyer
• Cees Witteveen