Compiling the Votes of a Subelectorate

1 Introduction

Voting is a general method for a group of agents to agree on a common decision. Now, in many practical contexts where a number of agents have to find a common decision via a voting process, the votes do not come all together at the same time. For instance, in some political elections, the votes of the citizens living abroad are known only a few days after the rest of the votes. Or, when voting about a date of a meeting, it often happens that some participants express their preferences later than others. In such situations, we may want to preprocess the information given by the subelectorate (consisting of those voters who have expressed their votes) so as to prepare the ground for the time when the latecomers will have expressed their votes. What does "preparing the ground" exactly mean? We may think of two different criteria:

• space: synthesize the information contained in the votes of the subelectorate, using as little space as possible, while keeping enough information for computing the outcome once the last votes are known;
• on-line time: compile the information, using as much off-line time and space as needed, in such a way that once the last votes are known, the outcome can be computed as fast as possible.

These two criteria not only differ, but are, to some extent, opposed, and lead to two very different lines of research. The research area of knowledge compilation (e.g., [Cadoli et al., 2002; Darwiche and Marquis, 2002]) lay the focus on on-line time, and typically looks for worst-case exponentially large rewritings of the "fixed part" of the input, enabling on-line time complexity to fall down. While knowledge compilation is definitely relevant to voting (the fixed part being the known votes, and the varying part the votes of the latecomers), and would surely deserve a paper on its own, in this paper, however, we focus on minimizing space.

Why should we care about synthesizing the votes of a subelectorate in as little space as possible in the first place? There are two main reasons for that.

The first reason has to do with the practical acceptance of the voting rule. Suppose the electorate is split into different districts (generally, corresponding to geographical entities, or clusters of agents in a system). Each district can count its ballots separately and communicate the partial outcome to the central authority, which, after gathering the outcomes from all districts, determines the final outcome. The space needed to synthesize the votes of a district (with respect to a given voting rule) is precisely the amount of information that the district has to send to the central authority. Now, it is important that the voters should be able to check as easily as possible the outcome of the election. In other words, one property that we would like to ensure is the possibility to perform an easy distributed verification of the outcome. Take a simple rule, such as plurality or Borda. Obviously, it is enough (and almost necessary, as we see later) for each district to send only its "local" plurality or Borda scores to the central authority. If the district is small enough, it is not difficult for the voters of this district to check that the local results are sound (for instance, each political party may delegate someone for checking the ballots). Note that this only requires these local results to be made public (which is usually the case in real life: in most countries, they are published in newspapers). Every voter can then check the final outcome from these local outcomes (in the case of plurality or Borda, simply by summing up the local scores). Clearly, if the information about the votes of a district being necessary for computing the final outcome is large (e.g., if one needs to know how many voters have expressed every possible linear order on the candidate set), it will be impractical to publish the results locally, and therefore, difficult to check the final outcome, so that voters may then be reluctant to accept the voting rule.

The second reason is foundational: the size of the minimum information to be extracted from a subset of the votes, and still guaranteeing that we will have enough information to compute the outcome, is an important property of voting rules that has not been studied yet. Even if this minimum information is, in some cases, easy to determine (such as in the case of plurality), in some other cases it is far from being obvious (see for instance our results about STV).

Although the compilation of the votes of a subelectorate has not been considered before (as far as we know), several related problems have been investigated:

• the complexity of vote elicitation [Conitzer and Sandholm, 2002; Walsh, 2008]: given a voting rule r, a set of known votes S, and a set of t new voters, is the outcome of the vote already determined from S?
• the computation of possible and necessary winners [Konczak and Lang, 2005; Xia and Conitzer, 2008; Pini et al., 2007]: given a voting rule r, a set of incomplete votes (that is, partial orders on the set of candidates), who are the candidates who can still possibly win the election, and is there a candidate who surely wins it?
• the communication complexity of voting rules [Conitzer and Sandholm, 2005]: given a voting rule r and a set of voters, what is the worst-case cost (measured in terms of number of bits transmitted) of the best protocol allowing to compute the outcome of the election?

In the first two cases, the connection is clear. In the most favourable case where the outcome is already determined from S (corresponding to the existence of a necessary winner, or to a positive answer to the vote elicitation problem), the space needed to synthesize the input is just the binary encoding of the winner. The connection to communication complexity will be discussed in Section 2, once communication complexity has been formally introduced. In Section 3, we determine the compilation complexity of some of the most common voting rules. Lastly, in Section 4 we discuss our results and mention further research issues.

