Summary
The paper looks at a type of voting where people approve several candidates and a committee must be chosen. It studies whether it's possible to pick committees that are both fair to voters and cannot be improved upon without hurting someone else (called Pareto optimal). The authors show that figuring out such a committee quickly is a very hard problem—actually NP-hard, meaning no fast solution is known. This settles a previously open question in the field. Interestingly, part of the proof was first created by an AI called ChatGPT Astra and then carefully checked and rewritten by the author.
approval-based multiwinner votingjustified representationPareto optimalitycommittee selectionNP-hardnesscomputational complexitysocial choice theoryalgorithmic fairness
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.