Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections

Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections

Cynthia Maushagen, David Niclaus, Paul Nüsken, Jörg Rothe, Tessa Seeger

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2940-2948. https://doi.org/10.24963/ijcai.2024/326

Both Schulze and ranked pairs are voting rules that satisfy many natural, desirable axioms. Many standard types of electoral control (with a chair seeking to change the outcome of an election by interfering with the election structure) have already been studied. However, for control by replacing candidates or voters and for (exact) multimode control that combines multiple standard attacks, many questions remain open. We solve a number of these open cases for Schulze and ranked pairs. In addition, we fix a flaw in the reduction of Menton and Singh showing that Schulze is resistant to constructive control by deleting candidates and re-establish a vulnerability result for destructive control by deleting candidates. In some of our proofs, we study variants of s-t vertex cuts in graphs that are related to our control problems.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice