| paper | d4-conf-aaai-2026-1451 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(\operatorname{poly}(m,\tau,L,k)\); consequently fixed-parameter tractable in \(\rho_C+\rho_V\), with \(f(p)=1\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given candidates \(C\), a committee size \(k\), and \(\tau\) approval types \(A_t\subseteq C\) with positive binary-rational masses \(\mu_t\) summing to \(1\), suppose the types have an order in which each candidate is approved by consecutive types. For a fixed Thiele sequence \(w\), can an optimal size-\(k\) committee maximizing \(S_\mu(W)=\sum_t\mu_t\sum_{i=1}^{|A_t\cap W|}w_i\) be computed in time \(f(\rho_C+\rho_V)\operatorname{poly}(m,\tau,L)\), where \(\rho_C=\max_c|\{t:c\in A_t\}|\), \(\rho_V=\max_t|A_t|\), and \(L\) is the total mass bit length?
The society is a distribution \(\mu\) over complete approval-ballot types \(A_t\), with a voter-interval order on its support. The decision variable is a discrete committee \(W\subseteq C\) of size \(k\); its objective is the mass-weighted Thiele score \(S_\mu(W)\). The structural parameters are the maximum number of types approving a candidate, \(\rho_C\), and the maximum number of candidates approved by a type, \(\rho_V\).
The mirror covers Theorem 7's voter-interval result and the weighted type analogue of Theorem 10; it does not address general unstructured weighted winner determination or the score-parameterized algorithm.
The paper has no numbered result asserting hardness, so there is no eligible named hardness anchor to lead with. Its general-instance hardness claims are cited background. The strongest named anchor is therefore the paper’s structured-domain algorithm.
The mirror I believe in is weighted winner determination for a continuous approval electorate. A type \(t\) is a complete approval ballot \(A_t\subseteq C\); all agents share the same fixed Thiele rule. The society is a list of \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\). For a size-\(k\) committee \(W\), its per-capita score is
\[
S_\mu(W)=\sum_{t}\mu_t\sum_{i=1}^{|A_t\cap W|}w_i.
\]
The decision is to output a size-\(k\) committee maximizing this score. The input records \(C,k\), the ballots, and the binary encodings of their masses; running time should be measured in \(m=|C|\), \(\tau\), and the mass bit length \(L\). The committee remains discrete: it is the population whose description is continuous.
This has a plausible large-population regime. Imagine millions of residents, or a population limit, whose approval ballots fall into a modest number of exact types. The masses are the fractions holding those ballots. For the voter-interval case, place the types along an age or income axis and require each candidate’s approving types to form an interval. The paper itself motivates VI with demographic groups and candidates appealing to specific groups. The population is large relative to \(\tau\), while the committee size and candidate set remain finite.
Lead — Continuous-VI Thiele Winner Determination. Theorem 7, proved in this paper, says that Generalized Thiele winner determination on VI profiles is FPT parameterized by \(\Delta_C+\Delta_V\), and XP parameterized by \(\Delta_C\), where \(\Delta_C\) is the maximum number of voters approving a candidate and \(\Delta_V\) is the maximum number of candidates approved by a voter. The text immediately before the theorem also notes that the unstructured problem is NP-hard even with \(\Delta_C=3\) and \(\Delta_V=2\); that hardness is cited from prior work [AGG+15, SFL16], not proved as Theorem 7.
The continuous question is: given the rational-mass society above and a type order in which every candidate’s approving types are consecutive, can an optimal committee be computed in FPT time in
\[
\rho_C+\rho_V,
\qquad
\rho_C=\max_c|\{t:c\in A_t\}|,\quad
\rho_V=\max_t|A_t|?
\]
A solution is a maximizing committee and its exact score. This is a deliberate type-level analogue of the theorem’s parameters: \(\rho_C\) counts distinct complete voter types, rather than the number of people whose mass has that ballot. I expect this to be tractable, in Class A. The dynamic program in the proof works with approval patterns and local neighborhoods; repeated identical voters can be represented by one type with a rational score weight. The type-level version is therefore a natural extension of the stated theorem, not a claim that Theorem 7 already proves this exact weighted-input bound. Further questions include whether the type-level bound can be removed for PAV, and whether the discrete polynomial-time VI algorithms mentioned in the paper’s conclusion extend to rational masses.
Second anchor — Type-2-Support Thiele Winner Determination. Theorem 10, proved in the paper, says that Generalized Thiele winner determination is polynomial-time solvable when every candidate is approved by at most two voters. Its proof modifies the ILP so its constraint matrix is a generalized matching matrix, invoking Theorem 9’s algorithmic result.
The continuous mirror asks: given a rational-mass type society with no VI requirement, is winner determination polynomial-time solvable when each candidate is approved by at most two distinct types? The output is again an optimal size-\(k\) committee. I expect Class A. In the paper’s matching-ILP view, use one row per type and weight that row’s score contribution by \(\mu_t\). After adding a dummy type for candidates supported by only one type, each candidate variable appears in two type constraints; each satisfaction variable appears in its type constraint and the total-score-count constraint. The constraint matrix retains the matching structure, while rational masses affect the objective coefficients. This is a credible direct extension of the proof, though the theorem itself bounds individual supporters, not types. Follow-up questions are whether the type-support bound can be raised to three, and how this weighted formulation behaves without any support bound.
These mirrors cover winner determination on VI profiles and the paper’s low-support polynomial case. They do not try to continuize the committee, voting outcomes, or axioms. The authors should recognize the underlying problem: for each committee, the objective is exactly the aggregate of voters’ Thiele satisfaction, expressed as a mass-weighted sum. The paper’s cited hardness also remains relevant outside these structured cases: any discrete election embeds by assigning each ballot type its multiplicity divided by the number of voters, which preserves the winning committees.
My weakest point is that this is a high-multiplicity representation of an additive objective, not a new feasible action for voters. Clearing denominators turns rational masses into integer multiplicities, so the unrestricted problem may be a compressed encoding of familiar weighted elections. Also, both numbered anchors count voters, while my strongest continuous formulations count types; those are not the same parameter. The case survives because identical agents are exactly what high multiplicity is meant to aggregate, and the proposed mirrors retain the paper’s approval ballots, committee choice, and Thiele objective while asking whether its structural algorithms operate on the compressed society.
I can’t honestly make the universal negative case the prompt asks for: Theorem 7 and Theorem 10 are named computational results, and at least one strong population mirror survives.
The best argument against is that the paper’s objective already discards voter identity. For every committee \(W\), it depends on the electorate only through the ballot masses:
\[
S_\mu(W)=\sum_t \mu_t\sum_{i=1}^{|A_t\cap W|}w_i.
\]
A continuous version therefore makes the input a rationally weighted approval profile, while leaving the committee and its optimization unchanged. That weakens any claim that the mirror introduces new social-choice semantics. Under ChoCo’s stated high-multiplicity scope, though, compressed weighted input is itself a legitimate computational question, so this point does not defeat the mirror.
Theorem 7 is the harder anchor to attack. Its algorithm uses \(\Delta_C\), the number of individual voters supporting a candidate, to bound the length of active neighborhoods on the voter axis. In a normalized population, support *mass* does not preserve that parameter. Counting supporting types instead gives the proposed \(\rho_C\), but that asks about the width of a weighted type profile, not the paper’s original population-count parameter. Still, weighted VI winner determination with rational masses is well-posed, and the paper’s demographic motivation supplies a plausible setting. I don’t see a fundamental reason to reject that better formulation.
Theorem 10 gives a stronger objection to its *direct* mirror. “At most two voters support each candidate” has no stable population-scale analogue: if total mass is normalized, a fixed bound of two people tends to zero as the population grows. Replacing voters with at most two supporting types avoids that collapse, but changes the condition to a restriction on ballot diversity. That is a different question. It could still be a sensible one, so the mismatch weakens this anchor without disposing of every possible mirror.
Thus the negative case is that the paper’s results concern finite committee optimization, and their continuous versions mainly change how an additive objective’s voter data is encoded. Theorem 10’s faithful low-support condition degenerates, while the type-based replacements for both anchors shift the parameter being studied. But those points do not establish that no worthwhile scenario exists. The weighted VI version of Theorem 7 remains the strongest surviving mirror, so an honest case against it is weak.
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.