2020/02/13 by Manel Ayadi, Nahla Ben Amor, Ayadi, Manel +4
Computer Science · Economics, Econometrics and Finance · #Game Theory and Voting Systems #Rough Sets and Fuzzy Logic #cs.GT
paper · pdf · doi:10.48550/arxiv.2002.06009
17 pages, 7 figures
arxiv created 2020/02/13 · arxiv updated 2020/02/17
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. 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.