# extending_tournament_solutions__03a3929c.pdf

Extending Tournament Solutions

Felix Brandt Institut f ur Informatik Technische Universit at M unchen 85748 Garching, Germany brandtf@in.tum.de

Markus Brill Department of Computer Science Duke University Durham, NC 27708, USA brill@cs.duke.edu

Paul Harrenstein Department of Computer Science University of Oxford Oxford OX1 3QD, UK paul.harrenstein@cs.ox.ac.uk

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.

1 Introduction Preference aggregation and voting are fundamental problems in multiagent systems research (see, e.g., Brandt, Conitzer, and Endriss 2013). For example, a team of autonomous agents or robots may use a voting rule to jointly decide on a course of action. Perhaps one of the most natural ways to aggregate binary preferences from individual agents to a group of agents is simple majority rule, which prescribes that one alternative is socially preferred to another whenever a majority of agents prefers the former to the latter. Majority rule has an intuitive appeal to democratic principles, is easy to understand and most importantly satisfies some attractive formal properties (May 1952). Moreover, almost all common voting rules coincide with majority rule in the two-alternative case. It would therefore seem that the existence of a majority of individuals preferring alternative a to alternative b signifies something fundamental and generic about the group s preferences over a and b. A majoritarian (or C1) social choice function is a function that maps a vector of individual preference relations to a nonempty set of socially preferred alternatives and whose output only depends on the pairwise majority relation. When dealing with majoritarian functions, it is often assumed that

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

there are no majority ties. For example, this can be guaranteed by insisting on an odd number of agents with linear preferences. Under this assumption, a preference profile gives rise to a tournament and a majoritarian function is equivalent to a tournament solution, i.e., a function that associates with every complete and antisymmetric directed graph a subset of the vertices of the graph. Examples of wellstudied tournament solutions are the Copeland set, the top cycle, the uncovered set, or the Slater set (see, e.g., Laslier 1997). Recent years have witnessed an increased interest in the axiomatic and algorithmic aspects of tournament solutions from the AI community (Brandt and Fischer 2008; Faliszewski et al. 2009; Brandt et al. 2010; Brandt, Brill, and Seedig 2011; Brandt et al. 2014; Aziz et al. 2012) as well as from the theoretical computer science community (Woeginger 2003; Alon 2006; Baumeister et al. 2013). While technically convenient, the assumption that preferences do not admit majority ties is rather artificial. Particularly if the number of agents is small, majority ties are likely to occur. It is therefore natural to ask how a given majoritarian function can be generalized to the class of preference profiles that may admit majority ties. Mathematically speaking, we are looking for ways to apply a tournament solution to a complete, but not necessarily antisymmetric, directed graph a so-called weak tournament. For many tournament solutions, generalizations or extensions to weak tournaments have been proposed. Often, it turns out that there are several sensible ways to generalize a tournament solution and it is unclear whether there exists a unique correct generalization. Even for something as elementary as the Copeland set or the top cycle, there is a variety of extensions that are regularly considered in the literature. A natural criterion for evaluating the different proposals is whether the extension satisfies appropriate generalizations of the axiomatic properties that the original tournament solution satisfies. In this paper, we propose a generic way to extend any tournament solution to the class of weak tournaments. This so-called conservative extension of a tournament solution S returns all alternatives that are chosen by S in some orientation of the weak tournament at hand. We show that many of the most common axiomatic properties of tournament solutions are inherited from S to its conservative extension (see Table 1 for an overview). We argue that these re-

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

Property inherited by [S] Result

monotonicity Prop. 1 independence of unchosen alternatives Prop. 2 set-monotonicity Prop. 3 bα Prop. 4 stability (bα bγ) Prop. 5 composition-consistency Prop. 6

Table 1: Properties that [S] inherits from S

