We study the phase transition of the coalitional manipulation problem for generalized scoring rules. Previously it has been shown that, under some conditions on the distribution of votes, if the number of manipulators is @math , where @math is the number of voters, then the probability that a random profile is manipulable by the coalition goes to zero as the number of voters goes to infinity, whereas if the number of manipulators is @math , then the probability that a random profile is manipulable goes to one. Here we consider the critical window, where a coalition has size @math , and we show that as @math goes from zero to infinity, the limiting probability that a random profile is manipulable goes from zero to one in a smooth fashion, i.e., there is a smooth phase transition between the two regimes. This result analytically validates recent empirical results, and suggests that deciding the coalitional manipulation problem may be of limited computational hardness in practice.
Recent work by Xia @cite_21 is independent from, and closely related to, our work. As mentioned above, Xia's paper is concerned with computing the margin of victory in elections. He focuses on computational complexity questions and approximation algorithms, but one of his results is similar to Parts and of Theorem . However, our analysis is completely different; our approach facilitates the proof of Part of the theorem, which is our main contribution. An even more recent (and also independent) manuscript by Xia @cite_27 considers similar questions for generalized scoring rules and captures additional types of strategic behavior (such as control), but again, crucially, this work does not attempt to understand the phase transition (nor does it subsume our Theorem ).
@cite_27 @cite_21
1644339822 2065358633
In this paper, we propose a framework to study a general class of strategic behavior in voting, which we call vote operations. We prove the following theorem: if we fix the number of alternatives, generate @math votes i.i.d. according to a distribution @math , and let @math go to infinity, then for any @math , with probability at least @math , the minimum number of operations that are needed for the strategic individual to achieve her goal falls into one of the following four categories: (1) 0, (2) @math , (3) @math , and (4) @math . This theorem holds for any set of vote operations, any individual vote distribution @math , and any integer generalized scoring rule, which includes (but is not limited to) almost all 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 (but not limited to) constructive destructive manipulation, bribery, and control by adding deleting votes, margin of victory, and minimum manipulation coalition size. Therefore, our main theorem naturally applies to these problems. The margin of victory of an election, defined as the smallest number k such that k voters can change the winner by voting differently, is an important measurement for robustness of the election outcome. It also plays an important role in implementing efficient post-election audits, which has been widely used in the United States to detect errors or fraud caused by malfunctions of electronic voting machines. In this paper, we investigate the computational complexity and (in)approximability of computing the margin of victory for various voting rules, including approval voting, all positional scoring rules (which include Borda, plurality, and veto), plurality with runoff, Bucklin, Copeland, maximin, STV, and ranked pairs. We also prove a dichotomy theorem, which states that for all continuous generalized scoring rules, including all voting rules studied in this paper, either with high probability the margin of victory is Θ(√n), or with high probability the margin of victory is Θ(n), where n is the number of voters. Most of our results are quite positive, suggesting that the margin of victory can be efficiently computed. This sheds some light on designing efficient post-election audits for voting rules beyond the plurality rule.