Finite Local Consistency Characterizes Generalized Scoring Rules

1 Introduction

Computational social choice is a rapidly growing research area within artificial intelligence and multiagent systems. Often, agents have different preferences over a set of alternatives, and a common decision must be made. One way to resolve this problem is to ask each agent to report her preferences (rank the alternatives), and then apply a voting rule to the vector of rankings to select the winning alternative.

Sometimes, an agent can make herself better off by reporting false preferences. In this case, we say that the voting rule is manipulable. If a voting rule is not manipulable, then it is said to be strategy-proof. Unfortunately, no voting rule that satisfies certain extremely natural properties can be strategy-proof, due to the celebrated Gibbard-Satterthwaite Theorem [Gibbard, 1973; Satterthwaite, 1975]. In recent

Vincent Conitzer

Department of Computer Science Duke University

Durham, NC 27708, USA

conitzer@cs.duke.edu

years, researchers in the computational social choice community have tried to circumvent this impossibility result by investigating whether there are desirable voting rules that are computationally hard to manipulate. The idea is that even if a successful manipulation exists, it will not occur unless the agent can discover the manipulation. It has been shown that, in various circumstances-that is, for various rules, numbers of manipulators, manipulation goals, etc.-finding a successful manipulation is NP-hard [Bartholdi et al., 1989; Bartholdi and Orlin, 1991; Conitzer and Sandholm, 2003; Elkind and Lipmaa, 2005; Conitzer et al., 2007; Hemaspaandra and Hemaspaandra, 2007; Faliszewski et al., 2008; Xia et al., 2009].

Unfortunately, all of these results are worst-case results. That is, there are some cases where manipulation is hard (if P̸=NP), but manipulation might be easy most of the time. Some recent research suggests that this is indeed the case [Procaccia and Rosenschein, 2007b; Conitzer and Sandholm, 2006; Procaccia and Rosenschein, 2007a; Zuckerman et al., 2009; Xia and Conitzer, 2008]. Specifically, we [Xia and Conitzer, 2008] introduced a new class of voting rules called generalized scoring rules (GSRs), and studied the probability that the manipulators are able to influence the outcome of the election, given a distribution over the nonmanipulators' votes. Under some minor conditions on the rule and distribution, we showed the following results (generalizing earlier work for positional scoring rules [Procaccia and Rosenschein, 2007a]). When the number of manipulators is relatively small (o(np ), where n is the number of voters, and p < 12 ), this probability goes to zero. On the other hand, when the number of manipulators is relatively large (O(np ) and o(n), where 12 < p), the probability that the manipulators can make any alternative win goes to one (under some conditions on the distribution and the rule). This only leaves a knifeedge case where there are Θ(√n) manipulators; see [Walsh, 2009] for an empirical study of this case.

Moreover, to argue the relevance of our results, we showed that a variety of common rules fall into the category of GSRs, and remarked that we did not know of any commonly studied rule that is not a GSR. (However, we did not give any formal result about the generality of this class of rules.) The apparent wide applicability of GSRs makes this class potentially interesting from the perspective of other problems in computational social choice. Indeed, some such uses are quite obvious. GSRs map every vote to a vector of scores (which are not necessarily associated with alternatives), and the outcome of the rule is based strictly on the sum of these vectors. As a result, the votes of a subset of the electorate can be summarized completely by the sum of their score vectors. (The problem of summarizing the votes of a subelectorate was recently introduced and studied [Chevaleyre et al., 2009].) In fact, the definition of GSRs is even more restrictive: the final outcome only depends on direct comparisons among the components of the summed score vector. For example, the outcome may depend on a comparison between the first component and the third component of the summed vector; then, it does not matter (for this comparison) whether these components are 42 and 50, respectively, or 101 and 967, because in both cases component 1 is smaller. Because of this, the GSR framework is also useful for preference elicitation, specifically, for determining whether enough information has been elicited from the voters to declare the winner. In particular, if it becomes clear that the remaining (not yet elicited) information about the voters' preferences can no longer change any of the comparisons in scores, then we can terminate elicitation.

