# preserving_condorcet_winners_under_strategic_manipulation__8f15c51b.pdf

Preserving Condorcet Winners under Strategic Manipulation

Sirin Botan and Ulle Endriss Institute for Logic, Language and Computation, University of Amsterdam {sirin.botan, ulle.endriss}@uva.nl

Condorcet extensions have long held a prominent place in social choice theory. A Condorcet extension will return the Condorcet winner as the unique winner whenever such an alternative exists. However, the deﬁnition of a Condorcet extension does not take into account possible manipulation by the voters. A proﬁle where all agents vote truthfully may have a Condorcet winner, but this alternative may not end up in the set of winners if agents are acting strategically. Focusing on the class of tournament solutions, we show that many natural social choice functions in this class, such as the well-known Copeland and Slater rules, cannot guarantee the preservation of Condorcet winners when agents behave strategically. Our main result in this respect is an impossibility theorem that establishes that no tournament solution satisfying a very weak decisiveness requirement can provide such a guarantee. On the bright side, we identify several indecisive but otherwise attractive tournament solutions that do guarantee the preservation of Condorcet winners under strategic manipulation for a large class of preference extensions.

1 Introduction The notion of strategyproofness has been studied across disciplines, including economics, game theory, and artiﬁcial intelligence (Arrow, Sen, and Suzumura 2010; Shoham and Leyton-Brown 2009; Brandt et al. 2016; Meir 2018). For multiagent systems, including those utilising voting to reach a collective decision, ensuring some level of strategyproofness is an important consideration (Amanatidis, Birmpas, and Markakis 2016; Hajaj et al. 2015). By a seminal result in social choice theory, we know that every non-trivial resolute social choice function or voting rule is susceptible to strategic manipulation by voters (Gibbard 1973; Satterthwaite 1975). Our proposal in this paper is to deﬁne a more ﬁne-grained strategyproofness axiom that dictates a speciﬁc kind of undesirable manipulation should not occur. We do not examine whether strategyproofness can be satisﬁed alongside a set of other desirable axioms, but whether the fact that strategyproofness fails can affect the strength of the other axiom(s). Our focus is on Condorcet extensions, and how failure of strategyproofness affects Condorcet consistency.

Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

If an agent manipulates under a Condorcet extension meaning she submits a preference other than her true one it is possible that this will result in a reported proﬁle without a Condorcet winner, despite the fact that the truthful proﬁle has one. In particular, it is possible that a Condorcet extension in some cases fails to return the Condorcet winner of the truthful proﬁle as the outcome. We examine exactly when the lack of strategyproofness affects whether we can trust that a Condorcet extension will give us all true Condorcet winners, even under the assumption that agents might vote strategically. Strategyproofness on proﬁles with a Condorcet winner is also appealing from a practical viewpoint as real-world elections have a high probability of giving us a Condorcet winner (Gehrlein 2006; Gehrlein and Lepelley 2011).

Related work. There are various methods in the literature for circumventing the impossibility result due to Gibbard (1973) and Satterthwaite (1975). A well-employed strategy is to consider a restricted domain for the social choice function, where strategyproofness is guaranteed. Among these domain restrictions, the best-known is the single-peaked domain of Black (1948).1 There are also many examples of positive results relative to more ﬁne-grained axioms that focus on and limit the type of manipulation performed by the agent (Sato 2013; Bossert and Sprumont 2014; Kruger and Terzopoulou 2020). Similar positive results have been obtained by considering voters ignorance of others preference as an informational barrier (Conitzer, Walsh, and Xia 2011; Reijngoud and Endriss 2012; Osborne and Rubinstein 2003). Another approach has been to argue for the computational hardness of computing a successful manipulation strategy as a barrier to manipulation (Bartholdi, Tovey, and Trick 1989; Conitzer and Walsh 2016). While the Gibbard-Satterthwaite Theorem pertains to resolute social choice functions, there are similar impossibility results for irresolute rules (G ardenfors 1976; Kelly 1977; Barber a 1977; Duggan and Schwartz 2000; Sato 2008). These results differ in how they deﬁne manipulability, as they by necessity must make assumptions about agents preferences over sets of alternatives. Duggan and Schwartz (2000), for example, work with optimistic and pessimistic

1For a more thorough treatment of single-peakedness and many other domain restrictions, see Gaertner (2001).

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

agents, while G ardenfors (1976) deﬁnes manipulability relative to his eponymous preference extension. Shifting focus away from resoluteness has also led to positive results regarding the strategyproofness of social choice functions. For example, G ardenfors (1976) identiﬁes two such strategyproof functions for the G ardenfors extension and Brandt (2015) identiﬁes social choice functions that are strategyproof under the Kelly preference extension. The idea of preserving Condorcet winners has also been examined in the setting of probabilistic social choice. Hoang (2017) shows that maximal lotteries (Fishburn 1984) are strategyproof on proﬁles with Condorcet winners when based on the majority relation. Brandl, Brandt, and Stricker (2018) extend this result to all maximal lotteries.

