Fractional Pareto-Optimality in Multiwinner Voting
2026-06-09 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a voting concept called fractional Pareto-optimality (fPO), which is a stronger form of efficiency than the usual Pareto-optimality (PO) used in multiwinner voting. They show that fPO is a better way to ensure that chosen committees are efficient even when candidates are duplicated. The authors provide a way to check for fPO efficiently and find that some popular voting methods, like proportional approval voting, do not always satisfy fPO. They also identify specific voting scenarios where PO and fPO are effectively the same.
multiwinner votingPareto-optimalityfractional Pareto-optimalitycommittee selectionweighted utilitarian welfareproportional approval votingpreference domainsefficiencycommittee monotonicity
Authors
Patrick Becker, Niclas Boehmer, Fabian Frank, Lara Glessen
Abstract
Efficiency in multiwinner voting is most naturally captured by Pareto-optimality (PO), yet this notion is computationally and structurally difficult to handle. We therefore study fractional Pareto-optimality (fPO), under which a committee may not be dominated even by a fractional committee, i.e., any convex combination of committees. fPO turns out to be a natural refinement of PO as it retains exactly those Pareto-optimal committees whose efficiency is robust under uniform cloning of candidates. Furthermore, fPO committees are guaranteed to exist and have strong structural properties. We present a characterization of fPO in terms of weighted utilitarian welfare maximization, which yields a polynomial-time algorithm for verifying fPO and shows that the set of fPO committees satisfies committee monotonicity and is connected under single-candidate swaps. Analyzing welfarist rules through the lens of fPO, we further uncover an incompatibility between fPO and equality-oriented objectives. Most notably, we show that proportional approval voting (PAV) violates fPO in the approval setting. We close by pinpointing preference domains, including various one-dimensional ones, on which PO and fPO collapse into one notion.