2 Compilation complexity as one-round communication complexity

Let X be a finite set of candidates, and p = |X|. A vote is a linear order over X. We sometimes denote votes in the following way: a ≻ b ≻ c is denoted by abc, etc. For any m ≥ 0, a m-profile is a tuple P = 〈V1, . . . , Vm〉 of votes. Let P m X be the set of all m-profiles over X. We denote by P ∗X the set of all m-profiles for m ≥ 0, i.e., P ∗X = ∪k≥0P kX . An element of P ∗X is called a partial profile.

Let N a finite set of voters, with n = |N|. A voting rule is a function r from P nX to X. As the usual definition of most voting rules does not exclude the possibility of ties, we assume these ties are broken by a fixed priority order on candidates. A voting rule is anonymous if it insensitive to the identity of voters.

For P ∈ P m X and x ∈ X, let n(P, i, x) be the number of votes in P ranking x in position i, and ntop(P, x) = n(P, 1, x) the number of votes in P ranking x first. Let ⃗s = 〈s1, . . . , sp〉 be a vector of integers such that s1 ≥ . . . ≥ sp. The scoring rule induced by ⃗s is defined by: r⃗s(P) is the candidate maximizing ∑pi=1 si.n(P, i, x). Plurality (resp. Borda) is the scoring rule rP (resp. rB) corresponding to the vector 〈1, 0, . . . , 0〉 (resp. 〈p - 1, p - 2, . . . , 0〉).

We now consider situations where only some of the voters (the "subelectorate") have expressed their votes. Let m be number of voters who have expressed their vote, and P ∈ P m X the partial profile obtained from these m voters. We say that two partial profiles are r-equivalent if no matter the remaining unknown votes (and no matter how many they are), they will lead to the same outcome 1 :

Definition 1 Let P,Q ∈ P m X be two m-voters X-profiles, and r a voting rule. P and Q are r-equivalent if for every k ≥ 0 and for every R ∈ P kX we have r(P ∪R) = r(Q∪R).

Example 1 Let rP be plurality and rB Borda, X = {a, b, c}, and m = 4. Let P1 = 〈abc, abc, abc, abc〉, P2 = 〈abc, abc, acb, acb〉, and P3 = 〈acb, acb, abc, abc〉.

• P2 and P3 are rP -equivalent and rB-equivalent. More generally, they are r-equivalent for every anonymous voting rule r.
• P1 and P2 are rP -equivalent. However they are not rB-equivalent: take R = 〈bca, bca, bca〉, then we have rB(P1 ∪ R) = b while rB(P2 ∪ R) = a.

We denote r-equivalence by ∼r. Obviously, ∼r is an equivalence relation. Informally, the compilation complexity of r is the minimum space needed to compile a m-voter partial profile P without knowing the remaining profile R. This notion does not take into account the off-line time needed to compute σ, nor the off-line time needed to compute ρ.

Definition 2 Given a voting rule r, we say that a function σ from P m X to {0, 1}∗ is a compilation function for r if there exists a function ρ : {0, 1}∗ ×P ∗X →X, such that for every P ∈ P m X , every k ≥ 0, and every R ∈ P kX , ρ(σ(P),R) = r(P ∪ R). The compilation complexity of r is defined by

Up to minor details, compilation complexity coincides with one-round communication complexity (even if their intuitive interpretations differ). We start by recalling standard communication complexity. When n agents have to compute a function f, each of them knowing only a part of the input, the deterministic communication complexity (see [Kushilevitz and Nisan, 1997]) of f is the worst-case number of bits that the agents must exchange so as to be able to know the outcome. A one-round protocol for two agents A and B is a protocol where A sends only one message to B, and then B sends the output to A (see Section 4.2 of [Kushilevitz and Nisan, 1997]). The one-round communication complexity (ORCC) of f is the worst-case number of bits of the best one-round protocol for f . Note that while standard communication complexity does not impose any restriction on the protocol that the agents may use to compute f, ORCC imposes a severe restriction, so that these two notions differ significantly.

The only difference between compilation complexity and ORCC is that compilation complexity does not care about B