Contribution. To distinguish between social choice functions that do not incentivise manipulation in proﬁles with a Condorcet winner and those that do, we introduce the notion of a robust Condorcet extension. We then show that no irresolute tournament solution that is weakly resolute in the sense of returning a single winning alternative in at least one proﬁle that does not have a Condorcet winner can possibly be such a robust Condorcet extension. This class of weakly resolute rules includes the well-known social choice functions of Copeland (1951) and Slater (1961). Finally, we identify several attractive social choice functions that are robust Condorcet extensions (and thus fail weak resoluteness) for a large class of preferences. This includes, in particular, the minimal extending set (Brandt 2011) and its coarsenings.

Paper outline. The remainder of the paper is organised as follows. We introduce the framework and relevant literature in Section 2. In Section 3 we present an impossibility result for weakly resolute rules. In Section 4 we we present a number of sufﬁcient conditions for a Condorcet extension to be robust. We conclude in Section 5.

2 The Model

In this section we introduce the framework and notation we will be using throughout the paper. Much of the material up to Section 2.5 is familiar from social choice theory (Arrow, Sen, and Suzumura 2010; Brandt et al. 2016). In Section 2.5, we introduce the novel notion of a robust Condorcet extension, the central concept of this paper.

2.1 Preference Proﬁles

Let A be a ﬁnite set of alternatives, and N = {1, . . . , n} a ﬁnite set of agents. A preference proﬁle P = ( P 1 , . . . , P n ) is a vector of strict linear orders over A, where P i is the preference relation of agent i in the proﬁle P . For two proﬁles P and P , and agent i N, we write P = i P , and say they are i-variants, if P j = P j for all j N \ {i}. L(A) denotes the set of all linear orders over A, and L(A)n denotes the set of all proﬁles for n agents. For a proﬁle P , P (with asymmetric part P ) is the majority relation for P and is deﬁned such that a P a if and only if |{i N | a P i a }| |{i N | a P i a}|, for all a, a A. An alternative a A is a Condorcet winner in proﬁle P if it defeats every other alternative in a pairwise

majority contest, meaning a P a for all a A \ {a}. We deﬁne DCondorcet as the set of all proﬁles with a Condorcet winner. We say a relation over A is complete if for all a, b A it is the case that a b or b a. A relation is connex if a b or b a for all distinct a, b A. Note that the majority relation of any proﬁle is complete, and any individual preference relation is connex.

2.2 Social Choice Functions An irresolute social choice function (SCF) is a mapping from proﬁles to nonempty subsets of alternatives: f : L(A)n 2A \ { } To avoid having to break majority ties, we deﬁne SCFs for odd n. Of course we do not strictly speaking need odd n, but rather that proﬁles input to the function have a strict majority relation. A SCF f is a Condorcet extension, or is Condorcetconsistent, if it returns (only) the Condorcet winner whenever one exists. For irresolute SCF, the size of the set of winning alternatives is an important consideration. As an example of a rule that returns quite large sets, take the rule that returns the Condorcet winner if one exists, and returns the whole set of alternatives otherwise. While this is clearly a Condorcet extension, it is a very indecisive rule, as it often results in many ties in the outcome. A SCF is resolute if it always returns a singleton. In order to quantify how decisive an irresolute rule is, we deﬁne a weaker notion of resoluteness. We say f is weakly resolute if there exists a proﬁle P L(A)n \ DCondorcet for which |f(P )| = 1. So, a rule is weakly resolute if it sometimes returns a singleton for a proﬁle without a Condorcet winner. For some SCFs, we can directly compare how decisive they are relative to each other. A SCF f is a reﬁnement of f if for all proﬁles P L(A)n it is the case that f(P ) f (P ), meaning f always returns a subset of f . If f is a reﬁnement of f , we say f is a coarsening of f. If a rule is a reﬁnement of another, it is clearly the more decisive of the two.

2.3 Tournaments and Tournament Solutions A tournament T is a pair (S, T ), where S is a set of nodes and T is an asymmetric and connex relation over S, which we call the dominance relation of the tournament. For a set S, we denote by T (S) all tournaments on S. For a tournament T = (S, T ), we say an alternative a S dominates a S in the tournament T if a T a . The dominion of a in T is deﬁned as DT (a) = {a S | a T a }, the set of alternatives it dominates. The dominators of a in T is deﬁned as DT (a) = {a S | a T a}, the set of alternatives that dominate it. For S S, we deﬁne the restriction T S = {(a, a ) S S | a T a }, which is T restricted to the set S . A subtournament of T = (S, T ) is a tournament (S , T S ) where S S. Thus, a subtournament of T is a subset of the nodes in T , and the edges between those nodes. We say π : S S is an isomorphism between two tournaments T = (S, T ) and T = (S , T ) if π is a bijection, and a T a π(a) T π(a ) for all (a, a ) S S.

