Summability criterion

Condorcet methods Positional voting Cardinal voting Quota-remainder methods Approval-based committees Fractional social choice Semi-proportional representation By ballot type Pathological response Strategic voting Paradoxes of majority rule Positive results 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.

Often, a group has to accept a decision, but not all the votes can be gathered together in a single location.

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.

However, we focus on c alone for simplicity, as we are usually interested in the case with a very large number of unknown votes.

[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

[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.

[2] For the closely-related highest median voting rules, the complexity for a ballot including