# on_swap_convexity_of_voting_rules__71676c1a.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

On Swap Convexity of Voting Rules

Svetlana Obraztsova Nanyang Technological University Singapore svetlana.obraztsova@gmail.com

Edith Elkind University of Oxford Oxford, UK elkind@cs.ox.ac.uk

Piotr Faliszewski AGH University of Science and Technology Krakow, Poland faliszew@agh.edu.pl

Obraztsova et al. (2013) have recently proposed an intriguing convexity axiom for voting rules. This axiom imposes conditions on the shape of the sets of elections with a given candidate as a winner. However, this new axiom is both too weak and too strong: it is too weak because it deﬁnes a set to be convex if for any two elements of the set some shortest path between them lies within the set, whereas the standard definition of convexity requires all shortest paths between two elements to lie within the set, and it is too strong because common voting rules do not satisfy this axiom. In this paper, we (1) propose several families of voting rules that are convex in the sense of Obraztsova et al.; (2) put forward a weaker notion of convexity that is satisﬁed by most common voting rules; (3) prove impossibility results for a variant of this deﬁnition that considers all, rather than some shortest paths.

1 Introduction Voting and elections are traditional ways in which societies of agents make decisions (Moulin 1991; Arrow, Sen, and Suzumura 2002). Since these decisions often carry signiﬁcant weight, it is important to identify suitable voting rules for each application scenario. The requirements that a voting rule should satisfy, also called axioms, are applicationdependent: e.g., in some settings in may be desirable to treat all opinions in the same way (voting rules with this property are called anonymous), while in other settings it may be more important to avoid rules that suffer from the so-called no-show paradox, where voters have an incentive to withdraw from the election. The axioms themselves can be classiﬁed in several ways. For instance, some axioms constrain the behavior of a voting rule in individual elections: this is the case, e.g., for the unanimity axiom, which requires that if all voters rank some candidate ﬁrst, the rule outputs this candidate. Other axioms relate the behavior of the rule in elections obtained from each other by some transformation: e.g., the anonymity axiom describes the behavior of the rule on proﬁles obtained from each other by permuting votes. Recently, Obraztsova et al. (2013) proposed two new axioms, which recognize the fact that collective decision-

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

making is a dynamic process, and aim to capture how voting rules should behave when voters preferences evolve. Speciﬁcally, consider a society that moves between two states A and B such that candidate a is considered to be the best choice in both states. We assume that the voters preferences change gradually, that is, at each step some voter reports a small change in her beliefs. One can then expect that it should be possible to transition from A to B so that a remains the collective choice along the way; more ambitiously, we may require that this remains the case when we pick the shortest route from A to B. Formally, Obraztsova et al. (2013) construct a graph whose vertices are all n-voter m-candidate elections, and there is an edge between two elections if one can be obtained from the other by swapping two adjacent candidates in some voter s ranking. The shortest path distance in this graph is the well-known swap distance (Deza and Deza 2009). Obraztsova et al. (2013) are interested in shapes of sets of vertices of this graph that have a common deﬁning property: for instance, these can be elections where a given candidate is ranked ﬁrst by all voters or by a strict majority of voters (such elections are known, respectively, as unanimity consensus elections and majority consensus elections), elections that are single-peaked with respect to a ﬁxed axis, or elections where a given candidate is a winner under a speciﬁc voting rule. Yet, the results of Obraztsova et al. (2013) turn out to be rather discouraging. While they do show that for most natural voting rules the sets of elections with a given winner are connected in Gn,m, i.e., it is possible to get from one election with winner a to another such election so that a stays an election winner along the way, it may be impossible to do so if one insists on staying on the shortest path between the two elections. That is, such sets are not convex, even in the sense of the somewhat non-orthodox deﬁnition that they use1 (we elaborate on the differences between their

1We remark that this is not the ﬁrst attempt to deﬁne a notion of convexity for voting rules: in particular, Saari (1990; 2003) proposed another notion of convexity, but his deﬁnition is very different in spirit, and, in particular, imposes constraints on the behavior of voting rules on elections with a different number of voters.

deﬁnition and the more standard one in Section 3; brieﬂy put, their deﬁnition is quite natural, but less demanding). In fact, Obraztsova et al. (2013) are unable to identify a single voting rule that satisﬁes their convexity axiom (the only possible exception is the Plurality rule, which satisﬁes a relaxed variant of their deﬁnition). On the other hand, they show that the sets consisting of unanimity/majority consensus elections with a given winner are convex, and this is also the case for sets of elections that are single-peaked with respect to a ﬁxed axis. Their conclusion, then, is that convexity is an appropriate notion of niceness for consensus notions (such as the unanimity consensus or the majority consensus), but not for voting rules. In this paper, we revisit this conclusion. First, we focus on the notion of convexity proposed by Obraztsova et al. (2013), and identify a family of rules that are convex, anonymous, neutral and unanimous (see Section 2 for the statements of these axioms). While it turns out that it is not too difﬁcult to satisfy these axioms simultaneously if one is willing to accept rules that are not very decisive, we explore ways to increase decisiveness while maintaining the other desiderata, and identify a voting rule with the required properties that returns a unique winner on many proﬁles. Nevertheless, the rule we propose is not a commonly used voting rule, such as Plurality, Borda, or STV, and, indeed, it is already known that these rules are not convex in the sense of Obraztsova et al. (2013). Thus, if we are interested in a notion of convexity that can be used to distinguish among common voting rules, we need a different deﬁnition. To achieve this goal, we make use of the notion of star convexity that is ﬁrmly rooted in the topology literature. Intuitively, a set is star convex if it has a central point such that all other points in the set can be reached from this point along shortest paths that stay within the set. This notion turns out to be closely related to the notion of feeble monotonicity (which Obraztsova et al. used to show their connectivity results), and for many (but not all!) voting rules we can show that the set of elections that have a given candidate as a winner is star convex. Emboldened by these positive results, we revisit the definition of convexity used by Obraztsova et al. (2013). Their deﬁnition is somewhat non-orthodox in that, instead of requiring that all shortest paths between two elements of a set lie within this set, they only require that this holds for some shortest path. Now, of course, the all-paths deﬁnition is even more demanding than the original one, but given that we have identiﬁed a voting rule that is convex according to the original deﬁnition, perhaps there are reasonable rules that satisfy this more stringent deﬁnition as well? We show that this is not the case, by proving an impossibility result. Our results indicate that convexity, as deﬁned by Obraztsova et al. (2013), is a meaningful, if stringent condition not just for consensus classes, but also for voting rules. In contrast, star convexity turns out to be closely related to existing notions of monotonicity, while building on a very different intuition; this axiom provides additional justiﬁcation for rules such as STV that are not monotone in the standard sense, but are nevertheless considered fairly wellbehaved.

