On the Tractability Landscape of the Conditional Minisum Approval Voting Rule
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929694676353024 |
|---|---|
| author | Amanatidis, Georgios Lampis, Michael Markakis, Evangelos Papasotiropoulos, Georgios |
| author_facet | Amanatidis, Georgios Lampis, Michael Markakis, Evangelos Papasotiropoulos, Georgios |
| contents | This work examines the Conditional Approval Framework for elections involving multiple interdependent issues, specifically focusing on the Conditional Minisum Approval Voting Rule. We first conduct a detailed analysis of the computational complexity of this rule, demonstrating that no approach can significantly outperform the brute-force algorithm under common computational complexity assumptions and various natural input restrictions. In response, we propose two practical restrictions (the first in the literature) that make the problem computationally tractable and show that these restrictions are essentially tight. Overall, this work provides a clear picture of the tractability landscape of the problem, contributing to a comprehensive understanding of the complications introduced by conditional ballots and indicating that conditional approval voting can be applied in practice, albeit under specific conditions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09005 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Tractability Landscape of the Conditional Minisum Approval Voting Rule Amanatidis, Georgios Lampis, Michael Markakis, Evangelos Papasotiropoulos, Georgios Computer Science and Game Theory Computational Complexity Multiagent Systems This work examines the Conditional Approval Framework for elections involving multiple interdependent issues, specifically focusing on the Conditional Minisum Approval Voting Rule. We first conduct a detailed analysis of the computational complexity of this rule, demonstrating that no approach can significantly outperform the brute-force algorithm under common computational complexity assumptions and various natural input restrictions. In response, we propose two practical restrictions (the first in the literature) that make the problem computationally tractable and show that these restrictions are essentially tight. Overall, this work provides a clear picture of the tractability landscape of the problem, contributing to a comprehensive understanding of the complications introduced by conditional ballots and indicating that conditional approval voting can be applied in practice, albeit under specific conditions. |
| title | On the Tractability Landscape of the Conditional Minisum Approval Voting Rule |
| topic | Computer Science and Game Theory Computational Complexity Multiagent Systems |
| url | https://arxiv.org/abs/2412.09005 |