One important open problem posed in [Xia and Conitzer, 2008] is to give a natural axiomatic characterization of the class of GSRs, based on some criteria that we would like voting rules to have. Such axiomatizations are important because they give us deeper insight into the rules, and can often be used to prove important results about these rules. For GSRs, having an axiomatic characterization is especially important in order to know how the frequency-of-manipulability results in [Xia and Conitzer, 2008], which are negative results for the agenda of making manipulation computationally hard, might be circumvented. Axiomatic characterization of voting rules is a common topic in the social choice literature. For two alternatives, the majority rule has been characterized in [May, 1952]. Young characterized positional scoring rules by consistency, neutrality, and anonymity [Young, 1975]. When ties are not possible (the voting rule always produces a single winner), we say that an anonymous voting rule r is consistent if the following holds: for any profiles (multisets of votes) P1 and P2 with r(P1) = r(P2) = c, we must have r(P1 ∪ P2) = c. Young's paper [Young, 1975] also allows for ties, so that r is a set-valued function; the more general definition of consistency is that if r(P1) ∩ r(P2) ̸= ∅, then r(P1 ∪ P2) = r(P1) ∩ r(P2). (We note that the union of two multisets adds the multiplicities.) However, in this paper we will only consider rules that always produce a single winner.

In this paper, we introduce a new criterion for voting rules: finite local consistency. A voting rule satisfies finite local consistency (FLC) if the set of all profiles can be partitioned into finitely many parts, such that the voting rule is consistent within each part. The minimum number of parts for a rule is the degree of consistency for the rule. For example, a consistent rule has degree of consistency 1. We then characterize generalized scoring rules by anonymity and finite local consistency, and we show that the order of a GSR (that is, the dimension of the score vector) is related to the degree of consistency of the rule. It follows that Dodgson's rule is not a GSR, because it does not satisfy homogeneity [Brandt, 2009], and FLC is a stronger property than homogeneity. Finally, we give lower and upper bounds on the degree of consistency for some common voting rules.

2 Preliminaries

Basics of voting. Let C = {c1, . . . , cm} be the set of alternatives (or candidates). A linear order on C is a transitive, antisymmetric, and total relation on C. The set of all linear orders on C is denoted by L(C). An n-voter profile P on C consists of n linear orders on C. That is, P = (V1, . . . , Vn), where for every i ≤ n, Vi ∈ L(C). The set of all profiles on C is denoted by P(C). In the remainder of the paper, m denotes the number of alternatives and n denotes the number of voters (agents). A (voting) rule r is a function from the set of all profiles on C to C, that is, r : P(C) → C. A rule r is anonymous if the output of the rule is insensitive to the names of the voters; in this case, we can think of a profile as a multiset rather than a vector. An anonymous rule r is homogenous if for any profile P and any k ∈ N, k > 0, r(P) = r(kP), where kP is the profile composed of k copies of P .

Common rules. Common rules are anonymous and homogenous, including the following example rules:

Copeland: For any two alternatives ci and cj, we can simulate a pairwise election between them, by seeing how many votes prefer ci to cj, and how many prefer cj to ci. Then, an alternative receives one point for each win in a pairwise election. Typically, an alternative also receives half a point for each pairwise tie. The winner is the alternative who has the highest score.

Bucklin: An alternative c's Bucklin score is the smallest number k such that more than half of the votes rank c among the top k alternatives. The winner is the alternative that has the smallest Bucklin score. Ties are broken by the number of votes that rank an alternative among the top k.

Other common voting rules include positional scoring rules, STV, maximin, and ranked pairs. Due to space constraint, we omit their definitions here. All the above rules need some tiebreaking mechanism. In this paper, we assume nothing about this mechanism, except that in each voting rule, ties are broken in a consistent way.

Generalized scoring rules [Xia and Conitzer, 2008]. Let K = {1, . . . , k}.

Definition 1 For any ⃗a,⃗b ∈ Rk , we say that ⃗a and ⃗b are equivalent with respect to K, 1 denoted by ⃗a ∼K ⃗b, if for any i, j ∈ K, ai ≥ aj ⇔ bi ≥ bj (where ai denotes the ith component of the vector ⃗a, etc.).

Definition 2 A function g : Rk → C is compatible with K if for any ⃗a,⃗b ∈ Rk , ⃗a ∼K ⃗b ⇒ g(⃗a) = g(⃗b).

That is, for any mapping g that is compatible with K, g(⃗a) is completely determined by comparisons within K. Generalized scoring rules are defined as follows.

Definition 3 Let k ∈ N, f : L(C) → Rk (a generalized scoring function), and g : Rk → C where g is compatible with K (a decision function). f and g determine the (unweighted) generalized scoring rule GS(f, g) as follows. For any profile of votes V1, . . . , Vn ∈ L(C), GS(f, g)(V1, . . . , Vn) = g(∑ni=1 f(Vi)). We say that GS(f, g) is of order k.