sults provide a justification for restricting attention to tournaments when studying majoritarian functions. The conservative extension also leads to interesting computational problems that are strongly related to the possible winner problem (Lang et al. 2012). In fact, computing the conservative extension of a tournament solution is equivalent to solving its possible winner problem when pairwise comparisons are only partially specified. Of course, there is an exponential number of orientations of a weak tournament in general. Early results, however, indicate that for many well-known tournament solutions, the corresponding conservative extensions can be computed efficiently by exploiting individual peculiarities of these concepts. The paper is organized as follows. After introducing the necessary notation in Section 2, we define the conservative extension in Section 3 and show that it inherits many desirable properties in Section 4. Furthermore, we compare the conservative extension to other generalizations that have been proposed in the literature (Section 5) and study its computational complexity (Section 6) for a number of common tournament solutions. Due to the space constraint, most proofs are omitted. They can be found in the full version of this paper.

2 Preliminaries

Let U be a universe of alternatives. For notational convenience we assume that N U. Every nonempty finite subset of U is called a feasible set. For a binary relation on U and alternatives a, b U, we usually write a b instead of the more cumbersome (a, b) . A weak tournament is a pair W = (A, ), where A is a feasible set and is a complete binary relation on U, i.e., for all a, b U, we have a b or b a (or both).1 Intuitively, a b signifies that alternative a is (weakly) preferred to b. Note that completeness implies reflexivity, i.e., a a for all a U. We write a b if a b and not b a, and a b if both a b and b a. We denote the class of all weak tournaments by W. The relation is often referred to as the dominance relation. One of the best-known concepts defined in terms of the dominance relation is that of a Condorcet winner. Alternative a is a Condorcet winner in a weak tournament

1This definition slightly diverges from the common graphtheoretic definition where is defined on A rather than on U. However, it facilitates the definition of tournament solutions and their properties.

W = (A, ) if a b for all alternatives b A \ {a}. A tournament is a weak tournament (A, ) whose dominance relation is also antisymmetric, i.e., for all distinct a, b A, we have that a b and b a imply a = b.2 For a tournament T = (A, ) and distinct alternatives a, b A, a b if and only if a b. We therefore often write T = (A, ) instead of T = (A, ). We denote the class of all tournaments by T . Obviously, T W. For a pair of weak tournaments W = (A, ) and W = (A , ), we say that W is contained in W , and write W W , if A = A and a b implies a b for all a, b A. We will often deal with the set of all tournaments that are contained in a given weak tournament W.

Definition 1. For a weak tournament W W, the set of orientations of W is given by [W] = {T T : T W}.

Every orientation of a weak tournament W = (A, ) can be obtained from W by eliminating, for all distinct alternatives a and b such that a b, one of (a, b) and (b, a) from . The relation can be raised to sets of alternatives and we write A B to signify that a b for all a A and all b B. For a weak tournament W = (A, ) and a feasible set B A, we will sometimes consider the restriction W|B = (B, ) of W to B. A tournament solution is a function S that maps each tournament T = (A, ) to a nonempty subset S(T) of its alternatives A called the choice set. It is generally assumed that choice sets only depend on |A and that tournament solutions cannot distinguish between isomorphic tournaments. Two examples of well-known tournament solutions are the top cycle and the Copeland set. The top cycle TC(T) of a tournament T = (A, ) is defined as the smallest set B A such that B A \ B. The Copeland set CO(T) consists of all alternatives whose dominion is of maximal size, i.e., CO(T) = arg maxa A |{b A \ {a} : a b}|.

3 The Conservative Extension

In order to render tournament solutions applicable to general preference profiles, we need to generalize them to weak tournaments. A generalized tournament solution is a function S that maps each weak tournament W = (A, ) to a nonempty subset S(W) of its alternatives A. A generalized tournament solution S is called an extension of tournament solution S if S(W) = S (W) whenever W is a tournament. For several tournament solutions, extensions have been proposed in the literature (e.g., Dutta and Laslier 1999; Peris and Subiza 1999). Of course, there are many ways to extend any given tournament solution, and there is no definite obvious way of judging whether one proposal is better than another one. We are interested in a generic way to extend any tournament solution to the class of weak tournaments. In particular, our goal is to extend tournament solutions in such a way that

