| paper | d4-conf-ecai-2020-0022 |
| 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: Computing an exact maximizing committee is NP-hard; deciding whether \(\operatorname{OPT}=1\) is NP-complete. Both problems admit \(2^m\operatorname{poly}(m,\tau,L)\) and \(2^{O(8^\tau)}\operatorname{poly}(m,\tau,L)\) algorithms. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), a finite support \(\mathcal A\subseteq 2^C\) of approval types, and positive binary-rational masses \(\mu_A\) summing to \(1\), find a nonempty committee \(S\subseteq C\) maximizing \(\sum_{A\in\mathcal A}\mu_A\mathbf 1[|A\cap S|\ge\lceil |S|/2\rceil]\). Classify the exact problem in terms of \(|C|\), \(|\mathcal A|\), and the mass encoding length; in particular, determine the complexity of deciding whether the optimum is \(1\).
A society is a finite distribution over approval types \(A\subseteq C\), each with mass \(\mu_A\). The decision variable is a nonempty committee \(S\subseteq C\); its objective is the population share whose type approves at least half its members.
The mirror covers Theorem 3’s majority-threshold hardness and Theorem 1’s minimum representing committee membership result. It leaves the other rules, their complexity results, and the committee-size simulations aside.
The strongest continuous-population fit is a weighted version of the paper’s \(t_{\mathrm{maj}}\)-Threshold rule. Take candidates \(C\) and a finite support of approval types \(\mathcal A\subseteq 2^C\), with positive binary-rational masses \(\mu_A\) summing to \(1\). Type \(A\) approves exactly the candidates in \(A\). For a nonempty committee \(S\), define
\[
\operatorname{sat}_A(S)=\mathbf 1\!\left[|A\cap S|\ge \left\lceil |S|/2\right\rceil\right],
\qquad
F_\mu(S)=\sum_{A\in\mathcal A}\mu_A\operatorname{sat}_A(S).
\]
Mass-\(t_{\mathrm{maj}}\) Winner Selection asks for a committee maximizing \(F_\mu(S)\), returning any tied maximizer. This preserves the paper’s rule and its variable-size committee decision; it changes the count of satisfied voters into their share of the population.
A plausible regime is a large public consultation choosing a small panel of potential delegates. Residents approve the delegates they believe can represent their concerns; standardized survey profiles or recurring stakeholder groups create many repeated ballots. For example, \(N\) could be in the hundreds of thousands while the observed support has \(\tau\) in the hundreds. Each type is complete for the rule: residents with the same approval set are indistinguishable to it. The paper itself motivates variable-size and representative committees, including citizen focus groups, so this is a scenario its authors could recognize. Repeating each type’s residents by a common factor leaves \(\mu\) unchanged and makes \(N/\tau\) arbitrarily large.
The lead anchor is Theorem 3, proved in this paper by reduction from SET COVER. It states that deciding whether there is a nonempty committee satisfying every voter under the \(t_{\mathrm{maj}}\)-Threshold rule is NP-hard; a voter satisfies a committee when at least half its members are approved. In the continuous problem, ask whether \(\max_{S\ne\varnothing}F_\mu(S)=1\). This is exactly the all-voters-satisfied question: with finitely many positive-mass types, satisfaction mass is \(1\) precisely when every supported type is satisfied. A discrete instance maps to \(\mu_A\) equal to the fraction of its voters with ballot \(A\), so the paper’s hardness transfers. The expected classification is Class B: the reduction’s combinatorics lie in choosing candidates to cover elements, not in the population count. This is my strongest anchor because the mass-weighted objective mirrors the rule’s full winner-selection problem, while Theorem 3 supplies a clear hard decision question inside it.
A second, independently credible mirror is Continuous Minimal Representing Committee. On the same input, ignore empty approval types and find a smallest \(S\subseteq C\) such that \(S\cap A\ne\varnothing\) for every supported nonempty type \(A\). Given a candidate \(c^\star\), the decision version asks whether \(c^\star\) belongs to at least one such minimum-size committee; a yes certificate is such a committee. This matches the paper’s MRC rule: in a finite-support society, representing almost every resident is equivalent to covering every positive-mass type.
Its anchor is Theorem 1, proved here: deciding whether a given candidate belongs to some MRC winning committee is complete for \(\Theta_2^p\). The paper proves hardness by reducing from Vertex Cover Member, whose hardness it cites from elsewhere, and proves containment by binary-searching the minimum committee size and using an NP oracle to test membership at that size. The same membership question on the continuous input has the same complexity: masses matter only through whether a type has positive mass, and the discrete reduction maps to positive rational masses. This is also Class B. It is a particularly natural mirror for the paper’s goal of representing a spectrum of opinions, though its masses play less of a role than in the lead problem.
These questions also suggest studying whether optimizing satisfied mass remains hard when only a small number of ballot types occur, how robust the selected committee is to changes in \(\mu\), and what happens when a small fraction of the population may remain unrepresented. For MRC, an especially direct extension is a partial-cover version that permits up to an \(\varepsilon\) fraction of residents to lack an approved representative.
The main weakness is that the hardness anchors do not show a tractability gain from continuization. In the all-satisfied threshold question, masses distinguish the wider model but do not affect the yes/no condition; in MRC, only positive support matters. The reductions also need growing candidate/type sets, so they do not settle the usefulness of algorithms in regimes with moderate \(\tau\). The case is narrower than that: these are bona fide continuous-population versions of two computational questions the paper studies, and their hardness identifies a meaningful boundary where the agenda’s combinatorics survive. The mirror covers Theorem 3 and Theorem 1, not the paper’s other rules, simulations, or all its complexity results.
The strongest case against is that both named hardness anchors land at the point where the population’s *masses* stop mattering. For \(t_{\mathrm{maj}}\), asking whether the maximum satisfied mass is \(1\) is equivalent, on finite positive support, to asking whether every supported ballot type is satisfied. The reduction therefore carries over, but the continuous part contributes no new structure: the question depends only on which types occur. MRC has the same feature. Its minimum committee depends on the support, not the masses, so an arbitrarily small positive type can constrain the answer as much as a type containing nearly everyone. That makes exact MRC brittle under vanishingly small population changes.
Those are real weaknesses in the two *exact* mirrors, but they do not defeat the best versions. Maximizing satisfied mass under \(t_{\mathrm{maj}}\) is the natural weighted version of the paper’s winner-selection rule, and its answer can depend on the masses. It remains a discrete optimization over committees, but the programme’s criterion is that the society be continuous; it does not require continuous outcomes or an LP formulation. MRC’s brittleness could motivate an \(\varepsilon\)-coverage version, which makes the masses matter. That changes the exact MRC question, but it is a plausible population-level variant the authors might recognize.
Nor does the scenario fail for lack of multiplicity. A large consultation with repeated approval profiles is plausible, and the paper itself discusses representative committees for citizen consultations. Approval sets are complete types for the rules at issue. Calling the resulting questions support-based or combinatorial is not enough to rule them out: the continuous-population programme explicitly allows hardness to transfer and treats that boundary as worth charting.
So the negative case can show that the MRC anchor, and the all-satisfied endpoint of the threshold anchor, use the continuum weakly. It cannot honestly rule out a worthwhile mirror in every scenario. The weighted threshold version survives, and the paper’s consultation setting makes its population model credible.
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.