| paper | Multiwinner Approval Rules as Apportionment Methods |
| authors | Markus Brill, Jean-François Laslier, P. Skowron |
| venue | AAAI 2017 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Computing an optimal seat distribution is in \(\mathrm{P}\), using the Hamilton largest-remainder method. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given parties \(i\in[p]\), \(k\) candidates \(C_i\) per party, approval types \(A_i=C_i\), and masses \(\mu_i\ge0\) with \(\sum_i\mu_i=1\), choose a committee \(S\subseteq\bigcup_i C_i\) with \(|S|=k\) and mass assignments \(y_{i,c}\ge0\) satisfying \(y_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in S}y_{i,c}=\mu_i\), and \(\sum_i y_{i,c}=1/k\) for \(c\in S\), maximizing \(\sum_i\sum_{c\in S\cap A_i}y_{i,c}\); output the optimal seat distribution \(x_i=|S\cap C_i|\).
The continuous party-list Monroe problem keeps the \(k\)-candidate committee integral while assigning each selected candidate exactly \(1/k\) of population mass. Its value is \(\sum_i\min(\mu_i,x_i/k)\), so the induced computation is Hamilton's largest-remainder rule on quotas \(k\mu_i\).
Theorem 4 itself covers only the paper's party-list slice, while the unrestricted approval-type Monroe problem proposed by the proponent is a new integral committee-selection problem not solved by that theorem; the anchor therefore supports a narrow mirror, not the full extension.
fatal: False
The mirror directly covers Theorem 4's Monroe-to-Hamilton correspondence and gives analogous population-weighted versions of Theorems 1 and 5; it leaves general approval-profile winner determination, quota axioms, thresholds, and degressive-proportionality claims without a computational mirror.
The strongest honest case is a qualified one. The paper contains no named theorem establishing NP-hardness, membership in \( \mathrm{P} \), FPT tractability, or another formal complexity classification. Its named results are structural correspondences between multiwinner rules and apportionment methods. Thus, under a strict computational-anchor requirement, this paper is not a fully compliant positive case. Nevertheless, it has an unusually natural high-multiplicity mirror, and the following is the best substantive case for it.
The population mirror is this. Let \(C\) be the candidate set and \(k\) the committee size. A voter type is an approval set \(A_t\subseteq C\). A society is a mass distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the fraction of voters of type \(t\), \(\sum_t\mu_t=1\). The committee remains an integral \(k\)-element subset of \(C\); only the population is continuized. For rational masses, \(\mu_t=n_t/n\) recovers an ordinary profile with \(n_t\) voters of each type, and multiplying all masses by \(n\) recovers the paper’s objective exactly.
This is a plausible regime for large party-list or institutional elections: millions of voters, but relatively few repeated approval types, such as supporters approving every candidate of one party or members of a professional constituency approving a common candidate pool. The paper itself constructs precisely such groups \(N_i\) of identical voters, so the authors should recognize the high-multiplicity interpretation. The relevant comparison is \(n\gg |T|\), not merely “many voters” in the abstract.
My lead is the following problem, anchored in Theorem 4.
Continuous Monroe Committee. Given \(C\), \(k\), approval types \(A_t\), and masses \(\mu_t\), choose a committee \(S\subseteq C\) with \(|S|=k\), together with nonnegative assignment masses \(y_{t,c}\), satisfying
\[ \sum_{c\in S}y_{t,c}=\mu_t \quad\text{for every }t, \qquad \sum_t y_{t,c}=\frac{1}{k} \quad\text{for every }c\in S. \]
The objective is to maximize
\[ \sum_t\sum_{c\in S\cap A_t}y_{t,c}. \]
Thus every selected candidate represents exactly \(1/k\) of the population, but assignments may split a type’s mass. A solution is an optimal committee and an optimal mass-assignment witness.
Theorem 4, proved in this paper, states: assuming the number of seats divides the number of voters, Monroe’s rule induces the Hamilton apportionment method. In the paper’s party-list construction, if party \(i\) has population mass \(\mu_i\) and \(x_i\) of the \(k\) selected candidates belong to that party, the continuous Monroe value becomes
\[ \sum_i \min\!\left(\mu_i,\frac{x_i}{k}\right). \]
Consequently, the optimal \(x\) is obtained by assigning \(\lfloor k\mu_i\rfloor\) seats first and distributing the remaining seats to the parties with the largest fractional remainders. This is exactly Hamilton’s largest-remainder rule, now expressed in population proportions. The continuum removes the paper’s divisibility assumption: there is no need for an integer number of voters per representative.
I regard this as the strongest mirror because the continuous assignment variable is not an arbitrary fractional outcome. It is the natural mass analogue of Monroe’s balanced assignment, while the committee itself remains indivisible. On the party-list slice this is Class A: compute quotas and sort remainders. For unrestricted approval types, I would expect candidate-side hardness to remain, hence a likely Class B phenomenon rather than a continuum-specific obstruction. The paper does not prove that complexity claim, however.
A second, independent mirror is anchored in Theorem 1.
Continuous Weighted-Thiele Winner. Given \(C\), \(k\), a finite type distribution \(\mu\), and a non-increasing positive weight sequence \(w\), choose a size-\(k\) committee maximizing
\[ \sum_{t\in T}\mu_t \left( \sum_{j=1}^{|A_t\cap S|}w_j \right). \]
For PAV, \(w_j=1/j\), so the objective is
\[ \sum_{t\in T}\mu_t H_{|A_t\cap S|}, \]
where \(H_r=\sum_{j=1}^r1/j\).
Theorem 1, proved here, states that for every weight sequence satisfying \(w_j\ge w_{j+1}>0\), the apportionment method induced by \(w\)-Thiele coincides with the divisor method whose divisor sequence is
\[ d_w=\left(\frac{1}{w_1},\frac{1}{w_2},\frac{1}{w_3},\ldots\right). \]
Its PAV specialization is Corollary 2, also proved here: PAV induces D’Hondt. In the party-list mirror, the objective reduces to
\[ \sum_i \mu_i H_{x_i}, \]
and the next seat for party \(i\) has marginal value \(\mu_i/(x_i+1)\), exactly D’Hondt’s priority score.
This is a genuine population-weighted version of the paper’s underlying winner problem, not a fractional committee problem. Its party-list restriction is tractable by the divisor procedure, so that slice is Class A. For unrestricted approval types, I would expect hardness to survive through the integral choice of candidates; changing voter counts into masses does not make candidates divisible. Any claim that PAV becomes easy merely because the population is continuous would therefore be unjustified.
The third possible anchor is Theorem 5.
Continuous Variance-Phragmén Committee. Given \(C\), \(k\), and \(\mu\), choose a committee \(S\) and nonnegative per-unit-mass loads \(\ell_{t,c}\) satisfying
\[ \ell_{t,c}=0 \quad\text{if }c\notin A_t, \]
\[ \sum_t\mu_t\ell_{t,c} = \begin{cases} 1,&c\in S,\\ 0,&c\notin S, \end{cases} \]
and minimize
\[ \sum_t\mu_t \left(\sum_{c\in C}\ell_{t,c}\right)^2. \]
The solution consists of an optimal committee and a witnessing load density.
Theorem 5, proved here using the cited characterization of Sainte-Laguë, states that the apportionment method induced by the variance-minimizing Phragmén rule coincides with Sainte-Laguë. In the party-list case, if party \(i\) receives \(x_i\) seats, the optimal load is uniform within its mass and the objective becomes
\[ \sum_i\frac{x_i^2}{\mu_i}. \]
This is the normalized form of the paper’s expression \(\sum_i x_i^2/v_i\), and its minimizers are precisely the Sainte-Laguë allocations, using priority scores \(\mu_i/(2x_i+1)\).
Again, the party-list restriction is Class A, while the unrestricted problem likely retains candidate-driven hardness through the integral committee choice. The load variables are fractional because the paper’s own Phragmén model already uses fractional loads; the population continuization merely replaces individual voters by load densities over repeated types.
These mirrors generate natural follow-up questions: minimum \(L_1\)-mass transfer needed to change the winning committee; robustness of D’Hondt, Hamilton, and Sainte-Laguë outcomes under population perturbations; approximation and parameterized complexity in the number of approval types; and whether hardness remains when every type has large multiplicity. Those are computational questions about distributions over voter types, not merely restatements of the paper’s axiomatic discussion.
The weakest point is decisive: the paper does not supply a qualifying named computational result. Statements that sequential rules are tractable and non-sequential rules are often NP-hard occur in prose or citations, not as numbered theorems proved here. Therefore the positive case is substantively credible—especially for Continuous Monroe Committee—but formally weaker than the ChoCo programme’s ideal anchors. If structural correspondence theorems are admissible anchors, this is a good Class A/B mirror. If only explicit complexity theorems count, the honest verdict is that the paper has a natural continuous analogue but no compliant computational anchor.
The negative case has a strong formal core, but not a fully convincing universal one.
The decisive point is that this paper contains no named computational result of the required kind. Theorems 1, 4, and 5 establish structural correspondences with D’Hondt, Hamilton, and Sainte-Laguë; they do not classify the complexity of winner determination, approximation, or parameterized computation. The remarks that sequential rules are “easy” and Thiele rules are “often NP-hard” are neither numbered results nor results proved in this paper. Thus none of the proponent’s three anchors is a compliant computational anchor for ChoCo.
The Monroe proposal is the strongest substantive mirror, but it is not actually anchored in Theorem 4’s computational content, because Theorem 4 has none. On the paper’s party-list construction, the proposed continuous problem reduces to maximizing \( \sum_i \min(\mu_i,x_i/k) \), hence to Hamilton’s largest-remainder calculation. That is a natural population-scale formulation, but it is precisely an apportionment identity, not a complexity question established by the paper.
The proponent’s stronger unrestricted version—continuous Monroe winner determination over arbitrary approval types—is well-defined. The mass assignment is a legitimate nonatomic analogue of balanced Monroe assignments: a type’s mass may be partitioned among candidates, while each selected candidate receives mass \(1/k\). I therefore cannot honestly object that it is an invalid limit or that multiplicity is implausible. The paper itself explicitly constructs large blocks of identical voters.
The objection is instead that this unrestricted problem is a new problem, not a continuization of a computational result in this paper. Conditional on an integral committee, the assignment part is a transportation or flow problem; the remaining combinatorics lies in selecting candidates. That may be worth studying, but the paper supplies no reason to regard it as a specifically ChoCo mirror rather than a generic continuous version of any assignment-based multiwinner rule.
The same problem is sharper for Theorem 1. The continuous weighted-Thiele objective, \( \sum_t \mu_t\sum_{j=1}^{|A_t\cap S|}w_j \), is simply the ordinary Thiele objective with repeated voters aggregated and their multiplicities normalized. On the party-list domain, Theorem 1 already says that the rule induces a divisor method; replacing integer vote counts by proportions adds no computational statement. Extending to arbitrary approval types could generate an interesting weighted winner-determination problem, but then the paper’s theorem is only motivation, not an anchor. The construction would apply almost verbatim to every additive voter-scoring rule.
Theorem 5 is weaker still as a continuous-population motivation. Phragmén’s rule already has fractional load variables for a finite electorate. When voters with the same approval set are aggregated, both feasibility and the quadratic objective factor through their total mass. For rational masses, multiplying by a common denominator recovers the corresponding finite weighted instance exactly. The population continuum therefore contributes no distinctive modelling issue here; it is mainly a compressed representation of duplicated rows in an existing convex optimization problem. This is not a formal collision—the population is still the continuized object—but it makes the proposed mirror especially generic and unmoored from the paper’s contribution.
Accordingly, the best negative verdict is: no compliant computational anchor exists, and all three proposed mirrors either restrict to the paper’s apportionment identities or extend them into new, generic weighted optimization problems. That is a serious reason not to prioritize this paper in a programme specifically about computational consequences of continuizing populations.
But the universal claim is not honestly airtight. Continuous Monroe over approval types is a sensible high-multiplicity model, and the paper supplies a convincing repeated-type regime. If ChoCo accepts computational questions motivated by structural theorems rather than explicitly stated complexity results, the negative case probably loses on Monroe.
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.