| paper | d4-conf-ecai-2023-0167 |
| 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{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Input a finite set of exposure types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric rational contact matrix \(A\), thresholds \(\theta_t\), initial black, white, and gray masses \(z_t^b,z_t^w,z_t^g\) summing to \(\mu_t\), per-turn mass capacities \(r_b,r_w\), and target \(\alpha\). Assume every type has positive total exposure. Type \(t\) is eligible for opinion \(p\in\{b,w\}\) when \(\sum_u A_{tu}z_u^p\ge\theta_t\sum_u A_{tu}\mu_u\). On each turn, a polynomial-size rational-circuit policy chooses transfers from currently eligible gray types, bounded by their available gray mass and totaling the lesser of the player's capacity and the total eligible gray mass; apply the transfers, then alternate turns starting with black until no player can move. Decide whether there exists a black policy such that, for every white policy, terminal black mass is at least \(\alpha\).
A finite-type block-contact diffusion game: each type carries rational population mass, a contact profile, and an adoption threshold. Compact feedback policies allocate each player's per-turn transfer capacity among currently eligible gray mass; the decision objective is whether black can guarantee terminal mass at least \(\alpha\) against every compact white policy.
The mirror covers Theorem 6's cautious opinion-maximization problem in a finite-type exposure model. It leaves Theorem 5's brave problem and the experiments comparing centrality strategies on named networks outside its scope.
The lead mirror I would defend is Typed-Continuum Cautious Opinion Maximization. It preserves the paper’s central question: can black guarantee a target share of the population against every compact strategy white might use, given the initial opinions, diffusion speeds, and progressive threshold dynamics?
My anchor is Theorem 6, proved in this paper: CAUTIOUS-OM is \(\Sigma_2^P\)-complete. In full, its instance is a graph \(G=(N,E)\), an initial configuration \(S^0=(S_b^0,S_w^0)\), speeds \(\rho=(\rho_b,\rho_w)\), and a target \(\alpha\in[0,1]\). It asks whether black’s cautious-optimal compact strategy can ensure \(\gamma_b(\pi[S^0,\rho,\tau_b^\bot,\tau_w])\ge\alpha|N|\) for every compact white strategy \(\tau_w\), where the strategies choose eligible individuals as the progressive threshold process unfolds. The paper proves completeness here by reducing from validity of a quantified formula \(\exists x\,\forall y\,\varphi\), with \(\varphi\) in disjunctive normal form. This is a strong anchor because its difficulty lies in the interaction between a strategic choice and an adversarial response, and the outcome being measured is population coverage.
In the mirror, the population is partitioned into a finite set \(T\) of complete behavioral and exposure types. Each type \(t\) has rational mass \(\mu_t>0\), with \(\sum_t\mu_t=1\); members share a switching threshold \(\theta_t\) and the same contact profile with other types. Represent those profiles by a symmetric rational matrix \(A\), where \(A_{tu}\) is the contact density between types \(t\) and \(u\). The initial state gives rational black, white, and gray masses \(z_t^b,z_t^w,z_t^g\) for each type, summing to \(\mu_t\). A plausible regime is a large platform with millions of users grouped into a few dozen or hundred stable behavioral and community segments. The type records everything the model uses about a person; within the model, members of a type are interchangeable. Individual friendship lists have been replaced by the model’s block-level exposure profile, so this is a typed mean-field network model rather than an exact copy of any particular graph.
For a type \(t\), black makes its gray members eligible when \(\sum_u A_{tu}z_u^b\ge\theta_t\sum_u A_{tu}\mu_u\); white’s condition is the same with \(z_u^w\). During black’s turn, a compact feedback policy allocates its available effort across currently eligible gray types. Formally, it returns nonnegative rates \(q_t\) supported on those types, with \(\sum_t q_t=1\) whenever a move is possible; integrating the rates transfers at most \(\rho_b\) population mass from gray to black that turn. White acts analogously with quota \(\rho_w\), and turns alternate starting with black. A compact policy has a finite, polynomial-size rational description evaluated on the current type-mass vector, the continuous counterpart of the paper’s compact strategy encoding. Diffusion ends when neither player has eligible mass.
The resulting decision problem is: given \((T,\mu,A,\theta,z^0,\rho_b,\rho_w,\alpha)\), does there exist a compact black policy \(\sigma_b\) such that, for every compact white policy \(\sigma_w\), the terminal black mass satisfies \(\sum_t z_t^{b,\mathrm{final}}\ge\alpha\)? A yes-solution is a black feedback policy with that guarantee; the universal quantifier over white policies is part of the problem. This asks about the continuous population’s strategic diffusion and coverage, not about a fractional-outcome rule or a continuum of equilibria.
For the unrestricted problem where the number of types \(\tau=|T|\) grows with the input, my expectation is hardness transfers (Class B): the paper’s quantified strategic choices and threshold interactions look like the combinatorial core, and distinct network roles can be represented as distinct types. That is a prediction, not a result. The paper’s reduction does not establish it for this mirror: its graph gadgets use many individually specified nodes, while the continuous model permits partial transfers of a type’s mass. Whether those gadgets can enforce the needed all-or-nothing behavior under fractional actions is a central proof question. For fixed or small \(\tau\), tractability or fixed-parameter algorithms remain quite plausible.
The mirror covers the paper’s theoretical result on cautious opinion maximization, not its experiments comparing degree, betweenness, closeness, eigenvector, and vote-rank strategies on named networks. Its appeal is that it retains the threshold rule, progressive adoption, alternating competition, turn speeds, compact policies, uncertainty about the opponent, and the final coverage objective. The weak point is the network co-modification: replacing local neighborhoods with type-level exposure could erase topology that the authors consider essential. Still, large populations in repeated behavioral and exposure classes are a sensible regime for their problem, and the mirror gives them a concrete computational question about that regime.
Theorem 6 is a real computational anchor: CAUTIOUS-OM is \(\Sigma_2^P\)-complete. The strongest objection is that its strategic content lives in a labelled network. A move selects a particular eligible person, whose particular neighbors determine which cascades become possible. The final objective counts people, but replacing that count with population mass does not preserve the game that produces it.
In the proposed type model, masses and a contact matrix generally do not determine which individuals are eligible. Two networks can have the same type-level exposure totals and opinion masses but different eligible sets, because their edges connect different individuals. A compact strategy can exploit those differences. To make a type complete for the original problem, it would need to capture each person’s relevant neighborhood; in an irregular graph, that can leave nearly every person in a separate type, so \(\tau\) grows with the population. Collapsing people into exposure classes instead changes the network and the strategy space. That is a legitimate co-modification, but it is not a high-multiplicity account of Theorem 6 on general graphs.
A graphon model could retain more local structure, with the state and policies varying over a continuum of positions. But then the computational question depends on how the kernel and policies are finitely represented; it no longer has the simple finite-type input the proposed mirror suggests. This makes the general-graph bridge doubtful, not impossible. Existing analytic mean-field work does not settle the computational question, and I would not use it as a prior-art objection.
That is the best negative case: the theorem’s hardness is bound up with who is connected to whom, and ordinary type aggregation can erase exactly that information. But it does not defeat the better mirror. A large, genuinely block-structured population with a few contact communities is a plausible instance regime for these authors’ opinion-diffusion problem. In that regime, partial mass adoption and type-level exposure define a coherent cautious-maximization question. Whether its answer is easy or hard is precisely the sort of computational result the programme seeks.
So I cannot honestly defend the universal claim that no scenario offers a worthwhile mirror. The case against a faithful continuous mirror of the paper’s general-graph theorem is substantial; the case against every plausible structured-network mirror is weak.
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.