| paper | d4-conf-aaai-2018-0528 |
| 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}\text{-hard}\), even with \(\tau=1\), singleton classes, and explicit four-entry monotone tables. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given alternatives \(A\) partitioned into classes \(C_1,\ldots,C_z\), committee size \(k\), and a finite support of complete rankings \(t\) with binary-rational masses \(\mu_t\geq 0\) summing to \(1\), define each alternative's SNTV support share as \(p_\mu(a)=\sum_{t:\,a\text{ is ranked first in }t}\mu_t\). Given explicit nonnegative rational synergy tables \(g_J\) for listed class subsets \(J\), each nondecreasing in every coordinate, compute a size-\(k\) committee \(S\subseteq A\) maximizing \(\sum_{a\in S}p_\mu(a)+\sum_{J}g_J((|S\cap C_j|)_{j\in J})\).
A continuous electorate is a finite-support distribution \(\mu\) over complete rankings; its SNTV mass supplies candidate scores, while the paper's integral size-\(k\) committee and monotone class-synergy tables remain in place.
Covers Theorem 4's hardness for monotone synergy functions; leaves the paper's other hardness, tractability, and structural results unmirrored.
The strongest mirror I see is for Theorem 4, the paper’s hardness result for monotone synergies. It is proved in this paper by modifying the reduction used for Theorem 1. Theorem 4 states that CSC is NP-hard and W[1]-hard with respect to the number \(z\) of classes, even when every synergy function is monotone—that is, nondecreasing in each coordinate. This is a good anchor because it keeps the paper’s distinctive setting of classed alternatives and committee-level synergies, while showing that hardness survives a natural restriction.
A plausible regime is a very large membership organization electing a governing committee. Members’ rankings may fall into a relatively small set of recurring patterns, so the electorate has millions of people but far fewer distinct ranking types. Candidates can be grouped by region or specialty, and the synergy functions can express how the committee’s coverage or capabilities change with the number chosen from each group. The number of voters \(N\) can greatly exceed the support size \(\tau\). This is a scenario claim, not a claim that every committee election is a high-multiplicity one.
The corresponding problem is Continuous-Population Monotone CSC. An instance gives a candidate set \(A\), partitioned into classes \(C_1,\ldots,C_z\); a committee size \(k\); and a finite support of rankings \(t\), each with binary-rational mass \(\mu_t\geq 0\), where \(\sum_t\mu_t=1\). Use SNTV scores, which the paper identifies as a separable committee scoring rule, and define each candidate’s support share by
\[
p_\mu(a)=\sum_{t:\,a\text{ is ranked first in }t}\mu_t.
\]
The instance also gives an explicit family \(\mathcal F\) of synergy tables \(g_J\), one for each listed subset \(J\) of classes; each table takes the committee counts \((|S\cap C_j|)_{j\in J}\) and has nonnegative rational entries that are nondecreasing in every coordinate. The question is to output a committee \(S\subseteq A\), \(|S|=k\), maximizing
\[
\sum_{a\in S}p_\mu(a)
+\sum_{J\in\mathcal F}g_J\bigl((|S\cap C_j|)_{j\in J}\bigr).
\]
The population is continuous; the elected committee remains an integral set of candidates.
I expect this problem to remain hard by hardness transfer (Class B). In the hard instances in Theorem 4’s proof, the individual candidate weights are nonnegative. Given those weights \(w(a)\), let \(W=\sum_{a\in A}w(a)>0\). For each candidate with positive weight, create a ranking type with that candidate first and assign it mass \(w(a)/W\). Divide every synergy-table entry by \(W\). Then every committee’s continuous score is its original CSC score divided by the same positive constant, so the maximizing committees are exactly the same. The transformation preserves monotonicity and \(z\), and its rational numbers have polynomial bit length. Thus the theorem’s hard family embeds directly in this continuous-population problem. This argument does not establish hardness for constant \(\tau\); it establishes that replacing integer support weights by a rational population distribution does not remove the paper’s class-parameterized hardness.
The mirror is plausible because it retains the paper’s actual decision problem: select a size-\(k\) committee using candidate support plus intraclass and interclass synergies. The paper explicitly connects its individual weights to scores from an implicit electorate, including SNTV. Normalizing those supports into population shares changes how the society is represented, not what the committee-selection problem asks.
This case covers Theorem 4’s monotone-synergy hardness, not the paper’s tractable special cases or its other results. It also suggests follow-up questions: whether additional restrictions on the synergy tables yield efficient algorithms in terms of \(m,\tau,z\), and how the class interaction graph’s structure affects exact or approximate computation.
The soft spot is that the electorate enters only through an additive vector of support scores; the reduction’s hard combinatorics lie in the alternatives, classes, and synergy tables. So this mirror does not show that continuization makes the problem tractable, and its contribution as a new model could be viewed as modest. But it is a faithful continuous-population formulation of a named, proved-hard problem. Its main result is precisely that this population representation leaves the paper’s hardness intact.
The strongest objection is that the electorate is only a wrapper around the candidate weights. In CSC, voter support contributes an additive score for each candidate; the synergy tables, which carry the paper’s distinctive structure, are specified separately. In the proposed mirror, the society \(\mu\) can therefore be compressed to the first-place shares \(p_\mu(a)\). Any two societies with the same shares produce exactly the same optimization problem. The continuous type distribution does not shape the committee interactions or create a population-level operation to analyze.
That limits what the anchor demonstrates. Theorem 4’s reduction can be encoded as an electorate with at most one ranking type per positively weighted candidate, while the synergies carry the reduction’s combinatorics. It shows that rationalizing the score vector preserves hardness; it does not show hardness arising from population multiplicity or from the distribution over voter types. A more ambitious mirror could investigate what additional algorithms become possible when \(\tau\) is small, but this theorem’s reduction does not establish that story.
Still, this objection does not defeat the anchor. The proposed problem gives a genuine continuous society, uses its SNTV support shares, and asks a named computational question from the paper. A large membership organization with recurring ballot types is a sensible high-multiplicity regime. The fact that the society’s relevant information compresses to a score vector, or that the hardness reduction’s combinatorics lie in the alternatives, is not by itself a reason to reject the mirror under ChoCo’s criteria.
I cannot honestly make the universal negative case. The anchor survives the strongest objection I can make: it may be a modest, mostly representational mirror, and its hardness transfer does not establish a population-driven phenomenon, but it remains a plausible continuous-population question.
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.