Approximating Electoral Control Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911681289912320 |
|---|---|
| author | Bui, Huy Vu Chavrimootoo, Michael C. Le, Kien T. Nguyen, Son M. |
| author_facet | Bui, Huy Vu Chavrimootoo, Michael C. Le, Kien T. Nguyen, Son M. |
| contents | Much research in electoral control -- one of the most studied form of electoral attacks, in which an entity running an election alters the structure of that election to yield a preferred outcome -- has focused on giving decision complexity results, e.g., membership in P, NP-completeness, or fixed-parameter tractability. Approximability on the other hand has received little attention in electoral control, despite its prevalence in the study of other forms of electoral attacks, such as manipulation and bribery. Early work established preliminary results about popular voting rules such as plurality, approval, and Condorcet. In this paper, we completely determine for each of the "standard" control problems under plurality, approval, and Condorcet, whether they are approximable, and we prove our results in both the weighted and unweighted voter settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_19279 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Electoral Control Problems Bui, Huy Vu Chavrimootoo, Michael C. Le, Kien T. Nguyen, Son M. Computer Science and Game Theory Much research in electoral control -- one of the most studied form of electoral attacks, in which an entity running an election alters the structure of that election to yield a preferred outcome -- has focused on giving decision complexity results, e.g., membership in P, NP-completeness, or fixed-parameter tractability. Approximability on the other hand has received little attention in electoral control, despite its prevalence in the study of other forms of electoral attacks, such as manipulation and bribery. Early work established preliminary results about popular voting rules such as plurality, approval, and Condorcet. In this paper, we completely determine for each of the "standard" control problems under plurality, approval, and Condorcet, whether they are approximable, and we prove our results in both the weighted and unweighted voter settings. |
| title | Approximating Electoral Control Problems |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2509.19279 |