Understanding the Impact of Proportionality in Approval-Based Multiwinner Elections - Boehmer, Niclas; Glessen, Lara; Peters, Jannik (Proceedings of the AAAI Conference on Artificial Intelligence, 2026)
Despite extensive theoretical research on proportionality inapproval-based multiwinner voting, its impact on which committees and candidates can be selected in practice remainspoorly understood. We address this gap by (i) analyzing thecomputational complexity of several natural problems relatedto the behavior of proportionality axioms, and (ii) conducting an extensive experimental study on both real-world andsynthetic elections. Our findings reveal substantial variationin the restrictiveness of proportionality across instances, including previously unobserved high levels of restrictivenessin some real-world cases. We also introduce and evaluate newmeasures for quantifying a candidate’s importance for achieving proportional outcomes, which differ clearly from assessing candidate strength by approval score.