| paper | The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections |
| authors | L. Sánchez-Fernández, Norberto Fernández, Jesús Arias-Fisteus, Markus Brill |
| venue | AAAI 2021 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6.1
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), committee size \(k\), finite approval-type set \(T\), and rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), choose an integral committee \(W\subseteq C\) with \(\lvert W\rvert=k\) maximizing \(M_\mu(W)=\max_f\min_{c\in W}\sum_{t:c\in t}\mu_t f_{t,c}\), where \(f_{t,c}\ge0\), \(f_{t,c}=0\) when \(c\notin t\), and \(\sum_{c\in t\cap W}f_{t,c}=1\) for every positive-mass type intersecting \(W\).
A high-multiplicity approval election: complete approval sets are voter types \(t\), \(\mu_t\) is their population mass, \(W\) remains an integral committee, and \(f\) is only an auxiliary type-level support allocation; the objective is maximum minimum support, equivalently minimum maximum load per unit mass.
Hardness in the genuinely compressed regime with small \(\tau\) is not established, and the paper's NP-hardness consequence is imported rather than proved there.
fatal: False
The mirror covers global maximin-support optimization and sequential MMS computation, with the normalization also carrying over approximation guarantees such as Proposition 6.1. It leaves the paper's axiomatic results, counterexamples, characterizations, and rule comparisons unmirrored.
The strongest honest positive case is narrow but real: this paper gives an exact high-multiplicity model of approval-based committee selection, with one lead hardness mirror and one clean tractable mirror.
Let \(C\) be the candidates and \(k\) the committee size. A voter type is an approval set \(t\subseteq C\), with no other voter-specific data because the paper’s problem uses nothing else. A continuous society is a rational distribution \(\mu=(\mu_t)_{t\in T}\) over the explicitly represented approval types, where \(\sum_t\mu_t=1\). The intended regime is a large electorate—say millions of voters—with perhaps tens or hundreds of recurring approval types generated by stable policy blocs, regions, organizations, or issue profiles. Thus \(n\gg\tau\), while the committee and candidates remain indivisible and finite.
For a committee \(W\), let \(f_{t,c}\) be the fraction of type \(t\)’s approval vote assigned to \(c\). For every type approving at least one member of \(W\),
\[ \sum_{c\in t\cap W} f_{t,c}=1, \qquad f_{t,c}=0\text{ if }c\notin t, \]
and define the support of \(c\) by
\[ \operatorname{supp}_{\mu,f}(c) = \sum_{t:c\in t}\mu_t f_{t,c}. \]
The continuous maximin support of \(W\) is
\[ M_\mu(W) = \max_f\min_{c\in W}\operatorname{supp}_{\mu,f}(c). \]
The fractional \(f\) is only an auxiliary support-allocation variable; \(W\) itself remains an integral \(k\)-committee. This is population continuization, not outcome-space continuization.
The finite-to-continuous bridge is exact. If a finite profile has \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\). Averaging any finite voter-level assignment within each type gives a type-level assignment with the same normalized candidate supports, and conversely a type-level assignment can be given identically to all voters of that type. Hence
\[ M_\mu(W)=\frac{1}{n}\operatorname{maximin}(A,W). \]
So this is not merely an analogy or a fractional weakening of the paper’s objective.
My lead mirror is the following.
Continuous Global Maximin-Support Committee, equivalently Max-Phragmén\(_\infty\). Given \(C\), \(k\), an explicit finite set of approval types \(T\), and rational masses \(\mu\), output a committee \(W\subseteq C\) with \(|W|=k\) maximizing \(M_\mu(W)\), together with an optimal support assignment \(f\). Equivalently, in the paper’s load language, distribute one unit of load for every elected candidate across the approving population mass and minimize the maximum total load of a type.
This is a direct mirror of the paper’s global maximin-support problem, not a simplified approval-score problem. It preserves the difficult choice of \(W\), the committee size, overlapping approval sets, and the global redistribution of support across elected candidates.
The anchor is Theorem 6.1. The paper proves that, for every finite election \(E\),
\[ \operatorname{max\text{-}Phragm\acute{e}n}(E) = \arg\max_{W\subseteq C,\ |W|=k} \operatorname{maximin}(A,W). \]
Thus max-Phragmén’s globally optimal committees are exactly the committees maximizing minimum support. The equality is proved in this paper using Lemma 6.1’s correspondence between load distributions and vote assignments. The paper then states that computing max-Phragmén winners is NP-hard, citing Brill et al. [7], and concludes that finding a committee maximizing minimum support is NP-hard as well. The hardness itself is therefore imported rather than newly proved here, but it is explicitly attached to the numbered theorem’s result.
For the continuous problem with unrestricted \(m\) and \(\tau\) as part of the input, I expect hardness to transfer: any finite election maps to rational masses \(\mu_t=n_t/n\), and the objective changes only by the factor \(1/n\). The combinatorics live in selecting \(k\) candidates, not in naming voters. This is therefore a likely Class B mirror. The more interesting high-multiplicity question is whether hardness survives when \(\tau\ll n\), or perhaps when \(\tau\) is fixed or parameterized. The paper does not establish that stronger statement, but it makes it precise: one can ask whether the candidate-side optimization remains hard after all repeated approval cohorts have been compressed.
The main follow-up questions are whether Global Maximin-Support is fixed-parameter tractable in \(\tau\) or \(k\), whether approval-pattern compression yields a polynomial algorithm for fixed \(\tau\), and what approximation guarantees are possible when exact optimization remains hard.
My second mirror uses the paper’s sequential rule.
Continuous MMS\(_\infty\) Selection. Given the same \((C,k,T,\mu)\) and a fixed candidate priority order, start with \(W_0=\varnothing\). At round \(j+1\), for every \(c\notin W_j\), compute
\[ q_\mu(W_j,c)=M_\mu(W_j\cup\{c\}), \]
and add a candidate maximizing this value, breaking ties by the priority order. Output \(W_k\), together with the optimal support assignment computed at each round.
This is exactly the population version of the paper’s Maximin Support Method, not a newly invented greedy rule. The anchor is Theorem 4.2, which states that “the maximin support method can be computed in polynomial time.” That theorem is proved in the paper by solving a linear program for every candidate considered at every iteration.
After type aggregation, the LP for a candidate set \(D\) is
\[ \begin{array}{ll} \text{maximize} & s\\[2mm] \text{subject to} & \displaystyle\sum_{t:c\in t}\mu_t f_{t,c}\ge s \quad\text{for every }c\in D,\\[3mm] & \displaystyle\sum_{c\in t\cap D}f_{t,c}=1 \quad\text{for every positive-mass type }t\text{ with }t\cap D\neq\varnothing,\\[3mm] & f_{t,c}\ge 0. \end{array} \]
It has \(O(\tau m)\) variables and polynomially many constraints. At most \(km\) such LPs are needed, so the continuous MMS problem is solvable in time polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\). I therefore expect this mirror to be Class A.
This tractable mirror is weaker as a programme anchor because the original finite rule is already polynomial-time computable. Its value is that it demonstrates the exact high-multiplicity compression: the computation depends on the number of distinct approval types rather than on the number of named voters. It also generates useful questions about faster type-sensitive implementations, exact dependence on \(\tau\), rounding finite populations, and approximation of the globally optimal maximin-support committee by MMS.
The paper’s fractional vote assignments and load distributions do not create a novelty collision. They fractionalize support allocation while retaining a finite, individually listed electorate. My mirror instead makes the electorate itself the continuous object \(\mu\); the committee remains integral. The type-level averaging is a necessary co-modification forced by high multiplicity, and it preserves the paper’s underlying objective exactly.
The weakest point is the hardness claim in the genuinely compressed regime. The paper’s cited NP-hardness immediately embeds into the unrestricted rational-mass problem, but it does not show that NP-hardness remains when only a small number of approval types have positive mass. The cited reduction might use many distinct approval patterns. I would therefore not claim that this paper has already proved a continuum-specific complexity classification. The defensible positive claim is more modest: Theorem 6.1 supplies a legitimate hardness anchor whose hard core plausibly survives population aggregation, while Theorem 4.2 supplies an unquestionably proved polynomial anchor for the sequential counterpart. Together they make approval-based multiwinner selection a credible continuous-population mirror, even though the decisive \(\tau\ll n\) boundary remains open.
The strongest negative case is that this paper is a poor source for a continuous-computation programme, even though its model admits a formally correct population-distribution reformulation.
Theorem 6.1 is not, strictly speaking, a computational-complexity result proved by the paper. It establishes an equivalence between max-Phragmén and global maximin support. The NP-hardness statement immediately afterwards is imported from Brill et al. [7], rather than established here. Thus the proposed lead anchor is already weaker than it appears: the paper contributes a structural identity, not a new continuous-versus-discrete complexity phenomenon.
Its continuous version would nevertheless be well-defined. Approval sets are legitimate voter types, and normalizing multiplicities gives masses \(\mu_t\). But the resulting global problem is an exact rescaling of the finite one:
\[ M_\mu(W)=\frac{1}{n}\operatorname{maximin}(A,W). \]
Nothing in the global optimization changes. The committee remains an integral subset of candidates; the hard choice is still which candidates to select; and the population enters only through linear coefficients in the support-allocation LP. This is not an objection that hardness survives—Class B results are valuable in the ChoCo programme—but it means that the mirror supplies no new population-side structure. It is a high-multiplicity encoding of the same candidate-selection problem.
The proposed refinement, asking whether hardness survives for small \(\tau\), is more interesting, but it is a new parameterized research programme rather than a consequence of Theorem 6.1. Indeed, for fixed \(\tau\), every candidate is characterized by its approval signature
\[ S_c=\{t\in T:c\in t\}\subseteq T. \]
There are at most \(2^\tau\) such signatures, and candidates with the same signature are interchangeable in the maximin LP. One can enumerate the numbers of selected candidates of each signature and solve the corresponding LPs. This gives an \(m^{O(2^\tau)}\)-type algorithm for fixed \(\tau\). That may be worthwhile, but its value comes from a new analysis of the compressed candidate space, not from continuizing the theorem proved in this paper. If one instead uses a richer succinct distribution or adds mass-transfer interventions, one has changed the input model or introduced bribery/control; those are plausible ChoCo problems, but they are no longer mirrors of the paper’s result.
Theorem 4.2 is a genuine named computational result, so the negative case cannot rely on the paper having no algorithmic content. The best objection is that its continuous mirror is almost entirely mechanical. The paper already solves the relevant optimization by an LP with variables \(f(i,c)\in[0,1]\). If voters \(i\) and \(i'\) have the same approval set, their variables can be averaged. Conversely, a type-level solution can be assigned identically to every voter of that type. Therefore replacing the finite profile by masses merely replaces repeated rows by weighted rows:
\[ \sum_{i:c\in A_i} f(i,c) \quad\longrightarrow\quad \sum_{t:c\in t}\mu_t f_{t,c}. \]
The polynomial algorithm in Theorem 4.2 then survives immediately. The continuum has not created a new optimization object, a new feasibility issue, a new separation problem, or a new source of tractability. It has compressed an already polynomial finite LP.
That compression is not illegitimate. A large electorate with a small number of recurring approval ballots is a sensible high-multiplicity regime, and the finite-to-continuous correspondence is exact. But the paper itself is anonymous and additive: voter identity is irrelevant, and all information used by the algorithm is already captured by approval multiplicities. Thus the proposed MMS\(_\infty\) problem is best described as a normalized, compressed implementation of Theorem 4.2, not as a substantive continuous-population extension. The fact that the paper’s auxiliary support variables are already fractional makes the population continuization especially close to a change of notation.
The proponent’s stronger repairs do not remove this problem. Keeping committees integral is correct, but it leaves only coefficient aggregation. Making committee membership or seats fractional would produce a more interesting LP, but that would continuize the outcome rather than the population and would violate the programme’s scope. Adding campaign, turnout, or approval-mass transfer would generate worthwhile computational questions, but those would be new intervention problems absent from the paper. Using type-dependent prices or budgets would likewise create a new model rather than reveal content latent in MMS.
The negative case therefore has real force as a source-selection argument: Theorem 6.1 is structurally rather than computationally contributed, while Theorem 4.2 yields an exact cohort compression whose algorithm follows by linearity. There is no identity obstruction, no implausible high-multiplicity regime, and no degeneracy of the continuous population. Approval cohorts are perfectly sensible here. Consequently I cannot honestly defend the requested universal claim that no worthwhile mirror exists in any scenario. The global mirror is mathematically legitimate, and the small-\(\tau\) boundary may support a useful new study. The strongest defensible verdict is narrower: this particular paper offers a weak and mostly tautological continuous anchor, not a compelling continuization programme on its own.
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.