The remainder of this paper is structured as follows. First, in Section 2 we introduce the necessary background regarding voting rules. Then, in Section 3 we formulate the notions of convexity that we are going to consider, starting with the original deﬁnition of Obraztsova et al. (2013). Next, we present several families of voting rules that are convex with respect to the original deﬁnition (Section 4). Section 5 presents our results for star convexity. We conclude the paper by presenting the impossibility results regarding allpaths convexity (Section 6). We omit some proofs due to space constraints.

2 Preliminaries

We write [n] to denote the set {1, . . . , n}. Given a ﬁnite set of candidates C = {c1, . . . , cm}, a vote over C is a linear order over C; a proﬁle over C is an ordered list R = (R1, . . . , Rn) of n votes over C. Given a proﬁle R = (R1, . . . , Rn), we will refer to the elements of [n] as voters; i.e., Ri is the vote of voter i in proﬁle R. We will sometimes write i in place of Ri. We will say that voter i ranks a candidate a C above b C (or, prefers a to b) if a i b. We denote the top candidate in vote Ri by top(Ri), i.e., we write a = top(Ri) if a i b for all b C \ {a}. We say that two voters disagree on a pair of candidates (a, b) C C if one of the voters ranks a above b, while the other voter ranks b above a; otherwise, we say that these voters agree on (a, b). A voting rule is a mapping F that given a proﬁle R over a set of candidates C outputs a non-empty set of candidates W = F(R) C; the candidates in W are called the winners in R under the voting rule F. A canonical example of a voting rule is the Plurality rule, which, given a proﬁle R = (R1, . . . , Rn) over a set of candidates C, outputs the set of all candidates a C such that |{i [n] : top(Ri) = a}| |{i [n] : top(Ri) = b}| for all b C. A candidate a C is a Condorcet winner in a proﬁle R over C if for each c C \ {a} more than half of the votes in R rank a above c. We say that a proﬁle R is a unanimity consensus with winner a if all votes in R rank a ﬁrst; R is a majority consensus with winner a if more than half of the votes in R rank a ﬁrst; and R is a Condorcet consensus with winner a if a is a Condorcet winner in R. Given a proﬁle R = (R1, . . . , Rn) over a set of candidates C, we say that a candidate a C is nominated in R if top(Ri) = a for some i [n]; we say that a is popular in R if |{i [n] : topi(Ri) = a}| n |C|. We denote the set of all nominated candidates in R by Nom(R), and the set of all popular candidates by Pop(R). For any proﬁle R we have Pop(R) Nom(R) and, by the pigeonhole principle, Pop(R) = ; thus, Nom and Pop are voting rules. A vote R over a set of candidates C is said to be singlepeaked with respect to an ordering < of C if for every pair of candidates a, b C\{top(R)} such that b < a < top(R) or top(R) < a < b it holds that R ranks a above b; the order < is often called an axis. A proﬁle (R1, . . . , Rn) is said to be single-peaked with respect to an axis < if for every i [n] the vote Ri is single-peaked with respect to <.

Axioms Given a permutation π : C C and a vote R over C, let π(R) denote the vote such that for every pair of candidates (a, b) C C it holds that a is ranked above b in R if and only if π(a) is ranked above π(b) in π(R). We extend this notation to proﬁles: given a permutation π : C C and a proﬁle R = (R1, . . . , Rn) over C, we denote by π(R) the proﬁle (π(R1), . . . , π(Rn)). Given a pair of candidates (a, b) C C and a proﬁle R over C, we denote by Ra b the proﬁle π(R), where π is given by π(a) = b, π(b) = a, π(c) = c for c C \ {a, b}. Also, given a permutation σ : [n] [n] and a proﬁle R = (R1, . . . , Rn), we denote by σ(R) the proﬁle (Rσ(1), . . . , Rσ(n)). Below we state the axioms that we consider in this paper.

