Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOPTIMAL DIFFUSION is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite directed community template \(H\) with buyer roles \(V\), inviteable roles \(R_s\), and role values, consider \(N\) copies of \(H\) attached to a common seller. The seller assigns each copy an invitation pattern \(S\subseteq R_s\), with fraction \(\lambda_S\) of copies receiving that pattern, where \(\lambda_S\ge 0\) and \(\sum_S\lambda_S=1\). Let the supply be \(k_N\) units with \(k_N/N\to\kappa\), fix a deterministic role-based tie order, and run DNA-MU on the finite population. Does there exist a rational mass vector \(\lambda\) for which the limiting seller revenue per copy is at least \(Q\)?
Given a loopless directed template \(H=(V,E)\), with \(m=|V|\ge1\), inviteable roles \(R_s\subseteq V\), nonnegative binary-rational unit-demand values \(v_a\), a total order of roles, supply density \(\kappa\in\mathbb Q_{>0}\), and threshold \(Q\in\mathbb Q\), the seller chooses a distribution over invitation patterns \(S\subseteq R_s\), including the empty pattern. Buyers report their values truthfully and forward to every outgoing neighbor.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are invitation patterns, masses \(\lambda_S\) sum to \(1\), and \(\tau\) is the support size, not the number of possible patterns. The distribution is the seller's decision, not part of the instance; its support is unrestricted. State running times in \(m\), binary input length \(L\), and any dependence on \(\tau\); include society encoding length when a society is supplied.
For a rational distribution, let \(D\) be the least common denominator of its masses. For each \(N\) divisible by \(D\), create \(N\) disjoint copies of \(H\), with exactly \(N\lambda_S\) copies assigned pattern \(S\); add edges from a common seller to precisely the roles in that pattern. Number copies in lexicographic pattern blocks and set \(k_N=\lfloor\kappa N\rfloor\).
DNA-MU without a reserve price operates on the reachable buyers \(C\). For \(i\in C\), let \(D_i\) contain every other buyer whose every seller-to-buyer path passes through \(i\), and put \(C_{-i}=C\setminus(\{i\}\cup D_i)\). Process buyers by increasing shortest-path distance in the invitation graph, then role order, then copy number.
Initialize remaining supply \(q=k_N\) and winners \(W=\varnothing\). At buyer \(i\), charge the \(q\)-th highest value in \(C_{-i}\setminus W\), interpreted as \(0\) if fewer than \(q\) buyers remain and as \(+\infty\) if \(q\le0\). If \(v_i\) is at least this price, allocate one unit, collect the price, add \(i\) to \(W\), and decrease \(q\) by one; otherwise collect zero. Unreachable buyers receive nothing and pay zero.
Write \(\operatorname{Rev}_N(\lambda)\) for total collected payments. A distribution qualifies precisely when \(\lim_{N\to\infty,\,D\mid N}\operatorname{Rev}_N(\lambda)/N\) exists and is at least \(Q\).
Is deciding whether a qualifying rational distribution exists solvable in polynomial time, or is it NP-hard?
For finite societies, choosing the seller's invitation subset to meet a DNA-MU revenue threshold is reported NP-complete in [Kawasaki et al.](https://arxiv.org/pdf/1911.08809); revenue for a fixed subset is polynomial-time computable.
No result settling this exact replicated-template mass problem was located in the literature search.
The decision problem is \(\mathrm{NP}\text{-hard}\). This holds even when the template is acyclic, all values belong to \(\{0,1\}\), and both the supply density and revenue threshold are positive integers.
The reduction below handles unrestricted rational distributions: its NO-instance argument applies to every support size \(\tau\). YES instances have a qualifying distribution with \(\tau=1\).
We reduce from \(\mathrm{3SAT}\). Let the formula \(F\) have variables \(x_1,\ldots,x_n\) and clauses \(C_1,\ldots,C_s\). We assume \(n\ge2\); adding unused variables ensures this without changing satisfiability.
Define
\[ A=n+s,\qquad B=A+1,\qquad M=nB,\qquad K=3nB+A. \]
Here and below, displayed equations express ordinary integer equalities.
Construct the following roles.
| Roles | Number | Value |
|---|---:|---:|
| Distinguished root \(a\) | \(1\) | \(0\) |
| Literal roots \(r_\ell\), one for each literal \(\ell\) | \(2n\) | \(0\) |
| Distinguished root \(p\) | \(1\) | \(1\) |
| Tokens \(t_{\ell,b}\), for each literal \(\ell\) and \(1\le b\le B\) | \(2nB\) | \(1\) |
| Variable leaves \(y_j\) | \(n\) | \(1\) |
| Clause leaves \(z_h\) | \(s\) | \(1\) |
| Probe leaves \(g_b\), for \(1\le b\le M-1\) | \(M-1\) | \(1\) |
Thus there are exactly \(K\) value-\(1\) roles and
\[ m=K+2n+2 \]
roles altogether.
The inviteable roles are precisely
\[ R_s=\{a,p\}\cup\{r_{x_j},r_{\neg x_j}:1\le j\le n\}. \]
The template edges are:
There are no other edges. In particular, the template is loopless and acyclic, and every non-root role is a leaf.
Choose the role order with \(a\) first, all literal roots next, \(p\) next, and all leaves last. Set
\[ \kappa=K,\qquad Q=K. \]
Consequently, \(k_N=KN\) for every \(N\).
For an invitation pattern \(S\), let \(h(S)\) be the number of reachable value-\(1\) roles in its copy. Always \(h(S)\le K\).
Every winner pays at most their value. Therefore, for any rational distribution \(\lambda\) and every compatible \(N\),
\[ \frac{\operatorname{Rev}_N(\lambda)}{N} \le \sum_S\lambda_S h(S) \le K. \]
If \(\lambda\) qualifies for threshold \(K\), its limiting revenue must equal \(K\). Hence
\[ \sum_S\lambda_S\bigl(K-h(S)\bigr)=0. \]
Each summand is nonnegative. Since every supported pattern has positive mass, every supported pattern must reach all \(K\) value-\(1\) roles.
Call such patterns full patterns. For a full pattern \(S\), write
\[ T(S)=\{\ell:r_\ell\in S\}. \]
Full reachability implies:
In particular, \(|T(S)|\ge n\). If \(|T(S)|=n\), exactly one literal is selected for each variable. Those selected literals define a satisfying assignment, by the clause-coverage condition.
Thus, if \(F\) is unsatisfiable, every full pattern satisfies
\[ |T(S)|\ge n+1. \]
For a reachable buyer \(i\), put \(B_i=\{i\}\cup D_i\), and let \(e_i\) be the number of value-\(1\) buyers in \(B_i\).
Exclusions stay inside \(i\)'s copy, because different copies have no edges between them.
For full patterns, the relevant exclusion counts are as follows.
If \(a\) is invited, it dominates a token \(t_{\ell,b}\) exactly when \(r_\ell\) is not invited. Indeed, that token’s only possible incoming paths use \(a\) or \(r_\ell\). Hence
\[ e_a=B\bigl(2n-|T(S)|\bigr). \]
It dominates no other value-\(1\) role.
An invited literal root can dominate only its own \(B\) tokens and some of the \(A\) variable and clause leaves. Therefore
\[ e_{r_\ell}\le B+A<M. \]
The strict inequality follows from
\[ B+A=2A+1<2B\le nB=M, \]
using \(n\ge2\).
For every full pattern, \(p\) is invited and dominates all its probe leaves. Thus
\[ e_p=M. \]
Every value-\(1\) leaf has exclusion count \(1\).
Suppose every supported pattern is full. Then initially there are exactly \(KN\) reachable value-\(1\) buyers.
All reachable zero-value roots have distance \(1\), and the role order processes them before \(p\). Thus no value-\(1\) buyer has yet won during this phase.
Let \(t\) be the number of zero-value winners so far. At a zero-value buyer \(i\), remaining supply is \(KN-t\), and its competitors contain exactly \(KN-e_i\) value-\(1\) buyers. Provided supply remains positive, its price is therefore
\[ \begin{cases} 0,&t<e_i,\\ 1,&t\ge e_i. \end{cases} \]
Since its value is \(0\), it wins exactly when \(t<e_i\). Each such win increases \(t\) by one.
Let \(t\) be the final number of zero-value winners. During the subsequent processing of \(p\), suppose \(z\) previous copies of \(p\) have won.
Remaining supply is \(KN-t-z\). The current buyer’s competitors contain \(KN-M-z\) value-\(1\) buyers. Its price is consequently
\[ \begin{cases} 0,&t<M,\\ 1,&t\ge M, \end{cases} \]
whenever remaining supply is positive.
Suppose \(F\) is satisfiable. Choose one true literal for each variable, and let \(S\) invite:
This pattern is full: \(a\) reaches every token, the chosen literals reach every variable and clause leaf, and \(p\) reaches every probe leaf.
Use the distribution assigning mass \(1\) to \(S\). Its least common denominator is \(D=1\).
Because exactly \(n\) literal roots are selected,
\[ e_a=B(2n-n)=M. \]
For every \(N\ge M\), the first \(M\) copies of \(a\) win at price \(0\). All remaining copies of \(a\) reject price \(1\). Literal roots also reject price \(1\), since their exclusion counts are strictly below \(M\). Thus the zero-value phase ends with exactly \(t=M\) winners.
Every copy of \(p\) then pays \(1\). Supply suffices to process all of them, since \(KN-M\ge N\) for \(N\ge M\).
Every subsequent value-\(1\) leaf also pays \(1\) while supply remains. To verify this, if \(z\) positive-value buyers have already won, a leaf has \(KN-z-1\) positive-value competitors, whereas remaining supply is \(KN-M-z\). The former is at least the latter because \(M\ge1\).
The mechanism therefore allocates exactly \(KN-M\) units to value-\(1\) buyers, each paying \(1\). Hence, for every \(N\ge M\),
\[ \operatorname{Rev}_N=KN-M. \]
It follows that
\[ \lim_{N\to\infty}\frac{\operatorname{Rev}_N}{N}=K=Q. \]
Thus \(S\) gives a qualifying rational distribution with support size \(1\).
Suppose \(F\) is unsatisfiable, and consider any rational distribution \(\lambda\).
If some supported pattern is not full, Section 2 gives
\[ \frac{\operatorname{Rev}_N(\lambda)}{N} \le\sum_S\lambda_Sh(S)<K \]
for every compatible \(N\). Such a distribution cannot qualify.
It remains to consider distributions supported entirely on full patterns. Every such pattern has \(|T(S)|\ge n+1\). Therefore, whenever \(a\) is invited,
\[ e_a\le B(n-1)<M. \]
Literal roots also have exclusion counts strictly below \(M\). Hence every reachable zero-value buyer, in every copy and every supported pattern, has
\[ e_i\le M-1. \]
The zero-value allocation rule proved in Section 3 now implies that the total number \(t\) of zero-value winners never exceeds \(M-1\). Once \(t=M-1\), every subsequent zero-value buyer faces price \(1\) and rejects it. This bound is independent of \(\tau\), the masses, and the ordering of pattern blocks.
Thus \(t<M\). Every copy of \(p\) pays \(0\), by Section 3. For all sufficiently large compatible \(N\), supply remains positive throughout these \(N\) buyers, so all of them win at price \(0\).
There are only \((K-1)N\) other positive-value buyers, each paying at most \(1\). Consequently,
\[ \operatorname{Rev}_N(\lambda)\le(K-1)N \]
for all sufficiently large compatible \(N\).
Any existing normalized revenue limit is therefore at most \(K-1<Q\). A nonconvergent distribution also fails to qualify, by the problem’s definition. No rational distribution qualifies.
This proves the required equivalence between satisfiability and existence of a qualifying rational distribution.
The construction has
\[ m=3n(n+s+1)+n+s+2n+2=O\bigl(n(n+s)\bigr) \]
roles and \(O(m)\) edges. All values are \(0\) or \(1\), and \(\kappa=Q=K<m\). Its binary encoding length \(L\) is polynomial in the formula’s binary input length. The reduction takes polynomial time.
The target instance contains no supplied society. The YES witness has \(\tau=1\), mass \(1\), and polynomial encoding length. The NO proof covers every \(\tau\), including unrestricted support.
For completeness, a supplied society also permits exact finite replicated revenue evaluation in polynomial time without expanding all copies. Let \(L_{\mathrm{soc}}\) be its encoding length, and supply \(N\) in binary with \(D\mid N\). The running time is
\[ \bigl(m+\tau+L+L_{\mathrm{soc}}+\log(N+1)\bigr)^{O(1)}. \]
Here is the justification.
If \(j\in D_i\), every seller-to-\(j\) path passes through \(i\), so its shortest-path distance is strictly larger than that of \(i\). Thus no member of \(B_i=\{i\}\cup D_i\) has already won when \(i\) is processed.
Precompute distances and exclusions for each supplied pattern. The processing order then consists of at most \(m\tau\) blocks, each containing all copies of a fixed role under a fixed pattern.
For one such block, let:
A buyer in the block wins precisely when supply is positive and
\[ W_{\le v}<k_N-H_{>v}+e_{>v}. \]
Accordingly, the number of winners in the block is exactly
\[ \ell= \max\left\{0,\, \min\left\{b,q,k_N-H_{>v}-W_{\le v}+e_{>v}\right\} \right\}. \]
If \(\ell>0\), all these winners pay the same price. For any positive value level \(u\le v\), a winning allocation reduces both remaining supply and the number of remaining competitors of value at least \(u\) by one. Their comparison is unchanged. Levels above \(v\) cannot determine a winning buyer’s price. Thus one price computation and one aggregate update suffice per block.
Distances and exclusions can be precomputed with polynomially many graph searches. All subsequent counts have polynomial binary length, giving the stated running time.
The reduction therefore establishes \(\mathrm{NP}\text{-hardness}\) for the exact replicated-template decision problem.
⟨structured verdict parsed — rendered above⟩
The reduction establishes NP-hardness in substance. The revenue calculations, the treatment of unrestricted rational support, and the compressed finite evaluation algorithm are correct. There is one minor issue concerning the wording of exclusion sets for unreachable buyers; it does not affect any revenue calculation.
The number of value-\(1\) roles is correctly counted:
\(1+2nB+A+(M-1)=3nB+A=K\).
Adding the \(2n+1\) zero-value roots gives \(m=K+2n+2\).
All listed edges go from roots to leaves, so the template is loopless and acyclic. The inviteable set, role order, values, supply density, and threshold satisfy the task’s requirements.
With \(B=n+s+1\), the stated bound \(m=O(n(n+s))\) is correct. For a standard \(3\mathrm{SAT}\) input, the number of literal-to-clause edges is at most \(3s\); all other edge families have size \(O(nB)\). Thus the claimed \(O(m)\) edge count and polynomial reduction time are justified. Adding unused variables to ensure \(n\ge2\) preserves satisfiability.
Every allocated buyer pays at most its value, directly from the allocation condition. Unreachable buyers pay zero. Consequently,
\(\operatorname{Rev}_N(\lambda)/N\le\sum_S\lambda_Sh(S)\le K\)
holds for every compatible \(N\).
For a qualifying distribution, the existing limit is at least \(K\), so both inequalities force \(\sum_S\lambda_Sh(S)=K\). Since each supported mass is positive and each deficit \(K-h(S)\) is nonnegative, every supported pattern must be full. This correctly handles arbitrary finite support, without assuming a bound on \(\tau\).
The reachability implications for \(p\), variable leaves, and clause leaves follow from the listed incoming edges. If a full pattern selects exactly \(n\) literal roots, variable coverage forces exactly one literal per variable, and clause coverage makes the resulting assignment satisfying. Hence the unsatisfiable-case bound \(|T(S)|\ge n+1\) is valid.
For reachable positive-value buyers, the exclusion counts are correct:
The strict bound on literal roots is numerically correct:
\(B+A=2A+1<2A+2=2B\le nB=M\).
All reachable zero-value roots have distance \(1\). The role order therefore places the entire zero-value phase before every copy of \(p\), and all leaves follow afterward.
Minor issue: “Exclusions stay inside \(i\)’s copy” is not literally justified for the complete set \(D_i\) under the task’s wording. If a buyer is unreachable, there are no seller-to-buyer paths, so the universal path condition can hold vacuously—even for a buyer in another copy. The same issue affects Section 6’s assertion that every \(j\in D_i\) has strictly greater shortest-path distance.
Only reachable buyers enter the competitor sets. The minimum clarification is to restrict these assertions, and the exclusion counts used by the algorithm, to \(B_i\cap C\). No substantive change to the reduction is required.
In the full-pattern case, there are initially \(KN\) reachable positive-value buyers. During the zero-value phase, removing previous zero-value winners does not change the number of positive-value competitors. That number is therefore \(KN-e_i\).
Comparing this with remaining supply \(KN-t\) gives exactly the stated price rule: price zero when \(t<e_i\), and price one when \(t\ge e_i\), provided supply is positive. This includes the convention that insufficient competitors yield price zero.
During the \(p\)-phase, previous winning copies of \(p\) lie outside the current copy’s relevant exclusion set. The positive-value competitor count \(KN-M-z\) and remaining supply \(KN-t-z\) are correct. Their comparison yields the stated cutoff \(t<M\). There is no off-by-one error.
The selected pattern is full, and \(e_a=M\). For \(N\ge M\), the stated processing rule gives exactly \(M\) zero-value winners among copies of \(a\). Every invited literal root then rejects because its exclusion count is strictly smaller than \(M\).
The claimed supply bound for processing all copies of \(p\) is valid. Each pays one.
For subsequent leaves, the competitor count \(KN-z-1\) and remaining supply \(KN-M-z\) are correct. The comparison establishing price one is valid. Once supply is exhausted, the task’s infinite-price convention prevents further allocations.
There are enough positive-value buyers to fill the remaining supply, so the exact formula \(\operatorname{Rev}_N=KN-M\) follows. Its normalized limit is \(K\). The mass-one distribution is rational and has denominator \(D=1\).
A supported nonfull pattern produces a strictly positive average reachability deficit. The resulting uniform revenue upper bound is strictly below \(K\), so such a distribution cannot qualify.
For distributions supported entirely on full patterns, unsatisfiability implies \(e_a\le B(n-1)<M\) whenever \(a\) is invited. Literal roots also have exclusion counts below \(M\). Thus all reachable zero-value buyers have \(e_i\le M-1\).
The zero-value allocation rule consequently bounds their total wins by \(M-1\), independently of support size or pattern-block ordering. Every copy of \(p\) then faces price zero. The claim that supply lasts through these copies for sufficiently large compatible \(N\) is valid.
All other positive-value buyers number \((K-1)N\), and each pays at most one. Therefore the eventual bound \(\operatorname{Rev}_N(\lambda)\le(K-1)N\) is correct. It excludes qualification whether the normalized revenue converges or fails to converge.
With the reachable-buyer clarification above, the preprocessing argument is correct: an excluded reachable descendant has greater distance and cannot already have won.
The processing order decomposes into at most \(m\tau\) blocks, since distance and role are fixed within each role-pattern combination, and copies of each pattern occupy contiguous copy-number intervals.
The winning criterion
\(W_{\le v}<k_N-H_{>v}+e_{>v}\)
follows correctly from comparing remaining supply with the number of competitors valued strictly above \(v\). The stated formula for the block’s winner count respects block size, available supply, and this strict inequality.
The constant-price claim is also valid. For each positive value level at most \(v\), a winning allocation reduces both remaining supply and the corresponding competitor count by one. Levels above \(v\) cannot determine a winning buyer’s price. Zero prices are covered by the mechanism’s convention.
Graph preprocessing, aggregate count updates, and rational arithmetic have polynomial binary complexity in the stated parameters. Including \(L_{\mathrm{soc}}\) and \(\log(N+1)\) appropriately accounts for supplied masses and binary-encoded replication size. This establishes finite evaluation, without claiming an additional algorithm for the limiting decision problem.
The only requested repair is the reachable-buyer qualification on exclusion-set assertions. There are no blocking issues, and the NP-hardness conclusion survives this expositional correction.
⟨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.