We say a proﬁle P L(A)n induces tournament T = (A, T ) if P = T . So a proﬁle induces a tournament if they range over the same alternatives, and the strict part of the majority relation is exactly the dominance relation of the tournament. Note that if a proﬁle induces a tournament, the strict component of the majority relation of that proﬁle must be connex. As tournaments do not speak about agents, we cannot directly talk about two tournaments being i-variants for some agent i N. Instead, we say two tournaments T = (A, T ) and T = (A, T ) are single-agent variants, and write T = 1 T , if there exist a set of agents N and proﬁles P , P L(A)n, for n = |N|, such that P = i P for some agent i N, and the proﬁles P and P induce the tournaments T and T , respectively. We say an element a S is the Condorcet winner of the tournament T = (S, T ) if DT (a) = . This corresponds to the notion of a Condorcet winner of a proﬁle; if a tournament has a Condorcet winner, that alternative will be the Condorcet winner in any proﬁle that induces this tournament. We write TCondorcet to refer to the set of tournaments that have a Condorcet winner. A tournament solution is a mapping from tournaments to sets of alternatives, that does not distinguish between isomorphic tournaments:

F : T (S) 2S \ { }

So F(T ) = {π(a) | a F(T )} if π is an isomorphism between T and T . For ease of reading, we sometimes write F( T ) to mean F(S, T ) when S is clear from context. A SCF f is equivalent to a tournament solution F if f(P ) = F(A, P ) for all P L(A)n. Note that the majority relation of this proﬁle P must be a strict order, as the SCF f is deﬁned for odd n only. In a slight muddling of terminology, we will refer to SCFs that are equivalent to tournament solutions as tournament-solution SCFs. Tournament solutions roughly correspond to Fishburn s C1 functions (Fishburn 1977), which require only the information in the majority graph to determine the winners. More precisely, tournament-solution SCFs correspond to neutral C1 functions,2 as tournament solutions do not distinguish between isomorphic tournaments, and therefore do not favour any alternatives over others.

2.4 Extending Preferences

Because the rules we examine are irresolute meaning they do not always return a single winner we need to specify how agent preferences over alternatives are extended to preferences over sets of alternatives. A preference extension e maps any given preference relation over alternatives in A, to a relation e (with strict part e) over sets of alternatives. We deﬁne two requirements for any preference extension e:

(i) x y implies {x} e {y} and,

(ii) X e Y implies that there exist some x X and y Y such that x y and {x, y} X Y .

2A SCF satisﬁes neutrality if for any proﬁle P and any permutation π : A A it is the case that f(π(P )) = π(f(P )).

The ﬁrst requirement simply dictates that e stays faithful to the agent s preferences when comparing singleton sets. The second requires that e does not extend the preferences in a way that completely disagrees with an agent s preferences over alternatives. Our ﬁrst requirement corresponds to the Extension Rule of Barber a, Bossert, and Pattanaik (2004), while our second requirement is similar in spirit to the lextension of Kruger and Terzopoulou (2020). For an agent i with preference relation P i in proﬁle P , we write P ,e i to denote her preferences over sets of alternatives, extended according to e. We say an agent has e-preferences, if P ,e i is her preference relation over sets of alternatives. We say a preference extension e is pessimistic if X e Y implies that there exists some y Y such that x y for all x X. Note that this deﬁnes a class of preference extensions. We highlight the G ardenfors extension (G ardenfors 1976) as a well-known example of a pessimistic preference extension. The G ardenfors extension dictates that if one set is preferred over another, then any alternative added to the ﬁrst set to reach the second is preferred to the alternatives in the initial set. Similarly, those alternatives removed from the initial set should be less preferred.

2.5 Robust Condorcet Extensions

We say an irresolute SCF f is Condorcet-manipulable by agent i in proﬁle P , under preference extension e, if there exists another proﬁle P = i P such that f(P ) P ,e i f(P ) and P DCondorcet. We are now ready to present our central deﬁnition.

Deﬁnition 1. A SCF f is a robust Condorcet extension (or simply, is robust) under a preference extension e if f is Condorcet-consistent and not Condorcet-manipulable in any proﬁle P DCondorcet, by any i N with e-preferences.

We sometimes write that a SCF is robust to mean that it is a robust Condorcet extension, as robustness is a property of Condorcet extensions. So a SCF is robust under a certain preference extension, if it is not Condorcet manipulable by any agent whose preferences over alternatives have been extended to sets of alternatives according to that extension. While robustness is a weak strategyproofness requirement, it also speaks about how well a rule can preserve Condorcet winners. A robust Condorcet extension ensures that, if the truthful proﬁle has a Condorcet winner, then it is a weakly dominant strategy for all agents to report their true preferences, thus ensuring that no Condorcet winner loses that designation because of strategic manipulation. A robust Condorcet extension therefore ensures that proﬁles with Condorcet winners are, in a sense, stable. We give an example of a Condorcet manipulation of the Copeland SCF,3 to demonstrate what failure of robustness looks like.

Example 1. Suppose the proﬁle below, along with the corresponding majority graph, is the truthful proﬁle, meaning

3The Copeland score of an alternative in a proﬁle (for odd n) is the number of other alternatives it beats in a pairwise majority contest. The Copeland rule selects those alternatives with the highest Copeland scores (Copeland 1951).