Deﬁnition 2.1. A voting rule F is neutral if for every set of candidates C, every proﬁle R over C, every permutation π : C C, and every candidate a C it holds that a F(R) if and only if π(a) F(π(R)).

Deﬁnition 2.2. A voting rule F is anonymous if for every proﬁle R = (R1, . . . , Rn) and every permutation σ : [n] [n] it holds that F(R) = F(σ(R)).

Deﬁnition 2.3. A voting rule F is unanimous if for every set of candidates C and every proﬁle R over C in which each voter ranks the same candidate a C in the top position in their vote it holds that F(R) = {a}.

Deﬁnition 2.4. A voting rule F is weakly monotone if for every set of candidates C, every proﬁle R over C, and every candidate a F(R) it holds that every proﬁle R obtained from R by picking a vote Ri in R with top(Ri) = a and swapping a with the candidate ranked right above her in Ri satisﬁes a F(R ).

We also consider the following weaker notion of monotonicity proposed by Obraztsova et al. (2013).

Deﬁnition 2.5. A voting rule F is feebly monotone if for every set of candidates C, every proﬁle R over C, and every candidate a F(R) it holds that either (1) top(Ri) = a for all i [n], or (2) there exists a vote Ri with top(Ri) = a such that the proﬁle R obtained from R by swapping a with the candidate ranked right above her in Ri satisﬁes a F(R ).

Swap distance and the graph Gn,m Given two votes Ri and Rj over a set of candidates C, the swap distance between Ri and Rj, denoted by dswap(Ri, Rj), is the number of pairs of candidates (a, b) C C such that a i b, but b j a. This notion can be extended to proﬁles: given two n-voter proﬁles R = (R1, . . . , Rn) and R = (R 1, . . . , R n) over a set of candidates C, the swap distance dswap(R, R ) is computed as

i [n] dswap(Ri, R i). Given a set of candidates C, |C| = m, and a positive integer n, consider the graph Gn,m = (V, E) whose vertices are all n-voter proﬁles over C and where we have an edge between two proﬁles R and R if and only if dswap(R, R ) = 1; that is, we have an edge between R = (R1, . . . Rn) and R = (R 1, . . . , R n) if and only if there is a voter j [n] such that dswap(Rj, R j) = 1 and for each i [n] \ {j} we have Ri = R i. We write G instead of Gn,m when the values

of n and m are clear from the context. Note that the length of a shortest path between two vertices of this graph is exactly the swap distance between them. A voting rule F can be viewed as a coloring of this graph (albeit one where each vertex may have several different colors): we identify each candidate with a color, so that the set of colors assigned to a proﬁle R is exactly F(R). Given a candidate a C, we denote by cola(Gn,m, F) the set of all vertices that are colored with a under F: cola(Gn,m, F) = {R : a F(R)}.

3 Deﬁnitions of Convexity Obraztsova et al. (2013) deﬁned convexity as follows. Deﬁnition 3.1. A subset V of the vertices of the graph Gn,m = (V, E) is said to be convex if for every R, R V there exists a path from R to R that lies entirely within V and has length d, where d is the length of a shortest path between R and R in G. A voting rule F is said to be convex if for every set of candidates C, every n 1, and every a C the set cola(Gn,|C|, F) is convex.

-Convexity Deﬁnition 3.1 is different from the usual one, used in topology, in that instead of requiring all shortest paths to stay within the set, it requires this for only one of them. In our context, the standard deﬁnition of convexity takes the following form. Deﬁnition 3.2. A subset V of the vertices of the graph Gn,m = (V, E) is -convex if for every R, R V and every shortest path ρ between R and R in G it holds that every proﬁle R on ρ belongs to V . A voting rule F is - convex if for every set of candidates C, every n 1, and every a C the set cola(Gn,|C|, F) is -convex. To avoid confusion, from now on we will refer to the notion of convexity from Deﬁnition 3.1 as -convexity. Clearly, if a set of proﬁles is -convex then it is -convex, but the converse is not true, as shown by the following example. Example 3.3. Fix n 1, and consider the space of all nvoter proﬁles over the set of candidates {a, b}. Theorem 4.8 in the work of Obraztsova et al. implies that the set of proﬁles where a strict majority of voters prefer a to b is -convex. However, this set if not -convex for all n 3. Indeed, let k = n

2 + 1, and consider a pair of proﬁles R, R , where in R the ﬁrst k voters prefer a to b and the remaining voters prefer b to a, whereas in R the last k voters prefer a to b and the remaining voters prefer b to a. In both proﬁles a is a strict majority winner, but there is a path from R to R that goes through a proﬁle where 2(n k) n/2 voters rank b ﬁrst: on this path, we ﬁrst swap a and b in the preferences of the ﬁrst n k voters, and then swap them in the preferences of the last n k voters. We discuss -convexity in more detail in Section 6.