2Defining tournaments with a reflexive dominance relation is non-standard. The reason we define tournaments in such a way is to ensure that every tournament is a weak tournament. Whether the dominance relation of a tournament is reflexive or not does not make a difference for any of our results.

common axiomatic properties are inherited from a tournament solution to its extension. This task is not trivial, as even the arguably most cautious approach has its problems. Let the trivial extension of a tournament solution S be defined as the generalized tournament solution that always selects the whole feasible set A whenever the weak tournament W = (A, ) is not a tournament. It is easy to see that the trivial extension does not satisfy Condorcet-consistency, i.e., the requirement that a Condorcet winner should be uniquely selected whenever it exists. Indeed, for the weak tournament ({a, b, c}, ) with a {b, c} and b c, the trivial extension of any tournament solution selects {a, b, c}. The trivial extension also fails to inherit composition-consistency, which will be defined in Section 4.4. We therefore propose to extend tournament solutions in a slightly more sophisticated way. The conservative extension of a tournament solution S returns all alternatives that are chosen by S in some orientation of the weak tournament at hand. Definition 2. Let S be a tournament solution. The conservative extension [S] of S is the generalized tournament solution that maps a weak tournament W W to

T [W ] S(T).

This definition is reminiscent of the parallel-universes tiebreaking approach in social choice theory (Conitzer, Rognlie, and Xia 2009; Brill and Fischer 2012) and corresponds to selecting the set of all possible winners of W when ties are interpreted as missing edges (Lang et al. 2012; Aziz et al. 2012). For example, the weak tournament depicted in Figure 1 has four orientations. It can be checked that {CO(T) : T [W]} = {{a}, {a, b}, {a, c}} and {TC(T) : T [W]} = {{a}, {a, b, c, d}}. Therefore, [CO](W) = {a, b, c} and [TC](W) = {a, b, c, d}.

Figure 1: Weak tournament W = ({a, b, c, d}, ) with [CO](W) = {a, b, c} and [TC](W) = {a, b, c, d}. An edge from vertex x to vertex y represents x y.

4 Inheritance of Properties The literature on (generalized) tournament solutions has identified a number of desirable properties for these concepts. In this section, we study which properties are inherited when a tournament solution is generalized via the conservative extension. After stating a useful lemma, we consider four classes of properties: dominance-based properties (Section 4.2) that deal with changes in the dominance

[W] f([W]) = [f(W)]

Figure 2: Orientation-consistency

relation, choice-theoretic properties that deal with varying feasible sets (Section 4.3), composition-consistency (Section 4.4), and regularity (Section 4.5).

4.1 A General Lemma Many properties express the invariance of alternatives being chosen (or alternatives not being chosen) under certain type of transformation of the weak tournament. That is, they have the form that if an alternative a is chosen (not chosen) from some weak tournament W, then a is also chosen (not chosen) from f (W), where f is an operation that transforms weak tournaments in a particular way. Formally, a tournament operation is a mapping f from the class of all weak tournaments to itself. A tournament operation f is orientation-consistent if applying the operation to any orientation of a weak tournament W results in a tournament that is an orientation of f (W). Definition 3. A tournament operation f is orientationconsistent if for all weak tournaments W and all T [W],

f ([W]) = [f (W)],

where f([W]) = {f(T) : T [W]}. Furthermore, a class F of tournament operations is orientation-consistent if each operation in F is orientation-consistent. In other words, f is orientation-consistent if the diagram in Figure 2 commutes. Observe that a necessary condition for f to be orientation-consistent is that f(T ) T . Let F be a class of tournament operations and C a subclass of weak tournaments. We then say that a generalized tournament solution S is inclusion-invariant under F on C if, for all weak tournaments W in C,

a S(W) implies a S(f (W)) for all f F.

Similarly, we say that S is exclusion-invariant under F on C if, for all weak tournaments W in C,

a / S(W) implies a / S(f (W)) for all f F.

