Английская Википедия:Compilation complexity
Compilation complexity is the smallest number of bits required to summarize a input to a function, such that the output of the function can be computed correctly. The notion was particularly studied in voting theory.[1] Often, a group has to accept a decision, but some of the voters have not arrived yet. It is desired to take the votes of the present voters and summarize them such that, when the other voters arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary.
An important advantage of low compilation complexity is that it makes it easier to verify voting outcomes. For example, suppose an elections are held in a country of 1,000,000 people, divided into 1000 voting-stations of 1000 voters each. Low compilation complexity lets us summarize the outcome in each voting-station separately, which is relatively easy to verify by double-counting by representatives of the parties. Then, every citizen can verify the final outcome by summing the results from the 1000 voting stations. This verifiability is important so that the public trusts and accepts the voting rule.[1] Compilation complexity is also algorithmically useful for computing the backward induction winner in Stackelberg voting games.[2]
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 ballot 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. This number is typically a function of n (the number of voters), k (the number of known votes) and c (the number of candidates).
A closely related notion is that of equivalence of partial profiles. Suppose there are n voters, of which only k<n have voted. The votes of these k voters are called a partial profile. Given a voting rule r, two partial profiles P and Q on k voters are called r-equivalent if, for any partial profile R, the rule winner on the complete profile P u R is equal to the rule winner on the complete profile Q u R. The relation "r-equivalent" is obviously an equivalence relation, so it partitions the set of profiles on k voters to equivalence classes. We denote by eq(r,k,c) the number of equivalence classes when the voting-rule is r, the number of known votes is k, and the number of candidates is c. The compilation complexity of any rule is the logarithm of the number of equivalence classes, that is,<math>\lceil \log(eq(r,k,c)) \rceil</math>.[1]
Compilation complexity of single-winner voting rules
This section describes bounds on the compilation complexity of some common single-winner voting rules based on ordinal ballots. The results are based on two papers:
- Chevaleyre, Lang, Maudet and Ravilli-Abadie[1] assume that u (= n-k - the number of unknown voters) is unknown, so their results are given as a function of k and c only.
- Xia and Conitzer[2] study also the case that k (the number of known votes) is unknown, and also the case that both u and k are known. For the latter case, lower compilation complexity results are possible. The upper bounds are constructive: they are based on easy-to-compute compilation functions.
Maximum and minimum compilation complexity
The number of equivalence classes for any rule is in <math>O(\min\left({(c!)}^k, k^{(c!)}\right))</math>. Therefore, the maximum compilation complexity of any voting rule is in <math>\min\left(k\cdot \log{c!},~ c!\cdot \log{k}\right)</math>. 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 <math>\log{c}</math>.[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 <math>O(c\log{k})</math>. 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 <math>\Theta(c\log{(1+k/c)} + k \log(1+c/k))</math> which is in <math>O(k+c)</math>.[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 <math>(c-1)\cdot \log{(k(c-1))}</math>, and there is a matching lower bound, so the complexity is in <math>\Theta(c \log{k c})</math>.[1] If u is known, then the bound is <math>\Theta(c \log{\min(k c, u c)})</math>.
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 <math>\frac{c(c-1)}{2}\log(k+1)</math>, 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 <math>\Omega(c^2 \log (\min(\frac{k \log c}{q c} - 1, u)))</math> and <math>O(c^2 \log(\min(k , u))).</math> When u is unknown, it is between <math>\Omega(c^2 \log (\frac{k }{q m} - 2))</math> and <math>O(c^2 \log(k)).</math>[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 <math>\Omega(c^2 \log (\min(\frac{k \log c}{q c} - 1, u)))</math> and <math>O(c^2 \log(\min(k , u c))).</math> When u is unknown, it is between <math>\Omega(c^2 \log (\frac{k }{q m} - 2))</math> and <math>O(c^2 \log(k)).</math>[2]
For Condorcet-consistent rules based on the weighted majority graph, when u is unknown, the compilation complexity is between <math>\Omega(\min(c^2 \log k, c u \log{u} ))</math> and <math>O(c^2 \log(k)).</math>[1]
Voting rules with runoff
The compilation complexity of two-round voting (plurality with runoff) is in <math>\Theta(c^2 \log{k})</math>. 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 <math>\Theta(c^2 \log{\min(u,k)})</math>.
The compilation complexity of Single transferable vote is in <math>\Omega\left(2^c \log (1+\frac{k}{2^c}) + k \log(1+\frac{2^c}{k})\right)</math> and in <math>O\left(c 2^c \log (1+\frac{k}{2^c}) + k c \log(1+\frac{2^c}{k})\right)</math>. [1]
Bucklin's rule
For the Bucklin voting rule, if min(k,u) ≥ m ≥ 12, the compilation complexity is in <math>\Theta(c^2 \log{\min(k,u)})</math>; when u is unknown it is <math>\Theta(c^2 \log{k})</math>.[2]
Compilation complexity of multi-winner voting rules
Karia and Lang[4] 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 <math>\Theta(c\log{(1+k/c)} + k \log(1+c/k))</math>.
- For Borda, the complexity is in <math>\Theta(c \log{k c})</math>.
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, then the compilation complexity is very small: 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[3] study the communication complexity of some common voting rules. Compilation complexity can be seen as one-round communication complexity.[1]
References