Star Convexity In geometry, a subset S of RN is said to be star convex, or star-shaped, if there exists a point c S such that for every a S the shortest path between a and c lies entirely in S; the set of all points c that have this property is called the kernel of S (Preparata and Shamos 1985). To extend this deﬁnition to subsets of the graph Gn,m, we have to decide whether we are interested in all shortest paths

between c and a or some shortest path between these points; we refer to the corresponding notions as star -convexity and star -convexity. Formally, we have the following deﬁnition.

Deﬁnition 3.4. A subset V of vertices of the graph Gn,m = (V, E) is star -convex if there exists a proﬁle R V such that for every R V all shortest paths between R and R lie entirely within V ; the set of all such R is called the -kernel of V . Further, V is star -convex if there exists a proﬁle R V such that for every R V there exists a path of length d between R and R that lies entirely within V , where d is the length of a shortest path between R and R in Gn,m; the set of all such R is called the -kernel of V . A voting rule F is star -convex (respectively, star -convex) if for every set of candidates C, every n 1, and every a C the set cola(Gn,|C|, F) is star -convex (respectively, star -convex).

We explore these two notions of star convexity in Section 5.

4 -Convexity Obraztsova et al. (2013) did not identify any -convex voting rules in their work. To close this gap, we describe several families of rules that are anonymous, neutral, unanimous and -convex. We start with the least decisive rule in this class, and then explore various ways to reﬁne it. Let FU be a voting rule deﬁned as follows: given a proﬁle R = (R1, . . . , Rn), if there exists an a C such that top(Ri) = a for all i [n], output {a}; else, output C.

Theorem 4.1. FU is anonymous, neutral and unanimous. It is -convex whenever n 3 .

Proof. It is immediate that FU is anonymous, neutral and unanimous. Now, suppose that n 3, and consider two proﬁles R = (R1, . . . , Rn) and R = (R 1, . . . , R n) over a candidate set C such that for some candidate a C we have a FU(R) FU(R ), or, equivalently, for each candidate b C \ {a} neither R nor R is a unanimity consensus with winner b. We will now describe a shortest path from R to R that avoids all proﬁles where all voters rank some candidate b C \ {a} ﬁrst. First, we use bubble sort to rearrange the candidates in the bottom m 1 positions in each vote Ri so that they are ordered according to R i. Formally, we consider a maximal sequence of proﬁles starting with R where each proﬁle is obtained from its predecessor by picking a voter i [n] and two candidates b, c C \ top(Ri) that are adjacent in i s preference order and such that the current vote of voter i disagrees with R i on (b, c), and ordering b and c according to R i. Let R = (R 1, . . . , R n) be the last proﬁle in this sequence. This sequence of proﬁles forms a preﬁx of a shortest path from R to R , and, since we do not touch the top candidate in any vote, we have FU(R ) = FU(R). Now, if top(Ri) = top(R i) for some i [n], then top(R i) is ranked in the second position in R i . Thus, to transform R into R it remains to swap the ﬁrst and the second candidate in R i for each i [n] such that top(Ri) = top(R i). Suppose ﬁrst that top(R i) = a for some i [n]. If top(Ri) = a as well, we can perform the remaining swaps

in any order: at any point in time, at least one voter ranks a ﬁrst, and this ensures that a is among the winners under FU. If top(Ri) = a, we can ﬁrst swap a and top(Ri) in the preferences of the ﬁrst voter: from then on, there exists a voter than ranks a ﬁrst. On the other hand, suppose that top(R i) = a for all i [n]. Since a FU(R ), there exist two distinct candidates b, c C and two voters i, j [n] such that top(R i) = b, top(R j) = c. As we assume that n 3, there is also a voter k [n] \ {i, j}; without loss of generality, we can assume that top(Rk) = b. We can then ﬁrst swap b and top(Ri) in the preferences of the i-th voter (and do nothing if top(Ri) = b), and then swap c and top(Rj) in the preferences of the j-th voter. We then perform the remaining swaps. After the ﬁrst step, the i-th voter and the k-th voter rank different candidates in the ﬁrst position, and from the second step onward the i-th and the j-th voter rank different candidates in the ﬁrst position, so our rule outputs C on all these proﬁles.

The rule FU is the minimally decisive rule that satisﬁes anonymity, neutrality and unanimity: it outputs a single winner if and only if this is required by the unanimity axiom, and otherwise it outputs the entire set C. There are two ways to obtain a more decisive rule based on similar intuition: ﬁrst, we can try to broaden the range of scenarios where our rule identiﬁes a clear winner (e.g., by replacing the unanimity consensus with Condorcet consensus), and second, even when there is no clear winner, we can try to eliminate the least popular candidates and output Nom(R) or, even more decisively, Pop(R) instead of C. It turns out that these ideas can be combined. Given a proﬁle R = (R1, . . . , Rn) over a set of candidates C and q > n 2 , we say that a candidate a C is a q-Condorcet winner if for every b C \{a} at least q voters prefer a to b. Let Fq,Cond be the rule that, given a proﬁle R over C, outputs a candidate a C if she is a q-Condorcet winner in R; if there is no such candidate, Fq,Cond outputs C. We will also consider variants of this rule that, given a proﬁle R that does not have a q-Condorcet winner, output all candidates in Nom(R), or, alternatively, in Pop(R); we denote these rules by FNom q,Cond and FPop q,Cond It turns out that all these rules are -convex whenever q n