all three agents have reported their true preferences. As alternative a is the Condorcet winner, Copeland will return a as the sole winner if all agents vote truthfully. Note, however, that agent 1 has the ability to reverse the dashed edges (a, b) and (a, d) in the majority graph, by moving b and d above a in her own preference order, while keeping their relative ranking as it is. Agent 1 also has an incentive to do so, as this would result in a majority graph where c her top choice is the only alternative with a single incoming edge.

agent 1 agent 2 agent 3

c a e a c d b e b d d a e b c

d As the Copeland winner is the alternative with the smallest number of incoming edges in the majority graph, c would be the lone Copeland winner if agent 1 misreports her preferences, meaning, Copeland incentivises a Condorcetmanipulation in this proﬁle.

While the proﬁle in Example 1 has a Condorcet winner, Copeland is not guaranteed to return this alternative as the winner (or even among them) unless we assume all agents vote truthfully. In the same proﬁle, a robust Condorcetextension would ensure no agent would have an incentive to misreport her preferences.

3 Impossibilites We present a ﬁrst impossibility result, showing there is no function that can meet our robustness requirement for all preference extensions.

Proposition 1. No tournament-solution SCF is robust under all preference extensions.

Proof. Let A = {a, b, c}, N = {1, 2, 3},4 and let f be a Condorcet-consistent SCF equivalent to the tournament solution F. Suppose agent 1 s preferences over sets of alternatives P ,e 1 are such that X P ,e 1 Y if and only if one of the following holds:

X = {a, b, c} and Y = {a}, or X = {x} and Y = {y} for some x, y A s.t. x y.

These preferences satisfy both our requirements for preference extensions, and are therefore a valid extension of P 1 . Let P be the proﬁle shown below, with the induced tournament T on the right. As f is a Condorcet extension, f(P ) = {a}. Let P = 1 P , where b P 1 c P 1 a, meaning agent 1 reverses the edge (a, c) in the induced tournament by reversing the order of these alternatives in her ranking. The tournament T , induced by P , consists of

4While our proof uses three agents and three alternatives, we can always construct proﬁles with a larger number m of alternatives, where the majority relation is an m-cycle.

agent 1 agent 2 agent 3

b a c a b a c c b

As tournament solutions do not distinguish between isomorphic tournaments, f(P ) = F(T ) = {a, b, c}. As {a, b, c} P ,e 1 {a}, this would constitute a successful manipulation for agent 1, meaning f cannot be robust.

As no SCFs are robust for all preference extensions, we redirect our search to those that may be robust for some preference extension. We ﬁrst recall a result by Mc Garvey (1953), which we will use to prove the main result of this section. We include the proof for the sake of completeness.

Theorem 1 (Mc Garvey, 1953). Let A be a set of alternatives, and let be a complete relation over A. Then there is a proﬁle P L(A)n for some even n such that P = , and if a > b, there are n

2 + 2 agents ranking a over b in P .

Proof. For a set of alternatives A and a relation (with strict component >) over A, the proﬁle P is constructed for an even number of agents N = {iab, jab | (a, b) >} as follows. For every pair of alternatives such that a > b, there are two voters iab and jab, with the following preferences:

a P iab b P iab x1 P iab P iab x|A| 2 and

x|A| 2 P jab P jab x1 P jab a P jab b,

Here {x1, . . . x|A| 2} = A \ {a, b}. For each agent in N \ {iab, jab} who prefers a over b, there will be exactly one corresponding agent who prefers b over a, meaning in the proﬁle P exactly n

2 + 2 agents prefer a to b. As this holds for any pair of alternatives, it is clear that P = .

Note that while our statement of Mc Garvey s Theorem is slightly stronger than the classical formulation, the proof and the proﬁle constructed in the proof remain the same. We now show that weakly resolute rules fail robustness for all preference extensions, and further, that they are the only rules that do so. This strengthens an observation from Brandt, Brill, and Harrenstein (2016) stating that all weakly resolute rules are Kelly-manipulable.

Theorem 2. A tournament-solution SCF is weakly resolute if and only if it fails robustness under all preference extensions.

Proof. For the right-to-left direction we prove the contrapositive. That is, we suppose f is a tournament-solution SCF that fails weak resoluteness and show it must be robust under some preference extension. To see that this must be the case, note that any rule failing weak resoluteness never returns singletons outside DCondorcet. This means the preference extension ranging only over singletons would never (strictly)

Figure 1: Tournaments T and T with winners marked in bold and relation M from the proof of Theorem 2. Ties are represented by bidirectional arrows.

