Approximating voting rules from truncated ballots

Abstract

Classical voting rules assume that ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. We suggest to fix a rank k, to ask all voters to specify their best k candidates, and then to consider “top-k approximations” of rules, which take only into account the top-k candidates of each ballot. The questions are then: Are these k-truncated approximations good predictors of the approximated rule? For which values of k and under which assumptions can we expect to output the correct winner with high probability? For different voting rules, we study these questions theoretically, by giving tight approximation ratios, and empirically, based on randomly generated profiles and on real data. We consider two measures of the quality of the approximation: the probability of selecting the same winner as the original rule, and the score ratio. We do a worst-case study (for the latter measure only), and for both measures, an average-case study and a study from real data sets.

Appendix: ANOVA by Ranks

The Friedman test [15] known as the Friedman two-way ANalysis Of VAriances by ranks (ANOVA by Ranks) is a non-parametric statistical test. The objective of this test is to determine if we may conclude from a sample of results that there is difference among treatment effects:

$$\begin{aligned} \chi ^{2}_{F} = \frac{12 b}{ v(v+1)} \sum _{j=1..v} R^2_j - \frac{v \times (v+1)^2}{4} \end{aligned}$$

(1)

where

• b is number of data sets (blocks, rows);

• v is number of treatments (voting rules, columns);

• $r_i^j$ is the rank of the jth of v rules on the ith of b data sets;

• $R_j=\frac{1}{b}\sum _{i=1..b} r_i^j$

The first step in calculating the ANOVA’s test is to convert the original results to ranks. Thus, it ranks the treatments for each problem separately, the best performing treatment should have rank 1, the second best rank 2, etc. In case of ties, average ranks are computed.

Under the null hypothesis ($H_0$) — which states that all the treatments behave similarly and thus their ranks $R_j$ for $j= \{1,\dots ,v\}$ should be equal — the Friedman statistic is distributed according to $\chi ^{2}_{F}$ with $b-1$ degrees of freedom when b and v are big enough (as a rule of a thumb, $b > 10$ and $v > 5$).

Iman and Davenport [17] showed that Friedman’s $\chi ^{2}_{F}$ presents a conservative behavior and proposed a better statistic which is distributed according to the F-distribution with two degrees of freedom $v-1$ and $(v-1)\times (b-1)$:

$$\begin{aligned} F_F = \frac{(b-1)\times \chi ^{2}_{F} }{b \times (v-1) - \chi ^{2}_{F} } \end{aligned}$$

(2)

In order to apply the ANOVA’s test to our specific case, let us consider the experimental results illustrated in Fig. 4 (a) when $m=7, n=15$ and $\phi =0.8$ presented in Table 1.

Table 1 ANOVA’s test for experiments in Fig. 4 (a)

Our goal is to compare statistically the behavior of voting rules (columns) for different values of $k\in \{1,\dots ,5\}$ (rows). In this example, $b=5$ and $v = 7$. We compute $\chi ^{2}_{F}$ and $F_F$ following Eqs. 1 and 2, respectively as follows:

$$ \begin{aligned}\chi ^{2}_{F} &= {\small \frac{12 \times 5}{7\times 8} [(3.8^2 + 3.6^2 + +6^2 + 6.8^2 + 4.8^2 + 1^2 + 2^2)-\frac{7\times (8)^2}{4}}]=27.514 \\ F_F &= \frac{4\times 27.514}{5 \times 6 - 27.514}=44.27\end{aligned}$$

The Friedman test proves whether the measured average ranks are significantly different from the mean rank $R_j=(3.8 +3.6 + 6 + 6.8 +4.8 + 1 + 2)/7 = 4$ where $j\in \{1,\dots ,7\}$ expected under the null hypothesis.

$F_F$ is distributed according to the F distribution with $DF1=7-1=6$ and $DF2=(7-1)\times (5-1)=24$ degrees of freedom. In this example, the null hypothesis is rejected because:

• The critical value (from the table of critical values for the F distribution for use with ANOVA) with 0.05 significance level and (6, 24) degrees of freedom, is 2.508, so the null hypothesis is rejected at a high level of significance since $F_F= 44.27>> 2.508$.

• The p-value computed by using F(6, 24) distribution is 8.12658E-12, so the null hypothesis is rejected at a high level of significance since 8.12658E-12 $<< 0.05$

From the obtained results, we can say that the considered voting rules have a very different behavior.

Table 2 summarizes the results of Friedman test and Iman–Davenport extension for different figures considered in this paper. Results suggest that the null hypothesis is always rejected for all settings which means that the k-truncated voting rules behave differently.

Table 2 Statistical test for different experiments