Efficient algorithm finds fair and nearly optimal voting committees
Finding Representative and Approximately Efficient Committees
Computer Science and Game Theory
Summary
Choosing a committee that fairly represents voters while being efficient is a tough computational problem. The authors study a popular voting rule called proportional approval voting (PAV) and analyze a local search version (local PAV) which is easier to compute. They show local PAV makes committees that are reasonably efficient but not perfectly so. Then, they present a new fast algorithm that combines good fairness with a nearly optimal efficiency guarantee, improving on previous methods and running in polynomial time.
What this means in practice
- •For election software developers: Implement fair and efficient committee selection in approval-based voting systems using the new polynomial-time algorithm.
- •For online platform designers: Build user groups or recommendation committees that balance proportional representation and efficiency efficiently with the proposed method.
Authors
Dominik Peters, Rohit Vaish, Jatin Yadav
Abstract
In approval-based committee voting, proportional approval voting (PAV) is a well-studied rule that combines proportional representation with Pareto efficiency. However, computing a PAV committee is NP-hard, raising a natural question: Can the proportionality and efficiency properties of PAV be achieved via computationally efficient procedures? We make two contributions toward answering this question. First, building on the known proportionality guarantees of the local-search-based variant of PAV (or local PAV), we systematically study its efficiency properties. We show that local PAV committees are weakly Pareto optimal, meaning that no other committee is strictly preferred by every voter. We also identify limitations: Local PAV guarantees only a $2$-approximation to fractional Pareto optimality ($2$-fPO) and a $2/3$-approximation to the optimal PAV score, and both bounds are tight. In contrast, global PAV is Pareto optimal and satisfies the stronger $α^\star$-fPO guarantee, where $α^\star \approx 1.346$ is the unique solution of $\int_0^{α^\star} \frac{1-e^{-y}}{y} \, dy = 1$, and this approximation is tight. Second, we design a polynomial-time algorithm that combines the best of these guarantees. The committee returned by our algorithm satisfies EJR$+$ (a proportionality guarantee), $α^\star$-fPO, and weak Pareto optimality. It also achieves a $0.79$-approximation to the optimal PAV score, matching the best possible polynomial-time approximation assuming $P \neq NP$. Our algorithm works by pipage rounding a concave relaxation of the PAV objective and using that committee to initialize local PAV, thereby combining global approximation guarantees with local search stability.