We are now in a position to formulate a very useful lemma. Lemma 1. Let F be an orientation-consistent class of tournament operations and S a tournament solution. Then, (i) if S is inclusion-invariant under F on T , so is [S] on W, (ii) if S is exclusion-invariant under F on T , so is [S] on W.

Proof. We give the proof for (i); the proof for (ii) runs along analogous lines. Assume that S is inclusion-invariant under F on T , i.e., for all T T and all alternatives a,

a S(T) implies a S(f(T)).

Consider an arbitrary weak tournament W in W and an alternative a [S](W). By definition of [S],

a S(T) for some T [W]. ( )

We show that a [S](f(W)) for all f F. For a contradiction assume a / [S](f(W)) for some f F. Then, a / S(T) for all T [f(W)]. By orientation-consistency of f, then also a / S(T) for all T f([W]). Recall that f([W]) = {f(T) : T [W]}. Hence, a / S(f(T)) for all T [W]. Our initial assumption then finally yields a / S(T) for all T [W], which contradicts ( ).

4.2 Dominance-Based Properties We first look at three properties that deal with changes in the dominance relation, namely monotonicity, independence of unchosen alternatives, and set-monotonicity. A tournament solution is monotonic if a chosen alternative remains in the choice set when it is strengthened against some other alternative, while leaving everything else unchanged. Here, strengthening a versus b refers to replacing b a with a b. In weak tournaments, we can also strengthen a against b by replacing a b with a b.3 In order to formalize monotonicity, let W = (A, ) be a weak tournament and define Wa b = (A, ), where

= \{(b, a)} {(a, b)}.

Definition 4. A generalized tournament solution S is monotonic if for all W = (A, ) and b A,

a S(W) implies a S(Wa b).

It is easy to see that monotonicity can be phrased as an inclusion-invariance condition. Invoking Lemma 1, we then obtain the following result.

Proposition 1. If a tournament solution S is monotonic on T , so is [S] on W.

Proof sketch. Let fa b be the tournament operation that maps each weak tournament W to Wa b and define

F MON a (W) = {fa b : b A \ {a}}.

It can then easily be appreciated that a generalized tournament solution is monotonic if and only if it is inclusioninvariant under F MON a . Observe that F MON a is orientationconsistent. Lemma 1 then gives the result.

Independence of unchosen alternatives (IUA) prescribes that the choice set is invariant under any changes in the dominance relation among unchosen alternatives.

Definition 5. A generalized tournament solution S is independent of unchosen alternatives (IUA) if for all W = (A, ) and a, b A \ S(A),

S(W) = S(Wa b).

3A subtler way to strengthen a against b consists in replacing b a with a b. Although this case is not covered by our definition of monotonicity, it can be shown that [S] satisfies this additional property as long as S is monotonic.

Reasoning along similar lines as for monotonicity, we find that IUA is inherited from S to [S].

Proposition 2. If a tournament solution S is independent of unchosen alternatives on T , so is [S] on W.

Proof sketch. Let F IUA(W) = {fa b : a, b A \ S(W)} and observe that a generalized tournament solution satisfies IUA if and only if it is both inclusion-invariant and exclusion-invariant under F IUA. To appreciate this observe that inclusion-invariance under F IUA implies that S(W) S(Wa b) and exclusion-invariance under F IUA implies S(W) S(Wa b), the other direction being straightforward. Moreover, F IUA(W) is orientation-consistent. An application of Lemma 1 then yields the result.

Set-monotonicity is a strengthening of both monotonicity and IUA and is the defining property in a characterization of group-strategyproof social choice functions (Brandt 2011). A tournament solution is set-monotonic if the choice set remains the same whenever some alternative is strengthened against some unchosen alternative.

Definition 6. A generalized tournament solution S is setmonotonic if for all W = (A, ), a A, and b A\S(A),

S(W) = S(Wa b).

