| paper | d4-journals-geb-2018-0114 |
| 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 · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given finite sets of types \(T\) and states \(\Omega\), rational type masses \(\mu_a\) summing to \(1\), rational full-support initial beliefs \(q_{a,0}\), and a rational interaction matrix \(W\) for which \(A_{ab}=W_{ab}\mu_b\) is primitive, compute the limiting consensus mode \(\arg\max_{\omega\in\Omega}\sum_{b\in T}\lambda_b\log q_{b,0}(\omega)\), where \(\lambda\) is the normalized positive left Perron–Frobenius eigenvector of \(A\). Assume the maximizing state is unique with a supplied rational score-gap lower bound, and determine the computation’s dependence on \(|T|\), \(|\Omega|\), input bit length, and the gap.
A nonatomic population represented by finitely many belief and interaction types, with each type \(a\) carrying mass \(\mu_a\), initial belief \(q_{a,0}\), and interaction intensities \(W_{ab}\). Type \(a\)’s update weights type \(b\)’s belief by \(A_{ab}=W_{ab}\mu_b\); the question is to compute the limiting consensus state. Agents are nonstrategic, so the limit does not replace an atomic strategic equilibrium with a different solution concept.
The paper gives no algorithm or complexity bound, so whether its explicit limit characterization should count as a computational result is the remaining point of doubt.
fatal: False
The mirror covers Proposition 1’s limiting-consensus prediction for finite interaction-class populations; it leaves the comparative statics in Propositions 2 and 3 and the wise-network learning claim in Proposition 4 outside its scope.
The strict anchor requirement blocks a fully compliant positive case: this paper has no named result about a problem being in P, NP-hard, FPT, or otherwise computationally classified.
The closest result is Proposition 1, proved in the paper. It says that if the network matrix \(T\) is connected and aperiodic, the initial beliefs have full support, and the \(\alpha\)-weighted product of initial beliefs has a unique maximizer, then everyone’s beliefs converge to a degenerate belief on that maximizer; \(\alpha\) is parallel to the Perron–Frobenius eigenvector of \(T\). That is a convergence characterization, not a complexity result. Proposition 4 is also about convergence, not complexity. So neither supplies an eligible anchor, and I would not present either as establishing an algorithmic classification.
The strongest positive *prospect* is a continuum version of Proposition 1 for large, dense communities with a small number of belief and interaction classes. A type \(a\) would specify an initial posterior \(q_{a,0}\) and its interaction profile; \(\mu_a\) would be its population share. With a finite state set \(\Omega\) and a rational matrix \(W\) of type-to-type interaction intensities, define \(A_{ab}=W_{ab}\mu_b\) and update by
\[
q_{a,k+1}(\omega)=
\frac{\exp\!\left(\sum_b A_{ab}\log q_{b,k}(\omega)\right)}
{\sum_{v\in\Omega}\exp\!\left(\sum_b A_{ab}\log q_{b,k}(v)\right)}.
\]
A concrete computational question is: given rational \(\mu\), full-support rational initial beliefs, and primitive \(A\), compute the limiting consensus mode. If \(\lambda\) is the positive left Perron–Frobenius eigenvector of \(A\), normalized to sum to one, the candidate mode is
\[
\arg\max_{\omega\in\Omega}\sum_b\lambda_b\log q_{b,0}(\omega).
\]
One could ask for an approximation to these scores, and for the mode when the top-score gap is promised. The expected direction is tractability through Perron–Frobenius computation and numerical approximation; further questions concern the dependence on the spectral gap and how the problem behaves as the number of types grows.
This scenario is plausible for a large forum or repeated communication setting with many users but relatively few shared belief and contact classes. Its weak point is also decisive for the requested analysis: it replaces the paper’s finite network with a dense, mass-normalized interaction model. That is a credible population-continuum extension of the paper’s dynamics, but Proposition 1 does not anchor a computational-complexity question about it. Under the stated anchor rule, the paper offers no named computational result to mirror.
The proponent’s opening concession is decisive for ChoCo’s stated remit: the paper has no named computational result to mirror. Proposition 1 characterizes limiting beliefs; Propositions 2 and 3 give comparative statics, and Proposition 4 gives a learning condition. None studies the complexity of a decision, optimization, or manipulation problem. So Proposition 1 cannot anchor the kind of computational-complexity mirror the programme is building.
The proposed type model makes sense under a strong homogeneous-interaction assumption. In the cleanest case—a complete network—types can be initial posteriors, and the limit mode is determined by maximizing \(\sum_a \mu_a\log q_{a,0}(\omega)\). That is a sound continuous-population version of the paper’s convergence result. But asking for an algorithm to compute that prediction adds a computational task the paper did not pose; it still concerns belief dynamics, not computational social choice. Turning it into a campaign or intervention problem would add further primitives and a new objective, rather than mirror a result in this paper.
There is also a fidelity tradeoff in the proposed \(A_{ab}=W_{ab}\mu_b\) model. In the paper, the relevant Perron–Frobenius weights come from the individual network. In sparse networks, agents with the same beliefs can have different network positions, and grouping them by belief loses information needed to preserve those weights. Types that encode enough of each agent’s interaction structure may have support growing with the population. A finite-class interaction matrix avoids that problem by imposing a particular block structure; it is a plausible model, but it is a substantive restriction on the network.
I would therefore reject this as a worthwhile ChoCo complexity mirror, while acknowledging that it is a legitimate continuous analytical extension. The negative case is strongest on programme fit, not on the claim that no useful continuous study of this model could exist: a homogeneous-population mirror of Proposition 1 plainly can. That possibility does not supply the missing computational-social-choice result.
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.