Theorem 4.2. For every integer q such that n

2 +2 q n the rules Fq,Cond, FNom q,Cond and FPop q,Cond are anonymous, neutral, and unanimous. They are -convex whenever n 3.

The rules considered in Theorem 4.2 are considerably more decisive that FU. This is particularly true for FPop q,Cond with q = n

2 + 2, which is the most decisive rule among the ones we consider. While variants of these rules with q = n

2 + 1 are even more decisive, we can show that they are not -convex, so Theorem 4.2 is tight in this regard. The rules discussed in this section are similar in spirit to the classic rule of Black, which outputs the Condorcet winner when it exists and outputs all Borda winners otherwise (under the Borda rule, each candidate in an m-candidate election gets j points from each voter who ranks her in posi-

tion m j, and the winners are the candidates with the highest total number of points) (Black 1958). Our rules, too, output the obvious winner when it exists and otherwise they output all acceptable candidates.

5 Star Convexity In this section we provide an in-depth exploration of the two notions of star convexity proposed in Section 3. We start by observing that both the majority consensus and the Condorcet consensus are star -convex (and hence star - convex).

Proposition 5.1. For any candidate set C and a candidate a C, both the set of all majority consensuses with winner a and the set of all Condorcet consensuses with winner a are star -convex. Moreover, the unanimity consensus with winner a lies in the -kernel of both of these sets.

Proof. Let R be a unanimity consensus with winner a, and let R be a majority consensus with winner a. At least n/2 + 1 voters in R rank a ﬁrst. In every proﬁle on every shortest path from R to R these voters still rank a ﬁrst, so all these proﬁles are majority consensuses with winner a. Similarly, let R be a Condorcet consensus with winner a. Consider a candidate c C \{a}. At least n/2 +1 voters in R rank a above c. In every proﬁle on every shortest path from R to R these voters still rank a above c. As this holds for every c C \ {a}, all these proﬁles are Condorcet consensuses with winner a.

5.1 Star -Convexity vs -Convexity It is instructive to compare -convexity and star -convexity. Intuitively, both are obtained from -convexity by replacing a quantiﬁer with an quantiﬁer: the former relaxes -convexity by considering, for each pair of proﬁles, some shortest path between these proﬁles (rather than all shortest paths), while the latter ﬁxes some proﬁle and only considers pairs of proﬁles that involve this proﬁle, but then imposes constraints on all shortest paths between the proﬁles in each pair. Obviously, star -convexity is a relaxation of both of these notions. We will now demonstrate that star - convexity and -convexity are incomparable: there exists a set that is -convex, but not star -convex and vice versa. For the ﬁrst direction, we show that the set of proﬁles that are single-peaked with respect to a given axis is not star - convex. Since, as shown by Obraztsova et al. (2013), this set is -convex, we know that it also is star -convex.

Proposition 5.2. For every candidate set C with |C| 4, every linear order < over C and every n > 0, the set of nvoter proﬁles that are single-peaked with respect to < is not star -convex.

Proof. Fix a linear order < over C, and let P be the set of all n-voter proﬁles that are single-peaked with respect to <. Assume without loss of generality that < orders the candidates as c1 < < cm. Suppose for the sake of contradiction that P is star - convex, and let R be some proﬁle in the -kernel of P. We can assume without loss of generality that the ﬁrst voter in

R ranks some candidate cj with j m/2 + 1 ﬁrst. Since m 4, this means that he ranks c3 above c2. Now, consider the proﬁle R where all voters rank the candidates as c1 cm; clearly, this proﬁle is single-peaked with respect to <. Let R be the proﬁle obtained from R by swapping c2 and c3 in the ﬁrst vote. Obviously, R lies on a shortest path from R to R. However, it is not single-peaked with respect to <: the only vote that ranks c1 ﬁrst and is single-peaked with respect to < is c1 cm.

An example of a subset of Gn,m that is star -convex, but not -convex is provided by a ball of radius d, i.e., the set B(E, d) of all proﬁles that are at distance at most d from a given proﬁle E.

Proposition 5.3. For any proﬁle R and any d 1 the set B(R, d) is star -convex. However, if d = m 1, then B(R, d) is not -convex.

Proof. To prove our ﬁrst claim, we observe that R lies in the -kernel of B(R, d): for every proﬁle R at distance d d from R it holds that every proﬁle on every shortest path from R to R is at distance at most d from R. To prove the second claim, ﬁx a proﬁle R = (R1, . . . , Rn) over {c1, . . . , cm}. Assume without loss of generality that R1 is given by c1 cm. Let R = (R 1, . . . , R n) be the proﬁle obtained from R by pushing c1 to the bottom of the ﬁrst vote, i.e., R 1 is given by c2 cm c1, and R i = Ri for i = 2, . . . , n. Similarly, let R = (R 1, . . . , R n) be the proﬁle obtained from R by pushing cm to the top of the ﬁrst vote, i.e., R 1 is given by cm c1 cm 1, and R i = Ri for i = 2, . . . , n. Note that both R and R are at swap distance m 1 from R. Now, let R = (R 1, . . . , R n) be the ﬁrst proﬁle on some shortest path from R to R . Clearly, R i = Ri for each i = 2, . . . , m. Further, the only pairs of candidates that R 1 and R 1 disagree on are (c1, c2), . . . , (c1, cm 1) and (cm, c2), . . . , (cm, cm 1). Among these pairs, the only one that is adjacent in R 1 (and therefore available for swapping) is (cm, cm 1), so it has to be the case that the ﬁrst vote in R is c2 cm cm 1 c1. But then R is at swap distance m from R, i.e., does not belong to B(R, m 1).

