Faster checks for fair voting groups using graph cuts
Faster Verification of PJR$^+$ via Mincuts
Computer Science and Game Theory
Summary
Certain voting systems need to make sure groups of voters have fair representation. This paper looks at a fairness rule called PJR+, which was hard to check efficiently before. The authors found a new way to check if a voting result is fair using a graph technique called mincuts, which is faster and easier to run. Their method also shows which groups might be unfairly treated and can find how much the fairness rule can be relaxed.
What this means in practice
- •For election software developers: Create faster tools that check if committee election results fairly represent voter groups using improved graph-based algorithms.
- •For online community moderators: Verify representation fairness in online polls that select groups or committees, improving trust in automated decision tools.
Authors
Drew Springham
Abstract
PJR$^+$ is a polynomial-time verifiable proportionality axiom for approval-based committee elections, but its known polynomial-time verification procedure relies on general submodular-function minimisation. We show that its objective is a maximum-closure problem and give a direct mincut formulation of the problem on a bipartite graph. Using an almost-linear-time maximum-flow algorithm, this yields an $\mathcal{O}(m(nk)^{1+o(1)})$-time verifier, where $n$, $m$, and $k$ are the numbers of voters, candidates, and committee members, respectively. The dependence of this bound on each parameter separately is almost linear: it is linear in $m$, and almost linear in $n$ and $k$. The verifier also returns an explicit group witnessing a violation and admits a slower but immediately implementable variant based on the preflow--push mincut algorithm. Finally, for the parameterised axiom $α$-PJR$^+$, where $α$ is used as a multiplier in the group size, we demonstrate how to compute the largest value of $α$ for which a committee still fails the axiom using this mincut formulation.