| paper | Proportional Representation in Practice: Quantifying Proportionality in Ordinal Elections |
| authors | Tuva Bardal, Markus Brill, David McCune, Jannik Peters |
| venue | AAAI 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates C, committee size k, an explicit finite set T of top-truncated ordinal ballot types with rational masses mu, and a committee W of size k, compute the infimum alpha such that every solid coalition of mass at least alpha times ell/k contains at least min(|C'|,ell) members of W for every candidate set C' and ell in [k].
A high-multiplicity society is an explicit distribution over complete top-truncated ballot types; masses define solid-coalition sizes, the decision object is an integral committee W, and the objective is the minimum PSC relaxation factor alpha.
The mirror may provide mainly input compression through a sufficient statistic rather than a genuinely new algorithmic phenomenon, so its research payoff is modest.
fatal: False
Covers Theorem 1’s PSC-value computation and Theorem 2’s alpha-PSC feasibility and optimization; it leaves the empirical rule comparisons, ballot-completion procedure, and non-PSC measures untouched.
A defensible continuous mirror exists, strongest for the paper’s quantitative PSC results. I would not claim that the whole paper continuizes: the empirical comparisons among STV, EAR, SNTV, and seq-RCV are not computational anchors. But the PSC-value problems are a good fit.
The natural regime is a large local-election electorate whose ballots come from a much smaller catalogue of ballot types. A type is a top-truncated ordinal ballot: a strict ranked prefix together with the common unranked bottom class, exactly as in the paper. Its mass is the fraction of voters casting that ballot. The decision variable remains an integral committee \(W\subseteq C\), \(|W|=k\); the mirror does not fractionalize seats or candidates. This could describe a ward with thousands or tens of thousands of voters but only tens or hundreds of recurring ballot forms, generated by party endorsements, slate voting, or common local campaigning. The paper does not report the number of distinct ballot types, so this is a plausible high-multiplicity regime rather than an empirical claim about every Scottish election.
The key fact is that PSC is already defined in normalized population terms. For a candidate set \(C'\), let
\[ \rho_\mu(C')=\sum_{t:\,C'\text{ is a prefix of }t}\mu_t \]
be the mass of the maximal solid coalition over \(C'\). Then \(W\) satisfies continuous \(\alpha\)-PSC precisely when, for every \(\ell\in[k]\) and every \(C'\subseteq C\),
\[ \rho_\mu(C')\ge \alpha\ell/k \quad\Longrightarrow\quad |W\cap C'|\ge \min(|C'|,\ell). \]
This is not a new proportionality notion; it is the paper’s definition with voter counts replaced by rational masses.
My lead anchor is Theorem 1, proved in this paper: “Given an instance and a committee \(W\), the PSC value of \(W\) can be computed in polynomial time.”
The corresponding continuous problem is:
Continuous PSC-Value. Given candidates \(C\), committee size \(k\), an explicit finite type set \(T\), rational masses \(\mu_t\), and a committee \(W\), output
\[ \alpha^\infty_{\mathrm{PSC}}(\mu,W) = \inf\{\alpha\ge 0: W\text{ satisfies continuous }\alpha\text{-PSC}\}. \]
The expected result is polynomial-time solvability in \(m\), \(\tau=|T|\), and the encoding length of the rational masses.
The paper’s proof transfers particularly cleanly. Every positive-mass maximal solid coalition is represented by a prefix of one of the \(\tau\) types, so there are only polynomially many relevant coalitions. For each such coalition and each \(\ell\), compute the threshold \(k\rho_\mu(C')/\ell\), then test whether \(W\) contains enough candidates from \(C'\). Thus the continuous problem has the same threshold structure as the discrete one, while its running time depends on the number of types rather than on the potentially enormous number of cloned voters.
This has exact rational-clone fidelity. If all masses have common denominator \(D\), replace type \(t\) by \(D\mu_t\) identical voters. Then
\[ \rho_\mu(C')=\frac{|N_{C'}|}{D}, \]
and every \(\alpha\)-PSC condition is identical. Conversely, any discrete profile collapses to its type frequencies. The mirror therefore preserves coalitions, thresholds, committees, ties, and certificates. It is a direct high-multiplicity version, not a relaxed welfare surrogate.
The second anchor is Theorem 2, also stated in this paper and proved in its full version: “Given an instance and a value \(\alpha<1\), deciding whether \(\alpha\)-PSC is satisfiable is NP-complete.”
Its continuous counterpart is:
Continuous \(\alpha\)-PSC Feasibility. Given \(C\), \(k\), an explicit rational distribution \(\mu\) over top-truncated ballot types, and a rational \(\alpha<1\), decide whether there exists a committee \(W\subseteq C\), \(|W|=k\), satisfying continuous \(\alpha\)-PSC. If the answer is yes, output such a committee.
Equivalently, one may ask for
\[ \alpha^\ast_{\mathrm{PSC}}(\mu) = \min_{|W|=k}\alpha^\infty_{\mathrm{PSC}}(\mu,W). \]
I expect this continuous problem to be NP-complete, with hardness transferring in the programme’s Class-B sense. The same common-denominator construction maps every discrete instance to a rational distribution without changing feasibility. Membership in NP remains straightforward: a committee is the certificate, and Theorem 1’s threshold procedure verifies it in polynomial time. The hardness is therefore not erased by replacing a population of clones with their mass; the difficult combinatorics remain in selecting a committee from the candidate agenda.
The mirror is especially plausible because the paper’s central motivation is precisely that ordinary thresholds such as \(n/k\) are too coarse in real electorates. Its \(\alpha\)-values already measure coalition size as a fraction of the population. Passing from \(|N'|/n\) to \(\rho_\mu(C')\) makes that interpretation exact and scale-free: duplicating every voter changes nothing, while changing the composition of the electorate does. That is exactly what one would want from a population-level model.
The scope should remain narrow. These mirrors cover the paper’s quantitative PSC computation and optimal PSC committee selection. They do not claim continuous versions of STV’s transfer dynamics, the experimental rule comparisons, or the ballot-completion procedure. Those would require separate modelling decisions and are not needed for the positive case.
The weakest point is that this is a relatively modest mirror. The committee remains discrete, and Theorem 1’s continuous algorithm is largely an exact aggregation and threshold computation rather than a dramatic new column-generation or convex-optimization result. Moreover, the paper’s tables do not establish that the number of distinct ballot types is always much smaller than the number of voters. In some elections, \(\tau\) could be close to \(n\), weakening the practical compression.
That weakness does not invalidate the mirror. The programme does not require every continuous analogue to create a new algorithmic phenomenon. Here the paper studies an aggregate, anonymity-respecting property whose semantics are invariant under cloning, and the rational distribution is therefore a faithful object. The two anchors together give a useful boundary: fixed-committee evaluation is expected to be tractable, while optimizing over committees remains hard because candidate-side combinatorics survive continuization.
Natural follow-up questions include whether the optimization problem becomes tractable for fixed \(k\) or fixed \(m-k\), whether \(\alpha^\ast_{\mathrm{PSC}}\) admits useful approximation guarantees, how robust the value is when \(\mu\) is estimated from samples, and whether STV or EAR can be characterized as approximate algorithms for the continuous PSC-optimization problem.
The strongest negative case is that both proposed anchors are exact normalizations of the paper’s existing finite problem, rather than new continuous computational objects.
For Theorem 1, every relevant quantity already depends only on the normalized size of a maximal solid coalition. If \(b(C')\) is the number of voters supporting \(C'\), the paper’s threshold is \(k\,b(C')/(n\ell)\). Replacing \(b(C')/n\) by a mass \(\rho_\mu(C')\) is therefore a change of notation. The proof already scans prefixes of the listed ballots and compares these rational thresholds. On an explicitly supported distribution, the “continuous algorithm” is the same scan with weighted sums. It uses neither a continuous optimization method nor a population-level structural insight; it is a compressed implementation of the finite algorithm.
The best high-multiplicity story does not repair this. Suppose ballots arise from party slates or recurring campaign templates, so millions of voters occupy a small catalogue of ballot types. That is a perfectly sensible regime, but the resulting problem is still simply the paper’s computation on the sufficient statistic it already implicitly uses. It may save input space, but it does not create a new computational question for ChoCo. Theorem 1 is thus better viewed as an immediate weighted corollary than as a substantive continuous mirror.
Theorem 2 is even more exact. Given rational masses, clear denominators and create \(D\mu_t\) cloned voters of each type. The resulting finite instance has exactly the same \(\alpha\)-PSC-feasible committees; conversely, every finite profile collapses to such a distribution. Membership in NP, threshold verification, and the hardness reduction all transfer mechanically. This is not an objection that “continuous does not help”: a hard continuous problem would still be valuable if it revealed a new boundary. The objection is that here the continuous problem is literally the same feasibility language under a quotient encoding. The paper’s NP-hardness already classifies it, and the proposed mirror contributes no independent algorithmic or structural problem.
The obvious attempts to make the mirror more ambitious leave the paper. Sampling uncertainty would turn it into a statistical estimation problem; a succinct or implicit ballot distribution would introduce representation complexity; fractional committees would continuize the outcome space rather than the population; and preserving individual sampling identities would abandon the high-multiplicity model. None is a stronger version of the paper’s own computational result.
There is no obstruction from identity, atomlessness, or degeneracy: PSC is anonymous, its coalitions have positive population mass, and the normalized \(\alpha\)-value remains nontrivial. That is precisely why this negative case is ultimately weak. The proponent has identified a legitimate high-multiplicity regime, and the programme explicitly permits faithful weighted restatements even when the result is modest. I would therefore reject the claim that these anchors establish a rich continuous research direction, but I could not honestly defend the universal claim that no worthwhile mirror exists. The paper is a poor source of new continuum-specific phenomena, not a paper for which a valid continuous mirror cannot be made.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.