Faster Verification of PJR${}^{+}$ via Mincuts

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 $\alpha$-PJR${}^{+}$, where $\alpha$ is used as a multiplier in the group size, we demonstrate how to compute the largest value of $\alpha$ for which a committee still fails the axiom using this mincut formulation.

15 pages, 10 page main body, 3 figures