Set-monotonicity can be characterized in terms of inclusion-invariance and exclusion-invariance with respect to an orientation-consistent class of tournament operations given by F SMON (W) = {fa b : a U, b A \ S(W)}. Thus, Lemma 1 also yields the following result.

Proposition 3. If a tournament solution S is set-monotonic on T , so is [S] on W.

4.3 Choice-Theoretic Properties We now turn to a class of properties that relate choices from different feasible sets to each other. For all of these properties, the dominance relation is fixed. We can therefore simplify notation and write S(A) for S((A, )). The central property in this section is stability (Brandt and Harrenstein 2011), which requires that a set is chosen from two different sets of alternatives if and only if it is chosen from the union of these sets.

Definition 7. A generalized tournament solution S is stable if for all feasible sets A, B and X A B,

X = S(A) = S(B) if and only if X = S(A B).

Stability can be factorized into conditions bα and bγ by considering each implication in the above equivalence separately.4

X = S(A B) implies X = S(A) = S(B) (bα) X = S(A) = S(B) implies X = S(A B) (bγ)

4Property bα is also known as Chernoff s postulate 5 (Chernoff 1954), the strong superset property (Bordes 1979), or outcast (Aizerman and Aleskerov 1995) (see Monjardet (2008) for a more thorough discussion of the origins of this condition).

Lemma 1 is not directly applicable to the choice-theoretic properties bα and bγ. For bα, however, we can utilize the following characterization: S satisfies bα if and only if

S(A) B A implies S(A) = S(B)

for all feasible sets A, B. This characterization allows us to reformulate bα as the conjunction of two invariance properties. For a feasible set B, we let f B denote the tournament operation that maps a weak tournament W = (A, ) with B A to its restriction to B, i.e., f B(W) = W|B. Furthermore, define F bα = {f B : S(A) B A}. Observe that a generalized tournament solution S satisfies bα if and only if S is both inclusion-invariant under F bα and exclusion-invariant under F bα. Since F bα is orientation-consistent, we can apply Lemma 1. Proposition 4. If a tournament solution S satisfies bα on T , so does [S] on W. For bγ, no characterization similar in spirit to the reformulation of bα above is known. In fact, we were not able to prove that bγ is inherited from a tournament solution S to its conservative extension [S]. However, it is inherited if S also satisfies bα. Proposition 5. Let S be a tournament solution that satisfies bα. If S satisfies bγ on T , so does [S] on W. Since stability is equivalent to the conjunction of bα and bγ, the following statement follows as an immediate consequence of Propositions 4 and 5. Corollary 1. If S is stable on T , so is [S] on W. Interestingly, requiring bα so that bγ is inherited is less restrictive than it might seem because all common tournament solution satisfy bα if and only if they satisfy bγ.5 In general, however, it is the case that bα and bγ are independent from each other, even though this requires the construction of rather artificial tournament solutions.

4.4 Composition-Consistency We finally consider a structural property that deals with sets of similar alternatives. A component of a tournament is a subset of alternatives that bear the same dominance relationship to all alternatives not in the set. A decomposition is a partition of the alternatives into components. A decomposition induces a summary tournament with the components as alternatives. A tournament solution is then said to be composition-consistent if it selects the best alternatives from the components it selects from the summary tournament. In order to extend the definition of compositionconsistency to weak tournaments, we need to generalize the concept of a component. By a component of a weak tournament W = (A, ) we understand a feasible set X A such that X is a singleton or for all y A \ X, either X y or y X. We have the following lemma. Lemma 2. Let W = (A, ) be a weak tournament and X A. Then, X is a component of W if and only if X is a component of every orientation T [W].

5For example, this statement holds for all tournament solutions considered in Section 5: TC, BP, and MC satisfy both bα and bγ, and CO, UC, BA, and TEQ satisfy neither bα nor bγ.

Given the definition of a component, decompositions and summaries of weak tournaments, as well as compositionconsistency of generalized tournament solutions, are then defined analogously to the case of tournaments. We find that composition-consistency is inherited to the conservative extension.

