| paper | d4-conf-ijcai-2016-0351 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable under the permitted succinct representation. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\), initial opinions \(q_t\in[0,1]\), and a rational matrix \(A\) with \(A_{tu}\ge 0\), \(\sum_u A_{tu}=1-\beta_t\) for \(\beta_t>0\), and \(\mu_t A_{tu}=\mu_u A_{ut}\), consider a nonatomic population in which every type-\(t\) member uses these shared parameters. In round \(r\), a member samples a current opinion from type \(u\) with probability \(A_{tu}\), or uses \(q_t\) with probability \(\beta_t\), then updates using \(\lambda(r)=r/(r+1)\). Given \(\epsilon>0\), find an explicit round bound \(R(\epsilon)\) guaranteeing that the vector of expected typewise opinion means is within \(\epsilon\) in \(\ell_\infty\) distance of the unique type-level FJ fixed point \(\mathbf{x}^*=A\mathbf{x}^*+\boldsymbol{\beta}\odot\mathbf{q}\).
A nonatomic population with masses \(\mu_t\) over finitely many immutable behavioral types, each with shared initial opinion \(q_t\) and reciprocal per-capita influence probabilities \(A_{tu}\). The dynamic state is each type's opinion distribution and its expected mean; the target is the type-level fixed point \(\mathbf{x}^*=A\mathbf{x}^*+\boldsymbol{\beta}\odot\mathbf{q}\).
Arbitrary agent-level networks may not admit a small exact type quotient, so the mirror is limited to regimes with repeated, reciprocal interaction profiles.
fatal: False
The mirror covers Theorem 1's LIP-FJ convergence-in-expectation guarantee; it leaves Theorem 2, Lemmas 2–3, and the experimental comparisons unmirrored.
The best positive case is a plausible high-multiplicity version of the Friedkin–Johnsen problem, but the paper has no named computational result that clearly passes your anchor test.
The closest result is Theorem 1, proved here. It bounds the distance between LIP-FJ’s expected opinion vector at round \(t\) and the Friedkin–Johnsen stable state:
\[
\left\|\mathbb{E}[\mathbf{x}(t)]-\mathbf{x}^*\right\|_\infty
\le
e^{-(1-\nu(A))\sum_{q=1}^{t}(1-\lambda(q))}
\left\|\mathbf{x}(0)-\mathbf{x}^*\right\|_\infty,
\]
where \(\mathbf{x}^*=(I-A)^{-1}B\mathbf{x}(0)\). The theorem analyzes a randomized protocol in which each agent consults one neighbor and mixes that opinion with her previous one. With \(\lambda(t)=t/(t+1)\), the paper says convergence takes time exponential in \(1/(1-\nu(A))\). This is a useful algorithmic *near-anchor*, but it is a convergence guarantee, not a result placing a computational problem in \(\mathrm P\), proving hardness, or giving a standard input-size running-time classification. Theorem 2 and Lemmas 2–3 likewise concern convergence of network-HK and random-HK. They do not supply a qualifying complexity anchor.
A plausible population regime is a very large online community or organization with many members but relatively few complete behavioral types. A type records an agent’s initial opinion, stubbornness, and interaction propensities; members of a type are interchangeable in every feature the model uses. If there are millions of agents but only \(\tau\) such types, their shares \(\mu_t\) are a natural description of the society.
One precise candidate is Type-FJ-Equilibrium. An instance consists of rational type masses \(\mu_t>0\) summing to \(1\), initial opinions \(q_t\in[0,1]\), and a nonnegative rational matrix \(A\) of type-level influence weights. Require each row sum to be less than \(1\), and require \(\mu_t A_{tu}=\mu_u A_{ut}\) to preserve reciprocal interactions. Let \(\beta_t=1-\sum_u A_{tu}\). The task is to output the unique rational vector \(\mathbf{x}^*\) satisfying
\[
x_t^*=\sum_u A_{tu}x_u^*+\beta_t q_t
\quad\text{for every }t,
\]
or equivalently the limiting opinion distribution \(\rho^*=\sum_t\mu_t\delta_{x_t^*}\). An exact solution counts. Rational linear algebra solves this in time polynomial in \(\tau\) and the input bit length \(L\), so this candidate is tractable. It mirrors the stable-state object in Theorem 1, but the direct linear-system algorithm is a proposed population formulation, not a result established by that theorem.
Its main weakness is decisive for the requested grading: the continuous question is recognizable as a type-based Friedkin–Johnsen equilibrium problem, but it is not anchored by a named computational-complexity result in this paper. Theorem 1 studies expected convergence of a limited-information protocol; it does not classify the complexity of computing that equilibrium. Thus the honest positive case is a credible new high-multiplicity extension with a precise tractable problem, while the paper itself offers no qualifying computational anchor. The proposed mirror covers only the FJ stable-state target, not the HK convergence results.
The strongest case against this paper as a ChoCo entry is that it supplies no computational-complexity result to mirror. Theorem 1 bounds the expected convergence of a particular randomized protocol; Theorem 2 proves convergence of network-HK; Lemmas 2 and 3 establish high-probability convergence for random-HK. These are results about the dynamics, not classifications of a computational problem by input size, exact or approximate algorithms, or parameterized complexity. Theorem 1 is the closest candidate because it bounds the number of rounds, but it analyzes a fixed protocol using a spectral parameter; it does not pose a separate computational task. The experiments do not fill that gap.
The proposed Type-FJ-Equilibrium is a plausible high-multiplicity model, but it does not mirror Theorem 1’s main result. It asks for the FJ fixed point, whereas Theorem 1 concerns the expected trajectory of LIP-FJ, where each agent samples one neighbor and mixes that opinion with her previous one. If the question is only about expected type opinions, the paper’s recurrence already reduces it to a deterministic system on those opinions. If the question preserves the randomness, a type generally needs a distribution of opinions over time, not just the single value \(x_t^*\). Either formulation can be studied, but neither supplies the missing complexity anchor.
There is also a real aggregation condition behind that candidate. In the paper’s network model, agents have individual influence weights. To represent many agents by a few types while keeping the dynamics exact, members of a type must have compatible influence across types—for example, through an equitable partition of the network. In an arbitrary network, describing those influence patterns can make each agent its own type, leaving no useful multiplicity reduction. Large communities with repeated roles and balanced interactions are plausible; in those cases, however, the paper’s central question about local-network convergence becomes a question about a restricted quotient system.
Theorem 2 has the same anchor problem, and its network structure makes a simple mass model especially incomplete. A distribution over opinions alone loses the social edges that determine which agents can influence each other; the paper’s results and experiments show those edges affect clustering and convergence. A more faithful continuum model could retain a type-level network structure or use a graph limit, but that would yield a new measure-valued dynamical system and new convergence questions, not a computational mirror of Theorem 2. The random-HK lemmas likewise concern convergence of a stochastic process. Preserving them continuously requires tracking how sampling shapes the distribution of opinions, rather than just tracking a fixed finite list of type averages.
A stronger proposal would be a control problem: in a large organization with repeated social roles, find the smallest population share of “seed” or stubborn agents needed to move the eventual opinion distribution into a target range. That could be worthwhile research. But it adds an intervention, a cost, and a target absent from this paper. It is a new problem inspired by opinion dynamics, not a continuation of a named computational result in the paper.
So the negative case is strong against treating this as an anchored computational continuization: none of the named results provides the required complexity problem. It is not strong enough to establish the universal claim that no worthwhile continuous-population research could arise in any scenario. The control direction, in particular, remains plausible; it just cannot rescue this paper as a mirror of its stated results.
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.