TY - JOUR AU - Bentert, Matthias AU - Skowron, Piotr PY - 2020/04/03 Y2 - 2024/03/29 TI - Comparing Election Methods Where Each Voter Ranks Only Few Candidates JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 02 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v34i02.5598 UR - https://ojs.aaai.org/index.php/AAAI/article/view/5598 SP - 2218-2225 AB - <p>Election rules are formal processes that aggregate voters' preferences, typically to select a single winning candidate. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized—we ask each voter to rank a random subset of ℓ candidates, and (ii) deterministic—we ask each voter to provide a ranking of her ℓ most preferred candidates (the ℓ-truncated ballot). We establish theoretical bounds on the approximation ratios and complement our theoretical analysis with computer simulations. We find that it is usually better to use the randomized approach.</p> ER -