Proposition 6. If a tournament solution S is compositionconsistent on T , so is [S] on W.

The literature on tournaments also distinguishes the concept of weak composition-consistency (see, e.g., Laslier 1997). We find that, rendering it applicable to weak tournaments in a way much similar as above, weak compositionconsistency is also inherited by [S] from S.

4.5 Regularity

A tournament solution is regular if it selects all alternatives from regular tournaments, i.e., tournaments in which the indegree and outdegree of every alternative are equal. Regularity extends naturally to weak tournaments, but we find that it is not generally inherited from S to [S]. A weaker, but likewise conservative, extension of the notion of regularity, which we call weak regularity, requires a generalized solution concept to choose all alternatives from regular weak tournaments of odd order only. Weak regularity is inherited from S to [S].

5 Comparison to Other Generalizations

For many tournament solutions, generalizations or extensions to weak tournaments have been proposed in the literature. In this section, we compare these extensions to the conservative extension for a number of well-known tournament solutions (for definitions, see Laslier 1997). For generalized tournament solutions S and S , we write S S if S = S and S (W) S(W) for all weak tournaments W. In this case, we say that S is a refinement of S.

Copeland Set The Copeland set CO gives rise to a whole class of extensions that is parameterized by a number α between 0 and 1. The generalized tournament solution COα

selects all alternatives that maximize the variant of the Copeland score in which each tie contributes α points to an alternative s score (see, e.g., Faliszewski et al. 2009). Henriet (1985) axiomatically characterized CO 1 2 , arguably the most natural variant in this class. While it is easy to check that [CO] COα for all α [0, 1], the inclusion of COα

in [CO] turns out to depend on the value of α.

Proposition 7. COα [CO] if and only if 1

Top Cycle Schwartz (1972; 1986) defined two generalizations of the top cycle TC (see also Sen 1986 and Brandt, Fischer, and Harrenstein 2009). GETCHA (or the Smith set) contains the maximal elements of the transitive closure of whereas GOCHA (or the Schwartz set) contains the maximal elements of the transitive closure of . The conservative extension [TC] coincides with GETCHA.

Proposition 8. GOCHA GETCHA = [TC].

Bipartisan Set Dutta and Laslier (1999) generalized the bipartisan set BP to the essential set ES, which is given by the set of all alternatives that are contained in the support of some Nash equilibrium of the underlying weak tournament game. The essential set does not coincide with the conservative extension [BP]. Whether ES [BP] holds is an open problem.

Uncovered Set Duggan (2013) surveyed several extensions of the covering relation to weak tournaments. Any such relation induces a generalization of the uncovered set. The so-called deep covering and Mc Kelvey covering relations are particularly interesting extensions. Duggan (2013) showed that for all other generalizations of the covering relation he considered, the corresponding uncovered set is a refinement of the deep uncovered set UCD. Another interesting property of UCD is that it coincides with the conservative extension of UC.

Proposition 9. UCD = [UC].

It follows that all other UC generalizations considered by Duggan (2013) are refinements of [UC].

Minimal Covering Set The generalization of MC is only well-defined for the Mc Kelvey covering relation and the deep covering relation. The corresponding generalized tournament solutions are known to satisfy stability. We have constructed a weak tournament in which [MC] is strictly contained in both the Mc Kelvey minimal covering set MCM and the deep minimal covering set MCD. There are also weak tournaments in which MCM is strictly contained in [MC].

Proposition 10. [MC] MCD, [MC] MCM , and MCM [MC].

Corollary 1 implies that [MC] satisfies the very demanding stability property. Hence, we have found a new sensible generalization of MC which is a refinement of MC D and sometimes yields strictly smaller choice sets than MCM .

Banks Set Banks and Bordes (1988) discussed four different generalizations of the Banks set BA to weak tournaments, denoted by BA1, BA2, BA3, and BA4. Each of those generalizations is a refinement of the conservative extension [BA].

Proposition 11. BAm [BA] for all m {1, 2, 3, 4}.

