Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916247019454464 |
|---|---|
| author | Maushagen, Cynthia Niclaus, David Nüsken, Paul Rothe, Jörg Seeger, Tessa |
| author_facet | Maushagen, Cynthia Niclaus, David Nüsken, Paul Rothe, Jörg Seeger, Tessa |
| contents | 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 [IJCAI 2013] 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_08956 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections Maushagen, Cynthia Niclaus, David Nüsken, Paul Rothe, Jörg Seeger, Tessa Computer Science and Game Theory 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 [IJCAI 2013] 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. |
| title | Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2405.08956 |