| paper | d4-conf-ijcai-2018-0659 |
| 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, even when every approval type has size two and every mass is a positive dyadic rational. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a path \(G=(C,E)\), approval types \(A_1,\ldots,A_\tau\subseteq C\) with positive binary-rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\), does there exist an independent set \(W\subseteq C\) such that \(\sum_{i=1}^{\tau}\mu_i H_{|A_i\cap W|}\ge q\), where \(H_j=\sum_{h=1}^{j}1/h\) and \(H_0=0\)? This problem is NP-hard even when every \(A_i\) has size two.
A continuum of residents partitioned into approval types \(A_i\subseteq C\) with masses \(\mu_i\); choose an integral independent committee \(W\) on the candidate path to maximize per-capita PAV score \(\sum_i\mu_i H_{|A_i\cap W|}\).
Covers PAV winner determination for independent admissible sets on path graphs, with hardness already when each ballot approves exactly two candidates; leaves the other rules, admissible-set classes, and strategyproofness results untouched.
The strongest mirror I see is the PAV hardness result for independent admissible sets. A natural setting is a large city choosing projects arranged along a corridor, where neighboring projects cannot both be selected. Residents submit approval ballots, and the city uses PAV to reward representation with diminishing returns. A voter type is an approval set \(A\subseteq C\); its mass \(\mu_A\) is the fraction of residents with that ballot. The candidate graph and PAV rule are exactly the paper’s. This is a sensible high-multiplicity regime when the electorate is large but many residents share ballot types.
My anchor is Theorem 8, proved in this paper. Its PAV result says that winner determination with independent admissible sets is NP-hard even when the candidate graph is a path and every voter approves exactly two candidates. The theorem also establishes the corresponding result for CCAV, but I would not add it as a separate anchor: the PAV result alone makes the case.
The continuous problem I would hand to a prover is Continuous Independent-PAV Winner Determination. An instance consists of candidates \(C\), a path \(G=(C,E)\), a list of approval types \(A_1,\ldots,A_\tau\subseteq C\) with positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\). The question is whether there is an independent set \(W\subseteq C\) such that
\[
\sum_{i=1}^{\tau}\mu_i H_{|A_i\cap W|}\ge q,
\qquad
H_j=\sum_{h=1}^{j}\frac1h,\quad H_0=0.
\]
A solution is such a committee \(W\); equivalently, one can ask for a maximum-score independent set.
This is the same underlying decision as in the paper, with each voter’s contribution replaced by that type’s population mass. The discrete-to-continuous correspondence is exact: for a paper instance with \(N\) voters, set \(\mu_A\) to the number of voters with ballot \(A\), divided by \(N\), and set \(q=r/N\). Every committee has continuous score equal to its discrete score divided by \(N\), so the threshold answer is unchanged. Theorem 8 therefore gives NP-hardness for this continuous problem too; the decision version is in NP because a committee is a polynomial-size certificate and its rational score can be checked. My expected classification is hardness transfers: the reduction’s structure is in the candidate graph and approval choices, not in needing individually distinct voters. Its construction is proved here, using a reduction from ALMOST 2-SAT.
I would scope the claim to this one result: PAV, independent admissible sets, and the path-graph restriction. It does not cover the paper’s strategyproofness results or its other admissible-set classes. It also generates a useful next question: what happens when the support size \(\tau\) is bounded or is small relative to \(m\), and can the continuous problem be fixed-parameter tractable in \(\tau\)? Theorem 8 does not settle that. Its hardness family can be replicated to produce arbitrarily many residents per ballot type, but that does not show hardness at bounded \(\tau\).
That is the weakest point in my case: the exact embedding makes the mirror easy to recognize, but it also means this anchor does not demonstrate that population continuization itself creates the hardness. I still consider the question legitimate. It asks whether the paper’s hard winner-determination problem remains hard when the electorate is represented by rational shares of approval types, and identifies a crisp boundary question about support size.
I cannot responsibly defeat this anchor. Theorem 8 is a genuine computational result, and its best continuous mirror is well posed: residents are grouped by approval set \(A_i\), with rational population shares \(\mu_i\), and the objective is
\[
\sum_i \mu_i H_{|A_i\cap W|}.
\]
The corridor-project story makes repeated approval types plausible. The committee can remain an integral independent set; the population is the object represented by masses.
The strongest case against is about the mirror’s research value. PAV scores add across voters, so the finite electorate already has sufficient statistics \(n_A\), the counts of each ballot type. Replacing \(n_A\) by \(\mu_A=n_A/N\) changes the encoding and normalization, while leaving the committee problem intact. Theorem 8’s reduction uses ballot types to encode clauses, and its support can grow with the reduction. It therefore gives no evidence about the especially attractive regime of many residents but few approval types. The suggested question about parameter \(\tau\) is real, but a direct dynamic program on a path, tracking how many selected candidates belong to each type, already gives an \(m^{O(\tau)}\) algorithm. The specific anchor thus looks more like weighted PAV optimization than a new continuum phenomenon.
That objection falls short of disqualifying the mirror. High-multiplicity type aggregation is exactly the programme’s population move, and binary rational masses are a different input regime from an explicitly listed electorate: clearing their denominators can require exponentially many voters. The changed encoding can matter to algorithms, even though the score formula is familiar. Nor does the framework require fractional committees or a continuous-specific effect; it explicitly allows integral outcomes for a continuous society. Theorem 8’s hardness transfer is therefore legitimate evidence for a Class B boundary, even if it supplies little evidence of tractability.
So the negative case is weak. The anchor is not merely a clumsy formulation that a better type space fixes: the proponent’s formulation is already the natural high-multiplicity version. I would expect this anchor to survive, while recording that its main unresolved value lies in the complexity landscape as a function of support size, not in a new continuum optimization method.
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.