Tournament Equilibrium Set Finally, Schwartz (1990) suggested six ways to extend the tournament equilibrium set TEQ and the notion of retentiveness in general to weak tournaments. However, all of those variants can easily be shown to lead to disjoint minimal retentive sets even in very small tournaments, and none of the variants coincides with [TEQ]. It is noteworthy that, in contrast to the conservative extension, some of the extensions discussed above fail to inherit properties from their corresponding tournament solutions. For instance, GOCHA violates bα and BA3 and BA4 violate the weak superset property (Banks and Bordes 1988).

6 Computational Complexity When a tournament solution S is generalized via the conservative extension to [S], it is natural to ask whether the choice set of [S] can be computed efficiently. Since the number of orientations of a weak tournament can be exponential in the size of the weak tournament, tractability of the winner determination problem of S is a necessary, but not a sufficient, condition for the tractability of [S]. Proposition 12. There is a tournament solution S such that the winner determination problem is in P for S, and NPcomplete for [S]. In light of Proposition 12, it is interesting to check for each tractable tournament solution S, whether the choice set of [S] can be computed efficiently. This question is mathematically equivalent to the problem of computing the set of possible winners for a partially specified tournament. The latter problem has been studied for the Copeland set CO, the top cycle TC, and the uncovered set UC. Proposition 13 (Cook et al. 1998). Computing [CO] is in P. Proposition 14 (Lang et al. 2012). Computing [TC] is in P. Proposition 15 (Aziz et al. 2012). Computing [UC] is in P. While the proof of Proposition 13 consists in a polynomial-time reduction to maximum network flow, [TC] and [UC] can be computed by greedy algorithms. It is a very interesting open problem whether the conservative extensions of more elaborate tournament solutions such as the minimal covering set or the bipartisan set can be computed efficiently. If computing winners is NP-complete for a tournament solution, the same is true for its conservative extension. Lemma 3. If winner determination for S is NP-complete, then winner determination for [S] is NP-complete.

Proof. Hardness of computing [S] immediately follows from hardness of computing S, because [S] and S agree whenever the weak tournament is in fact a tournament. For membership in NP, suppose that x [S](W). Then we can guess an orientation T [W] and an efficiently verifiable witness of the fact that x S(T).

Since the winner determination problem is NP-complete for the Banks set BA (Woeginger 2003), we have an immediate corollary. Corollary 2. Computing [BA] is NP-complete.

7 Conclusion We have shown that the conservative extension inherits many desirable properties from its underlying tournament solution (see Table 1). In general, the conservative extension [S] of tournament solution S is rather large and there might be more discriminating extensions of S that still satisfy its characterizing properties. However, the conservative extension may serve as proof of concept to show that generalizing a tournament solution in a meaningful way is possible. Whether there are more discriminating solutions that

are equally attractive is a different issue that needs to be settled for each tournament solution at hand.

Acknowledgements This work was supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/7-2, by a Feodor Lynen research fellowship of the Alexander von Humboldt Foundation, and by the ERC under Advanced Grant 291528 ( RACE ). We thank Vincent Conitzer, Christian Geist, and Hans Georg Seedig for helpful discussions.

