Papers for

decision support engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Pareto optimality and fair representation committee choice is NP-hard

Jointly Satisfying Pareto Optimality and Justified Representation is NP-Hard in Approval-Based Multiwinner Voting

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.

Tue 8 SeptComputer Science and Game Theory

The gist

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.

Open → 2609.08357v1