5.2 Star Convexity of Voting Rules We now move on to the study of voting rules. Our results for star -convexity are similar to known results for -convexity: while we were able to get positive results for consensus classes, most voting rules turn out not to be star -convex. We provide a proof for Plurality, but a similar argument works for many other common voting rules.

Proposition 5.4. If m 3 and n 9, the Plurality rule is not star -convex.

Proof. Fix a candidate set C and a candidate a C, and suppose for the sake of contradiction that the set of all nvoter proﬁles over C that have a as their Plurality winner has a non-empty -kernel. Let R be some proﬁle in this - kernel. Pick two distinct candidates b, c C \ {a}. We can assume without loss of generality that the ﬁrst n/2 voters in R prefer b to c. Now, consider a proﬁle R where the ﬁrst

n/3 voters rank c ﬁrst and b second, the next n/3 voters rank b ﬁrst, and the remaining voters rank a ﬁrst. Clearly, a is a Plurality winner at this proﬁle. Let R be the proﬁle obtained from R by swapping b and c in the ﬁrst n/3 votes. Clearly, this proﬁle is on a shortest path from R to R. However, in this proﬁle b is ranked ﬁrst 2 n/3 times, while a is ranked ﬁrst n 2 n/3 times, and for n 9 we have 2 n/3 > n 2 n/3 , so a is not a Plurality winner at this proﬁle.

However, if we further relax our notion of convexity and consider star -convexity, we obtain a positive result, by establishing a link between this notion of convexity and feeble monotonicity.

Theorem 5.5. Every feebly monotone unanimous voting rule F is star -convex. Moreover, for every candidate a C every unanimity consensus with winner a is in the - kernel of cola(G, F).

Proof. Fix a feebly monotone unanimous voting rule F and a candidate a. Consider two proﬁles R = (R1, . . . , Rn) and R = (R 1, . . . , R n) over a candidate set C such that R is a unanimity consensus with winner a F(R). If all voters in R rank a ﬁrst, then we are done: in any proﬁle R that lies on a shortest path from R to R candidate a is ranked ﬁrst in all votes, so a F(R ) by unanimity. Otherwise, by feeble monotonicity of F we can ﬁnd a voter i [n] with top(R i) = a such that a remains a winner after being swapped with the candidate ranked right above her in R i. When we perform this swap, we obtain a proﬁle that lies on a shortest path from R to R. We repeat this step until we arrive to a proﬁle R where a is ranked ﬁrst in every vote. Now we can transform this proﬁle into R by only swapping the pairs of candidates that contribute to the swap distance between R and R; by unanimity all proﬁles along the way have a as a winner.

To appreciate the power of Theorem 5.5, recall that almost all common voting rules, including, e.g., Plurality, Borda, and STV, are feebly monotone (Obraztsova et al. 2013). It is natural to ask whether the -kernel of cola(G, F) is equal to the respective unanimity consensus. In general, this is not the case: for many common voting rules the - kernel of cola(G, F) is considerably larger. In particular, for weakly monotone rules that are majority-consistent, i.e., elect the majority winner when one exists, the -kernel contains the respective majority consensus.

Proposition 5.6. Every weakly monotone majorityconsistent rule F is star -convex, and for every candidate a C every majority consensus with winner a is in the -kernel of cola(G, F).

It would be interesting to characterize the -kernel of cola(G, F) for common voting rules. E.g., it is not clear if for weakly monotone Condorcet-consistent rules the kernel of cola(G, F) contains the respective Condorcet consensus. The following result can be seen as a partial converse of Proposition 5.6: it shows that star -convexity, together with other standard axioms, implies weak monotonicity.

Proposition 5.7. Every star -convex anonymous, neutral and unanimous voting rule F is weakly monotone. Moreover, the -kernel of cola(G, F) consists of unanimity consensus proﬁles with winner a.

6 -Convexity In this section, we explore the possibilities offered by the notion of convexity that is most similar to the classic notion of convexity in geometry, namely, -convexity.

6.1 Examples and Counterexamples While Example 3.3 illustrates that even simple voting rules for two candidates may fail to be -convex, the following proposition establishes that there are interesting sets of proﬁles that have this property.

Proposition 6.1. Given a candidate set C and a candidate a C, let Un(a) denote the set of all n-voter proﬁles over C where each voter ranks a ﬁrst. Then Un(a) is -convex.

Proof. Let R and R be two n-voter proﬁles over C such that both in R and in R all voters rank a ﬁrst. Consider a voter i [n]. For every c C \ {a}, the votes Ri and R i agree on (a, c), so the pair (a, c) does not contribute to dswap(Ri, R i). Thus, on any shortest path from R to R in Gn,m candidate a is not swapped with c in the i-th vote. Hence, in every proﬁle on this path voter i ranks a ﬁrst. As this is true for every voter i, the proof is complete.