1 In the original definition of generalized scoring rules, ⃗a and ⃗b are allowed to be equivalent w.r.t. any partition of K. In this paper, we only consider the special case where the partition consists of a single element K.

That is, every vote results in a vector of scores according to f, and g decides the winner based on comparisons between the total scores. For example, Copeland can be modeled as a generalized scoring rule in the following way. The total generalized score vector will consist of the scores in the pairwise elections. Let

- kCopeland = m(m - 1); the components are indexed by pairs (i, j) such that i, j ≤ m, i ̸= j.

- gCopeland selects the winner based on fCopeland(P) as follows. For each pair i ̸= j, if (fCopeland(P))(i,j) > (fCopeland(P))(j,i), then add 1 point to i's Copeland score; if (fCopeland(P))(j,i) > (fCopeland(P))(i,j), then add 1 point to j's Copeland score; if tied, then add 0.5 to both i's and j's Copeland scores. The winner is the alternative that gets the highest Copeland score. The other voting rules we studied can also be modeled as GSRs:

Proposition 1 ([Xia and Conitzer, 2008]) All positional scoring rules, Copeland, STV, maximin, and ranked pairs are generalized scoring rules.

As for Bucklin, the results in this paper imply that it is also a generalized scoring rule.

3 Finite local consistency

In this section, we introduce finite local consistency.

Definition 4 Let S be a set of profiles. r is locally consistent on S if for any P1, P2 ∈ S with r(P1) = r(P2), we have P1 ∪ P2 ∈ S and r(P1 ∪ P2) = r(P1) = r(P2).

Definition 5 For any natural number t, a voting rule r is tconsistent if there exists a partition {S1, . . . , St} of all profiles such that for all i ≤ t, r is locally consistent within Si. A voting rule r is finitely locally consistent if it is t-consistent for some natural number t.

We note that if a voting rule satisfies FLC, then it must also satisfy homogeneity, because FLC requires that for any two profiles in the same component with the same winner, the union of those two profiles is also in the component (and has the same winner)-so any integer multiple of a profile must be in the same component (and have the same winner). 2

We emphasize that in this definition, a rule is defined for a fixed number m of alternatives, but for profiles of arbitrarily many voters. Later, we will show that some common rules are finitely locally consistent for every m ∈ N; however, in those cases, t depends on m, which is allowed, as long as t is finite. We note that this finiteness condition is important: for any homogeneous voting rule, there exists a partition that has infinitely many elements such that the voting rule is locally consistent on each element of the partition. Here, each element has the form {kP : k ∈ N} for some P that is not composed of multiple copies of any other profile.

2 We thank Felix Brandt and Markus Brill for pointing out the connection between FLC and homogeneity to us.

The degree of consistency of a voting rule r (for a particular m) is the smallest number of elements in a locally consistent partition of profiles. That is, the degree of consistency of r is t if r is t-consistent, and for any t′ < t, r is not t′ -consistent. (We note that the partition corresponding to this lowest t is not necessarily unique.) The degree of consistency can be seen as an approximation to consistency: the lower the degree of consistency of a voting rule, the more "consistent" it is, and 1-consistency is equivalent to the standard definition of consistency. We will be interested in the exact degree of consistency (rather than just whether it is finite or not), because, as we will show, this degree is related to the order of a GSR equivalent to the rule, which in turn is important for the summarization and elicitation problems that we mentioned in the introduction.

4 Finite local consistency characterizes generalized scoring rules

We now present our main result. Let P(k) be the number of total preorders over k elements, that is, the total number of ways to rank k elements, allowing for ties.

Theorem 1 r is a generalized scoring rule if and only if r is anonymous and finitely locally consistent. Moreover, for any t-consistent voting rule r, there exists a GSR of order ( t(t-1)m(m-1) 4 )m!+1 that is equivalent to r; conversely, for any GSR GS(f, g) of order k, there exists a P(k)-consistent voting rule r that is equivalent to GS(f, g). 3

