| paper | d4-conf-ijcai-2020-0622 |
| 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}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), rational internal opinions \(s_t\in[-1,1]\), a rational signed interaction kernel \(K_{tu}\), and a rational intervention share \(\beta\in[0,1]\), choose shielded masses \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\beta\). For each type, let the expressed opinion of its unshielded mass satisfy \(y_t=[s_t+\sum_u K_{tu}(x_us_u+(\mu_u-x_u)y_u)]/[1+\sum_u\mu_u|K_{tu}|]\). Find \(x\) maximizing the population’s average expressed opinion \(\sum_t[x_ts_t+(\mu_t-x_t)y_t]\), with running time measured in the type count and input bit length.
A finite-type, dense block social trust network: type \(t\) has population mass \(\mu_t\), internal opinion \(s_t\), and signed interaction profile \(K_{t\cdot}\). Shielding is a decision mass \(x_t\) within each type; the objective is average equilibrium expressed opinion.
The paper’s experiments use individual networks, and the case does not show that their topology is well represented by dense block interactions; this limits the mirror’s empirical reach, though the proposed large-platform regime keeps the question plausible.
fatal: False
Block-EOP mirrors Theorem 3. Block-IOP provides a separate type-mass version of Theorem 2. The other dynamics derivations and experimental comparisons are not computational results covered by these mirrors.
The strongest case is a mean-field block social trust network: a large online population divided into \(\tau\) cohorts, with \(N\gg\tau\). Each person in cohort \(t\) has the same internal opinion \(s_t\) and the same signed exposure profile across cohorts. If each tie from a person in \(t\) to a person in \(u\) has weight \(K_{tu}/N\), the total influence from cohort \(u\) approaches \(K_{tu}\mu_u\), where \(\mu_u\) is its population share. This gives the paper’s signed Friedkin–Johnsen dynamics at the level of population masses.
That is a plausible regime for a very large platform where users fall into a modest number of opinion and exposure profiles. The intervention also retains the paper’s meaning: a platform or campaign can shield selected users from peer influence, leaving their expressed opinion at their internal opinion. The model assumes cohort members have the same profile at its level of resolution; that is a real restriction on the network, not a claim that arbitrary social graphs are interchangeable.
My lead anchor is Theorem 3, proved in this paper. It states that EOP is NP-hard: given a social trust network, internal opinions, and an integer \(\mu\), choose a set \(\mathcal U\) of exactly \(\mu\) nodes, fix each selected node’s expressed opinion to its internal opinion, and maximize the resulting overall equilibrium opinion. The authors sketch a proof using a generalized absorbing random walk and a reduction from Vertex Cover on regular graphs.
A continuous version I would put to a prover is Block-EOP\(_\infty\). Its input is a finite set of types \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational internal opinions \(s_t\in[-1,1]\), a rational signed interaction kernel \(K_{tu}\), and a rational intervention mass \(\beta\in[0,1]\). Choose masses \(x_t\) to shield, with \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\beta\). The expressed opinion \(y_t\) of the unshielded mass is determined by the equilibrium equations \(y_t=[s_t+\sum_u K_{tu}(x_us_u+(\mu_u-x_u)y_u)]/[1+\sum_u\mu_u|K_{tu}|]\). Maximize the population’s average expressed opinion, \(\sum_t[x_ts_t+(\mu_t-x_t)y_t]\). A solution is a maximizing allocation \(x\) and its equilibrium \(y\); for algorithmic study, one can also ask for an \(\varepsilon\)-optimal allocation. This is the paper’s intervention and objective with the number of selected people replaced by a share of the population.
I would tentatively investigate this as Class C, since the equilibrium depends on the allocation through a system of linear equations, making the objective a nonlinear function of the chosen masses. But Theorem 3 does not establish that prediction: allowing fractional intervention within types may erase the integrality behind the Vertex Cover reduction. The central questions are whether the mass-allocation problem is tractable in \(\tau\) and input bit length, whether hardness persists even in simple block networks, and what approximation guarantees are possible. A useful boundary question is which restrictions on \(K\) make the objective concave or otherwise efficiently optimizable.
A second, independently good anchor is Theorem 2, proved in this paper. It states that Algorithm 1 returns an optimal solution to IOP: given a social trust network, internal opinions \(s\), and budget \(\mu\), choose changes \(\Delta s_i\) to maximize \(\mathbf 1^T(\bar L+I)^{-1}(s+\Delta s)\), subject to \(-1\le s_i+\Delta s_i\le1\) and \(\|\Delta s\|_1\le\mu\).
Its population mirror, Block-IOP\(_\infty\), uses the same type masses and kernel. Choose new type-level internal opinions \(\hat s_t\in[-1,1]\) with per-capita modification budget \(\sum_t\mu_t|\hat s_t-s_t|\le\beta\). The equilibrium satisfies \(y_t=[\hat s_t+\sum_u\mu_uK_{tu}y_u]/[1+\sum_u\mu_u|K_{tu}|]\); maximize \(\sum_t\mu_ty_t\). A solution is an optimal \(\hat s\) and its equilibrium \(y\). This is an LP: the equilibrium equations and constraints are linear in \(\hat s\) and \(y\). It therefore looks like Class A, with the paper’s contribution-index idea giving the response weights. The follow-up questions are how those weights behave as the type partition changes and how the finite and mass-budget versions relate under replication.
Theorem 3 is the lead because the programme’s prize question is whether discrete hardness survives population continuization; Theorem 2 supplies a separate, concrete tractability result. These mirrors cover EOP and IOP, not the paper’s entire analysis. The continuous-valued opinions in the paper are not themselves the continuization: the proposed mirrors make the population the continuous object.
The weakest point is that the paper’s hardness result concerns arbitrary finite networks, while the proposed EOP mirror uses a mean-field block structure and permits fractional selection within a type. The paper’s reduction may depend on distinctions that vanish under that change. That is also why this is a worthwhile mirror: it asks precisely whether the hardness is tied to individual selection or survives when the intervention and society are expressed in masses.
The strongest case against starts with the network structure. In EOP, the value of shielding a node depends on the signed, directed interactions that feed into the equilibrium. Theorem 3’s reduction from Vertex Cover on regular graphs makes that dependence concrete. In a typical sparse network, a complete type would need to include a detailed interaction profile, so the number of types could grow with the population. Keeping a fixed number of types instead leads to a dense, exchangeable block network. That is a coherent mean-field regime, but the paper gives no evidence that it captures the social trust networks motivating its problems. A graphon-style model could retain richer heterogeneity, but its computational question would need a finite input representation and complexity parameters first.
That objection does not dispose of Block-EOP\(_\infty\). The mean-field model has a clear finite encoding, and fractional shielding is a sensible per-capita intervention for a large population. Fractional choices may remove the integrality used in the Vertex Cover reduction, but whether hardness survives is precisely a worthwhile question under this programme. Calling the model too different from EOP would be a judgment about the regime’s relevance, not a fundamental obstacle to the mirror.
Theorem 2 is a weaker research anchor. With shared type profiles, its objective remains linear in the internal-opinion changes, and the population-weighted budget gives a type-level continuous optimization problem. The paper’s contribution weights make a tractable solution look immediate. That suggests little unresolved computational terrain in this mirror. Still, a quick Class A result is a legitimate outcome here; the fact that the answer may be straightforward does not make the question unworthy by the programme’s standards.
So the negative case is weak. The network’s individualized topology makes it hard to argue that a fixed-type model represents the paper’s general target domain, and IOP seems to offer limited new complexity. But neither point rules out a plausible high-multiplicity block regime, and EOP remains a named hardness result with a well-posed population-mass counterpart. I cannot honestly defend the universal 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.