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.
  Efficient post-election audits select the number of machines or precincts to audit based in part on the margin of victory (the number of ballots that must be changed in order to change the outcome); a close election needs more auditing than a landslide victory. For a simple "first-pastthe-post" election, the margin is easily computed based on the number of votes the first and second place candidates received. However, for instant runoff voting (IRV) elections, it is not immediately obvious how to compute the margin of victory. This paper presents algorithmic techniques for computing the margin of victory for IRV elections. We evaluate our method by attempting to compute the margin of victory for 25 IRV elections in the United States. The margin of victory computed can then be used to conduct post-election audits more effectively for IRV elections. There are many sources of error in counting votes: the apparent winner might not be the rightful winner. Hand tallies of the votes in a random sample of precincts can be used to test the hypothesis that a full manual recount would find a different outcome. This paper develops a conservative sequential test based on the vote-counting errors found in a hand tally of a simple or stratified random sample of precincts. The procedure includes a natural escalation: If the hypothesis that the apparent outcome is incorrect is not rejected at stage s, more precincts are audited. Eventually, either the hypothesis is rejected-and the apparent outcome is confirmed-or all precincts have been audited and the true outcome is known. The test uses a priori bounds on the overstatement of the margin that could result from error in each precinct. Such bounds can be derived from the reported counts in each precinct and upper hounds on the number of votes cast in each precinct. The test allows errors in different precincts to be treated differently to reflect voting technology or precinct sizes. It is not optimal, but it is conservative: the chance of erroneously confirming the outcome of a contest if a full manual recount would show a different outcome is no larger than the nominal significance level. The approach also gives a conservative P-value for the hypothesis that a full manual recount would find a different outcome, given the errors found in a fixed size sample. This is illustrated with two contests from November, 2006: the U.S. Senate race in Minnesota and a school hoard race for the Sausalito Marin City School District in California, a small contest in which voters could vote for up to three candidates. Risk-limiting post-election audits have a pre-specified minimum chance of requiring a full hand count if the outcome of the contest is not the outcome that a full hand count of the audit trail would show. The first risk-limiting audits were performed in 2008 in California. Three refinements to increase efficiency were tested in Marin and Yolo counties, California, in November 2009. The first refinement is to audit a collection of contests as a group by auditing a random sample of batches of ballots and combining observed discrepancies in the contests represented in those batches in a particular way: the maximum across-contest relative overstatements (MACRO). MACRO audits control the familywise error rate (the chance that one or more incorrect outcomes fails to be corrected by a full hand count) at a cost that can be lower than that of controlling the per-comparison error rate with independent audits. A risk-limiting audit for the entire collection of contests can be built on MACRO using a variety of probability sampling schemes and ways of combining MACRO across batches. The second refinement is to base the test on the Kaplan-Markov confidence bound, drawing batches with probability proportional to an error bound (PPEB) on the MACRO. The Kaplan-Markov bound is especially well suited to sequential testing: After each batch is audited, a simple calculation--a product of fractions--determines whether to audit another batch or to stop the audit and confirm the apparent outcomes. The third refinement is to audit individual ballots rather than larger batches of ballots, comparing the cast vote record (the machine interpretation of the voter's marks on the ballot) to a human interpretation of the voter's intent. Such single-ballot audits can greatly reduce workload: When the outcome is correct, the number of ballots that must be audited to attain a given risk limit is roughly proportional to the number of ballots per batch. All three of these refinements can be used together, resulting in extremely efficient risk-limiting audits. Post-election audits use the discrepancy between machine counts and a hand tally of votes in a random sample of precincts to infer whether error affected the electoral outcome. The maximum relative overstatement of pairwise margins (MRO) quantifies that discrepancy. The electoral outcome a full hand tally shows must agree with the apparent outcome if the MRO is less than 1. This condition is sharper than previous ones when there are more than two candidates or when voters may vote for more than one candidate. For the 2006 U.S. Senate race in Minnesota, a test using MRO gives a P-value of 4.05 for the hypothesis that a full hand tally would find a different winner, less than half the value Stark [Ann. Appl. Statist. 2 (2008) 550-581] finds. A general definition is proposed for the margin of victory of an election contest. That definition is applied to Instant Runoff Voting (IRV) and several estimates for the IRV margin of victory are described: two upper bounds and two lower bounds. Given round-by-round vote totals, the time complexity for calculating these bounds does not exceed O(C2 log C), where C is the number of candidates. It is also shown that calculating the larger and more useful of the two lower bounds can be viewed, in part, as solving a longest path problem on a weighted, directed, acyclic graph. Worst-case analysis shows that neither these estimates, nor any estimates based only on tabulation round-by-round vote totals, are guaranteed to be within a constant factor of the margin of victory. These estimates are calculated for IRV elections in Australia and California. Pseudo code for calculating these estimates is provided. 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.