Maximum and minimum compilation complexity

The number of equivalence classes for any rule is in ${\displaystyle O(\min \left({(c!)}^{k},k^{(c!)}\right))}$. Therefore, the maximum compilation complexity of any voting rule is in ${\displaystyle \min \left(k\cdot \log {c!},~c!\cdot \log {k}\right)}$. But there are rules with a much smaller compilation complexity. For example, if there is a sure winner, then the number of equivalence classes is c (the number of possible winners), so the compilation complexity is ${\displaystyle \log {c}}$.^[1]

Plurality voting

In plurality voting, any partial profile can be summarized by recording the plurality score of each candidate - the number of times each candidate appears first. Since this number is at most k, the compilation complexity is in ${\displaystyle O(c\log {k})}$. Another bound can be attained by counting equivalence classes: the equivalence classes correspond to all vectors of c integers with sum k. Taking the logarithm gives ${\displaystyle \Theta (c\log {(1+k/c)}+k\log(1+c/k))}$ which is in ${\displaystyle O(k+c)}$.^[1]

Borda voting

In Borda voting, any partial profile can be summarized by recording the Borda score of each candidate. Since the Borda score is at most k(c-1), the compilation complexity is at most ${\displaystyle (c-1)\cdot \log {(k(c-1))}}$, and there is a matching lower bound, so the complexity is in ${\displaystyle \Theta (c\log {kc})}$.^[1] If u is known, then the bound is ${\displaystyle \Theta (c\log {\min(kc,uc)})}$.

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 comiplation complexity is at most log(T(k,c)). An upper bound on log(T(k,c)) is ${\displaystyle {\frac {c(c-1)}{2}}\log(k+1)}$, 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]

For Condorcet-consistent rules based on the unweighted majority graph, such as Copeland or voting tree, there exists some constant q such that the compilation complexity is between ${\displaystyle \Omega (c^{2}\log(\min({\frac {k\log c}{qc}}-1,u)))}$ and ${\displaystyle O(c^{2}\log(\min(k,u))).}$ When u is unknown, it is between ${\displaystyle \Omega (c^{2}\log({\frac {k}{qm}}-2))}$ and ${\displaystyle O(c^{2}\log(k)).}$^[2]

For Condorcet-consistent rules based on the order of pairwise elections, such as ranked pairs or Minimax Condorcet method, there exists some constant q such that the compilation complexity is between ${\displaystyle \Omega (c^{2}\log(\min({\frac {k\log c}{qc}}-1,u)))}$ and ${\displaystyle O(c^{2}\log(\min(k,uc))).}$ When u is unknown, it is between ${\displaystyle \Omega (c^{2}\log({\frac {k}{qm}}-2))}$ and ${\displaystyle O(c^{2}\log(k)).}$^[2]

For Condorcet-consistent rules based on the weighted majority graph, when u is unknown, the compilation complexity is between ${\displaystyle \Omega (\min(c^{2}\log k,cu\log {u}))}$ and ${\displaystyle O(c^{2}\log(k)).}$^[1]

Voting rules with runoff

The compilation complexity of two-round voting (plurality with runoff) is in ${\displaystyle \Theta (c^{2}\log {k})}$. 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] When u is known, the bound is ${\displaystyle \Theta (c^{2}\log {\min(u,k)})}$.

The compilation complexity of Single transferable vote is in ${\displaystyle \Omega \left(2^{c}\log(1+{\frac {k}{2^{c}}})+k\log(1+{\frac {2^{c}}{k}})\right)}$ and in ${\displaystyle O\left(c2^{c}\log(1+{\frac {k}{2^{c}}})+kc\log(1+{\frac {2^{c}}{k}})\right)}$. ^[1]

Bucklin's rule

For the Bucklin voting rule, if min(k,u) ≥ m ≥ 12, the compilation complexity is in ${\displaystyle \Theta (c^{2}\log {\min(k,u)})}$; when u is unknown it is ${\displaystyle \Theta (c^{2}\log {k})}$.^[2]