On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910880637124608 |
|---|---|
| author | Yang, Yongjie |
| author_facet | Yang, Yongjie |
| contents | A variety of constructive manipulation, control, and bribery problems for approval-based multiwinner voting have been extensively studied recently. However, their destructive counterparts seem to be less explored. This paper investigates the complexity of several destructive bribery problems under five prestigious approval-based multiwinner voting rules -- approval voting, satisfaction approval voting, net-satisfaction approval voting, Chamberlin-Courant approval voting, and proportional approval voting. Broadly, these problems are to determine if a number of given candidates can be excluded from any winning committees by performing a limited number of modification operations. We offer a complete landscape of the complexity of the problems. For NP-hard problems, we study their parameterized complexity with respect to meaningful parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2002_00836 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting Yang, Yongjie Computer Science and Game Theory Multiagent Systems A variety of constructive manipulation, control, and bribery problems for approval-based multiwinner voting have been extensively studied recently. However, their destructive counterparts seem to be less explored. This paper investigates the complexity of several destructive bribery problems under five prestigious approval-based multiwinner voting rules -- approval voting, satisfaction approval voting, net-satisfaction approval voting, Chamberlin-Courant approval voting, and proportional approval voting. Broadly, these problems are to determine if a number of given candidates can be excluded from any winning committees by performing a limited number of modification operations. We offer a complete landscape of the complexity of the problems. For NP-hard problems, we study their parameterized complexity with respect to meaningful parameters. |
| title | On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2002.00836 |