favour a larger set over the singleton set with the Condorcet winner.5 As f will always return a set larger than a singleton outside the Condorcet domain, Condorcet-manipulation with these preferences is not possible, thereby making f robust under this preference extension. For the left-to-right direction, let A be our set of alternatives. Suppose f is a weakly resolute tournament-solution SCF, equivalent to a tournament solution F. We show it is possible for an agent to manipulate f from a proﬁle with a Condorcet winner under an arbitrary preference extension e, meaning f cannot be robust under any preference extension. We ﬁrst deﬁne two tournaments T and T , which we will show are single-agent variants. As F is equivalent to a weakly resolute SCF, there is some tournament T = (A, T ) T (A) \ TCondorcet such that F(T ) = {x} for an alternative x A. As x is not a Condorcet winner in T , there must be some y A such that y T x, and by the same reasoning, there must be at least one alternative z A such that z T y. We conclude that the nodes {x, y, z} and the edges (y, x), (z, y) must be present in T . For a visual representation, see Figure 1. Let S = DT (y) be the dominators of y in T . We deﬁne a second tournament T = (A, T ), where y T a for all a S, and T agrees with T on all other pairs of alternatives. In other words, we simply reverse all incoming edges of y in T to obtain T . Note that this makes y a Condorcet winner in T , meaning F(T ) = {y}. We now show that T and T are single-agent variants. We start by constructing a proﬁle P that induces T . To this end, consider a complete relation M (with strict component M, and symmetric component M) over A, such that M = T {(a, y) | a S}. This means M and T agree on all pairs of alternatives except those for which T and T differ. In those cases, M gives a tie between the

5Note that all relevant manipulations here would be between singleton outcomes, meaning we are taking advantage of strategyproofness of the Condorcet, or majority, rule (Campbell and Kelly 2003).

alternatives. By Theorem 1, we know there exists a proﬁle P = ( P 1 , . . . , P n ) with majority relation M. Further, we know that we can construct P with an even number of agents n, such that for any a, a A, where a M a , there are exactly n

2 +2 agents who prefer a to a in P . We use P

to construct the proﬁle P . Let P = ( P 1 , . . . , P n , P i ), where x P i y P i a for all a A \ {x, y}. To see that P induces tournament T , note that for any pair of alternatives (a, a ), either

(i) a M a meaning a T a , and n

2 +2 prefer a to a in P , or (ii) a M a meaning a = y, and a S (or vice versa).

If (i) is the case, a majority of agents in P will prefer a to a regardless of agent i s preferences; n

2 + 2 agents still form a strict majority of n+1 agents. If on the other hand (ii) is the case, we know from agent i s preferences that y P i a. As these alternatives were tied in P , adding agent i to the proﬁle breaks these ties in favour of y, so a majority of agents in P will now prefer y to a. Thus the only differences between M and P relate to the pairs on which M and T differ. As the changes agree with T , this makes T = P , meaning P induces T . As F(T ) = {y}, we can conclude that f(P ) = {y}. It now remains to construct a proﬁle P such that P = i P and P induces T . Let P = ( P 1 , . . . , P n , P i ), and x P i a P i y, for all a A \ {x, y}, meaning agent i moves y to the bottom of their ranking. Clearly, P is an i-variant of P . In the tournament induced by P , it must be the case that the edges (a, y) for all a S are present as the majority on these alternatives is dictated by agent i (and all other edges remain as they were in T ). As these edges correspond exactly to those where T and T differ, P must induce T , and as F(T ) = {x} we conclude f(P ) = {x}. Finally, let P ,e i be agent i s true preferences over sets of alternatives, extended according to e. It is immediately clear, as both outcomes are singletons and x P i y, that f(P ) P ,e i f(P ). As P has a Condorcet winner, this constitutes a Condorcet-manipulation, meaning f cannot be robust under preference extension e.

We note that Theorem 2 applies to two of the most prominent Condorcet extensions Copeland, and Slater.6

4 Robust Tournament Solutions In this section, we present our robustness results for several tournament-solution SCF, and their coarsenings. Our results hold for all pessimistic extensions.

4.1 Relation to Kelly-Strategyproofness While strategyproofness for say, G ardenfors preferences, is not easily satisﬁed, there are several tournament-solution SCFs that have been shown to be strategyproof for the Kelly preference extension (Kelly 1977) which we will refer to as k. For any two sets X and Y in 2A \ { }, X k Y if and

6The result also extends to Slater s weighted counterpart, the Kemeny rule (Kemeny 1959).

only if x y for all x X and all y Y , and there exists an x X and a y Y such that x y. We say a SCF f is Kelly-strategyproof if no agent with Kelly preferences can successfully manipulate. A SCF satisfying G ardenfors-strategyproofness implies it also satisﬁes Kelly-strategyproofness, as the former must exclude more cases of manipulation to be satisﬁed. However, as robustness only requires taking into account comparisons where at least one singleton set is present, we can use strategyproofness results for Kelly preferences to show robustness for all pessimistic extensions, including G ardenfors. Proposition 2. If a Condorcet-consistent SCF f is Kellystrategyproof, then it is a robust Condorcet extension under any pessimistic preference extension.

Proof. Suppose we have a rule f that is Kelly-strategyproof and let e be a pessimistic extension. That is, for any two proﬁles P and P , and any agent i N, if P = i P , then f(P ) P ,k i f(P ). Suppose P has a Condorcet winner, meaning f(P ) = {a} for some a A. Because f(P ) P ,k i f(P ), it cannot be the case that all elements of f(P ) are preferred to a. So either f(P ) = f(P ) or there is some a f(P ) s.t. a P i a . It is then immediate from the deﬁnition of a pessimistic extension that f(P ) P ,e i f(P ).

