d4-conf-sagt-2012-0017

The strongest mirror I see is the slow-mixing result for the complete bipartite graph. Its appeal is that the population really does have two repeated roles, so the continuous model can preserve the paper’s opinion game and its network interactions.

Anchor: Theorem 4.13, proved in this paper. It states that on \(K_{m,m}\), there are choices of internal beliefs and edge weights for which, for every \(\beta=\Omega(1/m)\), the logit dynamics has mixing time at least \(e^{\beta\Theta(\mathrm{CW})}/n\), where \(\mathrm{CW}\) is the graph’s cutwidth and \(n=2m\). In the proof’s instance, all beliefs are \(1/2\) and all edges have equal unit weight. Since the cutwidth is \(\Theta(m^2)\), taking \(\beta=c/m\) for a sufficiently large constant \(c\) gives an exponential lower bound in \(m\), up to the polynomial factor \(n\).

My proposed continuous problem is Mean-Field Logit Barrier. There are two types, \(A\) and \(B\), each with mass \(\mu_A=\mu_B=1/2\). Type records an agent’s belief and network role: each \(A\)-agent interacts uniformly with the \(B\) population, and vice versa. All agents have belief \(1/2\) and two actions, opinions \(0\) and \(1\). Let \(q_A,q_B\in[0,1]\) be the fractions of each type playing \(1\). For \(N=2m\) agents, give each cross-type edge weight \(1/m=2/N\), so each agent’s total interaction weight stays bounded as the population grows. The type masses remain fixed while \(N\) grows.

More generally, for finite support \(T\), rational masses \(\mu_t\), beliefs \(b_t\), and a symmetric nonnegative interaction matrix \(J\), define \(q_t\) as the fraction of type \(t\) playing \(1\), and set
\[ \phi(q)= \sum_t\mu_t\bigl((1-q_t)b_t^2+q_t(1-b_t)^2\bigr) +\frac12\sum_{t,u}\mu_t\mu_uJ_{tu} \bigl(q_t(1-q_u)+(1-q_t)q_u\bigr), \]
\[ F_\beta(q)=\phi(q)-\frac1\beta\sum_t\mu_t h(q_t), \qquad h(z)=-z\log z-(1-z)\log(1-z). \]
Here \(\phi\) is the limiting potential per agent, and the entropy term accounts for the number of individual action profiles represented by each type-level mass vector. For the \(K_{m,m}\) instance above, \(T=\{A,B\}\), \(b_A=b_B=1/2\), and \(J_{AB}=J_{BA}=2\).

Given rational input for this model, a rational \(\beta\), and two rational boxes promised to isolate distinct local minima \(q^-\) and \(q^+\) of \(F_\beta\), the problem asks for an additive-\(\epsilon\) approximation to
\[ B_\beta(q^-,q^+)= \inf_{\substack{\gamma\in C([0,1],[0,1]^\tau)\\ \gamma(0)=q^-,\ \gamma(1)=q^+}} \ \max_{s\in[0,1]}F_\beta(\gamma(s)) -\min\{F_\beta(q^-),F_\beta(q^+)\}. \]
A solution is a value within \(\epsilon\) of this barrier; a path attaining the upper bound within \(\epsilon\) would make the answer more useful. This is a question about the continuous population’s macroscopic opinion masses and the computation of the bottleneck between free-energy wells.

I expect the fixed two-type member to be tractable: it is a fixed-dimensional barrier problem and admits additive approximation by discretizing the square and searching for a lowest-height connecting path. For variable support \(\tau\), I would leave the complexity open; this anchor gives no basis for claiming transferred discrete hardness or continuum-specific hardness. The \(K_{m,m}\) result is the low-noise instance to mirror: with the edge weights normalized by \(1/m\), the choice \(\beta=c/m\) in the paper corresponds to constant \(\beta=c\) here. The finite chain’s exponential lower bound is therefore evidence that a positive macroscopic barrier can survive continuization.

I think the authors would recognize this as their problem: it keeps their two opinions, belief costs, network interaction, logit equilibrium, and the mixing bottleneck. It also makes the population continuous: \(q_A\) and \(q_B\) are fractions of mass, while each individual still chooses an integral opinion. The broader questions are whether the barrier determines the limit of \(N^{-1}\log t_{\mathrm{mix}}\), whether its computation is fixed-parameter tractable in \(\tau\), and how the barrier changes across the high-noise regime of Theorem 4.9.

The weak point is that Theorem 4.13 proves a finite-chain mixing lower bound, not an equivalence between its mixing exponent and this free-energy barrier. Establishing that equivalence is necessary before the barrier can be called a theorem-level mirror. This case covers Theorem 4.13’s two-cohort slow-mixing regime; it does not mirror the paper’s best-response results or its bounds for arbitrary network topologies.