Approval-Based Committee Voting: A Comprehensive Review

Approval-based committee scoring rules are a type of voting system used to elect committees from a set of candidates. In this paper, the authors aim to characterize these rules by grouping them into different classes based on their computational complexity. They present several directions for future work and highlight the importance of studying these rules in detail.
Firstly, the authors show that all Thiele rules (a class of ABC scoring rules) are NP-hard to compute on the full domain, meaning they cannot be solved efficiently without sacrificing accuracy. However, by restricting the domain of preference profiles, it is possible to develop efficient algorithms for computing these rules.
Secondly, the authors characterize several important ABC voting rules, including Phragmén’s rule and the method of equal shares, which are still missing in previous research. They provide insights into how their ideas might be used to derive these results.
Finally, the authors note that while they have identified all relevant ABC scoring rules as belonging to one of their classes, a full characterization of the set of ABC scoring rules is still an interesting area for future work.
The paper’s findings have implications for understanding and improving voting systems, particularly those based on approval votes. By demystifying complex concepts through engaging metaphors or analogies, this summary aims to help readers comprehend the key takeaways from the article without oversimplifying its contents.