Answer: polynomial-time solvable
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a symmetric graph G of n nodes, the maximization of fp′(GS, 0) can be done in O(n2ω) time, where ω is the matrix-multiplication exponent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite role set \(R\), rational role masses \(\mu\), a rational reversible symmetric block-interaction kernel \(Q\), and a rational intervention budget \(\alpha\), construct the canonical \(N\)-agent exchangeable block lift with \(N\mu_r\) agents of role \(r\) and choose \(N b_r\) biased target agents from role \(r\), with \(0 \le b_r \le \mu_r\) and \(\sum b_r \le \alpha\). Define \(\Phi(\mu,Q,b)\) as the limit, over compatible \(N\), of the derivative at \(\delta=0\) of the paper's one-random-mutant fixation probability, taking the derivative before \(N\) tends to infinity. Compute a feasible mass vector \(b\) maximizing \(\Phi\).
A society is given by its support: the list of the \(\tau\) roles with positive masses \(\mu_r\), each a binary rational, with \(\sum_r\mu_r=1\). Here \(m=|R|=\tau\); support size means listed positive-mass types, not all possible types. Let \(L\) be the total input bit length.
The interaction kernel is a nonnegative rational symmetric matrix \(Q\), with connected positive-entry support and \(d_r=\sum_s\mu_sQ_{rs}>0\). Its induced role transition matrix \(P_{rs}=\mu_sQ_{rs}/d_r\) is reversible.
Given a rational budget \(0\leq\alpha\leq1\), a feasible intervention is a rational vector \(b\) satisfying \(0\leq b_r\leq\mu_r\) and \(\sum_r b_r\leq\alpha\).
For every sufficiently large integer \(N\) with all \(N\mu_r,Nb_r\) integral, form a population with \(N\mu_r\) agents of role \(r\). Every ordered pair of agents of roles \(r,s\), including an agent paired with itself, has interaction weight \(Q_{rs}\); designate any \(Nb_r\) agents of role \(r\) as biased, forming \(S_N\).
Initially exactly one uniformly random agent carries \(A\), and all others carry \(B\). At each step choose a target \(u\) uniformly, then let it copy a source \(v\), sampled with probability proportional to \(Q_{r(u),r(v)}(1+\delta\mathbf1_{u\in S_N}\mathbf1_{v\text{ carries }A})\), where \(\delta\geq0\).
Let \(F_N(\delta,b)\) be the probability of eventually reaching all \(A\), and define \(\Phi(\mu,Q,b)=\lim_{N\to\infty}\left.\frac{\partial F_N(\delta,b)}{\partial\delta}\right|_{\delta=0^+}\), along these compatible integers, with no additional rescaling.
Is computing a feasible \(b\) maximizing \(\Phi(\mu,Q,b)\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite connected graphs with symmetric interaction weights, exact maximization of the corresponding fixation derivative is possible in \(O(n^{2\omega})\) arithmetic operations, where \(\omega\) is the matrix-multiplication exponent ([source](https://arxiv.org/pdf/2211.14676)).
No result settling this precise distributional limit optimization was located in the literature search.
The problem is solvable exactly in polynomial time. An optimal intervention fills roles in decreasing order of \(d_r=\sum_s\mu_sQ_{rs}\).
More precisely, define
\(D=\sum_r\mu_r d_r\) and \(K=\sum_r\mu_r d_r^2\).
Then the specified limit exists for every feasible rational intervention, and
\(\displaystyle \boxed{\Phi(\mu,Q,b)=\frac{D}{2K}\sum_r b_r d_r.}\)
Thus the objective is linear, with coefficients proportional to the weighted role degrees.
The supplied [finite-graph result, Theorem 5](https://arxiv.org/pdf/2211.14676), establishes polynomial-time optimization at fixed population size. The proof below establishes and evaluates the distributional limit directly.
Fix a compatible population size \(N\). Write \(r(u)\) for agent \(u\)'s role. Its neutral source-selection probabilities are
\(\displaystyle W_{uv}=\frac{Q_{r(u),r(v)}}{N d_{r(u)}}.\)
Define agent weights
\(\displaystyle \pi_u=\frac{d_{r(u)}}{ND}.\)
They sum to one and satisfy detailed balance:
\(\displaystyle \pi_uW_{uv}=\frac{Q_{r(u),r(v)}}{N^2D}=\pi_vW_{vu}.\)
Consequently, \(\pi W=\pi\).
For the analysis, give each agent an independent rate-one update clock. The resulting continuous-time process has exactly the same fixation probabilities as the stated discrete-time process: its update events select targets uniformly and use the same copying rule. This changes only the time parametrization.
For a configuration \(x\in\{0,1\}^N\), let
\(\displaystyle a_u(x)=\sum_vW_{uv}x_v,\qquad h_0(x)=\sum_u\pi_u x_u.\)
At neutrality, the generator satisfies
\(\displaystyle \mathcal L_0h_0(x)=\sum_u\pi_u(a_u(x)-x_u)=0,\)
by stationarity of \(\pi\). Moreover, \(h_0\) equals zero at all \(B\) and one at all \(A\). Hence it is the neutral fixation probability.
To justify this identification and subsequent differentiation, the lifted agent graph is connected. Indeed, positive role edges connect every pair of role classes along role paths; agents in the same class can also connect through such paths. In the single-role case, \(d_r>0\) implies \(Q_{rr}>0\). From any nonconsensus configuration, a finite sequence of positive-probability copying events propagates one existing opinion along a spanning tree to consensus. Since the state space is finite, all nonconsensus states are transient and have finite mean absorption time.
For a biased target, its probability of carrying \(A\) immediately after an update is
\(\displaystyle \frac{(1+\delta)a_u(x)}{1+\delta a_u(x)}.\)
Its derivative at zero is \(a_u(x)(1-a_u(x))\). Therefore,
\(\displaystyle \left.\frac{\partial}{\partial\delta}\mathcal L_\delta h_0(x)\right|_{\delta=0} =\sum_{u\in S_N}\pi_u a_u(x)(1-a_u(x)).\)
The finite-state fixation equations are differentiable near zero. To see this, their coefficients are rational functions of \(\delta\), analytic near zero, and their transient-state matrix is invertible at zero. Differentiating these equations gives the Poisson equation for the fixation derivative. Its occupation-time representation yields
\[\displaystyle F_N'(0,b) =\int_0^\infty \mathbb E_0\!\left[\sum_{u\in S_N}\pi_u a_u(X(t))(1-a_u(X(t)))\right]\,dt,\tag{1}\]
where \(\mathbb E_0\) includes the uniformly random initial singleton. Thus (1) does not require interchanging differentiation with an infinite-time limit.
Under neutrality, copying events can be represented by arrows from sources to targets. Tracing an agent's ancestry backward gives a continuous-time walk with rate-one source draws from \(W\). Two ancestral walks evolve independently until they meet, after which they share one lineage.
Let \(T_{vw}\) be their coalescence time when started at agents \(v,w\), with \(T_{vv}=0\). Connectedness gives finite mean coalescence times: one walker can follow a path to the other while that other walker stays in place, so the absorbing diagonal is reachable from every pair state.
At time zero there is exactly one uniformly chosen \(A\)-agent. Conditional on the genealogical arrows, both agents at time \(t\) carry \(A\) precisely when their ancestral lineages have coalesced and the common ancestor is that initial agent. Consequently,
\(\displaystyle \mathbb E_0[X_v(t)X_w(t)] =\frac1N\Pr(T_{vw}\le t),\qquad \mathbb E_0[X_v(t)]=\frac1N.\)
Expanding \(a_u(1-a_u)\), using that the rows of \(W\) sum to one, gives
\(\displaystyle \mathbb E_0[a_u(X(t))(1-a_u(X(t)))] =\frac1N\sum_{v,w}W_{uv}W_{uw}\Pr(T_{vw}>t). \)
Substitution into (1), followed by integration of the nonnegative terms, gives the exact identity
\[\displaystyle F_N'(0,b)=\frac1N\sum_{u\in S_N}\pi_u \sum_{v,w}W_{uv}W_{uw}\mathbb E[T_{vw}]. \tag{2}\]
For sufficiently large compatible \(N\), every role has at least two agents. For these \(N\), let \(H_N(r,s)\) be the mean coalescence time of two distinct agents of roles \(r,s\). This is well defined by permutation symmetry within roles. In particular, \(H_N(r,r)\) refers to distinct agents of the same role.
Two independent source draws by a role-\(r\) target have roles \(s,t\) with probability \(P_{rs}P_{rt}\). Conditional on \(s=t\), they select the same agent with probability \(1/(N\mu_s)\); that pair has coalescence time zero. Thus (2) becomes
\[\displaystyle F_N'(0,b)= \sum_r\frac{b_r d_r}{D} \sum_{s,t}P_{rs}P_{rt} \left(1-\frac{\mathbf1_{\{s=t\}}}{N\mu_s}\right) \frac{H_N(s,t)}N. \tag{3}\]
Here we used \(\sum_{u\in S_N:r(u)=r}\pi_u=b_r d_r/D\). This also shows that the choice of designated agents within each role does not affect the derivative.
Consider functions \(f\) on the \(m^2\) ordered role pairs. Define
\(\displaystyle (Af)_{rs} =\sum_tP_{rt}(f_{ts}-f_{rs}) +\sum_tP_{st}(f_{rt}-f_{rs}). \)
This is the generator of two independent role walks, each with rate-one source draws.
Define another linear operator by
\(\displaystyle (Bf)_{rs} =\frac{Q_{rs}}{d_r}f_{ss} +\frac{Q_{sr}}{d_s}f_{rr}. \)
The generator of the role-pair process killed upon agent-level coalescence is
\(\displaystyle A-\frac1N B.\)
Indeed, when the first lineage has role \(r\) and the second has role \(s\), the first selects the exact agent occupied by the second at rate \(Q_{rs}/(Nd_r)\). The independent role generator would assign this event successor value \(f_{ss}\), whereas the killed process assigns value zero. Subtracting this contribution, and its counterpart for the second lineage, gives the stated operator. This reasoning also applies when \(r=s\).
Let \(\mathbf1\) denote the constant-one vector and \(M=-A\). The backward equations for mean coalescence time are therefore
\[\displaystyle \left(M+\frac1N B\right)H_N=\mathbf1.\tag{4}\]
We now prove the required limit from this fixed-dimensional system.
The stationary role distribution is
\(\displaystyle \rho_r=\frac{\mu_r d_r}{D}.\)
Indeed,
\(\displaystyle \rho_rP_{rs}=\frac{\mu_r\mu_sQ_{rs}}D=\rho_sP_{sr}.\)
The product generator \(A\) has stationary row vector
\(\displaystyle \nu_{rs}=\rho_r\rho_s.\)
The role chain is irreducible because the positive-entry support of \(Q\) is connected and every \(\mu_r\) is positive. The product generator is also irreducible: each coordinate can follow any role path while the other remains fixed. Hence
\(\displaystyle \ker M=\operatorname{span}\{\mathbf1\},\qquad \nu M=0,\qquad \nu\mathbf1=1.\)
For completeness, the kernel assertion follows from the maximum principle: if \(Af=0\), at a state maximizing \(f\), every positive-rate successor must have the same value. Irreducibility propagates that equality to every state.
Set \(\varepsilon=1/N\) and \(h_N=H_N/N\). Equation (4) becomes
\[\displaystyle (M+\varepsilon B)h_N=\varepsilon\mathbf1.\tag{5}\]
Multiplying by \(\nu\) gives the exact normalization
\[\displaystyle \nu Bh_N=1.\tag{6}\]
Define
\(\displaystyle \kappa=\nu B\mathbf1.\)
Stationarity of \(\rho\) gives
\[\displaystyle \kappa =2\sum_{r,s}\rho_r\rho_s\frac{Q_{rs}}{d_r} =2\sum_s\frac{\rho_s}{\mu_s}\sum_r\rho_rP_{rs} =2\sum_s\frac{\rho_s^2}{\mu_s} =\frac{2K}{D^2}>0. \tag{7}\]
Introduce the matrix \(J=M+\mathbf1\nu B\). It is invertible: if \(Jf=0\), multiplying by \(\nu\) gives \(\nu Bf=0\), and then \(Mf=0\). Thus \(f=c\mathbf1\), and \(0=\nu Bf=c\kappa\) implies \(f=0\).
Adding \(\mathbf1\) times (6) to (5) yields
\(\displaystyle (J+\varepsilon B)h_N=(1+\varepsilon)\mathbf1.\)
Since \(J\) is invertible, matrix inversion is continuous for sufficiently small \(\varepsilon\). Moreover, \(J(\mathbf1/\kappa)=\mathbf1\). Consequently,
\[\displaystyle \boxed{\lim_{N\to\infty}\frac{H_N(r,s)}N =\frac1\kappa=\frac{D^2}{2K}} \quad\text{for every }r,s. \tag{8}\]
This argument requires no population-size bound or mixing estimate uniform across input instances.
The sums in (3) contain only finitely many role pairs. By (8), each normalized coalescence time tends to \(D^2/(2K)\). Also,
\(\displaystyle 1-\frac{\mathbf1_{\{s=t\}}}{N\mu_s}\longrightarrow1, \qquad \sum_{s,t}P_{rs}P_{rt}=1. \)
Taking limits in (3) therefore proves
\(\displaystyle \Phi(\mu,Q,b) =\sum_r\frac{b_r d_r}{D}\frac{D^2}{2K} =\frac{D}{2K}\sum_r b_r d_r. \)
The argument applies along every compatible sequence of integers. Such sequences exist because all masses and intervention coordinates are rational.
As a normalization check, if \(Q_{rs}=1\) for every pair, then every \(d_r=1\) and \(D=K=1\), so \(\Phi(\mu,Q,b)=\frac12\sum_r b_r\).
Since \(D/(2K)>0\), it suffices to maximize \(\sum_r d_r b_r\).
Sort the roles so that \(d_{r_1}\ge d_{r_2}\ge\cdots\ge d_{r_m}\), and set
\[\displaystyle b_{r_i}^*= \min\!\left\{\mu_{r_i}, \max\!\left\{0,\alpha-\sum_{j<i}\mu_{r_j}\right\}\right\}. \tag{9}\]
This vector is rational, respects every capacity, and uses total budget \(\alpha\).
To prove optimality, define the prefix sums
\(\displaystyle B_k=\sum_{i=1}^k b_{r_i},\qquad M_k=\sum_{i=1}^k\mu_{r_i}.\)
Every feasible intervention satisfies \(B_k\le\min\{\alpha,M_k\}\). The intervention (9) attains equality for every prefix. The telescoping identity
\(\displaystyle \sum_{i=1}^m d_{r_i}b_{r_i} =d_{r_m}B_m+ \sum_{k=1}^{m-1}(d_{r_k}-d_{r_{k+1}})B_k \)
has nonnegative coefficients. Thus maximizing every prefix simultaneously proves that \(b^*\) maximizes the objective over all feasible rational interventions.
Computing the degrees uses \(O(m^2)\) rational arithmetic operations; sorting uses \(O(m\log m)\) exact comparisons; constructing (9) uses \(O(m)\) further operations. Products, sums, comparisons, and budget differences all have bit lengths polynomial in the total input length \(L\). Standard exact rational arithmetic therefore implements the algorithm in polynomial bit complexity in \(m=\tau\) and \(L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated optimization problem. The finite-population derivative, the coalescence-time limit, and the exact optimization argument are correct. I found no major or minor mathematical issues requiring repair.
The normalization
\(W_{uv}=Q_{r(u),r(v)}/(Nd_{r(u)})\)
is correct, including self-interactions: summing over all agents gives row sum one.
The proposed stationary weights
\(\pi_u=d_{r(u)}/(ND)\)
sum to one. The displayed detailed-balance calculation is correct and uses precisely the symmetry of \(Q\). Consequently, the calculation \(\mathcal L_0h_0=0\) is valid.
The connectivity argument covers both multiple roles and the single-role case. Positive masses ensure that compatible populations contain agents of every role. Symmetric positive role edges permit copying along a spanning tree. On the finite configuration space, reachability of consensus from every nonconsensus state implies transience of all nonconsensus states and finite mean absorption time. This justifies identifying \(h_0\) with the neutral fixation probability.
Independent rate-one update clocks select targets uniformly at successive events. Thus the continuous-time formulation preserves fixation probabilities and their derivatives.
For a biased target, the displayed post-update probability
\((1+\delta)a_u/(1+\delta a_u)\)
follows directly from the specified source weights. Its derivative at zero is correctly computed as \(a_u(1-a_u)\). Unbiased targets contribute zero to the generator derivative.
The differentiability argument is sufficient: the finite transient-state fixation system has coefficients analytic near zero and an invertible transient matrix at zero. Differentiating its equations gives the Poisson equation with zero boundary values for the fixation derivative. The occupation-time representation in equation (1) has the correct sign and integrates the correct forcing term.
The uniformly random initial singleton is included in the expectation. No interchange of differentiation with an infinite-time limit is asserted or needed. The analytic derivative at zero also supplies the requested right derivative.
The neutral graphical construction gives rate-one ancestral walks with transition probabilities \(W\). Before meeting, distinct ancestral locations use independent update clocks; after meeting, they share an ancestor. Self-copying events cause no difficulty.
Conditional on the ancestral arrows, distinct ancestors cannot both equal the unique initial \(A\)-agent. A common ancestor equals that uniformly chosen agent with probability \(1/N\). Therefore both displayed expectation identities are correct, including \(v=w\), where \(T_{vv}=0\).
Expanding \(a_u(1-a_u)\) gives the claimed survival-probability expression. Integrating nonnegative terms gives equation (2), using the standard identity between mean nonnegative lifetime and its integrated survival probability.
Equation (3) correctly accounts for:
In particular, no population factor or additional rescaling is missing.
The definition of \(H_N(r,r)\) explicitly concerns distinct agents. Restricting to sufficiently large compatible populations ensures that such pairs exist in every role.
Permutation symmetry within roles makes the role-pair description valid before coalescence. From distinct agents of roles \(r,s\), the first lineage selects the exact second agent at rate \(Q_{rs}/(Nd_r)\). The independent role generator assigns that event value \(f_{ss}\), while coalescence assigns value zero. The corresponding correction is therefore exactly the first term of \(B/N\); the second lineage supplies the other term.
This remains correct when \(r=s\). In that case, selecting the other agent coalesces the lineages, whereas selecting oneself does not. The subtraction correctly removes the two coalescing events even though they do not change the role pair.
Thus \(A-B/N\) is the killed generator, and the mean-lifetime backward equation
\((M+B/N)H_N=\mathbf1\)
has the correct sign and right-hand side.
The proposed role distribution
\(\rho_r=\mu_rd_r/D\)
is positive, normalized, and satisfies the displayed detailed-balance identity. The product distribution \(\nu_{rs}=\rho_r\rho_s\) is consequently stationary for \(A\).
Connected positive-entry support and positive masses imply irreducibility of the role chain. Updating coordinates separately makes the continuous-time product chain irreducible as well. Periodicity of a discrete-time role chain would not invalidate this argument. The maximum-principle justification of
\(\ker M=\operatorname{span}\{\mathbf1\}\)
is sufficient, including the singleton state-space case.
Substituting \(H_N=Nh_N\) and \(\varepsilon=1/N\) into equation (4) gives equation (5) correctly. Multiplication by \(\nu\) then gives \(\nu Bh_N=1\).
The calculation of
\(\kappa=\nu B\mathbf1=2K/D^2\)
is correct. Symmetry accounts for the equal contributions of the two terms of \(B\); stationarity of \(\rho\) justifies the subsequent summation identity. Positivity follows from positive masses and positive degrees.
The proof that \(J=M+\mathbf1\nu B\) is invertible is valid. Multiplication by \(\nu\) first forces \(\nu Bf=0\); the kernel characterization then forces \(f=c\mathbf1\), and \(\kappa>0\) forces \(c=0\).
Adding the normalization to equation (5) produces the stated perturbed system. Continuity of inversion at the invertible matrix \(J\), together with
\(J(\mathbf1/\kappa)=\mathbf1\),
establishes equation (8). No unproved boundedness or uniform mixing assumption is needed.
Equation (3) contains finitely many role-pair terms for each fixed input. Equation (8) therefore permits taking the limit term by term. The coincidence corrections tend to one because each \(\mu_s>0\), and the source-role probabilities sum to one.
The resulting formula
\(\Phi(\mu,Q,b)=D\sum_r b_rd_r/(2K)\)
follows with the stated constant.
Rationality of the masses and intervention coordinates guarantees arbitrarily large compatible integers through common denominator multiples. The proof consequently covers every feasible rational intervention and every compatible sequence required by the task. The stated complete-interaction normalization check is also correct.
Since \(D/(2K)>0\), maximizing the derived objective is equivalent to maximizing \(\sum_r d_rb_r\).
Formula (9) respects all capacities and uses exactly budget \(\alpha\), because total capacity is one and \(0\leq\alpha\leq1\). It also covers \(\alpha=0\), \(\alpha=1\), tied degrees, and one role.
Every feasible prefix satisfies \(B_k\leq\min\{\alpha,M_k\}\), and the proposed allocation attains each bound. The telescoping identity is correct; all its coefficients are nonnegative after sorting. Hence the prefix argument proves optimality over the entire feasible rational domain.
The arithmetic-operation counts are correct. The sums and products involved have polynomial bit length in the explicitly listed rational input, exact comparisons have polynomial cost, and the output coordinates have polynomial bit length. The algorithm therefore has polynomial bit complexity, rather than merely polynomial arithmetic complexity. It never needs to construct a compatible population.
The contextual citation accurately describes [Theorem 5 of the supplied paper](https://arxiv.org/pdf/2211.14676): it concerns exact maximization of the fixation derivative on symmetric finite graphs. The lifted population has symmetric interaction weights, as required. The distributional proof does not depend on inferring its limit from that theorem.
The output addresses the precise support-based encoding, the unrescaled derivative limit, and construction of an exact rational maximizer. No additional clarification is needed to make the argument verifiable.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.