Summary
The paper looks at a problem in voting systems where groups are chosen by approval votes. It asks if there is a way to pick committees that are both fair to all represented voters and efficient in making everyone as happy as possible. The authors show that finding such committees quickly is very hard—so hard that no fast algorithm is likely to exist. This means computer programs cannot easily solve this problem perfectly for all cases.
What this means in practice
- •For voting system designers: Avoid relying on exact algorithms to find committees that meet both fairness and efficiency criteria in approval voting systems.
- •For decision support engineers: Focus on approximation or heuristic methods for selecting committees when fairness and Pareto optimality are both desired but must accept computational limits.
A theory result. No direct application yet.
Abstract
An open problem in approval-based multiwinner voting concerns whether we can efficiently compute committees that satisfy both justified representation and Pareto optimality. We answer this question negatively by proving that, on the domain of all profiles, outputting a committee satisfying both axioms is NP-hard. An initial proof was found by ChatGPT Astra. This was then verified and rewritten by the author.