Proof of Theorem 1: We prove the "if" part by a geometrical representation of a voting rule that is anonymous and homogenous, similarly to [Young, 1975]. Let L(C) = {l1, . . . , lm!} be the set of all linear orders over C. Let r be a voting rule that satisfies anonymity and FLC. It follows that r is anonymous and homogenous, so that profiles can be represented as multisets of votes. Hence, there is a one-to-one correspondence between the set of all profiles and the set of all points in Nm! : any profile P = ∑m! x=1 wxlx, wx ∈ N is associated with the point ⃗ p = (w1, . . . ,wm!), that is, ⃗ p ∈ Nm! , and for any j ≤ m!, the jth component of ⃗ p is exactly the number of voters whose preferences are lj in P. Therefore, r can also be seen as a mapping from Nm! to C, defined as follows: for any ⃗ p ∈ Nm! , r(⃗ p) = r(P), where P is the profile that ⃗ p corresponds to. In the remainder of the proof, we will not distinguish between the point ⃗ p and the profile P. Also, because r is homogenous, the domain of r can be extended to Q≥0m! (vectors of nonnegative rationales) in the following way. For any ⃗ p ∈ Q≥0m! , let h ∈ N be such that h⃗ p ∈ Nm! ; then, let r(⃗ p) = r(h⃗ p). (This is well defined because by homogeneity, the choice of h does not matter.)

Because r is t-consistent, there exists a partition (S1, . . . , St) of Nm! such that r is locally consistent within each Si. We note that ⃗ p ∈ Si implies h⃗ p ∈ Si for each h ∈ N, because each Si must be closed under the union of vectors that produce the same result, and we can take the union of h vectors ⃗ p. Now, for any i ≤ t, we define SQ i = {q⃗ p : q ∈ Q≥0, ⃗ p ∈ Si}. It follows that Q≥0m! = ⋃ti=1 SQ i , and for any i1 ̸= i2, SQ i1 ∩ SQ i2 = {0}. For any i ≤ t, any j ≤ m, we define Sj i = SQ i ∩ r-1 (cj). That is, Sj i is the set of points (equivalently, profiles) in SQ i whose winner is cj. It follows that for any ⃗ p1, ⃗ p2 ∈ Sj i ∩Nm! , we have ⃗ p1 + ⃗ p2 ∈ Sj i ; for any ⃗ p ∈ Sj i , any q ∈ Q≥0, we must have q⃗ p ∈ Sj i . For any S ⊆ R≥0m! , we say that S is Q-convex if for any λ ∈ Q ∩ [0, 1], any ⃗ p1, ⃗ p2 ∈ S, we have λ⃗ p1 + (1 - λ)⃗ p2 ∈ S. We say a Q-convex set S is a Q-convex cone, if for any q ∈ Q≥0, any ⃗ p ∈ S, we have q⃗ p ∈ S. We make the following easy claim (proof omitted).

3 The P(k) bound can be improved if more information about the structure of the GSR is taken into account. For the sake of simplicity, we omit discussion of this in this paper.

Claim 1 For any i ≤ t, any j ≤ m, Sj i is a Q-convex cone.

For any S ⊆ R≥0m! , we let conv(S) be the convex hull of S in R≥0m! . That is, conv(S) = {∑hi=1 αi⃗ pi : h = 1, 2, . . . , ∑hi=1 αi = 1, (∀i ≤ h) αi > 0, αi ∈ R, ⃗ pi ∈ S}.

Lemma 1 (proved in [Young, 1975]) S ⊆ Qm! is Q-convex if and only if S = conv(S) ∩ Qm! .

Let d ∈ N, S1, S2 ⊆ Rd , and for any x ∈ R, let δ(x) = 1 if x > 0, δ(x) = -1 if x < 0, and δ(0) = 0. We say that S1 and S2 are separated by a finite set of vectors I = {⃗ p1, . . . , ⃗ po}, in which ⃗ pi ∈ Rl for all i ≤ o, if there exist two sets O1, O2 ⊆ {-1, 0, 1}I such that O1 ∩ O2 = {0}, and for any ⃗ p ∈ S1 (⃗ p ̸= 0), we have δ(⃗ p, I) = (δ(⃗ p·⃗ p1), . . . , δ(⃗ p·⃗ po)) ∈ O1; for any ⃗ p ∈ S2 (⃗ p ̸= 0), we have (δ(⃗ p·⃗ p1), . . . , δ(⃗ p·⃗ po)) ∈ O2. In this case we also say that I separates S1 from S2 via O1, O2. S ⊆ Rd is called an affine space if for any ⃗

