| paper | d4-conf-aaai-2023-1689 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exactly solvable in polynomial time. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite type set \(T\) with rational masses \(\mu_t\), innate opinions \(s_t\), roles \(r(t)\), and a rational nonnegative contact kernel \(K_{ru}\), let \(\nu_r=\sum_{t:r(t)=r}\mu_t\). Define \(H_{ru}=(1+\sum_v K_{rv}\nu_v)\mathbf{1}[r=u]-K_{ru}\nu_u\), and let the role equilibrium after intervention \(x\) satisfy \(Hz=\bar{s}(x)\), where \(\bar{s}_r(x)=\sum_{t:r(t)=r}(\mu_t-x_t)s_t/\nu_r\). For a population-share budget \(\alpha\), find \(x\) minimizing \(G(x)=\sum_r\nu_r z_r\), subject to \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\alpha\).
A finite-type, nonatomic FJ society: each type \(t\) has mass \(\mu_t\), innate opinion \(s_t\), and role \(r(t)\); the rational kernel \(K\) specifies role-to-role influence. The decision is intervention mass \(x_t\), reset to opinion \(0\); minimize the population-average equilibrium opinion \(G(x)\).
The paper provides no evidence that large real directed networks admit a fixed-size role and contact-kernel representation; the proponent acknowledges the restricted regime but does not establish its empirical reach.
fatal: False
The mirror covers Theorem 4.1 as a fractional type-mass allocation problem; Theorem 5.4 has a plausible role-level estimation analogue, while the paper's results for arbitrary individual-node graphs and its real-network experiments remain unmatched.
I see a credible, deliberately narrow mirror for OpinionMin. The natural regime is a citywide or national campaign with millions of people but a modest number of contact-and-opinion profiles. A type records an agent’s initial opinion and social role: everyone of that type has the same directed contact pattern across roles and is eligible for the same intervention. A campaign can reach a specified fraction of each type, rather than choosing named individuals. This is a high-multiplicity setting: population size grows while the number of distinct types stays comparatively small.
Here is a finite-type FJ model for that regime. Let \(t\in T\) have mass \(\mu_t\) and initial opinion \(s_t\), and let \(r(t)\) be its social role. Write \(\nu_r=\sum_{t:r(t)=r}\mu_t\) for the mass of role \(r\). A nonnegative contact kernel \(K_{ru}\) gives the influence weight an agent in role \(r\) places on role \(u\), per unit of that role’s mass. If the campaign resets mass \(x_t\) of type \(t\) to opinion \(0\), its role’s mean innate opinion is
\[
\bar{s}_r(x)=\frac{\sum_{t:r(t)=r}(\mu_t-x_t)s_t}{\nu_r}.
\]
The role-level FJ equilibrium is
\[
z_r=\frac{\bar{s}_r(x)+\sum_u K_{ru}\nu_u z_u}{1+\sum_u K_{ru}\nu_u},
\]
and the objective is the population average \(G(x)=\sum_r\nu_r z_r\). The mass variables obey \(0\le x_t\le\mu_t\) and \(\sum_t x_t=\alpha\), where \(\alpha\) is the campaign’s population share.
Lead mirror — Continuous OpinionMin-\(\alpha\). Given rational type masses, opinions, contact kernel and budget \(\alpha\), find a feasible mass allocation \(x\) minimizing \(G(x)\). The solution is the allocation itself. For
\[
H_{ru}=\left(1+\sum_v K_{rv}\nu_v\right)\mathbf{1}[r=u]-K_{ru}\nu_u,
\qquad
h_r=(\nu^\top H^{-1})_r,
\]
the per-unit-mass benefit of intervening in type \(t\) is
\[
b_t=s_t\frac{h_{r(t)}}{\nu_{r(t)}}.
\]
Indeed, \(G(0)-G(x)=\sum_t x_t b_t\). So the optimum fills the budget with types in descending order of \(b_t\), taking only a fraction of the last type if needed. This is a fractional allocation problem, solvable by a linear solve on the \(q\) roles and a sort over the \(\tau\) types; its exact rational running time is polynomial in \(q,\tau\), and the input bit length \(L\).
The anchor is Theorem 4.1, proved in this paper: an optimal OpinionMin set consists of the \(k\) nodes with largest \(\rho_i s_i\), equivalently every selected node \(i\) has \(\rho_i s_i\ge \rho_j s_j\) for every unselected node \(j\). The continuous result is the corresponding per-unit-mass ranking. In the singleton-role case with \(\mu_i=1/n\) and \(H=I+L\), \(h_i=\rho_i\); selecting mass \(1/n\) yields benefit \(\rho_i s_i\), exactly the paper’s ranking criterion. The paper’s adjacent exact algorithm computes the required centralities in \(O(n^3)\); for the type model, the matrix dimension is the number of roles.
Second mirror — Continuous structure-centrality estimation. Given the same finite-role model and accuracy parameters \(\epsilon>0\), \(\delta\in(0,1)\), estimate \(h_r\) for each role \(r\), returning estimates with error at most \(\epsilon\) and the requested confidence. Here \(h_r\) is the population mass whose influence-forest component is rooted at role \(r\), in expectation. A weighted forest sampler on the role graph estimates it by averaging the mass in each sampled root basin.
The anchor is Theorem 5.4, proved in this paper: with
\[
l=\left\lceil \frac{1}{2\epsilon^2}\ln\frac{2}{\delta}\right\rceil,
\]
for any fixed node \(i\), the paper’s estimator satisfies
\[
\mathbb{P}\!\left(\left|\widehat{\rho}[i]s_i-\rho_i s_i\right|>\epsilon\right)\le\delta.
\]
For the continuous role model, taking \(s=1\) gives the pointwise centrality-estimation question. The theorem’s guarantee is per node; for simultaneous accuracy across \(q\) roles, a union bound replaces \(\ln(2/\delta)\) with \(\ln(2q/\delta)\). Using these estimates to choose the fractional allocation raises a further question: how does regret depend on role masses, especially for very small roles, since the per-mass scores divide by \(\nu_r\)? The expected direction is tractable, though the weighted sampler’s runtime needs its own analysis.
The authors would likely recognize the lead mirror: it keeps the FJ equilibrium, the average expressed opinion, and the intervention on innate opinion, while replacing a count of selected nodes with a population-share quota. This is a computational question about allocating campaign effort across a high-multiplicity society. Analytic mean-field work is relevant machinery, not a replacement for that optimization question.
The scope is OpinionMin and its centrality-based solution. The paper offers no named hardness result, so this is an A-class tractability mirror, not a claim that continuum treatment dissolves discrete hardness. My weakest point is the role-homogeneity assumption: arbitrary directed networks can give individuals in the same apparent social group very different centralities. The mirror is persuasive for block-homogeneous or type-mixing populations, but it would be a different regime from an unconstrained, idiosyncratic graph.
The strongest case against a broad mirror is that the paper’s input is the network’s individual structure. Its centrality \(\rho_i\) depends on where a node sits in that structure, not just on the node’s opinion or social category. In a sparse social network, grouping people by ordinary traits will generally erase relevant differences in their contacts. To preserve those differences, types would have to encode increasingly detailed network positions, so their number could grow with the population.
That problem applies to both anchors. For Theorem 4.1, the most convincing mirror is the proponent’s intervention by population share in a finite-role FJ model. It is coherent, but its role-level contact kernel imposes homogeneous mixing and changes the paper’s unweighted individual graph into a weighted, mass-scaled network. For Theorem 5.4, a weighted forest sampler estimates root-basin mass in that same altered model; it does not preserve the paper’s estimand for an arbitrary large sparse graph. These are substantive modeling assumptions, not just changes from selecting people to selecting mass.
This makes the mirrors narrow: they apply when a society really can be represented by a small number of contact roles with common interaction patterns. The paper’s experiments on large real networks do not establish that such a representation is adequate. If those assumptions fail, preserving the relevant structure may require one type per node, and the high-multiplicity benefit disappears.
But this is not enough to support the universal negative claim. A block-homogeneous population with repeated contact roles is a plausible instance regime, and the paper explicitly says its method extends to weighted digraphs. In that regime, the share-based optimization and root-basin estimation are recognizable FJ opinion-optimization questions. Their simple matrix and sorting solutions, or the availability of exact computation, cannot by themselves disqualify them under the stated criteria. So the honest negative case is that the mirrors cover a restricted regime whose relevance needs justification; it does not defeat the finite-role mirror, and I cannot make a convincing case 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.