We therefore get robustness under pessimistic preferences for free for Condorcet extensions known to be Kellystrategyproof, such as the bipartisan set and the minimal covering set (Brandt 2015).7

4.2 Minimal Extending Set & Beyond In this section we show that robustness for Condorcet extensions diverges from Kelly-strategyproofness, as we can ﬁnd rules which satisfy the former while failing the latter. Before we present our positive robustness results, we need to deﬁne the Banks set and the minimal extending set. A tournament T = (S , T ) is a maximal transitive subtournament of T = (S, T ) if (i) T is a subtournament of T ,

(ii) T is a transitive relation, and

(iii) there is no other transitive subtournament (S , T ) of T such that S S . We write ˆT to denote the set of all maximal transitive subtournaments of tournament T , and top( ) to denote the maximal element of the strict linear order . Note that if a tournament T has a Condorcet winner, it will be the maximal element of all maximal transitive subtournaments.8 The Banks set (Banks 1985) is the set of maximal elements of all maximal transitive subtournaments of a tournament: BA(T ) = {top( T S ) | (S, T S ) ˆT }.

7For a thorough treatment of Kelly-strategyproofness and functions which satisfy it, as well as deﬁnitions of the SCFs we have mentioned, we refer to Brandt, Brill, and Harrenstein (2016). 8As the existence of a Condorcet winner does not imply no cycles are present, there may indeed be several maximal transitive subtournaments.

Because the Condorcet winner will top all maximal transitive subtournaments, the Banks set is a Condorcet extension. A set S A is a BA-stable set of a tournament T if a BA(S {a}, T S {a}) for all a A \ S. A BA-stable set of a tournament T is minimal if there is no BA-stable set S of T such that S S. The minimal extending set ME(T ) (Brandt 2011) of a tournament T is the union of all minimal BA-stable sets of T :