p1, ⃗ p2 ∈ S, any q1, q2 ∈ R, we have q1⃗ p1 + q2⃗ p2 ∈ S. For any S′ ⊆ Rd , we let aff(S′ ) denote the affine extension of S′ as follows: aff(S′ ) = {∑hi=1 αi⃗ pi : h = 1, 2, . . . , (∀i ≤ h) αi ∈ R, ⃗ pi ∈ S′ }. That is, aff(S′ ) is the smallest affine space in Rd that contains S′ . We let relint(conv(S)) denote the relative interior of conv(S), defined as follows. relint(conv(S)) is the set of all vectors ⃗ p ∈ Rd such that there exists ϵ > 0 such that B(⃗ p, ϵ) ∩ aff(S) ⊆ conv(S), where B(⃗ p, ϵ) is the ball centered on ⃗ p with radius ϵ.

Lemma 2 Let S ⊆ Rm! be an affine space, and let S1, S2 ⊆ S ∩ Q≥0m! be two Q-convex cones such that S1 ̸= S2, S1 ∩ S2 = {0}. There exists a finite set of vectors I ⊆ Rm! that separates S1 from S2, and |I| ≤ dim(S).

Proof. We prove the claim by induction on dim(S). When dim(S) = 1, it must be the case that one of S1 and S2 is {0}, and the other has an element ⃗ p′ ̸= 0. Without loss of generality, we let S1 = {0}, S2 ̸= {0}. In this case, we let I = {⃗ p′ }, O1 = {0}, and O2 = {0, 1}.

Suppose Lemma 2 holds for dim(S) ≤ d. Without loss of generality, we assume dim(aff(S1)) ≥ dim(aff(S2)). When dim(S) = d + 1, there are two cases.

Case 1: dim(aff(S1)) = dim(aff(S2)) = d + 1. In this case S = aff(S1) = aff(S2). First we prove that relint(conv(S1)) ∩ relint(conv(S2)) = ∅. If not, suppose ⃗ p ∈ relint(conv(S1)) ∩ relint(conv(S2)). Let ⃗ p =

∑hj=1 αj ⃗ pj, where ∑hj=1 αj = 1, for all j ≤ h, ⃗ pj ∈ S1 and αj ≥ 0, and B(⃗ p, ϵ) ∩ S ⊆ conv(S1), B(⃗ p, ϵ) ∩ S ⊆ conv(S2). There exist βj ∈ Q≥0 (j ≤ h) such that ⃗ p∗ = ∑hj=1 βj ⃗ pj ̸= 0, and the distance between ⃗ p∗ and ⃗ p is less than ϵ (by setting the βj sufficiently close to the αj). We note that S1 is Q-convex, which means that ⃗ p∗ ∈ S1. It follows that ⃗ p∗ ∈ conv(S2), because ⃗ p∗ ∈ B(⃗ p, ϵ) ∩ S. From Lemma 1 we have that S2 = conv(S2) ∩ Q≥0m! . Therefore, ⃗ p∗ ∈ conv(S2) ∩ Q≥0m! = S2. This contradicts the assumption that S1 ∩ S2 = {0}.

Because relint(conv(S1)) ∩ relint(conv(S2)) = ∅, we apply the separating hyperplane theorem: there exists a hyperplane H⃗ p∗ characterized by ⃗ p∗ ∈ Rm! , such that for any ⃗ p1 ∈ S1, ⃗ p1 · ⃗ p∗ ≤ 0; for any ⃗ p2 ∈ S2, ⃗ p2 · ⃗ p∗ ≥ 0; and at least one of S1 and S2 is not contained in H⃗ p∗. We let S′ = S ∩H⃗ p∗ , and S′1 = S1∩S′ , S′2 = S2∩S′ . H⃗ p∗ does not contain S, so it follows that dim(S′ ) < dim(S) = d+1. Applying Lemma 2 on S′ , S′1 , S′2 (using the induction assumption), there exists a set of vectors I ′ that separates S′1 from S′2 via O′1 ,O′2 , |I ′ | ≤ d. Let I = {⃗ p∗ } ∪ I ′ and O1 = {⃗a ∈ {-1, 0, 1}I : ⃗a|{⃗ p∗ } = -1 ∨ (⃗a|{⃗ p∗ } = 0 ∧ ⃗a|I ′ ∈ O′1 )} (here, for J ⊆ I, let ⃗a|J be the components of ⃗a corresponding to the vectors in J). This works because for any ⃗ p ∈ S1, either ⃗ p is in the open halfspace {⃗ p′ : ⃗ p′ · ⃗ p∗ < 0}, or ⃗ p is in S1 ∩ H⃗ p∗. Similarly, let O2 = {⃗a ∈ {-1, 0, 1}I : ⃗a|{p∗ } = 1 ∨ (⃗a|{p∗ } = 0 ∧⃗a|I ′ ∈ O′2 )}. It follows that I separates S1 from S2 via O1, O2, and |I| = |I ′ | + 1 ≤ d + 1.

