| paper | d4-conf-atal-2022-0081 |
| 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: Both decision problems are in \(\mathrm P\), with bit running time \(O(L+m\tau^2L^2)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a rational finite-support initial opinion distribution \(\mu_0\) on \(\mathbb{Q}^d\) and rational \(\varepsilon>\delta>0\), evolve \(\mu_t\) by \(\dot{\mu}_t=(F_{\mu_t})_\#\mu_t-\mu_t\), where \(F_\mu(x)\) is the mean opinion within distance \(\varepsilon\) of \(x\). Determine or approximate the first time \(T_\delta\) when every \(x,y\in\operatorname{supp}(\mu_t)\) with \(\|x-y\|_2\le\varepsilon\) also satisfies \(\|x-y\|_2\le\delta\), including whether \(T_\delta\) is infinite.
Types are initial opinion vectors \(z_i\in\mathbb{Q}^d\) with masses \(p_i\), forming \(\mu_0=\sum_i p_i\delta_{z_i}\). The complete-network population evolves by rate-one local averaging; the objective is to compute the support-based \(\delta\)-stability hitting time. Under this flow, an initially unstable support pair persists at every finite time, so \(T_\delta=\infty\); an initially stable distribution has \(T_\delta=0\).
The rate-one mean-field flow retains at least an \(e^{-t}\) fraction of every initial opinion at each finite time, so any initially unstable pair remains in the support and \(T_δ=\infty\); this defeats transfer of the finite-population convergence guarantee and reduces the hitting-time question to an initial-state check.
fatal: False
The mirror covers Theorem 2’s complete-social-network convergence result. It leaves the arbitrary-network bound, the lower-bound theorem, the potential-drop result, and the simulations outside its scope.
I would anchor on Theorem 2, proved in this paper. It says that for any \(d\)-dimensional Hegselmann–Krause instance whose social network is the complete graph \(K_n\), uniform random asynchronous updates reach a \(\delta\)-stable state in expected time at most
\[
O\!\left(n^3\left(n^2+(\varepsilon/\delta)^2\right)\right).
\]
Here, \(\delta\)-stable means that every pair of agents within confidence distance \(\varepsilon\) is at distance at most \(\delta\). This is my strongest anchor: it is a named, proved bound on the computational time of the paper’s dynamics. The paper does not give a standard NP-hardness or parameterized-complexity result to anchor instead.
A plausible high-multiplicity regime is a large public discussion platform where every user can see every other user’s posts, but users are influenced only by opinions within distance \(\varepsilon\). Users with the same initial opinion vector and the same update rule form a type. A platform might have an enormous population \(N\) but only \(\tau\) distinct initial opinion vectors, with \(\tau\ll N\). Mass is the fraction of users in each cohort. The complete-network assumption is restrictive, but this is a recognizable setting for a public forum or broadcast platform, and it matches the theorem’s network assumption directly.
My lead mirror is Mean-Field \(\delta\)-Stability Hitting Time. Its input is a rationally supported initial distribution
\[
\mu_0=\sum_{i=1}^{\tau}p_i\,\delta_{z_i},
\]
where each \(z_i\in\mathbb Q^d\), each \(p_i>0\) is rational, and \(\sum_i p_i=1\), together with rational \(\varepsilon>\delta>0\). For a current opinion distribution \(\mu\), define the local averaging map
\[
F_\mu(x)=
\frac{\int_{\|y-x\|_2\le\varepsilon} y\,d\mu(y)}
{\mu(\{y:\|y-x\|_2\le\varepsilon\})}.
\]
The continuous population evolves by
\[
\dot{\mu}_t=(F_{\mu_t})_\#\mu_t-\mu_t.
\]
This is the rate-one mean-field version of asynchronous updating: mass at opinion \(x\) is refreshed to its current local average, while the distribution tracks the resulting population. Let \(T_\delta\) be the first time when every \(x,y\in\operatorname{supp}(\mu_t)\) with \(\|x-y\|_2\le\varepsilon\) also satisfies \(\|x-y\|_2\le\delta\). The computational question is to approximate \(T_\delta\), or determine that it is infinite, with accuracy \(\eta\); running time should be measured in \(d,\tau\), the input bit length, and the requested precision. A gap-promise decision version—whether \(T_\delta\le H-\eta\) or \(T_\delta>H+\eta\)—would make a concrete first complexity question.
I would provisionally expect this mirror to be Class A, at least for fixed \(d\) and inputs separated from confidence-threshold degeneracies. The paper’s potential suggests a continuous energy,
\[
\Phi(\mu)=\frac12\int\!\!\int
\min\{\|x-y\|_2^2,\varepsilon^2\}\,d\mu(x)\,d\mu(y),
\]
whose decrease may support a quantitative algorithm for the hitting-time question. Mean-field opinion dynamics is relevant prior art and possible machinery; the computational question of how efficiently to determine convergence time remains distinct.
The weakest point is the bridge from the theorem to this mirror. Theorem 2 bounds *finite-population update steps*. Normalizing time to \(n\) updates per unit gives a bound of \(O(n^2(n^2+(\varepsilon/\delta)^2))\), which does not supply a uniform bound as \(n\) grows. The confidence rule also changes discontinuously at distance \(\varepsilon\), so convergence of finite populations to the stated measure evolution, and transfer of hitting-time guarantees, need proof. The mirror covers Theorem 2’s complete-network convergence result only; it does not claim to continuize the arbitrary-network result or the paper’s simulations and lower bounds.
Theorem 2 is the strongest anchor: it bounds the expected number of asynchronous updates until every influential pair is \(\delta\)-close. But its most natural continuous-time mean-field mirror does not preserve that stopping condition. Under rate-one asynchronous updates, the proposed evolution
\[
\dot{\mu}_t=(F_{\mu_t})_\#\mu_t-\mu_t
\]
always retains an \(e^{-t}\) fraction of the initial distribution that has not updated. Thus \(\mu_t\ge e^{-t}\mu_0\), and every initial opinion remains in the support at every finite time. If the initial society has even one influential pair farther apart than \(\delta\), the proposed support-based \(T_\delta\) is infinite. The finite-\(n\) process can reach \(\delta\)-stability because, after enough random activations, every agent may have moved; the deterministic population limit records a positive mass of agents that have not yet moved instead.
The best repair is to ask when the *mass* of unstable agents or pairs falls below a tolerance \(\eta\). That is meaningful, but it replaces the theorem’s universal stability guarantee with a population-level approximation. Its time depends on \(\eta\); for the unupdated mass alone, reducing it below \(\eta\) takes time on the order of \(\log(1/\eta)\). Sending \(\eta\) to zero to recover the all-agent condition sends the hitting time to infinity; setting \(\eta\) to \(1/n\) to track a finite society puts \(n\) back into the question. A finite-size stochastic or large-deviation analysis might retain the original event, but it would retain population-scale randomness rather than give the clean continuous mirror proposed here.
So the case against this anchor is strong for a direct mirror of Theorem 2: the natural limit makes its defining event trivial or unattainable, and the natural repair changes that event. The broader claim that no worthwhile mirror exists is weaker. A tolerance-based computational question could still be worthwhile and might be one the authors recognize, but it is not supplied by Theorem 2’s all-pairs convergence bound.
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.