The Margin of Victory in Schulze, Cup, and Copeland Elections: Complexity of the Regular and Exact Variants

摘要

The margin of victory is a critical measure for the robustness of voting systems in terms of changing election outcomes due to errors in the ballots or fraud in using electronic voting machines. Applications include risk-limiting post-election audits so as to restore the trust in the correctness of election outcomes. Continuing the work of Xia [24], we show that the margin of victory problem is NP-complete for Schulze and cup elections. We also consider the exact variant of this problem, which we show to be complete for DP in Schulze, cup, and Copeland elections.