Proposition 6.1 can be viewed as a special case of a more general construction, which is suggested by Nehring and Puppe (2007). Given a candidate set C, |C| = m, let S = {(cj1, ck1), . . . , (cjs, cks)} be a set of s pairs of candidates in C. The sets {j1, k1}, . . . , {js, ks} are not required to be pairwise disjoint: e.g., we can have j1 = j2 or j3 = k5. Consider the set VS of all votes where cjℓis ranked above ckℓfor all ℓ= 1, . . . , s; we will say that VS is the set of all votes that are restricted by S. This set (viewed as a subset of G1,m) is -convex: as we move from one vote in VS to another along a shortest path, we only swap pairs of candidates that contribute to the swap distance between the votes, so we never swap cjℓand ckℓ, which means that we stay within VS. Of course, VS can be empty; this happens if the constraints imposed by S are incompatible with a linear order over C. This construction can be extended to subsets of Gn,m in a natural way: for each voter i [n] we ﬁx a set Si of pairs of candidates, and consider the set V(S1,...,Sn) of all proﬁles where i s vote is restricted by Si. Clearly, VS1,...,Sn is - convex; the argument is the same as in the case of n = 1. This construction produces many examples of -convex sets of proﬁles. In particular, it implies Proposition 6.1: it sufﬁces to set Si = {(a, c) | c C \ {a}} for all i [n]. However, it is easy to see that many other sets of similar proﬁles are not -convex. For instance, this holds for the set of all proﬁles that have a given candidate as their strict majority winner or their Condorcet winner.

Proposition 6.2. Given a candidate set C and a candidate a C, let Mn(a) denote the set of all n-voter proﬁles over C where more than n/2 voters rank a ﬁrst, and let Cn(a)

denote the set of all n-voter proﬁles over C where a is the Condorcet winner. If |C| 2 and n 3, then for every a C the sets Mn(a) and Cn(a) are not -convex.

Proof. The proof is a straightforward extension of Example 3.3: we can simply pad each vote in R and R with m 2 dummy candidates that are ranked in positions 3, . . . , m and are ordered in the same way in each vote.

Another illustration that -convexity is a very demanding notion is provided by the class of proﬁles single-peaked with respect to a given axis. Indeed, Obraztsova et al. (2013) argue that the set of n-voter m-candidate proﬁles that are single-peaked with respect to a given axis < is -convex for all n, m 1. However, by Proposition 5.2 this set is not star -convex and hence not -convex.

6.2 -Convexity of Voting Rules We will now formalize the intuition that no reasonable voting rule is -convex, by characterizing voting rules that satisfy -convexity and other well-studied axioms: it turns out that a voting rule is neutral, unanimous and -convex if and only if it is a dictatorship, and a voting rule is neutral, anonymous and -convex if and only if it outputs the entire set of candidates on every proﬁle. Recall that a voting rule F is a dictatorship if there exists a voter i [n] such that on any proﬁle R the rule F outputs the top candidate in Ri.

Theorem 6.3. A voting rule is neutral, unanimous and - convex if and only if it is a dictatorship.

Proof. It is immediate that a dictatorship is neutral, unanimous and -convex; in particular, for every two proﬁles where a voter i ranks a candidate a ﬁrst, it holds that in every proﬁle that lies on a shortest path between these two proﬁles voter i ranks a ﬁrst. For the converse direction, ﬁx a voting rule F that is neutral, unanimous and -convex. Consider a candidate a C. We claim that for each n > 1 there exists an n-voter proﬁle where a is nominated, but is not the unique winner under F. Indeed, consider a proﬁle R where some voters rank a ﬁrst and the remaining voters rank b ﬁrst. If a is the unique winner in R then by neutrality b must be the unique winner in π(Ra b), yet some voters in Ra b rank a ﬁrst. Let k be the largest integer such that there exists a proﬁle R where k voters rank a ﬁrst, yet a is not the unique winner under F; we have argued that k 1, and, by unanimity, k < n. Fix some such proﬁle Ra and let S [n] be the set of voters in Ra who rank a ﬁrst. As F(Ra) = {a}, there exists a candidate b F(Ra) \ {a}. Note that, by neutrality, for any candidate c C and any proﬁle where more than k voters rank c ﬁrst it holds that c is the unique winner under F. We will now argue that k = n 1. Suppose for the sake of contradiction that k n 2. Consider a proﬁle R where some voter i [n] \ S ranks a ﬁrst, while all other voters rank b ﬁrst. In R there are n 1 > k voters who rank b ﬁrst, so F(R ) = {b}. Thus, b F(R ) F(Ra). Now, consider the proﬁle obtained from Ra by shifting a to the

