2024/12/12 by Georgios Amanatidis, Michael Lampis, Evangelos Markakis +1 · 1 voice
Computer Science · #Advanced Graph Theory Research #Approval voting #Complexity and Algorithms in Graphs #Computer science #Condorcet method #Internet Traffic Analysis and Secure E-voting #Political science #Theoretical computer science #Voting #cs.CC #cs.GT #cs.MA
paper · pdf · doi:10.1016/j.ipl.2025.106561
arxiv published 2024/12/12 · openalex publication_date 2025/01/21 · crossref created 2025/01/21 · arxiv updated 2025/02/03 · crossref issued 2025/03/01 · crossref published 2025/03/01 · crossref published-print 2025/03/01 · openalex created_date 2025/10/10 · crossref deposited 2025/11/25 · crossref indexed 2025/11/25 · openalex updated_date 2026/07/23
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.