Efficiently finding committees satisfying justified representation and Pareto optimality
Given an approval profile and a target committee size , determine whether there exists a polynomial-time algorithm that outputs a committee of size satisfying both justified representation and Pareto optimality for every such profile. The cited preprint claims that, on the domain of all approval profiles, computing such a committee is NP-hard.
References
Primary source
Additional references
Progress summary
A new unrefereed preprint claims that finding committees with both fairness and efficiency guarantees is computationally hard.
The problem asks whether committees can be found efficiently while satisfying justified representation and Pareto optimality. A September 2026 preprint claims a negative answer via an NP-hardness proof.
September 2026 claimed NP-hardness result
The preprint claims that computing a committee satisfying both properties is NP-hard, establishing a computational barrier to jointly enforcing them. Its abstract credits ChatGPT Astra with finding the initial proof; the author says they verified and rewrote it. The result is unrefereed and remains unverified.
Current status (as of September 2026): A claimed NP-hardness resolution is publicly available but unverified; no independently verified result was found.
Joint justified representation and Pareto optimality shown NP-hard
Sources
- arxiv.org
- arxiv.org
- cse.unsw.edu.au
- semanticscholar.org
- ora.ox.ac.uk
- ifaamas.org
- researchgate.net
- dominik-peters.de
- openreview.net
- arxiv.org
- arxiv.org
- arxiv.org
- arxiv.org
- export.arxiv.org
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- www-cdn.anthropic.com
- alignment.anthropic.com
- www-cdn.anthropic.com
Solutions 0
No solutions have been posted yet.