Majority Opinion Diffusion in Social Networks: An Adversarial Approach (d4-conf-aaai-2021-1450)

Given a finite typed base graph \(H=(T,E_H)\), rational type masses \(\mu_i\) summing to \(1\), rational black and white seed masses \(b,w\), and horizon \(t\), form the atomless complete blow-up in which type \(i\) has mass \(\mu_i\) and each base edge induces all-to-all interaction between its two type masses. Choose \(x_i^B,x_i^W\ge0\) with \(x_i^B+x_i^W\le\mu_i\), \(\sum_i x_i^B=b\), and \(\sum_i x_i^W=w\); run majority diffusion for \(t\) rounds with aggregate half-splitting on ties, and minimize the resulting white mass \(\Phi_t\), or approximate its optimum.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Input comprises a simple undirected graph \(H=(T,E_H)\), where \(|T|=\tau\) and \(m=|E_H|\), masses \(\mu_i>0\) with \(\sum_i\mu_i=1\), rational budgets \(b,w>0\) with \(b+w\le1\), and a binary-encoded integer horizon \(t\ge1\). Let \(L\) be the total input bit length.
Each type is an atomless population of mass \(\mu_i\); adjacent types interact all-to-all, with no interactions within a type. Choose real seed masses \(x_i^B,x_i^W\ge0\) satisfying \(x_i^B+x_i^W\le\mu_i\), \(\sum_i x_i^B=b\), and \(\sum_i x_i^W=w\); the remaining mass is uncolored.
Colors are permanent. Updates are synchronous: writing \(B_i(r),W_i(r)\) for colored masses after round \(r\), each type compares \(\sum_{j:\{i,j\}\in E_H}B_j(r)\) and \(\sum_{j:\{i,j\}\in E_H}W_j(r)\). If their sum is zero, its uncolored mass remains uncolored; otherwise, all of that mass adopts the larger color in round \(r+1\), or splits equally between colors on a tie.
Define \(\Phi_t(x)=\sum_i W_i(t)\), including white seeds, and \(\mathrm{OPT}=\inf_x\Phi_t(x)\) over feasible real allocations. A multiplicative \(\beta\)-approximation returns a feasible rational allocation with \(\Phi_t(x)\le\beta\mathrm{OPT}\).

For each fixed \(0<\zeta<1\), does this continuous Minimum Influence problem admit a polynomial-time \(\tau^{1-\zeta}\)-approximation, or is achieving that factor NP-hard? State running times in \(m,\tau,L\) and their dependence on \(t\) and \(\zeta\).

