Proportional election rule works under complex voting constraints

Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule

Computer Science and Game Theory

Summary

Choosing a fair group of winners in elections can get tricky when there are special rules about which sets of candidates can win. The authors introduce a new fairness rule that works for many kinds of these rules and voting with ranked choices. They show this fairness fits well with known ideas and prove it works perfectly for certain mathematical cases called matroids. While the basic way to use their rule can be slow, they find practical shortcuts that make it efficient in many real situations. They also tested the rule in practice and discuss its limits when voters just approve multiple candidates instead of ranking them.

What this means in practice

  • For election system designers: Choose fair winners under complex rules by applying the new proportionality criterion and the solid coalition refinement method efficiently when constraints form matroids.
  • For committee software developers: Implement election software that handles ranked ballots and general constraints with improved proportionality checks and efficient computations in practical cases.

Authors

Grzegorz Kwacz, Georgios Papasotiropoulos, Piotr Skowron

Abstract

We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.