| paper | d4-conf-ecai-2014-0236 |
| 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 for \(m=1\); every instance satisfying the stated hypotheses admits the feedback \(U(t,y)=x^\star-y_r\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finitely many types \(a\in T\) with rational masses \(\mu_a>0\), \(\sum_a\mu_a=1\), a symmetric interaction matrix \(q_{ab}\), parameters \(b>c>0\) and \(\beta>0\), initial states \(y_a(0)\in[0,1]\), a target \(x^\star\in[0,1]\), and a controllable type \(r\) with \(\mu_r>0\), define \(d_a=\sum_b\mu_bq_{ab}\), \(F_a(y)=-cd_ay_a+b\sum_b\mu_bq_{ab}y_b\), \(p_{ab}(y)=q_{ab}\sigma(\beta(F_b(y)-F_a(y)))\), and \(g_a(y)=d_a^{-1}\sum_b\mu_bp_{ab}(y)(y_b-y_a)\), where \(\sigma(z)=(1+e^{-z})^{-1}\). With the type-interaction graph connected and every \(d_a>0\), the dynamics are \(\dot y_a=g_a(y)+\mathbf{1}_{a=r}u_r(t)\), with the same signal applied to all members of type \(r\). Construct an admissible feedback \(u_r(t)\) that ensures \(\lim_{t\to\infty}y_a(t)=x^\star\) for every type \(a\).
A finite-support mean-field CAIPD network with type masses \(\mu_a\), shared type states \(y_a\), and interaction rates \(q_{ab}\); the decision is a feedback signal applied uniformly to one positive-mass type, and the objective is convergence of every type state to \(x^\star\).
The paper's sparse small-world and scale-free experiments feature local neighborhoods and hubs that a fixed-support dense block model need not preserve.
fatal: False
The mirror extends Theorem 1's agreement reachability from one controlled individual to a positively weighted type; it leaves the iterative optimal-control algorithm and the empirical comparisons across sparse network structures aside.
The strongest honest case is narrow: this paper has no named result classifying computational complexity. Its one useful anchor is Theorem 1, proved here, which is a formal control result rather than a \(P\), NP-hardness, or parameterized-complexity result. The theorem says that in the finite CAIPD network with external control, from any initial state and for any target agreement \(x^\star\in[0,1]\), a controller acting on one individual can make every individual converge to \(x^\star\). It gives the control law \(u=B^{T}L_kx-\epsilon\,\operatorname{sgn}(e)\) when \(e=x_c-x^\star\ne0\), and \(u=B^{T}L_kx\) when \(e=0\), for any \(\epsilon>0\). The first part drives the controlled individual to the target; the second holds it there while the rest of the network converges.
A plausible high-multiplicity regime is a large network of firms considering a green technology, like the paper’s motivating example. Firms fall into a small number \(\tau\) of sector or market-role types: firms of a type have the same initial cooperation level, the same access to external influence, and the same interaction profile with every other type. There may be millions of firms but only a few such types. Here mass means the fraction of firms in each type. This scenario keeps the paper’s core ingredients—cooperation levels, peer influence, and external control—while treating the population, rather than each named firm, as the object.
One mirror would be Type-Mass CAIPD Agreement Reachability. An instance consists of positive rational type masses \(\mu_a\) summing to one; a symmetric interaction matrix \(q_{ab}\); CAIPD parameters \(b>c>0\) and \(\beta>0\); initial cooperation levels \(y_a(0)\in[0,1]\); a target \(x^\star\in[0,1]\); and one controllable type \(r\) of positive mass. Let \(d_a=\sum_b\mu_bq_{ab}\) and \(F_a(y)=-c\,d_a y_a+b\sum_b\mu_bq_{ab}y_b\). Define \(p_{ab}(y)=q_{ab}\sigma(\beta(F_b(y)-F_a(y)))\), with \(\sigma\) the logistic function, and the uncontrolled type drift
\[
g_a(y)=\frac{1}{d_a}\sum_b\mu_b p_{ab}(y)(y_b-y_a).
\]
The dynamics are \(\dot y_a=g_a(y)+\mathbf{1}_{a=r}u_r(t)\). The question is: given a connected type-interaction graph, produce an admissible feedback control for type \(r\) such that \(y_a(t)\to x^\star\) for every type \(a\). A solution is the feedback law and a proof of convergence. The direct mirror of the theorem’s law cancels \(g_r(y)\), drives \(y_r\) toward \(x^\star\) at rate \(\epsilon\), then holds it there. With positive interaction along the connected type graph, the other types continue to imitate through the network and converge to the held target.
I expect this finite-support reachability question to be tractable in a constructive sense: the controller has a description in \(\tau\), rather than in the number of firms, and follows the paper’s structural argument. A formal bit-complexity claim would need a specified numerical precision model for evaluating the sigmoid and the dynamics; neither this proposed result nor Theorem 1 supplies one. Natural follow-up questions include minimum-effort control, choosing which types to control when signals have costs, and how well the type-mass system approximates a large finite network.
The weak point is substantial. The theorem controls one named individual, whose mass vanishes in the continuum. My mirror instead gives a common signal to a positive-mass type. That is a meaningful model when a regulator can influence a whole sector or cohort, but it changes the control-access assumption; if each firm has a unique interaction profile, the number of types may grow with the population and the simplification disappears. And because the paper proves reachability rather than a complexity bound, this is a credible continuous-population control problem, but not evidence that a discrete hardness result dissolves.
The only anchor is Theorem 1, and it is a reachability theorem in control theory, not a computational-complexity result. Its question is whether an arbitrary agreement can be reached when a controller may act on one node; under the theorem’s assumptions it gives a feedback law that does so. There is no encoded decision or optimization problem whose complexity the theorem classifies.
The proponent’s best repair is coherent: use a dense block network of firms, let each type share an interaction profile and cooperation state, and broadcast the control signal to a positive-mass type. Granting that model, write its uncontrolled drift as \(g(y)\). The controller can set \(u_r=-g_r(y)-\epsilon\,\operatorname{sgn}(y_r-x^\star)\) until type \(r\) reaches \(x^\star\), then set \(u_r=-g_r(y)\) to hold it there. Under suitable connectivity conditions, the same pinning and consensus argument applies. That is a sensible continuous-population control model, but the theorem’s mirror remains a direct analytic adaptation of an explicit feedback law. Turning it into a ChoCo problem would require adding a finite-horizon or minimum-effort objective, or a search over which types to control. Those could be worthwhile questions, but they are new optimization problems, not mirrors of Theorem 1’s result.
There is also a fidelity cost to that repair. The paper’s experiments use sparse small-world and scale-free networks with average degree four, where hubs and local connections matter. At fixed type support, a deterministic type-level interaction matrix does not generally preserve those sparse neighborhoods as the population grows; replacing them with dense block interactions gives a clean mean-field model, but changes the network regime. Preserving detailed neighborhoods may instead require the number of types to grow with the population. This is not a fatal objection to the proposed dense-block scenario; it limits how much of the paper’s network result that scenario actually mirrors.
So the negative case is strongest as a scope judgment: this paper offers a plausible continuous control model, but no strong computational result for ChoCo to continuize. It is not airtight as a claim that no useful type-mass control question could ever arise. A finite-type, budgeted intervention problem might be worth studying; the paper simply does not establish that problem as its computational contribution.
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.