References Aizerman, M., and Aleskerov, F. 1995. Theory of Choice, volume 38 of Studies in Mathematical and Managerial Economics. North-Holland. Alon, N. 2006. Ranking tournaments. SIAM Journal on Discrete Mathematics 20(1):137 142. Aziz, H.; Brill, M.; Fischer, F.; Harrenstein, P.; Lang, J.; and Seedig, H. G. 2012. Possible and necessary winners of partial tournaments. In Conitzer, V., and Winikoff, M., eds., Proc. of 11th AAMAS Conference, 585 592. IFAAMAS. Banks, J. S., and Bordes, G. A. 1988. Voting games, indifference, and consistent sequential choice rules. Social Choice and Welfare 5:31 44. Baumeister, D.; Brandt, F.; Fischer, F.; Hoffmann, J.; and Rothe, J. 2013. The complexity of computing minimal unidirectional covering sets. Theory of Computing Systems 53(3):467 502. Bordes, G. 1979. Some more results on consistency, rationality and collective choice. In Laffont, J. J., ed., Aggregation and Revelation of Preferences. chapter 10, 175 197. Brandt, F., and Fischer, F. 2008. Computing the minimal covering set. Mathematical Social Sciences 56(2):254 268. Brandt, F., and Harrenstein, P. 2011. Set-rationalizable choice and self-stability. Journal of Economic Theory 146(4):1721 1731. Brandt, F.; Fischer, F.; Harrenstein, P.; and Mair, M. 2010. A computational analysis of the tournament equilibrium set. Social Choice and Welfare 34(4):597 609. Brandt, F.; Brill, M.; Fischer, F.; and Harrenstein, P. 2014. Minimal retentive sets in tournaments. Social Choice and Welfare 42(3):551 574. Brandt, F.; Brill, M.; and Seedig, H. G. 2011. On the fixedparameter tractability of composition-consistent tournament solutions. In Walsh, T., ed., Proc. of 22nd IJCAI, 85 90. AAAI Press. Brandt, F.; Conitzer, V.; and Endriss, U. 2013. Computational social choice. In Weiß, G., ed., Multiagent Systems. MIT Press, 2nd edition. chapter 6, 213 283. Brandt, F.; Fischer, F.; and Harrenstein, P. 2009. The computational complexity of choice sets. Mathematical Logic Quarterly 55(4):444 459. Brandt, F. 2011. Group-strategyproof irresolute social choice functions. In Walsh, T., ed., Proc. of 22nd IJCAI, 79 84. AAAI Press.

Brill, M., and Fischer, F. 2012. The price of neutrality for the ranked pairs method. In Hoffmann, J., and Selman, B., eds., Proc. of 26th AAAI Conference, 1299 1305. AAAI Press. Chernoff, H. 1954. Rational selection of decision functions. Econometrica 22:422 443. Conitzer, V.; Rognlie, M.; and Xia, L. 2009. Preference functions that score rankings and maximum likelihood estimation. In Proc. of 21st IJCAI, 109 115. Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. 1998. Combinatorial Optimization. Wiley and Sons. Duggan, J. 2013. Uncovered sets. Social Choice and Welfare 41:489 535. Dutta, B., and Laslier, J.-F. 1999. Comparison functions and choice correspondences. Social Choice and Welfare 16(4):513 532. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; and Rothe, J. 2009. Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research 35:275 341. Henriet, D. 1985. The Copeland choice function: an axiomatic characterization. Social Choice and Welfare 2(1):49 63. Lang, J.; Pini, M. S.; Rossi, F.; Salvagnin, D.; Venable, K. B.; and Walsh, T. 2012. Winner determination in voting trees with incomplete preferences and weighted votes. Journal of Autonomous Agents and Multi-Agent Systems 25(1):130 157. Laslier, J.-F. 1997. Tournament Solutions and Majority Voting. Springer. May, K. 1952. A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica 20:680 684. Monjardet, B. 2008. Statement of precedence and a comment on IIA terminology. Games and Economic Behavior 62:736 738. Peris, J. E., and Subiza, B. 1999. Condorcet choice correspondences for weak tournaments. Social Choice and Welfare 16(2):217 231. Schwartz, T. 1972. Rationality and the myth of the maximum. Noˆus 6(2):97 117. Schwartz, T. 1986. The Logic of Collective Choice. Columbia University Press. Schwartz, T. 1990. Cyclic tournaments and cooperative majority voting: A solution. Social Choice and Welfare 7(1):19 29. Sen, A. K. 1986. Social choice theory. In Arrow, K. J., and Intriligator, M. D., eds., Handbook of Mathematical Economics, volume 3. Elsevier. chapter 22, 1073 1181. Woeginger, G. J. 2003. Banks winners in tournaments are difficult to recognize. Social Choice and Welfare 20:523 528.