Approximating voting rules from truncated ballots

摘要

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.