Case 2: dim(aff(S2)) < d + 1. If aff(S1) = aff(S2), then let S′ = aff(S1), |S′ | < d + 1. Applying Lemma 2 on S′ , S1, S2 (by the induction assumption), we can conclude that there exists I ′ ⊆ Q≥0m! that separates S1 from S2, and |I ′ | ≤ d < d + 1. If aff(S1) ̸= aff(S2), then there exists a hyperplane H⃗ p∗ (orthogonal to ⃗ p∗ ) such that 0 ∈ H⃗ p∗ , S2 ⊆ H⃗ p∗, and S1 ⊈ H⃗ p∗ (because the intersection of all hyperplanes that contains S2 is S2). Let S′ = aff(S2), and S′1 = S1 ∩ S′ . S′ is an affine space whose dimension is dim(aff(S2)) < d + 1. For any ⃗ p1, ⃗ p2 ∈ S′1 , any λ ∈ Q≥0, we have that λ⃗ p1 +(1-λ)⃗ p2 ∈ S1 (because S1 is Q-convex), and λ⃗ p1 + (1 - λ)⃗ p2 ∈ S′ (because S′ is an affine space); hence, λ⃗ p1 + (1 - λ)⃗ p2 ∈ S′1 . Hence S′1 is a Q-convex cone.

By applying Lemma 2 on S′ , S′1 , S2 (using the induction assumption), there exists I ′ ⊂ Q≥0m! (|I ′ | ≤ d) that separates S′1 from S2 via O′1 ,O′2 . We let I = I ′ ∪ {⃗ p∗ }; O1 = {⃗a ∈ {-1, 0, 1}I : ⃗a|{⃗ p∗ } ̸= 0 ∨ (⃗a|{⃗ p∗ } = 0 ∧⃗a|I ′ ∈ O′1 )}. This works because for any ⃗ p ∈ S1, either ⃗ p · ⃗ p∗ ̸= 0 (meaning that ⃗ p is not in S′ ), or ⃗ p · ⃗ p∗ = 0, and δ(⃗ p, I ′ ) ∈ O′1 (meaning that ⃗ p is in S1 ∩ S′ ). Similarly we define O2 = {⃗a ∈ {-1, 0, 1}I : ⃗a|{⃗ p∗ } = 0 ∧ a|I ′ ∈ O′2 }. It follows that I separates S1 from S2, and |I| = |I ′ | + 1 ≤ d + 1. This completes the proof of Lemma 2. □

For any i1, i2 ≤ t, j1, j2 ≤ m, where either i1 ̸= i2 or j1 ̸= j2, Sj1 i1 ∩ Sj2 i2 = {0}. (We recall that Sj i is the set of points in SQ i whose winner is cj.) From Lemma 2, there exists a finite set Ii1j1,i2j2 of vectors that separates Sj1 i1 from Sj2 i2 via O1 i1j1,i2j2 , O2 i1j1,i2j2 , where |Ii1j1,i2j2 | ≤ m!. Now we can define a corresponding generalized scoring rule, as follows.

• k = | ⋃(i1,j1)̸=(i2,j2) Ii1j1,i2j2 | + 1, and the components are indexed by vectors in some Ii1j1,i2j2 , and a 0 component (which is always 0). Because |Ii1j1,i2j2 | ≤ m!, we have k ≤ ( t(t-1)m(m-1) 4 )m! + 1.
• For any (i1, j1) ̸= (i2, j2), any ⃗ p = (p1, . . . , pm!) ∈ Ii1j1,i2j2 , any b ≤ m!, the ⃗ p component of the generalized score vector given vote (ranking) lb is f(lb) = pb. We note that for any profile ⃗ p = (w1, . . . ,wm!), any ⃗ p∗ = (p∗1 , . . . , p∗m! ) ∈ Ii1j1,i2j2 , the ⃗ p∗ component of f(⃗ p) is ∑m! x=1 wxp∗x = ⃗ p · ⃗ p∗ .
• For any ⃗a ∈ Q≥0 k with ⃗a ̸= 0, g(⃗a) = cj if and only if there exists i ≤ t such that for any i′ ≤ t, j ′ ≤ m, there exists o ∈ O1 ij,i′ j ′ such that for any ⃗ p∗ ∈ Iij,i′ j ′ , the following three conditions hold: (1) ⃗a|⃗ p∗ is strictly larger than 0 (the value of the 0 component), if and only if o|⃗ p∗ = 1; (2) ⃗a|⃗ p∗ is equal to 0, if and only if o|⃗ p∗ = 0; and (3) ⃗a|⃗ p∗ is strictly smaller than 0, if and only if o|⃗ p∗ = -1. That is, g(⃗a) = cj if and only if there exists i ≤ t such that for any i′ , j ′ , we always have ⃗a ̸∈ Sj ′ i′ by using the set of separation vectors Iij,i′ j ′ . (That g is well defined will follow from the following argument.)

