Summability criterion

In election science, a voting method satisfies the summability criterion if it is possible to tally election results locally by precinct, then calculate the results by adding up all the votes. More formally, the compilation or summation complexity of a voting system measures the difficulty of vote counting for individual precincts, and is equal to the smallest number of bits needed to summarize all the votes. ^[1] A voting method is called summable if the number of bits grows as a polynomial function of the number of candidates.

Often, a group has to accept a decision, but not all the votes can be gathered together in a single location. In such a situation, we need to take the votes of the present voters and summarize them such that, when the other votes arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary.

A key advantage of low compilation complexity is it makes it easier to verify voting outcomes. Low compilation complexity lets us summarize the outcome in each voting-station separately, which is easy to verify by having representatives from each party count the ballots in each polling station. Then, any voter can verify the final outcome by summing up the results from the 1000 voting stations. This verifiability is important so that the public trusts and accepts the results. ^[1] The publicly-released information from each precinct can be used by independent election auditors to identify any evidence of electoral fraud with statistical techniques.

Compilation complexity is also algorithmically useful for computing the backward induction winner in Stackelberg voting games. ^{[2] [ clarification needed ]}

Definitions

Let r be a voting rule: a function that takes as input a list of n ranked ballots, representing the preferences of n voters, and returns an outcome. There are some k<n voters whose votes are known. A compilation function is a function f that takes as input a list of k ranked ballots and returns some output such that, given any number u := n-k of additional ranked ballots, the output of r on the entire set of ballots can be computed exactly.

The compilation complexity of a rule r is the worst-case number of bits in the output of the most efficient compilation function f. ^[1] This number is typically a function of n (the number of voters), k (the number of known votes), and c (the number of candidates). However, we focus on c alone for simplicity, as we are usually interested in the case with a very large number of unknown votes.

Compilation complexity of single-winner voting rules

The number of possible ballots for any ranked voting rule is ${\displaystyle \Theta (c!)}$, providing an upper bound on the complexity. However, most rules have a much smaller compilation complexity. ^[1]

Positional voting

In positional voting systems like plurality or Borda, any set of votes can be summarized by recording the total score of each candidate (e.g. the number of times a candidate appears first in plurality). The winner can then be found by adding the scores in each precinct giving a bound of ${\displaystyle \Theta (c)}$. A similar argument applies for score voting and approval voting. ^[1]

Voting rules based on weighted majority graph

The weighted majority graph of a voter profile is a directed graph in which the nodes are the candidates, and there is a directed edge from x to y iff a majority of voters prefer x to y. The weight of this edge is the number of voters who prefer x to y. Many rules are based only on the majority graph; the number of equivalence classes of such rules is at most the number of possible weighted majority graphs. This number is denoted by T(k,c) - the number of weighted tournaments on c vertices that can be obtained from k voters. Therefore, the compilation complexity is at most log(T(k,c)). An upper bound on log(T(k,c)) is ${\displaystyle {\frac {c(c-1)}{2}}}$, since it is sufficient to keep, for each pair of candidates x,y, the number of voters who prefer x to y, and this number is between 0 and k. ^{[1] [2]}

Voting rules with runoff

The compilation complexity of two-round voting (the contingent vote) is in ${\displaystyle \Theta (c^{2})}$. Note that this is higher than the compilation complexity of Borda voting, though the communication complexity of two-round voting is lower than that of Borda voting. ^[3]

The compilation complexity of the single transferable vote is in ${\displaystyle \Theta \left(2^{c}c\right)}$, making it non-summable. ^[1]

STAR voting is also in ${\displaystyle \Theta (c^{2})}$. ^[4]

Bucklin's rule

For Bucklin voting the compilation complexity is ${\displaystyle \Theta (c^{2})}$. ^[2] For the closely-related highest median voting rules, the complexity for a ballot including ${\displaystyle k}$ possible ratings is ${\displaystyle \Theta (ck)}$.

Compilation complexity of multi-winner voting rules

Karia and Lang study the compilation complexity of several multiwinner voting rules, with either ranked ballots or approval ballots. For example:

• For single non-transferable vote, the complexity is in ${\displaystyle \Theta (c)}$.
• For Borda, the complexity is in ${\displaystyle \Theta (c\log {kc})}$. ^[5]

Related problems

• Knowledge compilation: compiling a part of the input offline, such that the when the online input arrives, the output can be computed quickly. Here, the goal of the compilation is to save time, rather than to save space.
• Complexity of terminating elicitation: given a voting rule, a set of known votes and a set of new voters, is the outcome of the vote already determined from the known votes? Clearly, if the outcome is already determined, the compilation complexity is small, as we just have to keep this outcome.
• Computation of possible and necessary winners: Given a voting rule, a set of incomplete votes (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? Clearly, if there is a sure winner, then the compilation complexity is very small: we just have to keep the identity of this sure winner.
• Communication complexity: given a voting rule and a set of voters, what is the smallest number of bits that must be transferred between the voters and the center in order to compute the outcome of the election? Conitzer and Sandholm study the communication complexity of some common voting rules. ^[3] Compilation complexity can be seen as one-round communication complexity. ^[1]

See also

• Voting system
• Space complexity

References

1. Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Ravilly-Abadie, Guillaume (2009-07-11). "Compiling the votes of a subelectorate". Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI'09. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 97–102.
2. Xia, Lirong; Conitzer, Vincent (2010-07-04). "Compilation Complexity of Common Voting Rules". Proceedings of the AAAI Conference on Artificial Intelligence. 24 (1): 915–920. doi: 10.1609/aaai.v24i1.7627 . ISSN   2374-3468.
3. Conitzer, Vincent; Sandholm, Tuomas (2005-06-05). "Communication complexity of common voting rules". Proceedings of the 6th ACM conference on Electronic commerce. EC '05. New York, NY, USA: Association for Computing Machinery. pp. 78–87. doi:10.1145/1064009.1064018. ISBN   978-1-59593-049-1.
4. "Compare STAR and IRV - Equal Vote Coalition". Equal Vote Coalition. Retrieved 2018-11-12.
5. Karia, Neel; Lang, Jérôme (2021-05-18). "Compilation Complexity of Multi-Winner Voting Rules (Student Abstract)" (PDF). Proceedings of the AAAI Conference on Artificial Intelligence. 35 (18): 15809–15810. doi: 10.1609/aaai.v35i18.17901 . ISSN   2374-3468.