| paper | d4-journals-jair-2025-0038 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), already for fixed \(q=3/4\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
Given \(\tau\) exposure roles with positive rational masses \(\mu_i\) summing to \(1\), a symmetric nonnegative rational interaction matrix \(a_{ij}\), and rational \(q\in(1/2,1]\), does there exist a red mass \(x_i\in[0,\mu_i]\) for each role such that \(\sum_i(\mu_i-2x_i)>0\) and \(\sum_{i:\,\sum_j a_{ij}(2x_j-\mu_j)>0}\mu_i\ge q\)?
A continuous society has finitely many exposure-role types with masses \(\mu_i\); type \(i\) has contact intensity \(a_{ij}\) with type \(j\). Choose red mass \(x_i\) and blue mass \(\mu_i-x_i\) in each type, and decide whether blue is the strict population majority while at least \(q\) of the mass has a strict red majority in its contacts.
The mirror addresses the verification question in Theorem 1 over role masses; it does not reproduce the theorem’s bipartite hardness or cover Theorems 2–4’s graph restrictions and algorithms, or the edge-rewiring results.
The strongest anchor is Theorem 1, proved in this paper by a reduction from \(2P2N\text{-}3\text{-SAT}\). It states that, for every rational \(q\in(1/2,1]\), deciding whether a network admits a labeling under which at least a \(q\)-fraction of its vertices are under majority illusion is NP-complete, even when the network is bipartite. The reduction and theorem are the authors’ results here, rather than a cited result.
A plausible continuous setting is a large community whose members fall into a modest number \(\tau\) of exposure roles: members of a role have the same pattern of contact with the other roles. The roles might reflect residents’ usual community groups or recurring patterns of mutual contact. There may be millions of people but only dozens or hundreds of roles. Each person still holds one of the paper’s two opinions, red or blue; the continuous quantity is the mass of people in each role and opinion.
Here is the mirror I would put to a prover: Type-Mass \(q\)-Majority Illusion. An instance gives \(\tau\) roles, positive rational masses \(\mu_i\) summing to \(1\), a rational symmetric interaction matrix \(a_{ij}\geq 0\), and rational \(q\in(1/2,1]\). The matrix is fixed: \(a_{ij}\) describes the contact intensity between roles \(i\) and \(j\). A solution assigns red mass \(x_i\in[0,\mu_i]\) to each role; the remaining mass \(\mu_i-x_i\) is blue. Equivalently, red and blue are two opinion variants of each exposure role, with masses that sum to the role’s total mass.
The assignment must make blue the strict population majority and give at least \(q\) of the population a strict red majority among its contacts. In formulas, blue’s global surplus must be positive,
\[
\sum_i(\mu_i-2x_i)>0,
\]
and the mass of roles whose local red surplus is positive must be at least \(q\):
\[
\sum_{i:\,\sum_j a_{ij}(2x_j-\mu_j)>0}\mu_i\ \geq\ q.
\]
Everyone in a role has the same exposure, so that role’s full mass either has the illusion or does not. A rational vector \(x\) satisfying these conditions is a solution.
This model preserves the paper’s central question: does a society’s opinion distribution allow a sufficiently large share of people to perceive the wrong majority? It replaces counts by masses and each individual neighborhood by the contact exposure of their role. The continuous population is the object being modeled; the fixed interaction matrix supplies the role-level neighborhood structure.
The computational expectation is tractability in the support size \(\tau\), which would make this a Class A mirror in the many-agents, few-types regime. Enumerate subsets \(S\) of roles with \(\sum_{i\in S}\mu_i\geq q\). For each subset, test whether there is an \(x\) making the global blue surplus and every role’s red local surplus positive for \(i\in S\). This is linear feasibility with strict inequalities: maximize a common margin \(\delta\) subject to each required surplus being at least \(\delta\), then check whether the optimum is positive. The resulting algorithm takes \(2^\tau\operatorname{poly}(\tau,L)\) time, where \(L\) is the input bit length. The question left open is whether the dependence on \(\tau\) can be improved to polynomial time, or whether the unrestricted problem is hard as \(\tau\) grows.
There is a precise connection to the discrete anchor. For a graph on \(n\) vertices, make one role per vertex, set \(\mu_i=1/n\), and let \(a_{ij}=1\) exactly when the corresponding vertices are adjacent. If each \(x_i\) is restricted to \(0\) or \(\mu_i\), the resulting question is exactly the paper’s \(q\)-majority illusion problem: both global and local comparisons are the original ones, scaled by \(1/n\). Allowing interior values of \(x_i\) is the continuization. It means a role’s population may split between opinions, while every person still has an integral opinion.
My weakest point is also the key limit on the claim: Theorem 1’s NP-hardness does not automatically transfer. Fractional opinion mass may make a discrete no-instance positive, so the graph encoding establishes a bridge between the models, not an equivalence of their answers. And if real agents have sharply different individual neighborhoods, the exposure-role description may be too coarse. The case is strongest where many people share stable contact profiles and \(\tau\) is genuinely small; there, the mirror asks a recognizable version of the authors’ verification question and gives it a concrete continuous algorithm.
This case covers the verification result in Theorem 1. It does not mirror the paper’s separate edge-rewiring elimination results, where a continuous intervention model would need its own justification.
Theorem 1 is a real computational result, so the strongest available objection is about whether its local-neighborhood problem survives a genuine high-multiplicity model. In the paper, the input is an exact graph: illusion depends on the realized neighbors of each vertex. A small interaction matrix replaces that incidence structure with role-level exposure. Unless role members have genuinely interchangeable neighborhoods, it answers a different question: whether a population split produces the desired majorities under homogenized exposure.
The proponent’s one-role-per-vertex encoding preserves the original instance, but it has \(\tau=n\), so it supplies no many-agents, few-types regime. Allowing fractional \(x_i\) there is a relaxation whose answers need not match the discrete theorem. At small \(\tau\), the model becomes meaningful when contacts really are block-structured. But that is also where the authors’ own neighborhood-diversity result already gives an FPT algorithm for the discrete problem. That result is evidence the regime is sensible, as the programme’s brief requires; it is not a novelty objection. It does, however, leave the continuous mirror’s distinctive computational contribution unclear.
A richer graphon or neighborhood-type model could retain more topology, but arbitrary local neighborhoods then require many types, potentially one per agent. Restricting it back to finitely many exposure roles restores the averaging assumption. And the resulting feasibility problem still has a discrete choice of which roles have positive local red surplus; the proposed algorithm enumerates those choices. There is no obvious analogue of the exponential-variable LP and pricing structure that makes the programme’s bribery mirrors especially valuable.
That is the best negative case I can make, but it does not defeat the anchor. A large community with a small number of repeated contact roles is plausible, and in a block-structured network the mass model is a recognizable version of the authors’ verification question. The paper’s neighborhood-diversity result reinforces that this regime is worth considering. So the honest negative verdict is weak: the mirror’s added value is uncertain, but I cannot justify the claim that no worthwhile continuous mirror exists.
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.