Next, we prove that GS(f, g) = r. For any profile ⃗ p ∈ Q≥0m! , suppose ⃗ p ∈ Sj i . For any (i, j) ̸= (i′ , j ′ ), since ⃗ p ∈ Sj i , by using the separation vectors Iij,i′ j ′ and O1 ij,i′ j ′ , O2 ij,i′ j ′ , ⃗ p should be classified as "not in Sj ′ i′ ". That is, there exists o ∈ O1 ij,i′ j ′ such that for any ⃗ p∗ ∈ Iij,i′ j ′ , o|⃗ p∗ = δ(⃗ p · ⃗ p∗ ); and for any o′ ∈ O2 ij,i′ j ′ , there exists ⃗ p∗ ∈ Iij,i′ j ′ such that o′ |⃗ p∗ ̸= δ(⃗ p · ⃗ p∗ ). It follows that GS(f, g)(⃗ p) = cj .

The "only if" part is straightforward. For any total preorder O over {1, . . . , k}, we let SO = {⃗ p ∈ Q≥0m! : f(⃗ p) ∼ O}. {SO} is a finitely locally consistent partition for the rule, of size P(k). □

We are not aware of any closed-form formula for P(k), though there exist recursive formulas. We now give a simple upper bound on P(k). Any total preorder V can be represented by a strict order (ci1 ≻ ci2 ≻ . . . ≻ cim ) and a string ⃗s = (s1, . . . , sm-1) ∈ {0, 1}m-1 , as follows: if sl = 0 then cil ≻V cil+1 , and if sl = 1 then cil ≈V cil+1 . This implies P(k) ≤ k!2k-1 .

5 The degree of consistency of common rules

In this section, we prove upper and lower bounds for the degree of consistency of some common voting rules (which Theorem 1 relates to the order of a GSR representation of that rule). Positional scoring rules have degree of consistency 1, but other rules do not. To prove a lower bound L on the degree of consistency of a voting rule, we construct a set of L profiles P1, . . . , PL that all have the same winner, but, for any i ̸= j, the winner for P1 ∪ P2 is another alternative (hence, none of these profiles can belong to the same element of a partition). To prove an upper bound U, for any alternative cj , we partition the set of all profiles whose winner is cj into U parts, denoted by Sj1 , . . . , SjU , and prove that the rule is locally consistent within each part. Then, we let the partition of all profiles be {S1, . . . , SU}, where Si = ⋃mj=1 Sj i . It is easy to see that the rule must be locally consistent within each Si. Due to space constraint, we only include the proof for Bucklin (which is the shortest).

Theorem 2 The degree of consistency of Bucklin is at least ⌊ m2 ⌋, and at most ⌊ m2 ⌋ + 1.

Proof. First we prove the lower bound. For any k ≤ ⌊ m2 ⌋, define Pk = (V1, . . . , V8(m-2)) as follows.

• For 1 ≤ j ≤ 4(m- 2) + 1, let c1 be in the kth position of Vj , and let c2 be in the (k + 1)th position of Vj .
• For 4(m- 2) + 2 ≤ j ≤ 8(m- 2), let c1 be in the mth position of Vj , and let c2 be in the kth position of Vj .
• Let c3, . . . , cm be ranked in a cyclic way in V1, . . . , V8(m-2)-for example, c3 ≻ c4 ≻ . . . ≻ cm in V1; cm ≻ c3 ≻ c4 ≻ . . . ≻ cm-1 in V2; and so on.

