Summability criterion

A joint Politics and Economics series
Social choice and electoral systems
Social choice Mechanism design Comparative politics Comparison List (By country)
Single-winner methods Single vote - plurality methods First preference plurality (FPP) Two-round (US: Jungle primary) Partisan primary Instant-runoff UK: Alternative vote (AV) US: Ranked-choice (RCV) Condorcet methods Condorcet-IRV Round-robin voting Minimax Schulze Ranked pairs Maximal lottery Positional voting Plurality (el. IRV) Borda count (el. Baldwin) Antiplurality (el. Coombs) Cardinal voting Score voting Approval voting Majority judgment STAR voting
Proportional representation Party-list Apportionment Highest averages Largest remainders National remnant Biproportional List type Closed list Open list Panachage List-free PR Localized list Quota-remainder methods Hare STV Schulze STV CPO-STV Quota Borda Approval-based committees Thiele's method Phragmen's method Expanding approvals rule Method of equal shares Fractional social choice Direct representation Interactive representation Liquid democracy Fractional approval voting Maximal lottery Random ballot Semi-proportional representation Cumulative SNTV Limited voting
Mixed systems By results of combination Mixed-member majoritarian Mixed-member proportional By mechanism of combination Non-compensatory Parallel (superposition) Coexistence Conditional Fusion (majority bonus) Compensatory Seat linkage system UK: 'AMS' NZ: 'MMP' Vote linkage system Negative vote transfer Mixed ballot Supermixed systems Dual-member proportional Rural–urban proportional Majority jackpot By ballot type Single vote Double simultaneous vote Dual-vote
Paradoxes and pathologies Spoiler effects Spoiler effect Cloning paradox Frustrated majorities paradox Center squeeze Pathological response Perverse response Best-is-worst paradox No-show paradox Multiple districts paradox Strategic voting Lesser evil voting Exaggeration Truncation Turkey-raising Paradoxes of majority rule Tyranny of the majority Discursive dilemma Conflicting majorities paradox
Social and collective choice Impossibility theorems Arrow's theorem Majority impossibility Moulin's impossibility theorem McKelvey–Schofield chaos theorem Gibbard's theorem Positive results Median voter theorem Condorcet's jury theorem May's theorem Condorcet dominance theorems Harsanyi's utilitarian theorem
Politics portal Economics portal Mathematics portal
v t e

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]}

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.

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]

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]

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]

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]

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)}$.

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]

• 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]

• Voting system
• Space complexity