ME(T ) = [ {S A | S is a minimal BA-stable set of T }.

We give an example to shed some light on these deﬁnitions. Example 2. In the tournament T below, the two maximal transitive subtournaments are indicated using darker edges. It is clear that the subtournaments are transitive, and they are both maximal; adding the last alternative will break transitivity. From examining these subtournaments, we can see that BA(T ) = {a, b}. a

c The tournament has two minimal BA-stable sets: {a, b, d} because c BA(T ), and {a, b, c} because d BA(T ). ME will output the union of these sets: ME(T ) = {a, b, c, d}. Note that the set {b, c, d} is not BA-stable, as a BA(T ). ME is one of several tournament solutions that can be deﬁned based on this notion of stability. The top cycle for example, is the union of all minimal CNL-stable sets (Brandt 2011), where CNL is the tournament solution returning the set of all Condorcet nonlosers meaning alternatives with at least one outgoing edge. We will use BA and ME to refer both to the tournaments solutions, and the equivalent SCFs. The minimal extending set is Kelly-manipulable. However, we show it is still robust under pessimistic preferences, and extend this result to all coarsenings of ME. Theorem 3. ME is a robust Condorcet extension under all pessimistic preference extensions.

Proof. For a set of alternatives A, and a set of agents N, let P = i P be i-variant proﬁles for an agent i N. Let P be such that x A is the Condorcet winner in P . Let T = (A, T ) and T = (A, T ) be the (single-agent variant) tournaments induced by P and P , respectively. We assume ME(T ) = ME(T ).9 Because of this, we know DT (x) is nonempty, as the two outcomes cannot differ if x remains a Condorcet winner in T . As P = i P , any changes going from T to T must be counter to agent i s preferences. This implies x P i a for all a DT (x). So, all alternatives in DT (x) are worse than x to agent i. We want to show that there is some minimal BA-stable set S of T , such that S DT (x) = . This would guarantee the existence of an alternative a DT (x) that is also

9If no such i-variants exist, robustness of the rule would immediately follow.

in ME(T ), precluding agent i with pessimistic preferences from preferring this outcome to ME(T ). So suppose for contradiction that S is a minimal BAstable set of T such that S DT (x) = . The only way this can be the case is if S DT (x) {x}. We consider two cases. Case 1: Suppose x S. As x dominates all alternatives in DT (x), it will dominate all alternatives in S, as S DT (x). This means x is a Condorcet winner in the tournament (S {x}, T S {x}), and thus, x BA( T S {x}). So S cannot be a BA-stable set, contradicting our assumption that it is a minimal one. Case 2: Suppose instead x S. To reach our contradiction, we want to show there exists an alternative a DT (x) such that a BA( T S {a}) which would imply S is not BA-stable. We use an algorithm proposed by Hudry (2004) to ﬁnd such an alternative a BA( T S {a}). We start at

step 1 with a transitive subtournament of (S {a}, T S {a}).

Let S1 = ({x, a}, T {x,a}), for some a DT (x). We label all remaining elements of S which are all elements of DT (x) in any order from 2 to |S|. At step k, we look at the alternative labelled k, and add it to the tournament Sk 1 to create Sk, if it does not break transitivity to do so. As a dominates x, and x dominates all a DT (x), adding any alternative outside the dominion of a will break transitivity, as it will create a 3-cycle. Thus, at any step, an alternative a DT (x) will only be added to the tournament if a T a . When the algorithm terminates after iterating through all alternatives, we will be left with a subtournament S|S| of (S {a}, T S {a}). It is easy to see the resulting tournament will be transitive, and it will indeed be a maximal transitive subtournament of (S {a}, T S {a}), as no further alternatives can be added to the tournament without breaking transitivity. Importantly, the maximal element of the resulting subtournament will be a, meaning a BA( T S {a}). Thus, S cannot be an BA-stable set, which contradicts our assumption that it is a minimal one. As we have shown that no subset of DT (x) {x} can be a BA-stable set of T , any minimal BA-stable set must contain at least one element of DT (x), meaning it cannot be the case that ME(T ) P ,g i ME(T ) when e is a pessimistic preference extension.

In terms of decisiveness, ME is among the more decisive tournament solutions that fail weak resoluteness, as it is a reﬁnement of several prominent tournament solutions, including the top cycle and the Banks set (Brandt, Harrenstein, and Seedig 2017). We now show that all coarsenings of a robust SCF inherit the robustness property.

Proposition 3. If a Condorcet-consistent SCF f is robust under pessimistic preferences, then all Condorcet-consistent coarsenings of f are robust under pessimistic preferences.

Proof. Let f be a SCF that is robust under pessimistic preferences, and let f be a Condorcet-consistent coarsening of

f. Let P be a proﬁle with a Condorcet winner a. Note that f(P ) = f (P ) = {a} as both are Condorcet extensions. Suppose P is an i-variant of P for some agent i N. Because f is robust under pessimistic preferences, either (i) there must be some a f(P ) such that a P i a , or (ii) f(P ) = f(P ). If (i) is the case, then as f(P ) f (P ), a is also an element of f (P ). As f (P ) = {a}, we know a f (P ) \ f (P ), meaning by deﬁnition of a pessimistic extension that it cannot be the case that f (P ) P ,e i f (P ) for any pessimistic extension e. If (ii) is the case, we know a must also be the Condorcet winner in P as f cannot satisfy weak resoluteness if it is robust under any preference extension, and therefore does not return singletons outside the Condorcet domain. Since f is also a Condorcet extension, we know f (P ) = {a}, meaning f (P ) P ,e i f (P ).

Corollary 1. Condorcet-consistent coarsenings of ME are robust under pessimistic preferences.

Corollary 1 follows from Proposition 3 and Theorem 3, and it establishes the robustness of the Banks set. Note that Corollary 1 is not restricted to tournament-solution SCFs, but holds for all Condorcet-consistent SCFs.

5 Conclusion

We have introduced the strategyproofness-related notion of a robust Condorcet extension. We have argued that Condorcet extensions that are robust are preferable to those that are not, as we can trust that they will return true Condorcet winners when they exists. We have introduced an axiom weak resoluteness and shown that no weakly resolute tournament solution can be a robust Condorcet extension. Finally, we have shown that the minimal extending set is a robust Condorcet extension under all pessimistic preferences, and have extended this result to all coarsenings of ME. We have argued that in lieu of searching for fully strategyproof rules, a fruitful endeavour is to explore immunity against more speciﬁc manipulations that may interact with, and compromise, other desirable properties satisﬁed by manipulable social choice functions. We have scratched the surface in this paper, but have limited our exploration to robustness of irresolute rules in general, and tournament solutions in particular. These are, of course, only a small class of all Condorcet extensions, and it remains to be seen if similar results can be obtained for other classes. Finally, there are many other areas of social choice theory open to similar notions of strategyproofness. For example, while proportionality and strategyproofness cannot be satisﬁed by the same multiwinner approval voting rule (Peters 2018; Kluiving et al. 2020), one might want to ask to what degree proportionality is affected by the failure of strategyproofness.

Acknowledgements

We thank the reviewers for their extensive feedback.

References Amanatidis, G.; Birmpas, G.; and Markakis, E. 2016. On Truthful Mechanisms for Maximin Share Allocations. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI-2016).

Arrow, K. J.; Sen, A.; and Suzumura, K. 2010. Handbook of Social Choice and Welfare, volume 2. Elsevier.

Banks, J. S. 1985. Sophisticated Voting Outcomes and Agenda Control. Social Choice and Welfare 1(4): 295 306.

Barber a, S. 1977. Manipulation of Social Decision Functions. Journal of Economic Theory 15(2): 266 278.

Barber a, S.; Bossert, W.; and Pattanaik, P. K. 2004. Ranking Sets of Objects. In Handbook of Utility Theory, 893 977. Springer.

Bartholdi, J. J.; Tovey, C. A.; and Trick, M. A. 1989. The Computational Difﬁculty of Manipulating an Election. Social Choice and Welfare 6(3): 227 241.

Black, D. 1948. On the Rationale of Group Decisionmaking. Journal of Political Economy 56(1): 23 34.

Bossert, W.; and Sprumont, Y. 2014. Strategy-proof Preference Aggregation: Possibilities and Characterizations. Games and Economic Behavior 85: 109 126.

