| paper | d4-conf-atal-2021-0057 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete when \(k\) is part of the input, already for \(d=1\) and \(k\ge 3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Lemma 5.10
statement extracted from the paper’s text layer
Given candidates \(C\) with attribute values \(c[j]\in D_j\), committee size \(k\), dimensions \(j\in[1,d]\), and \(\tau\) complete voter types \(t=(A_t^1,\ldots,A_t^d)\) with positive rational masses \(\mu_t\) summing to \(1\), define \(U_W=\{t:\forall c\in W,\forall j,\ c[j]\notin A_t^j\}\). For each candidate-realizable value \(a\in D_j^C=\{c[j]:c\in C\}\), require \(\sum_{t\in U_W:\,a\in A_t^j}\mu_t<1/k\). Given a rational threshold \(q\), decide whether there is a committee \(W\subseteq C\), \(|W|=k\), satisfying these SJR constraints and \(\mathrm{AV}_\mu(W)=\frac{1}{d}\sum_t\mu_t\sum_{c\in W}\sum_{j=1}^d\mathbf{1}[c[j]\in A_t^j]\ge q\).
A society is a rational distribution over complete approval-vector types. The candidates remain named and indivisible; the decision is an integral size-\(k\) committee, scored by population-weighted AV and constrained by the mass version of SJR.
The mirror covers Lemma 5.10’s NP-completeness result for justified committees with highest AV. It leaves the paper’s other results, including the approximation scheme, JAV, and the CJR complexity results, unmirrored.
My strongest case is a direct, narrow Class B mirror of the paper’s AV optimization result.
The anchor is Lemma 5.10, proved in the paper. It states that selecting a justified committee with highest Approval Voting score is NP-complete for \(k\ge2,d\ge2\), and also for \(k\ge3,d=1\). Its decision version asks whether there is a size-\(k\) committee whose approval count reaches a given threshold while satisfying the justification condition: for every attribute-value outside the committee, fewer than \(n/k\) of its approving voters remain outside the committee’s represented voters. The paper gives the reduction from Set Cover for the multidimensional case and says the one-dimensional \(k\ge3\) case was also established independently at the same time in reference [10].
A plausible regime is a large professional association choosing a \(k\)-person board from a fixed slate. Each member approves desired values for dimensions such as region, expertise, and experience band. A voter type is the member’s complete vector of approval sets across those dimensions; \(\mu_t\) is the fraction of members with that vector. For example, an association with hundreds of thousands of members and hundreds or a few thousand recurring ballot types has \(N\gg\tau\). This is credible when members use a structured ballot and many submit the same approval pattern. The committee candidates remain named, indivisible people; only the electorate is continuized.
Here is the continuous problem I would hand to a prover, named Continuous Justified-AV Committee Selection. The input is a candidate set \(C\), attribute domains \(D_1,\ldots,D_d\), each candidate’s value \(c[j]\in D_j\), a target size \(k\), and a list of \(\tau\) voter types \(t=(A_t^1,\ldots,A_t^d)\) with positive rational masses \(\mu_t\) summing to \(1\). For \(W\subseteq C\), \(|W|=k\), define its paper-matched AV score by
\[
\mathrm{AV}_\mu(W)=\frac{1}{d}\sum_t\mu_t\sum_{c\in W}\sum_{j=1}^d \mathbf{1}[c[j]\in A_t^j].
\]
The question is to find a size-\(k\) committee maximizing this score subject to simple justified representation. To state that constraint without quantifying over arbitrary voter coalitions, let \(U_W\) be the types that approve no attribute-value appearing in any candidate in \(W\). For every dimension \(j\) and value \(a\in D_j\), require
\[
\sum_{t\in U_W:\,a\in A_t^j}\mu_t < \frac{1}{k}.
\]
Equivalently, no unrepresented population of mass at least \(1/k\) shares approval of an attribute-value. For a decision version, add a rational threshold \(q\) and ask whether a feasible \(W\) has \(\mathrm{AV}_\mu(W)\ge q\). The solution is the committee \(W\), or a report that no feasible committee exists.
This preserves the paper’s question: choose actual candidates to maximize their attribute-approval score while enforcing its SJR guarantee. The coalition threshold \(n/k\) becomes mass \(1/k\), and the objective becomes the mass-weighted AV score. An explicit election maps to this input by assigning each ballot type its voter count divided by \(n\); that transformation preserves the score up to normalization and preserves SJR exactly. Thus the paper’s hardness transfers to the continuous decision problem in the same parameter regimes. Verification is polynomial in the listed support and the rational bit lengths. I expect hardness transfers (Class B): the Set Cover structure lies in selecting candidates and their attributes, not in distinguishing individual voters.
This mirror covers Lemma 5.10 only. It does not claim a new algorithm or an LP-based tractability gain. It raises follow-up questions about FPT algorithms in \(k\) or \(\tau\), and about the complexity under restricted ballot supports.
The weakest point is also clear: population mass is a weight in the objective and SJR constraints, while the decision remains an integral committee choice. Continuization does not create a mass-transfer variable or an obvious pricing problem. Also, the lemma establishes hardness for the general input family, not for every regime with small \(\tau\); whether hardness persists when the number of ballot types is tightly bounded remains open. So this is a defensible high-multiplicity mirror and a useful hardness boundary, but its continuum-specific algorithmic payoff is modest.
The best argument against this mirror is about payoff, not validity. Even in a large association, the continuous version keeps the same integral choice among named candidates. Population mass only supplies weights for AV and the SJR constraint. There is no mass-transfer variable or evident pricing problem for continuous-optimization tools to exploit. The result may therefore amount to a weighted reformulation of the same candidate-selection problem, with the Set Cover hardness intact.
That objection does not defeat Lemma 5.10 under ChoCo’s scope. Its continuous mirror is well-defined: make a voter type the complete vector of attribute approvals, assign each type rational mass, and keep the committee integral. For a fixed committee \(W\), SJR is equivalent to requiring that, for every attribute value \(a\), the unrepresented mass approving \(a\) is less than \(1/k\). A discrete electorate maps directly to such a society by assigning each ballot type its fraction of the voters. Thus the proposed mirror preserves the paper’s question and its hardness.
Nor does the large-population scenario collapse under closer inspection. A large association voting on a fixed slate using structured attribute ballots could plausibly have many members per recurring type. The voters’ identities are not needed by the SJR or AV objective; the candidates’ identities remain in the outcome, as the model requires. And hardness surviving the population relaxation is a legitimate Class B result, not evidence that the question is out of scope.
So the negative case can reasonably say that this is a modest mirror with little prospect of a tractability gain. It cannot honestly say that no worthwhile mirror survives. Whether the result becomes more valuable through questions about support size \(\tau\), or algorithms for restricted type distributions, remains open; the paper and the proposed mirror do not settle that.
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.