Computational Aspects of Conditional Minisum Approval Voting in Elections with Interdependent Issues
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 304-310. https://doi.org/10.24963/ijcai.2020/43
Approval voting provides a simple, practical framework for multi-issue elections, and the most representative example among such election rules is the classic Minisum approval voting rule. We consider a generalization of Minisum, introduced by the work of Barrot and Lang , referred to as Conditional Minisum, where voters are also allowed to express dependencies between issues. The price we have to pay when we move to this higher level of expressiveness is that we end up with a computationally hard rule. Motivated by this, we focus on the computational aspects of Conditional Minisum, where progress has been rather scarce so far. We identify restrictions to every voter's dependencies, under which we provide the first multiplicative approximation algorithms for the problem. The restrictions involve upper bounds on the number of dependencies an issue can have on the others. At the same time, by additionally requiring certain structural properties for the union of dependencies cast by the whole electorate, we obtain optimal efficient algorithms for well-motivated special cases. Overall, our work provides a better understanding on the complexity implications introduced by conditional voting.
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting
Agent-based and Multi-agent Systems: Algorithmic Game Theory