For discrete graphs with \(n\) vertices, minimizing expected white count with prescribed positive black and white seed counts admits no polynomial-time \(n^{1-\zeta}\)-approximation unless \(\mathrm{P}=\mathrm{NP}\), already for \(t=2\). [Verified discrete result](https://arxiv.org/pdf/2012.03143).
No result settling this exact atomless, aggregate-half-splitting approximation problem was identified in the literature search.

Status and new partial results

I do not resolve whether a polynomial-time $\tau^{1-\zeta}$-approximation exists or whether achieving that factor is NP-hard.

The following results advance the general continuous problem:

• A feasible rational $(2\tau+1)$-approximation can be computed in polynomial time, independently of how small the budgets are.
• Optimizing at an arbitrary horizon reduces, within a factor approaching $2$, to optimizing at horizon $1$.
• A two-type example shows that this factor $2$ cannot be replaced by a smaller universal constant.

The first approximation factor is still linear in $\tau$, so it does not settle the requested question for any fixed $0<\zeta<1$.

Definitions and elementary bounds

Let $\mathcal F$ be the set of feasible seed allocations. For $x\in\mathcal F$, write
$$ s_i=x_i^B+x_i^W, \qquad u_i=\mu_i-s_i. $$
Thus $u_i$ is the initially uncolored mass of type $i$.

Define the initial neighboring colored mass and neighboring color difference by
$$ C_i(x)=\sum_{j\in N_H(i)}(x_j^B+x_j^W), \qquad D_i(x)=\sum_{j\in N_H(i)}(x_j^B-x_j^W). $$
In round $1$, the residual mass $u_i$ remains uncolored if $C_i(x)=0$. Otherwise it becomes black when $D_i(x)>0$, becomes white when $D_i(x)<0$, and splits equally when $D_i(x)=0$.

For each integer $r\ge1$, define
$$ a_r=\inf_{x\in\mathcal F}\Phi_r(x). $$
The target quantity is $a_t=\mathrm{OPT}$.

Because seed colors are permanent,
$$ w\le \Phi_r(x)\le 1-b. $$
In particular,
$$ w\le a_r\le1-b. $$

The feasible set is nonempty: the proportional allocation
$$ x_i^B=b\mu_i, \qquad x_i^W=w\mu_i $$
satisfies all constraints.

Exact polynomial-time cases

If $b>w$, this proportional allocation is optimal. Indeed, every nonisolated type has
$$ D_i(x)=(b-w)\sum_{j\in N_H(i)}\mu_j>0. $$
Its residual mass becomes black in round $1$. Isolated types acquire no additional color. Consequently,
$$ \Phi_t(x)=w=\mathrm{OPT}. $$

If $b+w=1$, the residual masses are nonnegative and sum to zero. Hence every feasible allocation has objective $w$.

There is also an exact case that allows $b\le w$. Suppose the total mass of isolated types is at least $w$. Place all white seeds on isolated types, respecting their capacities, and then set
$$ x_i^B=\frac{b}{1-w}\bigl(\mu_i-x_i^W\bigr). $$
The denominator is positive because $b>0$ and $b+w\le1$. The black seeds sum to $b$, and the capacity constraints hold because $b/(1-w)\le1$. Every nonisolated type receives positive black seed mass and no white seed mass. Thus no additional white mass appears, and again $\mathrm{OPT}=w$.

These constructions require $O(\tau)$ rational arithmetic operations and $\operatorname{poly}(L,\tau)$ bit operations. Their only dependence on $t$ is through reading the input.

A perturbation that finishes coloring in one round

Lemma

For every feasible allocation $x$ and every real $\eta>0$, there is a feasible allocation $x'$ such that every nonisolated type is fully colored after round $1$ and
$$ \Phi_t(x')=\Phi_1(x') \le 2\Phi_1(x)-w+\eta $$
for every $t\ge1$.

If $x$ and $\eta$ are rational, such an $x'$ can be computed using polynomially many bit operations in their encoding lengths and $L,m,\tau$, and its encoding length is polynomially bounded.

Proof

Keep the white seeds fixed. Define another black allocation by
$$ z_i=\frac{b}{1-w}\bigl(\mu_i-x_i^W\bigr). $$
It satisfies
$$ 0\le z_i\le\mu_i-x_i^W, \qquad \sum_i z_i=b. $$
For $0<\lambda<1$, set
$$ x_i^B(\lambda)=(1-\lambda)x_i^B+\lambda z_i, \qquad x_i^W(\lambda)=x_i^W. $$
This allocation is feasible by convexity.

Every type has positive colored seed mass under this allocation. If $x_i^W>0$, its white seeds suffice. If $x_i^W=0$, then
$$ z_i=\frac{b}{1-w}\mu_i>0, $$
so $x_i^B(\lambda)>0$. Therefore every nonisolated type sees positive colored mass initially and exhausts its residual mass in round $1$. Isolated types never change. This proves
$$ \Phi_t(x(\lambda))=\Phi_1(x(\lambda)) $$
for every $t\ge1$.

Let
$$ v_i=z_i-x_i^B. $$
The neighboring difference under the perturbation is
$$ D_i(x(\lambda)) = D_i(x)+\lambda\sum_{j\in N_H(i)}v_j. $$
There are finitely many types. Thus, for sufficiently small positive $\lambda$, every initially nonzero $D_i(x)$ retains its sign.

We consider the initially zero differences separately.

If $C_i(x)=0$ and $i$ is nonisolated, every neighbor originally has zero black and white seed mass. Every such neighbor receives positive black mass under the perturbation, while its white seed mass remains zero. Hence
$$ D_i(x(\lambda))>0. $$
The residual of $i$ therefore becomes black and contributes no additional white mass.

If $C_i(x)>0$ and $D_i(x)=0$, the perturbed residual can contribute at most all of its mass to white. Originally it contributed exactly half its mass.

Let
$$ I_-=\{i:D_i(x)<0\}, \qquad I_0=\{i:C_i(x)>0,\ D_i(x)=0\}. $$
For sufficiently small $\lambda$,
$$ \Phi_1(x(\lambda)) \le w+\sum_{i\in I_-}u_i(\lambda) +\sum_{i\in I_0}u_i(\lambda), $$
where
$$ u_i(\lambda)=u_i-\lambda v_i. $$
Since $z$ and $x^B$ are nonnegative vectors with the same sum $b$,
$$ \sum_i |v_i| \le \sum_i z_i+\sum_i x_i^B =2b. $$
Consequently,
$$ \Phi_1(x(\lambda)) \le w+\sum_{i\in I_-}u_i+\sum_{i\in I_0}u_i+2\lambda b. $$
The original round-one objective is
$$ \Phi_1(x) = w+\sum_{i\in I_-}u_i +\frac12\sum_{i\in I_0}u_i. $$
Combining these expressions gives
$$ \Phi_1(x(\lambda)) \le 2\Phi_1(x)-w-\sum_{i\in I_-}u_i+2\lambda b \le 2\Phi_1(x)-w+2\lambda b. $$
Choosing $\lambda$ sufficiently small makes the last term at most $\eta$.

For the rational construction, define
$$ M=\max_i\left|\sum_{j\in N_H(i)}v_j\right|. $$
If some $D_i(x)$ is nonzero, let
$$ \gamma=\min_{i:D_i(x)\ne0}|D_i(x)|; $$
otherwise set $\gamma=1$. The rational choice
$$ \lambda= \min\left\{ \frac12,\, \frac{\gamma}{2(1+M)},\, \frac{\eta}{2(1+b)} \right\} $$
preserves all initially nonzero signs and satisfies $2\lambda b\le\eta$.

All quantities require $O(m+\tau)$ rational arithmetic operations. Their encoding lengths remain polynomial in the input and allocation lengths. This proves the computational statement. $\square$

Consequences for the horizon

For every $t\ge1$,
$$ a_1\le a_t\le2a_1-w. $$

The first inequality follows from $\Phi_1(x)\le\Phi_t(x)$ for every allocation. For the second, the lemma gives, for every feasible $x$ and every $\eta>0$,
$$ a_t\le2\Phi_1(x)-w+\eta. $$
Taking the infimum over $x$ and then letting $\eta$ decrease to zero proves the claim. This argument does not assume that either infimum is attained.

More algorithmically, suppose an algorithm returns a rational allocation $x$ satisfying
$$ \Phi_1(x)\le\beta a_1. $$
Applying the lemma with $\eta=\varepsilon w$, for rational $\varepsilon>0$, returns a rational allocation satisfying
$$ \Phi_t(x') \le 2\beta a_1-w+\varepsilon w \le (2\beta+\varepsilon)a_t. $$
The additional work is polynomial in $m,\tau,L$, the encoding length of $x$, and the encoding length of $\varepsilon$. It has no numerical dependence on $t$.

Thus a strong approximation result for horizon $1$ would transfer to every horizon with only a constant loss.

A polynomial-time approximation independent of budget size

The next argument yields a polynomial-time approximation whose factor is linear in the support size.

Let
$$ T_{\mathrm{ni}}=\{i:N_H(i)\ne\varnothing\}, \qquad q=|T_{\mathrm{ni}}|. $$
If $q=0$, every allocation has objective $w$. Hence assume $q>0$.

Protecting a specified set by linear programming

For $A\subseteq T_{\mathrm{ni}}$, consider the condition
$$ \exists x\in\mathcal F \quad\text{such that}\quad D_i(x)>0 \quad\text{for every }i\in A. $$
Call this condition $\mathcal B(A)$.

It is testable by rational linear programming. Introduce a variable $\delta$, impose the original allocation constraints and
$$ D_i(x)\ge\delta \quad(i\in A), \qquad 0\le\delta\le1, $$
and maximize $\delta$.

The condition $\mathcal B(A)$ holds exactly when this program is feasible and its optimum is positive. Indeed, finitely many strict inequalities satisfied by one allocation have a positive common margin. Conversely, a positive feasible margin satisfies all the strict inequalities.

When $\mathcal B(A)$ holds, the program supplies a rational allocation of polynomial encoding length. Every type in $A$ sees a strictly black initial majority, so its residual becomes permanently black in round $1$. Therefore, writing
$$ R=T_{\mathrm{ni}}\setminus A, $$
the allocation satisfies
$$ \Phi_t(x) \le w+\sum_{i\in R}u_i \le w+\sum_{i\in R}\mu_i $$
for every $t\ge1$.

The standard polynomial-time theorem for rational linear programming applies here: there are $2\tau+1$ variables, $O(\tau)$ constraints, rational coefficients of polynomial encoding length, and bounded variables.

An infeasible protection condition gives a lower bound

Proposition. If $A\subseteq T_{\mathrm{ni}}$ is nonempty and $\mathcal B(A)$ fails, then
$$ \mathrm{OPT} \ge \frac{\min_{i\in A}\mu_i+w-b}{2}. $$

Proof. Fix any feasible allocation $x$.

Suppose every $i\in A$ satisfies either $D_i(x)>0$ or $C_i(x)=0$. The perturbation lemma preserves the former strict inequalities and turns the latter comparisons strictly black. It would therefore produce an allocation witnessing $\mathcal B(A)$, a contradiction.

Thus some $i\in A$ has
$$ C_i(x)>0, \qquad D_i(x)\le0. $$
At least half of its residual becomes white in round $1$. Permanence gives
$$ \Phi_t(x)\ge w+\frac{u_i}{2}. $$
Also,
$$ x_i^B+x_i^W\le b+w, $$
because the two seed totals are $b$ and $w$. Consequently,
$$ \Phi_t(x) \ge w+\frac{\mu_i-(b+w)}2 = \frac{\mu_i+w-b}{2} \ge \frac{\min_{j\in A}\mu_j+w-b}{2}. $$
This holds for every feasible $x$, so it also holds for their infimum. $\square$

Algorithm and approximation guarantee

Handle $b>w$ by the exact proportional construction. For the remaining case $b\le w$, order the nonisolated types by nondecreasing mass:
$$ \mu_{i_1}\le\mu_{i_2}\le\cdots\le\mu_{i_q}. $$
For $0\le k\le q$, define
$$ R_k=\{i_1,\ldots,i_k\}, \qquad A_k=T_{\mathrm{ni}}\setminus R_k. $$
Find the smallest $k$ for which $\mathcal B(A_k)$ holds, and return a rational witness from its linear program.

Such a $k$ exists because $A_q$ is empty. The tests are monotone: removing protection constraints cannot destroy feasibility.

If $k=0$, every nonisolated residual becomes black in round $1$, so the returned allocation has objective $w$ and is optimal.

Suppose $k>0$. Since $\mathcal B(A_{k-1})$ fails, the proposition gives
$$ \mathrm{OPT} \ge \frac{\mu_{i_k}+w-b}{2} \ge \frac{\mu_{i_k}}2, $$
where the last inequality uses $b\le w$.

The returned allocation protects all types outside $R_k$, so
$$ \begin{aligned} \Phi_t(x) &\le w+\sum_{j=1}^k\mu_{i_j}\\ &\le w+k\mu_{i_k}\\ &\le \mathrm{OPT}+2k\,\mathrm{OPT}\\ &=(2k+1)\mathrm{OPT}. \end{aligned} $$
Here $w\le\mathrm{OPT}$ was used in the third line.

Hence the algorithm is a
$$ (2k+1)\text{-approximation}, \qquad k\le q\le\tau, $$
and in particular a $(2\tau+1)$-approximation.

It also provides explicit instance-specific bounds when $k>0$:
$$ \max\left\{ w,\, \frac{\mu_{i_k}+w-b}{2} \right\} \le \mathrm{OPT} \le \Phi_t(x) \le w+\sum_{j=1}^k\mu_{i_j}. $$

Running time

Sorting takes $O(\tau\log\tau)$ rational comparisons. Binary search finds the smallest feasible $k$ using $O(\log(\tau+1))$ linear-programming calls. Thus the total bit running time is
$$ O\!\left(\log(\tau+1)\operatorname{poly}(m,\tau,L)\right). $$
The output is rational and has polynomial encoding length.

The construction does not simulate the dynamics and has no numerical dependence on $t$. It has no dependence on $\zeta$, because its proved approximation factor is $(2\tau+1)$ rather than the requested $\tau^{1-\zeta}$.

The factor-two horizon reduction is sharp

Consider two types joined by one edge, with
$$ \mu_1=\frac14, \qquad \mu_2=\frac34, \qquad b=w=\delta, \qquad 0<\delta<\frac1{16}. $$
The budgets can be chosen dyadic.

We prove
$$ a_1=\delta+\frac18, \qquad a_t=\frac14-\delta \quad(t\ge2). $$

Let
$$ d_i=x_i^B-x_i^W. $$
Since $b=w$,
$$ d_1+d_2=0. $$

Strictly opposite differences

If $d_1>0$, then $d_2<0$. Both types have positive initial colored mass. Type $1$ adopts white and type $2$ adopts black in round $1$, so
$$ \Phi_t(x) = \delta+\frac14-s_1 \quad(t\ge1). $$
Moreover,
$$ s_1=x_1^B+x_1^W<2x_1^B\le2\delta. $$
Thus
$$ \Phi_t(x)>\frac14-\delta. $$
This bound is approached by
$$ x_1^B=\delta,\qquad x_1^W=\delta-\eta,\qquad x_2^B=0,\qquad x_2^W=\eta, $$
as positive $\eta$ decreases to zero. These allocations are feasible and have objective
$$ \frac14-\delta+\eta. $$

If $d_1<0$, the symmetric calculation gives
$$ \Phi_t(x)>\frac34-\delta, $$
with that value approachable.

Zero differences

The remaining case has $d_1=d_2=0$.

If both types have positive seed mass, both residuals split in round $1$, giving
$$ \Phi_1(x)=\frac12. $$

If type $1$ has no seeds, all seeds lie on type $2$. In round $1$, type $1$ splits equally and type $2$ retains its residual. Therefore
$$ \Phi_1(x)=\delta+\frac18. $$
In round $2$, type $2$ sees equal positive black and white masses and splits its residual. Hence $\Phi_t(x)=1/2$ for every $t\ge2$.

If type $2$ has no seeds, the corresponding round-one value is
$$ \delta+\frac38, $$
and the value from round $2$ onward is again $1/2$.

These cases are exhaustive. Since $\delta<1/16$,
$$ \delta+\frac18<\frac14-\delta. $$
It follows that
$$ a_1=\delta+\frac18, \qquad a_t=\frac14-\delta \quad(t\ge2). $$
In particular,
$$ \frac{a_2}{a_1} = \frac{\frac14-\delta}{\frac18+\delta} \longrightarrow2 $$
as $\delta$ decreases to zero.

Thus no universal inequality $a_t\le c\,a_1$ with $c<2$ is valid. This example also has an unattained infimum at every horizon $t\ge2$.

Evaluation and binary-encoded horizons

Each type’s residual mass can change only once: its first update with positive neighboring colored mass colors all of that residual.

Every state-changing round therefore exhausts the residual of at least one previously unexhausted type. There are at most $\tau$ such types. If a round makes no change, the deterministic update starts the following round from the same state and can never restart.

Consequently, the process is fixed after round $\tau$, and
$$ \Phi_t(x)=\Phi_{\min\{t,\tau\}}(x). $$

For a rational allocation of total encoding length $K$, direct evaluation uses
$$ O\!\left((m+\tau)\min\{t,\tau\}\right) $$
rational arithmetic operations and
$$ O\!\left((m+\tau)\min\{t,\tau\}\operatorname{poly}(L+K)\right) $$
bit operations. Each type’s colored masses are its seeds plus either none, all, or half of its original residual, so their encoding lengths remain polynomially bounded.

What remains open

The polynomial-time approximation proved here has a linear factor. It does not imply a $\tau^{1-\zeta}$-approximation for any fixed positive $\zeta$.

The horizon reduction identifies horizon $1$ as a useful target for further work: a sufficiently strong approximation there transfers to all horizons with a constant loss. However, the present argument neither supplies the requested sublinear factor at horizon $1$ nor proves hardness for it under arbitrary fractional seeding.

⟨structured verdict parsed — rendered above⟩

The output is correct as a collection of partial results, but it does not resolve the assigned approximation question. I found no false central step or substantive gap in the proofs presented. The blocking issue is the explicitly acknowledged absence of either a polynomial-time $\tau^{1-\zeta}$-approximation or a hardness result for that factor.

• Definitions, feasibility, and elementary bounds

The definitions of $C_i(x)$ and $D_i(x)$ correctly describe the first-round update, including the distinction between an active tie and zero neighboring colored mass.

The bounds
$$ w\le\Phi_r(x)\le1-b $$
follow from permanence of the seeds and conservation of total mass. Taking infima preserves these bounds.

The proportional allocation is feasible: its totals are $b$ and $w$, and its typewise total is $(b+w)\mu_i\le\mu_i$. Thus the feasible set is nonempty.

Assessment: Correct.

• Exact polynomial-time cases

When $b>w$, positivity of every supported mass implies that every nonisolated type has strictly positive initial neighboring black-minus-white difference under the proportional allocation. All its residual becomes black in the first round. Isolated types never change, so the objective is exactly $w$, attaining the universal lower bound.

When $b+w=1$, the residual masses are nonnegative and sum to zero, so each residual is zero. Every feasible allocation therefore has objective $w$.

For the isolated-mass construction, placing all white seeds on isolated types is possible under the stated capacity assumption. The proposed black allocation has total $b$ and respects capacities because
$$ 0<\frac{b}{1-w}\le1. $$
Every nonisolated type has zero white seed mass and positive black seed mass. Consequently, every nonisolated type sees a positive black majority, and no additional white mass appears.

The stated arithmetic and bit-complexity bounds are consistent with these constructions. Identifying isolated vertices also requires inspecting the graph representation, which is covered by the polynomial bit-time bound.

Assessment: Correct.

• Perturbation lemma: feasibility and completion after one round

The vector $z$ satisfies the black budget and the capacities remaining after fixing the white seeds. Convex interpolation between $x^B$ and $z$ therefore preserves feasibility.

Every type receives positive total seed mass after perturbation: an existing positive white seed remains positive, and a type with no white seeds receives positive black mass through $z$. Thus every nonisolated type sees positive neighboring colored mass initially and exhausts its residual in the first round.

Isolated types remain unchanged. Consequently,
$$ \Phi_t(x(\lambda))=\Phi_1(x(\lambda)) $$
for every $t\ge1$.

Assessment: Correct, including types whose original seed mass or residual mass is zero.

• Perturbation lemma: objective bound

The neighboring differences depend affinely on $\lambda$, so finitely many initially nonzero differences retain their signs for sufficiently small positive $\lambda$.

The treatment of initially zero differences is also correct:

• If $C_i(x)=0$ for a nonisolated type, each neighbor originally has zero seeds of both colors. The perturbation gives those neighbors positive black seeds and leaves their white seeds zero, making the comparison strictly black.
• If $C_i(x)>0$ and $D_i(x)=0$, the original white contribution is half the residual, whereas the perturbed contribution is at most the entire perturbed residual.

The bound
$$ \sum_i|z_i-x_i^B|\le2b $$
is valid because both nonnegative vectors have total $b$. The subsequent calculation correctly yields
$$ \Phi_1(x(\lambda)) \le2\Phi_1(x)-w+2\lambda b. $$

The explicit rational choice of $\lambda$ is positive and at most $\tfrac12$. Moreover,
$$ \lambda M\le\frac{\gamma M}{2(1+M)}<\frac{\gamma}{2}, $$
so every initially nonzero difference retains its sign. Its final term also satisfies $2\lambda b\le\eta$.

Rational sums, comparisons, and the stated divisions have polynomial encoding length in the original input, allocation, and $\eta$ encodings. The arithmetic-operation count is consistent with scanning the adjacency lists.

Assessment: Correct for both real existence and rational construction.

• Consequences for the horizon

Permanence gives $\Phi_1(x)\le\Phi_t(x)$ pointwise, hence $a_1\le a_t$.

The perturbation lemma applies to every feasible real allocation and every positive $\eta$. Taking the infimum and then letting $\eta$ tend to zero correctly proves
$$ a_t\le2a_1-w. $$
This does not require either infimum to be attained.

The algorithmic transfer is also valid. From
$$ \Phi_t(x')\le2\beta a_1-w+\varepsilon w, $$
the inequalities $a_1\le a_t$ and $w\le a_t$ imply the stated $(2\beta+\varepsilon)$ guarantee. The additional work depends on the encoding of $\varepsilon$, rather than on its numerical magnitude through repeated simulation.

Assessment: Correct. The transfer preserves a constant loss; it does not itself establish the requested factor.

• Linear-programming protection test

For nonempty $A$, existence of one allocation satisfying all finitely many strict inequalities is equivalent to existence of a positive common margin. Conversely, a positive feasible $\delta$ directly certifies those inequalities.

The upper bound $\delta\le1$ does not invalidate this equivalence: neighboring black-minus-white differences cannot exceed the total black budget, which is at most $1$.

For empty $A$, the allocation constraints remain feasible and $\delta=1$ is available, correctly making the protection condition true.

The invoked rational linear-programming result applies: the program has rational coefficients, polynomial description length, a nonempty bounded feasible region, and a bounded objective. Exact optimization permits testing whether its optimum is positive and obtaining a rational witness of polynomial encoding length.

Protected types acquire no additional white mass. Isolated types acquire none either. Therefore
$$ \Phi_t(x)\le w+\sum_{i\in T_{\mathrm{ni}}\setminus A}u_i $$
is valid at every horizon.

Assessment: Correct.

• Lower bound from failed protection

The contradiction argument correctly uses properties established in the perturbation proof: existing strictly black comparisons survive, while zero-neighbor comparisons at nonisolated types become strictly black.

Thus failure of protection forces, for every feasible allocation, some type in $A$ with positive neighboring colored mass and a nonpositive difference. At least half its residual becomes white immediately.

The bound $x_i^B+x_i^W\le b+w$ follows from nonnegativity and the two global seed totals. Consequently, the displayed lower bound follows with the correct constant:
$$ \mathrm{OPT}\ge\frac{\min_{i\in A}\mu_i+w-b}{2}. $$
It remains valid when its right-hand side is negative, although then it is uninformative. The algorithm uses it in the regime $b\le w$, where the required positive mass bound follows.

Assessment: Correct.

• Approximation algorithm and running time

Protection feasibility is monotone under removing constraints, and the empty protection set is feasible. Hence the smallest successful index exists and can be located by binary search.

For $k>0$, the minimum mass in $A_{k-1}$ is exactly $\mu_{i_k}$, including when masses are equal. The lower-bound proposition therefore gives
$$ \mathrm{OPT}\ge\frac{\mu_{i_k}}2. $$
Combining this with $w\le\mathrm{OPT}$ verifies every step of
$$ \Phi_t(x)\le w+k\mu_{i_k}\le(2k+1)\mathrm{OPT}. $$

The $k=0$ case is optimal. The separate edgeless case is also correct.

Sorting and logarithmically many polynomial-time linear-programming calls justify the stated polynomial bit running time. The algorithm returns a feasible rational allocation of polynomial encoding length and does not need to simulate the horizon.

Assessment: The $(2\tau+1)$ guarantee is established. It is linear and does not supply the requested sublinear guarantee.

• Two-type sharpness example

The example satisfies all input conditions. Equal budgets imply $d_1+d_2=0$, so the sign cases are exhaustive.

When $d_1>0$, both types have positive seeds, and their residuals become white and black, respectively. The calculation
$$ \Phi_t(x)=\delta+\frac14-s_1>\frac14-\delta $$
is correct. The displayed approaching allocations are feasible for sufficiently small positive $\eta$, specifically $0<\eta<\delta$, as intended by the limiting statement.

The opposite-sign case gives the claimed larger bound by exchanging the type roles.

When both differences vanish, positive seed mass in both types produces total white mass $\tfrac12$ after one round. Concentrating all seeds in one type gives exactly the stated first-round values, followed by $\tfrac12$ from the second round onward.

The restriction $\delta<\tfrac1{16}$ correctly ensures
$$ \delta+\frac18<\frac14-\delta. $$
Hence the claimed infima, the limiting ratio $2$, and nonattainment for horizons at least $2$ all follow.

Assessment: Correct. This establishes sharpness of the universal horizon-comparison constant, not approximation hardness.

• Evaluation with a binary-encoded horizon

A type’s residual is either unchanged or exhausted completely at its first active update. Each state-changing round therefore exhausts at least one previously unexhausted residual.

A round with no change cannot be followed by a later change, since the update is deterministic and receives the same state. These facts justify stabilization by round $\tau$ and
$$ \Phi_t(x)=\Phi_{\min\{t,\tau\}}(x). $$

The stated evaluation-operation count follows from summing neighboring masses each round. The bit-length assertion is valid because each colored mass is a seed mass plus zero, half, or all of its original residual.

Assessment: Correct.

The output makes genuine progress: it establishes exact special cases, a polynomial-time linear-factor approximation, a sharp horizon comparison, and polynomial-time evaluation despite binary horizon encoding. It consistently identifies these as partial results.

The only major issue is assignment-level incompleteness. The minimum additional material needed to settle the assignment is a proved approximation guarantee at the requested factor, with the specified complexity dependence, or a hardness argument valid for arbitrary real seed allocations and aggregate half splitting. Clarification alone cannot supply either result.

⟨structured verdict parsed — rendered above⟩