{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T00:37:05Z","timestamp":1787359025684,"version":"build-2736575974"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher.\n\nA voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances.\n\nAs a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3.\n\nA recent breakthrough result showed that achieving this bound of 3 is possible;\n\nhowever, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search.\n\n\n\nOur main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. \n\nEach candidate starts with a score equal to his number of first-place votes.\n\nThese scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins.\n\nWe give a one-paragraph proof that this voting rule achieves distortion 3.\n\nThis rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead.\n\nWe also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al.\n\n\n\nWe also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k &lt; n rounds; then, a candidate is chosen with probability proportional to his residual score.\n\nThis general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output.\n\nWe show that for all k, this rule has expected distortion at most 3.<\/jats:p>","DOI":"10.24963\/ijcai.2022\/50","type":"proceedings-article","created":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T02:55:56Z","timestamp":1657940156000},"page":"349-355","source":"Crossref","is-referenced-by-count":16,"title":["Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion"],"prefix":"10.24963","author":[{"given":"Fatih Erdem","family":"Kizilkaya","sequence":"first","affiliation":[{"name":"University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[{"name":"University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}","theme":"Artificial Intelligence","location":"Vienna, Austria","acronym":"IJCAI-2022","number":"31","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2022,7,23]]},"end":{"date-parts":[[2022,7,29]]}},"container-title":["Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T11:07:25Z","timestamp":1658142445000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2022\/50"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2022\/50","relation":{},"subject":[],"published":{"date-parts":[[2022,7]]}}}