arXiv:1909.03162

Distance Restricted Manipulation in Voting

Aditya Anand, Palash Dey

제출 2019-09-07

원문 초록

We introduce the notion of {\em Distance Restricted Manipulation}, where colluding manipulator(s) need to compute if there exist votes which make their preferred alternative win the election when their knowledge about the others' votes is a little inaccurate. We use the Kendall-Tau distance to model the manipulators' confidence in the non-manipulators' votes. To this end, we study this problem in two settings - one where the manipulators need to compute a manipulating vote that succeeds irrespective of perturbations in others' votes ({\em Distance Restricted Strong Manipulation}), and the second where the manipulators need to compute a manipulating vote that succeeds for at least one possible vote profile of the others ({\em Distance Restricted Weak Manipulation}). We show that {\em Distance Restricted Strong Manipulation} admits polynomial-time algorithms for every scoring rule, maximin, Bucklin, and simplified Bucklin voting rules for a single manipulator, and for the $k$-approval rule for any number of manipulators, but becomes intractable for the Copeland$^\alpha$ voting rule for every $\alpha\in[0,1]$ even for a single manipulator. In contrast, {\em Distance Restricted Weak Manipulation} is intractable for almost all the common voting rules, with the exception of the plurality rule. For a constant number of alternatives, we show that both the problems are polynomial-time solvable for every anonymous and efficient voting rule.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.