| paper | d4-conf-aaai-2017-0352 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given a two-name complete-graph Naming Game with all ordinary agents initially holding \(\{1\}\), a rational stubborn-mass budget \(q\), tolerance \(\epsilon\), and finite horizon \(H\), what is the minimum mass \(p\le q\) to convert into stubborn agents holding \(\{0\}\) so that, under the induced mass-action flow, the mass of ordinary agents whose inventories still contain \(1\) is at most \(\epsilon\) at time \(H\)?
A distribution over ordinary inventory types and a fixed stubborn type, with mass as the population measure. Uniform pairwise interactions induce an ODE for the type masses; the decision variable is the stubborn mass \(p\), and the objective is to minimize \(p\) subject to the finite-horizon residual-mass constraint.
The concrete two-name instance may reduce to constant-dimensional ODE evaluation, leaving substantial complexity questions dependent on variable names or type structure; the proponent identifies that broader version but does not establish its complexity.
fatal: False
The mirror covers Theorem 5.1’s late manipulation result on complete graphs; it leaves the topology comparisons, community-structure results, and early stubborn-node findings aside.
The strongest mirror is the paper’s complete-graph manipulation result, Theorem 5.1, proved in this paper. After the Naming Game has converged to name \(1\), stubborn agents favoring name \(0\) are introduced. The theorem says there is a constant \(p_0\approx0.108\) such that, with a fraction \(p<p_0\) of stubborn agents, the expected time to consensus is \(\exp(\Omega(n))\); with \(p_0<p\le1\), for every \(\epsilon>0\), the fraction of the original opinion falls below \(\epsilon\) after \(O(n)\) steps. The paper gives no standard P/NP-hardness classification, so this expected-runtime threshold is its most relevant named computational anchor.
A plausible high-multiplicity regime is a large language-learning or collaboration platform that pairs users uniformly to negotiate a shared label. Many users start with the same label and follow the same update rule; a controlled group persistently promotes another. Their complete types are their current inventory and whether they are stubborn. For the two-name case, the relevant types are ordinary users with inventories \(\{0\}\), \(\{1\}\), or \(\{0,1\}\), and stubborn users fixed at \(\{0\}\). The population may have millions of users but only these few types, so mass is a natural measure of influence. This keeps the inventories and pairwise update rule that define the paper’s problem; it does not replace the Naming Game with a simpler opinion-voting process.
I would pose the mirror as the finite-horizon mean-field stubborn-control threshold. Its input is a rational control budget \(q\), target tolerance \(\epsilon\), and horizon \(H\), measured in interactions per capita. At time zero, a chosen mass \(p\le q\) of the population is converted from ordinary users holding only \(\{1\}\) into stubborn users holding only \(\{0\}\); the rest begin with \(\{1\}\). The complete-graph interaction rule induces a mass-action flow \(x(s)\): its state records the mass of each type, and its rate of change is the expected inventory update under uniformly sampled pairwise interactions. Let \(R_1(H)\) be the mass of ordinary users whose inventory still contains name \(1\). The question is: does there exist \(p\le q\) such that \(R_1(H)\le\epsilon\)? A solution is a yes/no answer, with a witnessing mass \(p\) for yes. The optimization version returns the least such \(p\). A \(\delta\)-approximation version can handle cases where the threshold is close to the tolerance boundary.
This is a plausible continuous form of the authors’ question: how much control is needed to change the convention after consensus? In the continuum, one unit of time corresponds to order \(n\) pairwise interactions in the finite process, so the theorem’s \(O(n)\)-step side motivates a finite \(H\). I would expect the fixed two-name, complete-graph version to be tractable: it has a constant number of mass variables and a rationally specified polynomial vector field. The broader version, with a variable number \(\tau\) of types and rational contact rates, is open; its complexity in \(\tau\), bit length \(L\), and \(H\) is the computational question to study. Further questions include approximating the least control mass, extending the model to multiple names, and identifying which contact structures preserve tractability.
The mirror covers Theorem 5.1, not the paper’s claims about stars, trees, or community structure. Its main weakness is also central to the connection: the continuum flow suppresses the rare stochastic fluctuations that let a finite population escape a metastable state. Thus the theorem’s exponential expected time does not itself prove that the continuum threshold equals \(p_0\), or establish a complexity classification for the proposed problem. It does, however, give a strong reason to study the continuous mass dynamics: the paper’s own analysis ties its runtime threshold to a stable mean-field state.
Theorem 5.1 is the strongest anchor, and its population has a natural high-multiplicity regime: in a large, uniformly mixed population, users with the same inventory and protocol are interchangeable. There is no convincing objection based on mass, identity, or an implausible scenario.
The proposed finite-horizon question is well-defined, but it moves away from the theorem’s distinctive result. The theorem separates an exponentially long stochastic escape from convergence in \(O(n)\) steps. On the per-capita time scale, the mean-field model suppresses the rare fluctuations responsible for that escape. Requiring only that the mass retaining name \(1\) fall below \(\epsilon\) by a finite horizon avoids the issue, but asks a different question. For the fixed two-name complete-graph case, the resulting model has a constant number of state variables and a single control parameter \(p\). Its computation is chiefly evaluation of a small mass-action system, not a complexity landscape whose difficulty arises from population multiplicity.
A stronger mirror could optimize how stubborn mass is allocated across many inventory types and interaction classes. That could become computationally interesting, but its hard input would be the number of names, types, or network classes. To preserve richer graph structure, types may also need to distinguish agents by their interaction neighborhoods, potentially removing the small-support advantage. This is a plausible research direction in computational control of population dynamics; it is harder to present as a continuous mirror of the paper’s named result or as a fit for ChoCo’s focus on computational social choice. The paper studies convention dynamics, with no preference aggregation or social choice rule, and its proof already develops the relevant mean-field system analytically.
So the negative case has a real weakness: a worthwhile continuous control problem can be formulated, and the paper’s own mean-field analysis supports the regime. What the evidence supports is narrower: the direct mirror of Theorem 5.1 appears too small and too close to a fixed ODE to deliver the programme’s intended complexity contribution. That does not establish that every richer mirror is unworthwhile.
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.