top of the i-th vote. In this proﬁle, k + 1 voters rank a ﬁrst, so a is the unique winner under F. On the other hand, this proﬁle lies on a shortest path from Ra to R , so we obtain a contradiction with -convexity of F. Now, let i be the unique voter in [n]\S. Consider an arbitrary proﬁle R where all voters in S rank a ﬁrst, and i ranks some candidate c C ﬁrst. We claim that F(R) {a, c}. Indeed, suppose that d F(R) for some d C \ {a, c}. Then by neutrality we have d F(Ra c). But there is a shortest path from R to Ra c that goes through a proﬁle where all voters rank a ﬁrst. The unique winner at that proﬁle is a by unanimity, a contradiction with -convexity of F. By the same argument, F(R) = {a, c}. Indeed, if F(R) = {a, c}, then by neutrality we have F(Pa c) = {a, c}, yet there is a shortest path from R to Ra c that goes through a proﬁle where all voters rank a ﬁrst. The argument in the previous paragraph implies that in Ra voter i ranks b ﬁrst, and F(Ra) = {b}. Hence by neutrality F(Ra a b) = {a}. But this means that b is the unique winner in any proﬁle R where all voters in S rank a ﬁrst, but i ranks b ﬁrst: indeed, we already know that F(R) {a, b}, and if a F(R), we get a contradiction since there is a shortest path from R to Ra a b that goes through a proﬁle where all voters rank b ﬁrst (and where b is the unique winner by unanimity). By neutrality, it holds that in any proﬁle where all voters in S rank some candidate c ﬁrst, but voter i ranks another candidate d ﬁrst, d is the unique winner, i.e., voter i is a dictator for all proﬁles of this type. It remains to show that i is also a dictator when not all voters in S rank the same candidate ﬁrst. To this end, consider an arbitrary proﬁle R and assume that i ranks candidate a ﬁrst, but c F(R) for some c C \ {a}. Let R be the proﬁle where i ranks c ﬁrst, but all voters in S rank a ﬁrst. As argued in the previous paragraph, we have F(R ) = {c}. Consider the proﬁle obtained by shifting a to the top of the i-th vote in R . In this proﬁle a is the unique winner, but it lies on a shortest path from R to R , a contradiction with -convexity of F. This completes the proof.

For our second characterization result we give up unanimity, but require anonymity. The resulting rule is the trivial rule that always outputs the entire set C.

Theorem 6.4. If the number of voters is at least 3, then a voting rule is neutral, anonymous and -convex if and only if it always outputs the entire set of candidates C.

Theorems 6.3 and 6.4 can be seen as impossibility results, since they show that -convex voting rules are bound to be either dictatorships or completely non-decisive. Note, however, that similar conclusions follow from, e.g., requiring that a voting rule is strategy-proof, in the sense that no voter can improve the election outcome from their perspective by casting a vote that differs from their true preference order (Gibbard 1973; Satterthwaite 1975). Arguably, then, our negative results suggest that -convexity is, in fact, a very attractive notion. It is well-known that there are restricted domains that admit strategyproof voting rules (Black 1958); is it perhaps the case that there are attractive voting rules that are -convex on restricted domains?

7 Conclusions

We have built on the idea of -convexity of voting rules, introduced by Obraztsova et al. (2013). We have introduced - convexity, which strengthens -convexity, star -convexity, which relaxes it, and star -convexity, which is incomparable to -convexity. We have shown that -convexity is such a demanding notion that no reasonable voting rule satisﬁes it, but nonetheless we have found a few natural sets of elections that are -convex. On the other hand, we have shown that many natural voting rules are star -convex; indeed, we have linked star -convexity to the notion of feeble monotonicity, which improves upon the result of Obraztsova et al. (2013) that establishes a connection between feeble monotonicity and connectivity. There is a number of research directions that stem from our work. First, we would like to build on the results of Section 4 to obtain a complete characterization of anonymous, neutral, unanimous and -convex voting rules. Further, it is remarkable that most of the rules considered in Section 4 are not star -convex, and it would be interesting to identify further examples of star -convex voting rules.

8 Acknowledgments

We are grateful to the reviewers for their helpful and encouraging comments. S. Obraztsova was supported by Tier-1 grant of MOE (Singapore) 2018-T1-001-118, E. Elkind was supported by ERC grant number 639945 (ACCORD), P. Faliszewski was supported by the funds assigned to the AGH University by the Polish Ministry of Science and Higher Education.

Arrow, K.; Sen, A.; and Suzumura, K., eds. 2002. Handbook of Social Choice and Welfare, Volume 1. Elsevier. Black, D. 1958. The Theory of Committees and Elections. Cambridge University Press. Deza, M., and Deza, E. 2009. Encyclopedia of Distances. Springer-Verlag. Gibbard, A. 1973. Manipulation of voting schemes. Econometrica 41(4):587 601. Moulin, H. 1991. Axioms of Cooperative Decision Making. Cambridge University Press. Nehring, K., and Puppe, C. 2007. The structure of strategyproof social choice part I: General characterization and possibility results on median spaces. Journal of Economic Theory 135(1):269 305. Obraztsova, S.; Elkind, E.; Faliszewski, P.; and Slinko, A. M. 2013. On swap-distance geometry of voting rules. In Proceedings of AAMAS-13, 383 390. Preparata, F. P., and Shamos, M. I. 1985. Computational geometry: an introduction. New York, USA: Springer-Verlag. Saari, D. 1990. Consistency of decision processes. Annals of Operations Research 23(1):103 137. Saari, D. 2003. Basic Geometry of Voting. Springer-Verlag.

Satterthwaite, M. 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.