Computer Science – Artificial Intelligence
Scientific paper
2012-04-05
Computer Science
Artificial Intelligence
Scientific paper
In this paper, we propose a framework to study a general class of strategic behavior in voting, which we call {\em vote operations}. Our main theorem is the following: if we fix the number alternatives, generate $n$ votes i.i.d. according to a distribution $\pi$, and let $n$ go to infinity. Then, for any $\epsilon >0$, with probability at least $1-\epsilon$, the minimum number of operations that are necessary for the strategic to achieve her goal falls into one of the following four categories: (1) 0, (2) $\Theta(\sqrt n)$, (3) $\Theta(n)$, and (4) $\infty$. This theorem holds for any set of vote operations, any individual vote distribution $\pi$, and any generalized scoring rule, which includes (but not limited to) most commonly studied voting rules, e.g., approval voting, all positional scoring rules (including Borda, plurality, and veto), plurality with runoff, Bucklin, Copeland, maximin, STV, and ranked pairs. We also show that many well-studied types of strategic behavior fall under our framework, including constructive and destructive manipulation, bribery, and control by adding/deleting votes, and margin of victory and minimum manipulation coalition size. Therefore, our main theorem naturally applies to these problems.
No associations
LandOfFree
How Many Vote Operations Are Needed to Manipulate A Voting System? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How Many Vote Operations Are Needed to Manipulate A Voting System?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How Many Vote Operations Are Needed to Manipulate A Voting System? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-212880