Phragmén's Voting Methods and Justified Representation

The strongest mirror is a high-multiplicity version of the paper’s variance-minimizing rule. I would treat it as a Class B problem: the population becomes continuous, but the committee remains an integral \(k\)-subset, and the hardness survives because the reduction’s combinatorics live in the candidate-incidence structure.

The paper’s lead anchor is Theorem 5.1, proved in the paper. Its relevant assertion is that the decision problem var-Phragmén is NP-complete even when every voter approves at most two candidates, \(s(A)=2\), and every candidate is approved by at most three voters, \(d(A)=3\). The problem asks, given an approval profile, committee size \(k\), and threshold \(\alpha>0\), whether there is a valid load distribution \(x\) whose voter loads \(\bar x_i\) satisfy \(\sum_i \bar x_i^2<\alpha\). The paper proves NP-hardness by reducing from Independent Set on cubic graphs, and establishes membership in NP through a mixed-integer quadratic formulation, invoking the cited result that MIQP is in NP.

Here is the continuous problem I would attach to that theorem.

Continuous var-Phragmén Threshold. An instance consists of candidates \(C\), a committee size \(k\), finitely many approval types \(t\in T\), rational masses \(\mu_t>0\) with \(\sum_t\mu_t=1\), a rational per-capita load scale \(\beta>0\), and a rational threshold \(\alpha\). Type \(t\) is an approval set \(A_t\subseteq C\); all agents of that type are identical for the purposes of Phragmén’s rule. The committee must remain integral: choose \(y_c\in\{0,1\}\) with \(\sum_c y_c=k\).

Let \(z_{t,c}\) be the total load assigned by candidate \(c\) to type \(t\). Require \(z_{t,c}=0\) whenever \(c\notin A_t\), \(0\le z_{t,c}\le \beta\mu_t y_c\), and \(\sum_t z_{t,c}=\beta y_c\) for every candidate \(c\). Thus each selected candidate contributes total load \(\beta\), distributed only among its approving population; \(\beta=1/N\) is the natural normalization of the paper’s unit candidate load for a population of \(N\) voters. The average load of type \(t\) is \(\ell_t=\mu_t^{-1}\sum_c z_{t,c}\). The question is whether there is a feasible integral committee and load allocation with \(\sum_t\mu_t\ell_t^2<\alpha\).

This is not continuizing the committee or the alternatives. It is exactly the paper’s load-balancing problem with the voter list replaced by a distribution over complete approval types. If one allows measurable allocations within a type, convexity means that an optimum for the variance objective can be taken uniform within each type, giving precisely the finite-dimensional formulation above.

The regime is natural in a large approval election or validator-selection process: millions of nominators may share one of a few hundred or thousand approval patterns because they belong to the same organization, constituency, issue coalition, or platform community. The number of agents can be \(N=R|E|\), while the number of types is only \(|E|\), with \(R\) arbitrarily large. This is genuine high multiplicity, not a claim that every small committee election is a continuum.

The hardness mechanism survives this limit. Given a cubic graph \(G=(V,E)\), create one candidate for each vertex and one approval type for each edge \(e=\{u,v\}\), with \(A_e=\{u,v\}\) and \(\mu_e=1/|E|\). Let the population contain \(R\) identical voters of every edge type, so \(\beta=1/(R|E|)\). If \(G\) has an independent set of size \(k\), the corresponding committee has \(3k\) disjoint incident edge types, and the loads can be equalized at \(1/(3R)\), giving objective \(k/(3|E|R^2)\). If the selected vertices are not independent, they jointly touch at most \(3k-1\) edge types. Since the total selected-candidate load is \(k\beta\), Cauchy–Schwarz gives objective at least \(k^2/(|E|R^2(3k-1))\), which is strictly greater than \((k/3+1/9)/(|E|R^2)\). Therefore the continuous instance can use threshold \(\alpha=(k/3+1/9)/(|E|R^2)\), and the Independent Set reduction remains valid for arbitrarily large \(R\).

So I expect Continuous var-Phragmén Threshold to be NP-hard, probably NP-complete under the usual rational-input convention. This is a transferred-hardness Class B mirror: population multiplicity disappears, but the graph structure among candidates does not. The natural follow-up questions are whether the problem becomes tractable for fixed \(k\), fixed number of approval types, or restricted candidate-incidence graphs; whether there are useful approximation schemes; and how much finite-election error is introduced when an arbitrary distribution is rounded to finitely many voters.

A second, weaker but very clean anchor is Theorem 5.4, also proved in the paper. It states that the output of seq-Phragmén can be computed exactly in \(O(k^3mn(\log n)^2)\) time, including the cost of rational arithmetic. The paper’s algorithm computes, in each round, \(s_c^{(j)}=(1+\sum_{i\in N_c}\bar x_i^{(j-1)})/|N_c|\), chooses a remaining candidate minimizing this value, and raises the loads of its approvers to that common level.

The corresponding problem is Continuous seq-Phragmén Output. Given \(C,k,(A_t,\mu_t)_{t\in T}\), a positive mass \(\rho_c=\sum_{t:c\in A_t}\mu_t\) for every candidate, a load scale \(\beta\), and a fixed tie-breaking order, begin with \(\ell_t^{(0)}=0\). In round \(j\), for every remaining candidate \(c\), compute \(q_c^{(j)}=(\beta+\sum_{t:c\in A_t}\mu_t\ell_t^{(j-1)})/\rho_c\). Select a candidate minimizing \(q_c^{(j)}\), and set \(\ell_t^{(j)}=q_c^{(j)}\) for approving types and \(\ell_t^{(j)}=\ell_t^{(j-1)}\) otherwise. After \(k\) rounds, output the selected committee and the type loads.

This is an exact Class A mirror. The discrete sums in the paper become mass-weighted sums, and the direct implementation uses \(O(km\tau)\) rational updates. With rational masses, the bit lengths grow polynomially in the input length and \(k\), so the type-compressed problem should be solvable in polynomial time. The paper’s own “cylindrical vessels” interpretation makes this especially plausible: the base area of a vessel is already proportional to the number of voters, and the continuum simply replaces that area by population mass.

I would not claim that the whole paper has been continuized. The axiomatic results in Section 6 are outside the computational scope here, and the paper’s fractional \(x_{i,c}\) variables do not themselves make the society continuous: they are load-allocation variables over a finite voter set. The mirror changes the input object from a named list of voters to a mass distribution over complete approval types while preserving the integral committee decision.

The weakest point is that the paper does not itself prove a continuous theorem. Its hardness construction has one edge type per graph edge, so the high-multiplicity interpretation requires the explicit replication argument above; and the variance mirror uses uniform within-type loads plus the per-capita scaling \(\beta\). Those are genuine co-modifications, although they are forced by normalization and are exact for the variance objective. The case is therefore strongest for the underlying load-balancing problem, not as a claim that every theorem in the paper automatically extends unchanged.