| paper | Phragmén Rules for Degressive and Regressive Proportionality |
| authors | Michał Jaworski, Piotr Skowron |
| venue | IJCAI 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2 gives an axiomatic PJR guarantee, while the paper's polynomial-time computability statement is unnumbered and not a named computational result. The proposed type-mass formulation is a faithful continuous population mirror, but it mirrors the rule and its guarantee rather than a qualifying computational theorem. Therefore bit (a) fails despite the mirror being mathematically sensible.
fails bit a — no named computational result to mirror
The proposed construction is only a weighted high-multiplicity restatement of an already polynomial-time rule, and its exact guarantee is already supplied by Theorem 2 rather than posed as a computational problem.
fatal: True
The mirror covers winner computation and the PJR guarantee for type masses corresponding to Theorem 2; it leaves the other proportionality bounds, Euclidean experiments, and voting-committee satisfaction analysis without computational mirrors.
On the strict ChoCo standard, this paper has no qualifying computational anchor. Theorem 1, Corollary 1, Proposition 1, Theorem 2, and Corollary 2 are proportionality guarantees, not results asserting membership in \(P\), NP-hardness, FPT, or any other complexity classification. The introduction says that the rules “can be computed in polynomial time,” but this is an unnumbered claim. Thus I cannot honestly present the paper as containing a named complexity result whose hardness might dissolve under continuization.
The strongest positive mirror is nevertheless quite natural, and is substantively anchored in Theorem 2, though not computationally anchored in the strict sense. Theorem 2 is stated in this paper, with its formal proof deferred to the authors’ extended 2022 version. It says that \(\beta\)-Phragmén’s rule guarantees PJR degree
\[ f_\beta(\gamma,k) = \left\lfloor (k+1) \frac{\gamma\beta(1-\gamma)} {(1-\gamma)\beta(\gamma)+\gamma\beta(1-\gamma)} \right\rfloor . \]
The corresponding continuous problem can be called Continuous \(\beta\)-Phragmén Representation.
An instance consists of candidates \(C\), committee size \(k\), finitely many complete approval types \(A_1,\ldots,A_\tau\subseteq C\), rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a fixed efficiently represented non-increasing function \(\beta\). Type \(A_i\) represents a mass \(\mu_i\) of voters approving exactly \(A_i\). For each candidate \(c\), let
\[ p_c=\sum_{i:c\in A_i}\mu_i . \]
The decision process maintains a committee \(W\) and a per-voter credit level \(q_i\) for each type. Initially \(W=\varnothing\) and \(q_i=0\). Credits grow at unit speed. Candidate \(c\notin W\) becomes affordable when
\[ \sum_{i:c\in A_i}\mu_i q_i\ge \beta(p_c). \]
At the first such time, \(c\) is selected, and the credit levels of all types approving \(c\) are reset to zero. The process stops after \(k\) selections. The required output is the resulting committee, together with its representation profile: for every mass \(\gamma\), determine the least number of committee members guaranteed to represent every measurable subpopulation of mass \(\gamma\) whose members share sufficiently many approved candidates.
This is a faithful mirror. The paper already uses continuous time; the mirror continuizes only the voter population. A type is an approval set, mass is population share, and the candidate price \(\beta(|V'|/|V|)\) becomes \(\beta(p_c)\). A finite election with \(n_i\) voters of type \(A_i\) embeds exactly by setting \(\mu_i=n_i/n\). Conversely, the continuous instance is the high-multiplicity form of a large electorate in which millions of voters share a moderate number of approval profiles—for example, a national or institutional electorate choosing a representative committee from a catalogue of proposals. Voter identities do not matter to this rule, so grouping identical approval ballots is not a distortion.
I expect the winner-computation part to be Class A. Between two selections, every \(q_i\) is affine in time; the next event is obtained by comparing the candidate affordability times, and there are only \(k\) events. With explicit type support, fixed \(\beta\), and rational or otherwise exact price representations, this should be solvable in time polynomial in \(m\), \(\tau\), \(k\), and the encoding length. Theorem 2’s PJR expression should transfer from cardinalities of voter groups to masses of measurable subpopulations. It is not hardness transferred from the paper, because the paper supplies no hardness result.
The natural follow-up questions are whether the exact worst-case PJR profile can be computed efficiently rather than merely lower-bounded; whether optimizing over tie-breaking is tractable; how approximate or sampled masses affect the guarantee; and whether imposing Euclidean approval structure permits stronger bounds.
The weakest point is decisive: this is a convincing population mirror of the paper’s proportionality analysis, but not yet a ChoCo complexity result anchored in the paper. Since the underlying finite rule is already polynomial-time computable, the mirror mainly compresses a high-multiplicity input and makes population fractions explicit; it does not demonstrate discrete hardness disappearing in the continuum.
The negative case is unusually strong at the programme’s first gate: this paper has no named computational anchor. Theorem 1, Corollary 1, Proposition 1, Theorem 2, and Corollary 2 are proportionality guarantees, not complexity, approximation, parameterized, or algorithmic results. The paper’s statement that the rules “can be computed in polynomial time” is unnumbered and supplies no computational problem or classification. Section 5 reports simulations and distributional observations. Thus there is no discrete computational theorem whose high-multiplicity counterpart ChoCo could classify.
Theorem 2 is the proponent’s strongest rescue, but its proposed mirror does not repair that defect. Replacing voter counts by masses is perfectly faithful: for approval types \(A_i\) with masses \(\mu_i\), one sets \(p_c=\sum_{i:c\in A_i}\mu_i\), and candidate affordability becomes \(\sum_{i:c\in A_i}\mu_i q_i\geq\beta(p_c)\). This is a sensible high-multiplicity formulation, and it is not undermined by identity loss. Approval-based Phragmén is anonymous, and large electorates with repeated approval profiles are entirely plausible.
But this construction is only a weighted restatement of the rule. The original rule already uses continuous time and normalized population sizes. With explicit support, the next event is found by comparing the affordability times of the \(m\) remaining candidates; the state has one credit variable per type, and there are only \(k\) events. The continuous version therefore mirrors an implementation detail of an already polynomial-time rule, not a computational result in the paper. That answer may be mathematically correct, but it does not create the complexity question the programme is designed to investigate.
The proposed output “for every mass \(\gamma\), determine the representation guarantee” does not help. Theorem 2 already universally quantifies over all voter groups and supplies the closed-form lower bound
\[ f_\beta(\gamma,k) = \left\lfloor (k+1) \frac{\gamma\beta(1-\gamma)} {(1-\gamma)\beta(\gamma)+\gamma\beta(1-\gamma)} \right\rfloor . \]
Computing an exact worst-case PJR profile, optimizing over tie-breaking, or studying approximation under sampled masses could be worthwhile new projects. They are not computational mirrors of a result stated in this paper; they manufacture a new optimization problem around an axiomatic theorem. That distinction is decisive under the ChoCo standard.
A stronger attempt would continuize the Euclidean experiments instead: take a density \(\rho(x)\) of voters on \([-1,1]\), retain finitely many candidates, and compute the exact satisfaction distribution. In the one-dimensional model, however, the approval set changes only at the finitely many endpoints \(x_c\pm\xi\). The population decomposes into finitely many intervals having identical approval types, whose masses are obtained by integrating \(\rho\). The committee computation therefore reduces to the same finite type-mass model. For the voting-committee satisfaction measure, one similarly obtains integrals of a finite collection of functions after the committee is known; the paper contains no computational claim about that quantity. If the density is supplied through a difficult oracle, any resulting hardness comes from distribution access or numerical integration, not from continuizing the population.
This is not a claim that approval elections lack meaningful high multiplicity, nor that a continuous study of Phragmén rules could never be useful. The honest conclusion is narrower but fatal here: the paper is an axiomatic and empirical analysis of already efficiently computable rules. Its natural mass version is faithful, but it contributes no named computational object for ChoCo to classify. The proponent has identified a plausible extension of the paper, not a worthwhile continuous computational mirror of it.
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.