In each Pk, c1 is ranked among the top k positions 4(m2) + 1 > 4(m - 2) times; c2 is ranked among the top k positions 4(m-2)-1 < 4(m-2) times. For any 3 ≤ i ≤ m, ci is ranked among the top k positions 8(k-1) times. Because k ≤ m2 , 8(k - 1) ≤ 4(m- 2). Hence, Bucklin(Pk) = c1. Now, for any k1 < k2 ≤ ⌊ m2 ⌋, in Pk1 ∪ Pk2 , c1 is ranked among the top k2 - 1 positions 4(m - 2) + 1 < 8(m - 2) times; c1 is ranked among the top k2 positions 8(m-2)+2 > 8(m- 2) times; and c2 is ranked among the top k2 positions 12(m-2)-1 > 8(m-2)+2 times. Hence, in Pk1 ∪Pk2 , c2 performs better than c1, and therefore, Bucklin(Pk1 ∪Pk2 ) ̸= c1. It follows that the degree of consistency of Bucklin is at least ⌊ m2 ⌋.

Next, we prove the upper bound. Without loss of generality, we focus on the alternative cm. Let P be a profile such that Bucklin(P) = cm. For any k, let Sm k be the set of profiles P such that Bucklin(P) = cm, and the Bucklin score of cm in P is k. For any P, P ′ ∈ Sm k , any i ≤m, ci is ranked among the top k - 1 positions at most |P| 2 (resp., |P ′ | 2 ) times in P (resp., P ′ ). Therefore, ci is ranked among the top k - 1 positions at most |P|+|P ′ | 2 times in P ∪ P ′ . By similar reasoning, cm is ranked among the top k positions strictly more than |P|+|P ′ | 2 times in P ∪ P ′ . It is possible that some other ci is also ranked among the top k positions strictly more than |P |+|P ′ | 2 times in P ∪ P ′ ; however, ci must be ranked among the top k at most as many times as cm in both P and P ′ , and hence also in P ∪ P ′ . If cm is ranked among the top k more often than ci in P ∪P ′ , then cm wins; if they are ranked among the top k equally often, then cm still wins, by consistent tiebreaking. It follows that Bucklin is locally consistent within each Sm k . Moreover, we note that Sm k is empty for k > ⌊ m2 ⌋ + 1. So, we only need the Sm k with k ≤ ⌊ m2 ⌋ + 1. By similar analysis for the other alternatives, it follows that the degree of consistency of Bucklin is at most ⌊ m2 ⌋ +1. □

Theorem 3 The degree of consistency of STV is (m- 1)!.

Theorem 4 The degree of consistency of maximin is at least (m- 3)m-1 , and at most (m- 1)m-1 .

Because limm→∞ (m-3)m-1 (m-1)m-1 = 1 e2 , the bounds on the degree of consistency of maximin are asymptotically tight up to a multiplicative constant.

Theorem 5 The degree of consistency of Copeland is at least (2-m′ (2m′ m′ ))m, where m′ = ⌊ m-1 2 ⌋, and at most 3 m(m-1) 2 .

Theorem 6 The degree of consistency of ranked pairs is at least (m- 2)!, and at most (m(m- 1))!2m2-m-1 .

6 Conclusion

The frequency of manipulability of a rule is an important problem in computational social choice. Recently, this frequency has been characterized-except for a knife-edge case-for the class of generalized scoring rules [Xia and Conitzer, 2008]. While it was previously observed (based on examples) that this class seems very general, no formal argument for this generality has been given. In this paper we gave such an argument, by characterizing generalized scoring rules as the class of rules that satisfy finite local consistency (in addition to anonymity), a very natural weakening of the standard notion of consistency. This definition also leads to a quantitative degree of consistency of a rule, which turns out to be closely related to the order (dimension of the score vector) of a generalized scoring rule. Our axiomatic characterization also shows that Dodgson's rule is not a generalized scoring rule, because it does not satisfy homogeneity [Brandt, 2009]. We provided lower and upper bounds on the degree of consistency for some common voting rules, summarized in Table 1. These bounds imply corresponding bounds on the order of a generalized scoring rule representation of these rules, per Theorem 1.

One direction for future research is to tighten the above bounds, and derive bounds for other rules. A related question is whether the bounds from Theorem 1 can be improved. Another direction is to study alternative uses of generalized scoring rules-we briefly mentioned the possibility of using them for elicitation and summarization purposes-as well as the properties that they possess.

Acknowledgments

We thank Felix Brandt, Markus Brill, and anonymous reviewers for helpful comments and suggestions. This work is supported by NSF under award number IIS-0812113. Lirong Xia is supported by a James B. Duke Fellowship, and Vincent Conitzer is supported by an Alfred P. Sloan Research Fellowship.