Brandl, F.; Brandt, F.; and Stricker, C. 2018. An Analytical and Experimental Comparison of Maximal Lottery Schemes. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence (IJCAI-2018).

Brandt, F. 2011. Minimal Stable Sets in Tournaments. Journal of Economic Theory 146(4): 1481 1499.

Brandt, F. 2015. Set-Monotonicity Implies Kelly Strategyproofness. Social Choice and Welfare 45(4): 793 804.

Brandt, F.; Brill, M.; and Harrenstein, P. 2016. Tournament Solutions. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 3. Cambridge University Press.

Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D. 2016. Handbook of Computational Social Choice. Cambridge University Press.

Brandt, F.; Harrenstein, P.; and Seedig, H. G. 2017. Minimal Extending Sets in Tournaments. Mathematical Social Sciences 87: 55 63.

Campbell, D. E.; and Kelly, J. S. 2003. A strategy-proofness characterization of majority rule. Economic Theory 22(3): 557 568.

Conitzer, V.; and Walsh, T. 2016. Barriers to Manipulation in Voting. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 6. Cambridge University Press.

Conitzer, V.; Walsh, T.; and Xia, L. 2011. Dominating Manipulations in Voting with Partial Information. In Proceedings of the 25th AAAI Conference on Artiﬁcial Intelligence (AAAI-2011).

Copeland, A. H. 1951. A Reasonable Social Welfare Function. University of Michigan Seminar on Applications of Mathematics to the Social Sciences.

Duggan, J.; and Schwartz, T. 2000. Strategic Manipulability Without Resoluteness or Shared Beliefs: Gibbard Satterthwaite Generalized. Social Choice and Welfare 17(1): 85 93.

Fishburn, P. C. 1977. Condorcet Social Choice Functions. SIAM Journal on Applied Mathematics 33(3): 469 489.

Fishburn, P. C. 1984. Probabilistic Social Choice Based on Simple Voting Comparisons. The Review of Economic Studies 51(4): 683 692.

Gaertner, W. 2001. Domain Conditions in Social Choice Theory. Cambridge University Press.

G ardenfors, P. 1976. Manipulation of Social Choice Functions. Journal of Economic Theory 13(2): 217 228.

Gehrlein, W. V. 2006. Condorcet s Paradox. Springer.

Gehrlein, W. V.; and Lepelley, D. 2011. Voting Paradoxes and Group Coherence. Springer.

Gibbard, A. 1973. Manipulation of Voting Schemes: A General Result. Econometrica 41(4): 587 601.

Hajaj, C.; Dickerson, J. P.; Hassidim, A.; Sandholm, T.; and Sarne, D. 2015. Strategy-Proof and Efﬁcient Kidney Exchange Using a Credit Mechanism. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI2015).

Hoang, L. N. 2017. Strategy-proofness of the Randomized Condorcet Voting System. Social Choice and Welfare 48(3): 679 701.

Hudry, O. 2004. A Note on Banks Winners in Tournaments are Difﬁcult to Recognize by G.J. Woeginger. Social Choice and Welfare 23(1): 113 114.

Kelly, J. S. 1977. Strategy-proofness and Social Choice Functions without Singlevaluedness. Econometrica 45(2): 439 446.

Kemeny, J. G. 1959. Mathematics without Numbers. Daedalus 88(4): 577 591.

Kluiving, B.; de Vries, A.; Vrijbergen, P.; Boixel, A.; and Endriss, U. 2020. Analysing Irresolute Multiwinner Voting Rules with Approval Ballots via SAT Solving. In Proceedings of the 24th European Conference on Artiﬁcial Intelligence (ECAI-2020).

Kruger, J.; and Terzopoulou, Z. 2020. Strategic Manipulation with Incomplete Preferences: Possibilities and Impossibilities for Positional Scoring Rules. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2020).

Mc Garvey, D. C. 1953. A Theorem on the Construction of Voting Paradoxes. Econometrica 21(4): 608 610.

Meir, R. 2018. Strategic voting. Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning 13(1): 1 167.

Osborne, M. J.; and Rubinstein, A. 2003. Sampling Equilibrium, with an Application to Strategic Voting. Games and Economic Behavior 45(2): 434 441. Peters, D. 2018. Proportionality and Strategyproofness in Multiwinner Elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS-2018). Reijngoud, A.; and Endriss, U. 2012. Voter Response to Iterated Poll Information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012). Sato, S. 2008. On Strategy-proof Social Choice Correspondences. Social Choice and Welfare 31(2): 331 343. Sato, S. 2013. A Sufﬁcient Condition for the Equivalence of Strategy-proofness and Nonmanipulability by Preferences Adjacent to the Sincere one. Journal of Economic Theory 148(1): 259 278. Satterthwaite, M. A. 1975. Strategy-proofness and Arrow s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions. Journal of Economic Theory 10(2): 187 217. Shoham, Y.; and Leyton-Brown, K. 2009. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press. Slater, P. 1961. Inconsistencies in a Schedule of Paired Comparisons. Biometrika 48(3 4): 303 312.