| paper | d4-conf-ijcai-2015-0468 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions; more precisely, \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational role masses \(w_i\), a symmetric nonnegative contact matrix \(W_{ij}\), and parameters \(\mu,\delta\), the adversary chooses red-expert and blue-expert masses \(a_i,b_i\) with \(0\leq a_i+b_i\leq w_i\), \(\sum_i a_i=(1/2+\delta)\mu\), and \(\sum_i b_i=(1/2-\delta)\mu\). Each nonexpert of role \(i\) follows the sign of \(q_i=\sum_j W_{ij}(a_j-b_j)\), splitting evenly on a tie. Determine whether every feasible adversary choice leaves strictly more than half the population believing the truth.
A society of mass \(1\) divided among \(\tau\) interchangeable social roles, with rational masses \(w_i\) and shared contact rates \(W_{ij}\). The adversary’s decision variables are the red- and blue-expert masses \(a_i,b_i\); the question is whether the resulting mass of agents believing the truth always exceeds \(1/2\).
The expander guarantee depends on individual vertex neighborhoods, and averaging contacts into a role matrix does not show that the theorem’s spectral bound carries over; this limits the result’s transfer to the proposed block-role setting.
fatal: False
The mirror covers strong-adversary, one-step majority robustness in role-block societies. It leaves aside the weak-adversary and random-process results, the lower bound, and iterative propagation.
The strongest positive case is a narrow, conditional one: the paper’s strong-adversary robustness result has a natural continuous-population analogue. But it does not meet the required anchor standard. Theorem 3 is a proved combinatorial guarantee about when majority reflects the truth; it does not classify an algorithmic problem as polynomial-time, hard, or otherwise. The paper gives no discrete hardness result whose fate in a continuum could be studied.
If a robustness theorem is accepted as an anchor, the best choice is Theorem 3, proved here: for an \((n,d,\lambda)\)-graph, if
\[
\frac{d^2}{\lambda^2}>\frac{1}{\delta^2\mu(1-\mu+2\delta\mu)},
\]
then every strong adversary—choosing \(\mu n\) experts and assigning \((\tfrac12+\delta)\mu n\) of them the truth and \((\tfrac12-\delta)\mu n\) the falsehood—still leaves a majority of the network holding the truth. In particular, for a Ramanujan graph this holds when
\[
d\geq \frac{4}{\delta^2\mu(1-\mu+2\delta\mu)}.
\]
That is a robustness guarantee, not a complexity classification.
A plausible mirror is Graphon Strong-Adversary Robustness. Imagine a large platform where many users share one of a small number of social roles, each with the same contact rates across roles. The roles are the types, their population shares are \(w_i\), and a symmetric matrix \(W_{ij}\) gives the interaction weight between roles \(i\) and \(j\). Here the society is continuous mass \(1\), with \(\tau\) roles and \(\tau\ll N\).
Given rational \(w_i,W_{ij},\mu,\delta\), the adversary chooses red-expert mass \(a_i\) and blue-expert mass \(b_i\) in each role, subject to
\[
0\leq a_i+b_i\leq w_i,\qquad
\sum_i a_i=(\tfrac12+\delta)\mu,\qquad
\sum_i b_i=(\tfrac12-\delta)\mu.
\]
A nonexpert of role \(i\) follows the weighted majority of experts:
\[
q_i=\sum_j W_{ij}(a_j-b_j).
\]
They believe the truth if \(q_i>0\), the falsehood if \(q_i<0\), and split evenly in the continuum limit if \(q_i=0\). The decision problem is whether every feasible adversarial choice leaves more than half the population believing the truth. A “yes” instance is robust; a solution to a “no” instance includes an attack that prevents a truthful majority.
This is a sensible high-multiplicity scenario: roles can contain many users, while the number of distinct interaction profiles stays small. The decision being mirrored is the paper’s underlying social question—whether an adversary can overturn the majority—not a change to the outcome space. Theorem 3 suggests a tractable route in the expander-like regime: a spectral bound on the interaction kernel may certify robustness. I would expect that restricted analysis to be tractable. The exact complexity of the unrestricted finite-role problem is not established by this paper, so I would not claim either hardness transfer or continuum-specific hardness from it.
The mirror would cover only Theorem 3’s strong-adversary result. Its weakest point is also decisive under the stated rules: the paper contains no named computational-complexity anchor. A graphon version could be a recognizable continuous model of the authors’ robustness question, but it cannot support the requested claim that discrete computational hardness dissolves—or persists—in the continuum.
Theorem 3 is the only anchor the proponent offers, and it misses ChoCo’s computational target at the source. It proves a spectral condition under which every strong adversary fails to overturn the majority. The paper gives no algorithmic classification of a computational problem: no running-time result, hardness reduction, or stated decision task. One can formulate the task “does any adversarial placement defeat the majority?”, but that is a new task to study, not a computational result whose continuous counterpart this paper supplies.
The proposed graphon model also loses the feature that makes Theorem 3 interesting. Its guarantee uses the incidence structure of an expander: the adversary chooses particular vertices, and the proof bounds how their particular neighborhoods behave. A finite interaction matrix \(W_{ij}\) replaces those neighborhoods with average contact rates. An adversary choosing expert mass by role cannot exploit within-role placements, as the paper’s adversary can. For sparse expander families with degree fixed as \(n\) grows, a standard dense graphon limit also loses the edges, since their density is \(d/n\). A richer interaction operator could retain local structure, but then agents’ neighborhood profiles generally require many types; if the number of types approaches the number of vertices, the high-multiplicity compression disappears.
For a fixed finite role model, there is a direct baseline computation: enumerate the possible response signs for each role, and solve the resulting linear optimization problem for each sign pattern. This gives at most \(3^\tau\) cells. That could still motivate a study when \(\tau\) varies, but it supplies no reason to expect the paper’s spectral theorem to uncover a new continuous-optimization bottleneck. The proposed model is therefore either a tractable role-level reformulation with an elementary starting point, or a richer network model that must recover the individual structure its type compression discarded.
The honest weakness in this negative case is that dense, block-structured networks with many interchangeable users per role are plausible. Their continuous strong-adversary robustness problem could be worthwhile, and the authors might recognize it as an extension of their question. That possibility stops me from claiming that no useful continuous model can exist in any scenario. It does not rescue this paper as an anchor for ChoCo’s computational programme: the surviving model is a new problem, and Theorem 3 itself is a robustness theorem rather than a computational result.
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.