Pareto Optimality in Approval-Based Multiwinner Voting
This research provides a deeper understanding of Pareto optimality for researchers and practitioners in computational social choice, particularly for multiwinner voting systems, by characterizing its properties and developing efficient algorithms in specific scenarios.
This paper investigates Pareto optimality in approval-based multiwinner voting, focusing on restricted domains like Candidate Interval and Voter Interval. It introduces the Single Dominance Only property to characterize Pareto optimality and demonstrates committee monotonicity and reconfigurability for these domains, showing any Pareto optimal committee can be transformed into another while preserving optimality. The authors also present polynomial-time algorithms for finding Pareto optimal committees satisfying EJR+ and for counting Pareto optimal committees in the Voter Interval domain.
In approval-based multiwinner voting, Pareto optimality is used as an axiom capturing efficiency of committees. We study the structure of the space of Pareto optimal committees in restricted domains and in general by investigating the monotonicity and reconfigurability of such committees. For the Candidate Interval and Voter Interval domains, we propose the Single Dominance Only property, which provides a simple characterization of Pareto optimality, and show that Pareto optimal committees satisfy committee monotonicity using this property. Further, we show that, for the above domains, any Pareto optimal committee can be reconfigured into any other Pareto optimal target committee without using auxiliary candidates, meaning that the candidates in the starting but not the target committee can be replaced by candidates in the target but not the starting committee one by one while preserving Pareto optimality at every step. In addition, we adapt a polynomial-time algorithm for finding a committee satisfying EJR+, a proportionality axiom, such that it also satisfies Pareto optimality, for the above domains. We further describe a polynomial-time algorithm for counting the number of Pareto optimal committees for voting instances satisfying Voter Interval, and give a proof idea for its correctness. For the unrestricted domain, we explain the challenges of proving committee monotonicity and reconfigurability. We provide an example in which the distance of two committees in the Pareto optimality reconfiguration graph exceeds the distance proven for the above domains, and outline an approach toward showing the connectedness of the graph.