1 We could write a similar definition for a fixed number of remaining votes, but we leave it out due to space limitations.

sending back the output to A. Here, A represents the set of voters having already expressed their votes, and B the remaining voters; the space needed to synthesize the votes of A is the amount of information that A must send to B so that B can be able to compute the final outcome.

Since one-round communication complexity is never smaller than standard communication complexity, we could expect the communication complexity of a voting rule is always smaller than its compilation complexity. However, this is not so simple, because in [Conitzer and Sandholm, 2005] (a) there is no partition between two subelectorates: their results mention only the total number of candidates, whereas ours mention the number of candidates who have already expressed their votes, and (b) they count the bits sent by each of the voters, while we do not count the bits sent by our m voters to communicate their votes - we only count the bits needed to communicate the synthesis of those votes.

We have the following characterization of C(r). Up to minor details, this is a reformulation (in our own terms) of Exercise 4.18 in [Kushilevitz and Nisan, 1997], and we omit the proof.

Proposition 1 Let r be a voting rule, m be the number of initial voters, and p the number of candidates. If the number of equivalence classes for ∼r is g(m, p) then the compilation complexity of C(r) = ⌈log g(m, p)⌉.

Proposition 2 Let r be a voting rule, and r′ an anonymous voting rule.

• C(r′ ) ≤ p! log {1+ mp! } + m log {1 + ≤ min(mlog(p!), p! logm)

The proof is easy. For any r, the number of equivalence classes cannot be larger than the number of profiles, and there are (p!)m possible profiles. For any anonymous voting rule r, the number of equivalence classes corresponds to the number of ways to choose a set of m orders among the set of all possible linear orders on X, which is equal to M m p! . The bound is then the logarithm of the latter number.

Importantly, these bounds are tight: it is possible to design a voting rule (resp. an anonymous voting rule) yielding these bounds. At the other extremity of the spectrum, the compilation complexity of a dictatorship is log p, and that the compilation complexity of r is 0 if and only if r is constant.

3 Some case studies

We now consider a few specific families of voting rules. For each rule r we adopt the following methodology: we first give a characterization of the equivalence classes for ∼r, which we use to count the number of equivalence classes. In simple cases, it will be easy to enumerate exactly these classes, and Proposition 1 will give us the exact compilation complexity of the rule. In more complex cases, we will exhibit a simple upper bound and provide a lower bound of the same order.

3.1 Plurality

Lemma 1 P ∼rP P ′ holds if and only if for every x, ntop(P, x) = ntop(P ′ , x).

Proof: (⇐) is straightforward. For (⇒), suppose there is an x ∈ X such that ntop(P, x) ̸= ntop(P ′ , x). Without loss of generality, assume ntop(P, x) > ntop(P ′ , x). Now, ∑x∈P ntop(P, x) = ∑x∈P ′ ntop(P ′ , x) = m, therefore there must be an y ̸= x such that ntop(P, y) < ntop(P ′ , y). Take a profile Q with 2m-ntop(P, x)-ntop(P, y)+1 votes, with m-ntop(P, x)+1 votes having x on top (and whatever below), and m - ntop(P, y) votes having y on top (and whatever below). We have ntop(P ∪ Q, x) = m + 1, ntop(P ∪ Q, y) = m, and for every z ̸= x, y, ntop(P ∪ Q, z) ≤ m. Therefore, rP (P ∪ Q) = x. Now, ntop(P ′ ∪ Q, x) = ntop(P ′ , x) - ntop(P, x) + m + 1 ≤ m, ntop(P ′ ∪ Q, y) = ntop(P ′ , y) - ntop(P, y) + m ≥ m + 1, and for every z ̸= x, y, ntop(P ′ ∪ Q, z) ≤ m. Therefore, rP (P ∪Q) = y. This shows that P ̸∼rP P ′ . ■

This characterization together with Proposition 1 tells us that the compilation complexity of rP is exactly ⌈logL(m, p)⌉, where L(m, p) be the number of vectors of positive integers 〈α1, . . . , αp〉 such that ∑pi=1 αp = m. The number of such vectors is exactly M m p , from which we get:

Observe that this result yields an upper bound in O(m+ p), to be compared with the "naive" upper bound that can be derived from the fact that it is sufficient to record the plurality scores of each candidate, which needs O(p logm) bits.

3.2 Borda

We get the following characterization of ∼B, similar to Lemma 1 for plurality (note that more generally, a similar result holds for any scoring rule). For P ∈ P m X and x ∈ X, let scoreB(x, P) be the Borda score of x obtained from the partial profile P .

Now, let B(m, p) be the number of vectors of positive integers 〈α1, . . . , αp〉 corresponding to Borda scores once m votes have been expressed. Note that ∑pi=1 αp = mp(p-1) 2 , since each voter distributes p(p-1) 2 points among the candidates. However, this alone does not suffice to characterize the set of realizable Borda scores (for instance, if a candidate gets a score of 0, then no other candidate can get less than m).

This upper bound is easily obtained by observing that is possible to simply record the scores of p - 1 candidates, and that this score can be at most m(p - 1). 2

Now we try to exhibit a lower bound approaching this upper bound. The general idea is to focus on a specific subset of vectors of Borda scores. For example, for those vectors where the candidate with the lowest score gets between 0 and m, the second one between m and 2m, and so on until the penultimate voter, the score of the last candidate can be chosen so as to make a realizable vector of Borda scores. (Observe that by taking these intervals, the scores of the first p - 1 candidates can really be chosen independently).

2 Note that more generally, for any scoring rule rS, we have C(rS) ≤ (p - 1) log m.s1.

In what follows, we show how to construct profiles that result in such a subset of vectors of Borda scores.

Proposition 4 Let {δ1, . . . , δp-1} be a collection of nonnegative integers such that ∑p-1 i=1 δi ≤ m2 . The vector of Borda scores ⃗α = 〈δ1,m+δ2, 2m+δ3, . . . ,m(p1) + δp〉, where δp = - ∑p-1 i=1 δi, can result from a m-voter profile.

Proof sketch: We only show that for any i < p, the vector of Borda scores 〈α1, α2, . . . , αi + 1, . . . , αp - 1〉 of the candidates, where ∀j ≤ p, αj = 2(j - 1), can result from a two-voter profile. Denote by 〈αv 1 , αv 2 , . . . , αvn 〉 the vector corresponding to the ballot of voter v. We initially assign to voters 1 and 2 the basic vectors 〈0, 1, . . . , p - 1〉. Now we construct the modified vectors of the two voters as follows: take the scores α1 i and α1 i+1 of voter 1 and swap them; then take the scores α2 i+1 and α2 i+2 of voter 2 and swap them; then move back to voter 1 and swap the scores α1 i+2 and α1 i+3 , and so on until the last score of voter 1 or voter 2 is reached, in which case no more swap is possible. Now, for any j ∈ [i + 1, p - 1], α1 j + α2 j = α′1 j + α′2 j because the swaps of voters 1 and 2 compensate each other, so the scores of these candidates remain unaffected. On the other hand, the Borda scores of candidates i and p are modified as required (resp. +1 and -1). Now, the same principle can be applied to m voters: it is possible to distribute up to m/2 points among the first p - 2 candidates to improve their score obtained from the basic vectors only (with the last candidate compensating by seeing its score decreased by the same amount of points). ■

Corollary 2 C(rB) = Θ(p logmp)

Proof: From Proposition 4, V p-1 m/2 is the number of profiles with increasing scores. We have V p-1 m/2 ≥ 12 × ( m2 )p-1 . The total number of profiles is at least (p - 1)!mp-1 2-p , and we get the lower bound (p - 1)(log2(p - 1) + log2 m - 2). Together with the upper bound, the result holds. ■

3.3 Rules based on the weighted majority graph

Let NP (x, y) be the number of voters in the profile P preferring x to y. The majority graph MP is the directed graph whose set of vertices is X and containing an edge from x to y if and only if NP (x, y) > NP (y, x). The weighted majority graph MP is the same as MP , where each edge from x to y is weighted by N(x, y) (note that there is no edge inMP between x and y if and only if NP (x, y) = NP (y, x).) A voting rule r is based on the majority graph (abridged into "MG-rule" ) if for any profile P , r(P) can be computed from MP , and based on the weighted majority graph (abridged into "WMG-rule" ) if for any profile P, r(P) can be computed fromMP . Obviously, a MG-rule is a fortiori a WMG-rule. A candidate x is the Condorcet winner for a profile P if it dominates every other candidate in MP . A voting rule r is Condorcet-consistent if it elects the Condorcet winner whenever there exists one.

Lemma 3 Let r be a WMG-rule rule. If MP = MP ′ then P ∼r P ′ .

Proof: for any Q, MP∪Q is fully determined fromMP and MQ, because NP∪Q(x, y) = NP (x, y) +NQ(x, y). Since r is WMG, r(P ∪ Q) is determined fromMP∪Q, therefore fromMP andMQ, and a fortiori fromMP and Q. ■

Note that for rules based on the (non-weighted) majority graph, we still need the weighted majority graph of P and P ′ to coincide - having only the majority graph coinciding is not sufficient for P ∼r P ′ , since MP∪Q is generally not fully determined fromMP andMQ.

Lemma 3 gives an upper bound on the compilation complexity of a WMG-rule. Let T(m, p) be the number of weighted tournaments on X that can be obtained as the weighted majority graph of some m-voter profile.

Proposition 5 If r is a WMG-rule then C(r) ≤ log T(m, p).

Getting a lower bound is not possible without a further assumption on r. After all, constant rules are based on the majority graph, yet they have a compilation complexity of 0. We say that a WMG-rule r is proper if P ∼r P ′ implies MP =MP ′ . It is easy to find a natural sufficient condition for a WMG-rule to be proper:

Lemma 4 If r is a Condorcet-consistent rule then P ∼r P ′ impliesMP =MP ′ .

Proof: assume r is Condorcet-consistent and MP ̸= MP ′ , i.e., there exists (x, y) ∈ X with NP (x, y) ̸= NP ′ (x, y). Without loss of generality, NP (x, y) = NP ′ (x, y) + k (and NP (y, x) = NP ′ (y, x) - k), with k > 0. Let Q be a set of m + 1 votes, of which m + 1 - NP (x, y) votes prefer x to y and y to anyone else and NP (x, y) votes prefer y to x and x to anyone else. From NP∪Q(x, y) = NP (x, y) + NQ(x, y) = m + 1, we get for any z ̸= x, y, NP∪Q(x, z) = NP (x, z) + m + 1 ≥ m + 1, and x is Condorcet winner in P ∪ Q (which contains 2m + 1 voters) and r(P ∪Q) = x. But NP ′∪Q(y, x) = NP ′ (y, x)+NQ(y, x) = NP (y, x) + k + NP (x, y) = m + k, and for any z ̸= x, y, NP ′∪Q(y, z) = NP ′ (y, z) + m + 1 ≥ m + 1, so y is Condorcet winner in P ′ ∪ Q and r(P ′ ∪ Q) = y. Hence P ̸∼r P ′ . ■

This gives us the following lower bound.

Proposition 6 If r is a Condorcet-consistent rule then C(r) ≥ log T (m, p).

From Propositions 5 and 6 we finally get that:

Proposition 7 If r is a Condorcet-consistent WMG-rule, then C(r) = log T (m, p).

Corollary 3 The compilation complexity of the following rules is exactly logT(m, p): Copeland, Simpson (maximin), Slater, Banks, uncovered set, Schwartz.

We now have to compute T(m, p). We easily get the following upper bound.

Proof: From Lemma 3 we know that it is enough to store MP . Let > be a fixed ordering on the candidates. Storing MP can be done by storing NP (x, y) for every pair (x, y) of distinct candidates such that x > y. We have p(p-1) 2 such pairs, and 0 ≤ NP (x, y) ≤ m, hence the result. ■

It is easy to observe that this bound is not necessarily reached: for any x, y, z ∈ X and any profile P we have NP (x, z) ≥ NP (x, y) + NP (y, z) -m (e.g, if m = 3 and NP (x, y) = NP (y, z) = 2, then NP (x, z) cannot be 0).

Proof: Assume m is even. Let {ci,j | 1 ≤ i < j ≤ p} be any set non-negative integers such that ∑i<j ci,j ≤ m2 . We will show how to build a profile such that N(i, j) = 2ci,j, where N(i, j) indicates how many voters prefer i to j. Let us divide voters into p(p-1) 2 groups gi,j with 1 ≤ i < j ≤ p and a final group g0, such that each group gi,j contains exactly 2ci,j voters and g0 contains the remaining m - ∑i<j 2ci,j voters. In each group gi,j, set the profile of half of the voters to i ≻ j ≻ x1 ≻ x2 ≻ . . . ≻ xp-2, and the other half to xp-2 ≻ . . . ≻ x1 ≻ i ≻ j, where x1 . . . xp-2 refer to the candidates other than i and j in an arbitrary order. In group g0 set half of the voters to x1 ≻ . . . ≻ xp and the other half to xp ≻ . . . ≻ x1. Let N g (x, y) denote the number of voters in group g preferring x to y. Clearly, N gij (x, y) = N(x, y) if x = i and y = j; and 0 otherwise; and N g0 (x, y) = 0. Thus, N(x, y) = ∑ N gi,j (x, y) = 2ci,j . ■

From Lemma 5, it directly follows that:

Corollary 4 If r is a Condorcet-consistent WMG-rule then C(r) = Θ(p2 log m).

3.4 Plurality with runoff

Plurality with runoff (denoted by r2) consists of two (virtual) rounds: the first round keeps the two candidates with maximum plurality scores (with some tie-breaking mechanism), and the second round is the majority rule.

Proposition 9 P ∼r2 Q holds if and only if the following two conditions hold:

1. for every x, ntop(P, x) = ntop(Q, x);

Due to space limitations, we give only a very quick sketch of the proof. The (⇐) direction (if the two conditions are met then P ∼r2 Q) is straightforward. Next, we show that if for some x, ntop(P, x) ̸= ntop(Q, x), then P ̸∼r2 Q; we do so by taking, without loss of generality, an x such that ntop(P, x) > ntop(Q, x), and then we construct a profile R such that in P ∪ R, the finalists are x and z, and the winner is x, while in Q ∪ R, the finalists are y and z (therefore the winner cannot be x). Lastly, we show that if for some x, y ∈ X, N(P, x, y) ̸= N(Q, x, y) then P ̸∼r2 Q. Assuming without loss of generality that N(P, x, y) > N(Q, x, y), we complete P and Q such that in both P ∪ R and Q ∪ R, the finalists are x and y, with x winning in P ∪ R and y in Q ∪ R.

Observe that the two conditions are not independent, so that the previous proposition only tells us that log T(m, p) ≤ C(r2) ≤ log L(m, p) + log T (m, p). It follows that:

In words, compiling the votes in the context of plurality with runoff or of a Condorcet-consistent WMG rule requires an asymptotically equivalent number of bits.

3.5 Single Transferable Vote (STV)

We recall that single transferable vote performs in successive rounds: at each round, the candidate with the lowest plurality score gets eliminated, and its votes are transferred to the next preferred candidate in each ballot. Given a collection P of votes, and a subset Z ⊆ X of candidates, we denote by P -Z the collection of votes obtained from P by removing those candidates in Z, leaving the rest unchanged. For instance, 〈abcde, bcade, beadc〉-bc = 〈ade, ade, ead〉.

Proposition 10 P ∼STV Q holds if and only if for all Z and x /∈ Z, ntop(P -Z , x) = ntop(Q-Z , x).

Proof: The (⇐) part is straightforward. As for the ⇒ part, suppose that for the partial profiles P and Q, there exist Z and x1 /∈ Z such that ntop(P -Z , x1) ̸= ntop(Q-Z , x1). Without loss of generality, suppose ntop(P -Z , x1) < ntop(Q-Z , x1). Note that if Z had contained all candidates but one, then these two scores would have necessarily been equal. Thus, there exist candidates not in Z and different from x1. Among these candidates, there exist at least two candidates such that ntop(P -Z , x) > ntop(Q-Z , x), and we will refer to one of them as x2. Let ϵ = ntop(P -Z , x1) - ntop(P -Z , x2) + 1. Let {e1, . . . , ek} = Z and {e1, . . . , el} be the candidates not in Z ∪{x1, x2}. We now add the profile R to P and to Q:

• 3m votes : x1 ≻ x2 ≻ e1 ≻ . . . ≻ el ≻ e1 ≻ . . . ≻ ek
• 3m+ ϵ votes : x2 ≻ x1 ≻ e1 ≻ . . . ≻ el ≻ e1 ≻ . . . ≻ ek
• 4m+2 votes: ¯ e1 ≻ x1 ≻ x2 ≻ e2 ≻ . . . ≻ el ≻ e1 ≻ . . . ≻ ek
• 4m+ 2 votes: e2 ≻ x1 ≻ x2 ≻ e3 ≻ . . . ≻ e1 ≻ e1 ≻ . . . ≻ ek

After the first k rounds of STV have been applied to P ∪R and Q ∪ R, all the candidates in Z are eliminated. Then, the score of ei is between 4m + 2 and 5m + 2. Note that ntop((P ∪ R)-Z , x2) = ntop((P ∪ R)-Z , x1) + 1, and ntop((Q ∪ R)-Z , x2) < ntop((Q ∪ R)-Z , x1). Thus, the scores of x1 and x2 are no larger than 4m+ 1 in P ∪ R and Q∪R. Moreover, candidate x1 is removed from P ∪R, and x2 is removed from Q ∪ R. After this round, the candidate that remains among {x1, x2} gets at least 6m votes. Thus, all candidates {e1, . . . , el} will be removed one after the other, and x1 will win in Q ∪ R, and x2 will win in P ∪ R. This proves that Q∪R and P ∪R are not STV-equivalent. ■

In other words, the previous proposition shows that the number of STV-equivalence classes is exactly the number of ways to define ntop(P -Z , x) for the p candidates.

Lemma 6 For a given candidate x, the number of score functions ntop(P -Z , x) realizable with a partial profile P of m voters and p candidates is exactly M m 2p-1 .

Proof: Observe that it is required and sufficient, for each candidate x and possible subset of candidates Z (not containing x), to record how many voters among m prefers x over any candidate in Z. ■

Proposition 11 The compilation complexity of STV is:

• Ω (2p log {1 + m 2p } + m log {1 + 2p m })
• O (p2p log {1 + m 2p } + mp log {1 + 2p m })

Proof: For a given x, Lemma 6 shows that there are exactly M m 2p-1 score functions ntop(P -Z , x). ■

Note that the score functions of the p candidates are not independent (knowing the score of some candidate(s) may constrain the score of other candidates). Therefore, the number of equivalence classes lies somewhere between M m 2p-1 and (M m 2p-1 )p .

4 Conclusion

This paper has introduced a notion that we believe to be of primary importance in many practical situations, especially in large systems where it is unlikely that all the votes will come together at the same time: the compilation of incomplete profiles. In particular, the amount of information that a given polling station (or cluster of agents) needs to transmit to the central authority is a good indicator of the difficulty of the verification process. We have introduced a general technique for determining the compilation complexity of a voting rule, have related it to communication complexity, and have derived results for most of the "common" voting rules.

Our results allow us to clearly rank most of the different voting rules wrt. the quantity of information required to encode the known profiles and still guarantee the correct outcomes when new voters come in. It is noteworthy to observe that the rules are ranked quite differently under the criteria of their communication complexity [Conitzer and Sandholm, 2005]. Consider for instance plurality with runoff: its compilation complexity is higher than Borda, although it exhibits a lower communication complexity. As another example, Borda is less costly to compile than Condorcet-consistent WMG-rules, but its communication complexity is higher.

A question that we plan to consider more carefully concerns the situations where the number k of remaining voters is fixed. In this case, a different approach can be taken: instead of compiling the partial profiles provided by the m voters, it may be more efficient to compile the possible completions of this partial profile together with the associated outcome, or, in other words, to compile the function that takes the remaining k profiles as input (there are (p!)k such inputs) and returns the outcome. As there are (p!)k possible profiles, the number of such functions is p(p!)k . Therefore, a general upper bound for C(r, k) is ≤ (p!)k . log p. Hence, overall we have C(r, k) ≤ min(m. log(p!), (p!)k . log p) (the second term becomes interesting only when m is big enough, and p and k small enough).

More generally, the problem of dealing with incomplete profiles in this sense opens a host of related questions, e.g. the probability that a voting process could be stopped after m voters, or the probability that the central authority would make a mistake were it forced to commit on a winner in situations when no candidate is guaranteed to prevail yet.

Acknowledgements

We thank the anonymous reviewers for helpful comments. This research is supported by the project ANR-05-BLAN0384 "Preference Handling and Aggregation in Combinatorial Domains".