Can we efficiently compute conditional approval votes?
On the Tractability Landscape of Conditional Minisum Approval Voting Rule
This paper analyzes the computational complexity of the Conditional Minisum Approval Voting (CMS) rule in multi-issue elections where voter preferences can be interdependent. It demonstrates that CMS, while offering expressive ballots, is generally computationally intractable. However, by introducing practical restrictions, like limiting ballot types (group-dichotomous ballots) or the structure of dependencies (bounded vertex cover number in dependency graphs), the computation becomes feasible in polynomial time. These findings are relevant to LLM-based multi-agent systems by offering insights into designing efficient preference aggregation mechanisms when agents have complex, interdependent preferences. Specifically, it shows the importance of imposing limitations on the expressiveness of preferences (analogous to ballot restrictions) and the structure of inter-agent dependencies (analogous to dependency graphs) to achieve computational tractability in real-world applications.