Proceedings

Winner Determination and Strategic Control in Conditional Approval Voting

Evangelos Markakis, Georgios Papasotiropoulos

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 342-348.

https://doi.org/10.24963/ijcai.2021/48

Keywords

  • Agent-based and Multi-agent Systems: Algorithmic Game Theory
  • Agent-based and Multi-agent Systems: Computational Social Choice
  • Agent-based and Multi-agent Systems: Voting

Abstract

Our work focuses on a generalization of the classic Minisum approval voting rule, introduced by Barrot and Lang (2016), and referred to as Conditional Minisum (CMS), for multi-issue elections.

Although the CMS rule provides much higher levels of expressiveness, this comes at the expense of increased computational complexity. In this work, we study further the issue of efficient algorithms for CMS, and we

identify the condition of bounded treewidth (of an appropriate graph that emerges from the provided ballots), as the necessary and sufficient condition for polynomial algorithms, under common complexity assumptions. Additionally we investigate the complexity of problems related to the strategic control of such elections by the possibility of adding or deleting either voters or alternatives. We exhibit that in most variants of these problems, CMS is resistant against control.

Evangelos Markakis, and Georgios Papasotiropoulos. 2021. Winner Determination and Strategic Control in Conditional Approval Voting. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 342–348. https://doi.org/10.24963/ijcai.2021/48
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards