Answer: The exact optimum is \(R_N(Q)=1-\frac{h_N-1}{h_N}(1-h_N/N)^Q\mathbb E[(N-h_N-D_Q)/(N-D_Q)]\), where \(D_Q\) counts distinct labels in \(Q\) independent uniform draws from \(N-h_N\) labels. For every fixed \(\epsilon>0\), budgets \(Q_N=O(N^{1-\epsilon})\) give \(R_N(Q_N)=(1+o(1))/h_N=o(1)\). If \(Q_Nh_N/N\to c\), the ratio tends to \(1-e^{-c}\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a family of graphs on which any algorithm with query cost O(n1−ϵ) for some ϵ > 0 has ap- proximation ratio no better than o(1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
For an \(N\)-indexed society with types \(H,I\), masses \(\mu_H=\lceil\log N\rceil/N\) and \(\mu_I=1-\mu_H\), and a hidden uniform assignment of identities to types, suppose \(H\) forms a clique and \(I\) consists of isolates. With \(q=1\), one seed, and Jump-Crawl queries costing mass \(1/N\) per queried identity, characterize the best approximation ratio for expected activated mass relative to the full-information optimum as a function of query budget \(Q_N\). In particular, must every policy with \(Q_N=O(N^{1-\epsilon})\), for fixed \(\epsilon>0\), have ratio \(o(1)\)?
A society is given by its support: the list of the \(\tau\) positive-mass types and their binary rational masses; \(\tau\) denotes support size, not the number of possible types. Let \(L\) be the input bit length.
For an integer \(N\geq4\), put \(h_N=\lceil\log_2N\rceil\). The support is \(\{H,I\}\), with \(\mu_H=h_N/N\) and \(\mu_I=1-\mu_H\), so \(\tau=2\) and total mass is one.
There are \(N\) publicly named identities, each of mass \(1/N\). A uniformly random subset of exactly \(h_N\) identities has type \(H\); its identities form an undirected clique, and all other identities are isolated. The assignment is hidden; the support and this distribution are known.
An adaptive randomized policy may jump to an independent uniformly random identity or crawl to a chosen neighbor of a previously surveyed identity. Each visit reveals the visited identity's complete labeled neighbor list.
Every visit, including a repeat, costs \(1/N\) mass. The integer budget \(Q_N\geq0\) bounds the number of visits on every execution, so the corresponding mass budget is \(Q_N/N\).
After exploration, the policy selects exactly one identity as seed, possibly an unqueried identity, without an additional query charge. Influence follows independent cascade with \(q=1\); activated mass includes the seed. No activation feedback is available before seed selection.
Let \(F_A\) be activated mass under policy \(A\), and let \(\mathrm{OPT}_N\) be the maximum activated mass with the assignment fully known. Define \(R_N(Q_N)=\sup_A\mathbb{E}[F_A]/\mathrm{OPT}_N\), with expectation over the hidden assignment and policy randomness. State algorithmic running times in \(m,\tau,L,N,Q_N\), where \(m=\binom{h_N}{2}\) is the edge count.
What is the optimal approximation ratio \(R_N(Q_N)\) as a function of the query budget? In particular, for every fixed \(\epsilon>0\), must \(R_N(Q_N)=o(1)\) whenever \(Q_N=O(N^{1-\epsilon})\), or can a policy achieve a ratio bounded away from zero?
For discrete exploratory influence maximization, a logarithmic clique with isolated vertices gives an \(o(1)\) approximation upper bound under \(O(N^{1-\epsilon})\) visits, even with one seed and \(q=1\). [Wilder et al.](https://cdn.aaai.org/ojs/11585/11585-13-15113-1-2-20201228.pdf)
No separate result for the exact budget-dependent optimum in this mass formulation was identified in the search; the discrete asymptotic bound already concerns its underlying identity model.
Write \(h=h_N=\lceil\log_2N\rceil\), \(n=N-h\), and \(Q=Q_N\). Let \(D_Q\) denote the number of distinct labels appearing in \(Q\) independent uniform draws from a set of size \(n\), with \(D_0=0\).
The exact optimum is
\(\displaystyle \boxed{R_N(Q)=1-\frac{h-1}{h}\left(1-\frac hN\right)^Q\mathbb E\!\left[\frac{n-D_Q}{N-D_Q}\right].}\)
An optimal policy jumps until its first clique visit or until it exhausts its budget. If it discovers the clique, it seeds the visited clique identity. Otherwise, it seeds any identity never visited.
In particular, for every fixed \(\epsilon>0\),
\(\displaystyle Q_N=O(N^{1-\epsilon})\quad\Longrightarrow\quad R_N(Q_N)=\frac{1+o(1)}{h_N}=o(1).\)
A constant ratio becomes possible at the larger query scale \(N/h_N\). More precisely,
\(\displaystyle \frac{Q_Nh_N}{N}\longrightarrow c\in[0,\infty)\quad\Longrightarrow\quad R_N(Q_N)\longrightarrow 1-e^{-c},\)
and \(Q_Nh_N/N\longrightarrow\infty\) implies \(R_N(Q_N)\longrightarrow1\).
Let \(C\subseteq[N]\) be the hidden clique, uniformly distributed among the subsets of size \(h\). Since \(h\geq2\), a visit distinguishes clique identities from isolated identities: their neighbor lists have sizes \(h-1\) and zero, respectively.
Because activation probability is one, a seed in \(C\) activates exactly \(h\) identities, while a seed outside \(C\) activates only itself. Consequently,
\(\displaystyle \mathrm{OPT}_N=\frac hN.\)
If a policy selects a clique identity with probability \(p\), then
\(\displaystyle \frac{\mathbb E[F_A]}{\mathrm{OPT}_N}=\frac1h+\left(1-\frac1h\right)p.\)
Thus maximizing expected influence is equivalent to maximizing the probability that the seed belongs to \(C\).
Suppose exploration has revealed only isolated identities, and let \(S\) be their set of distinct labels, with \(d=|S|\). Conditional on this history, \(C\) is uniform among the \(h\)-subsets of \([N]\setminus S\).
To justify this posterior statement, fix the policy’s private randomness. For every candidate clique disjoint from \(S\), the recorded visits reveal exactly the same empty neighbor lists. The jump probabilities and the policy’s decisions along this history are therefore identical for all such candidates. Conditioning excludes precisely the cliques intersecting \(S\), preserving uniformity among the remaining possibilities.
Every unvisited identity consequently has conditional clique probability
\(\displaystyle \frac h{N-d},\)
whereas every visited identity has probability zero. Selecting any unvisited identity is therefore conditionally optimal. Such an identity exists because \(d\leq n<N\).
Before a clique visit, every surveyed identity has an empty neighbor list. No crawl is available, so every visit must be an independent uniform jump.
After a clique visit, the policy can immediately seed that identity and attain \(\mathrm{OPT}_N\). Further exploration cannot improve this value.
Finally, stopping before exhausting the budget cannot improve the optimum. A policy can take another jump while retaining its previously intended seed as an available choice. After receiving the additional information, maximizing conditional expected influence is at least as good as retaining that seed. This follows from the law of total expectation.
These observations show that an optimal policy may be taken to jump until it discovers the clique or makes \(Q\) visits, followed by the seed rule above. This policy respects the budget on every execution.
Consider a full sequence of \(Q\) independent jumps, extending the sequence hypothetically after a discovery if necessary. Let \(E_Q\) be the event that all these jumps avoid \(C\). For every fixed clique,
\(\displaystyle \Pr(E_Q)=\left(\frac nN\right)^Q.\)
Conditional on \(E_Q\) and a fixed clique, the jump labels are independent and uniform among the \(n\) isolated identities. Hence their number of distinct labels has distribution \(D_Q\).
If \(E_Q\) fails, the optimal policy discovers the clique and selects a clique seed. If \(E_Q\) holds and \(D_Q=d\), its optimal seed is isolated with probability
\(\displaystyle 1-\frac h{N-d}=\frac{n-d}{N-d}.\)
Therefore the optimal probability of selecting an isolated seed is
\(\displaystyle f_Q=\left(\frac nN\right)^Q\mathbb E\!\left[\frac{n-D_Q}{N-D_Q}\right].\)
Substituting \(p=1-f_Q\) into the influence ratio proves the boxed formula.
For a finite expression, define \(A_{q,d}\) to be the number of length-\(q\) sequences over \(n\) labels containing exactly \(d\) distinct labels. These integers satisfy
\(\displaystyle A_{0,0}=1,\qquad A_{0,d}=0\quad(d>0),\)
and
\(\displaystyle A_{q+1,d}=dA_{q,d}+(n-d+1)A_{q,d-1},\)
with out-of-range entries interpreted as zero. The first term appends an already used label; the second appends a new label to a sequence containing \(d-1\) distinct labels.
Since \(\Pr(D_Q=d)=A_{Q,d}/n^Q\), the exact ratio is equivalently
\(\displaystyle \boxed{R_N(Q)=1-\frac{h-1}{hN^Q}\sum_{d=0}^{\min(Q,n)}A_{Q,d}\frac{n-d}{N-d}.}\)
For example,
\(\displaystyle R_N(0)=\frac1h+\frac{h-1}{N},\)
and
\(\displaystyle R_N(1)=1-\frac{h-1}{h}\frac{n(n-1)}{N(N-1)}.\)
The first identity explicitly includes the benefit of selecting an unqueried seed without paying for a visit.
Put \(a=h/N\), and let \(b_Q\) be the probability that exploration misses the clique but the final unvisited seed belongs to it. Then the optimal clique-seed probability is
\(\displaystyle p_Q=1-(1-a)^Q+b_Q.\)
We claim that \(b_Q\leq a\). To prove this, condition on the full jump sequence, whose distinct-label set is \(S\), of size \(d<N\). Choose the fallback seed \(s\notin S\). Because this sequence is independent of the hidden clique,
\(\displaystyle \Pr(C\cap S=\varnothing,\ s\in C\mid\text{jump sequence})=\frac{\binom{N-d-1}{h-1}}{\binom Nh}\leq\frac{\binom{N-1}{h-1}}{\binom Nh}=\frac hN.\)
The numerator is zero if too few identities remain. If \(d=N\), avoiding the clique is impossible, so the corresponding contribution is also zero. Averaging proves the claim.
The union bound gives \(1-(1-a)^Q\leq Qa\). Hence, for every budget,
\(\displaystyle \boxed{\frac1h\leq R_N(Q)\leq\min\!\left\{1,\frac1h+\frac{(h-1)(Q+1)}N\right\}.}\)
If \(Q_N=O(N^{1-\epsilon})\), multiplying these inequalities by \(h_N\) yields
\(\displaystyle 1\leq h_NR_N(Q_N)\leq1+O\!\left(N^{-\epsilon}(\log N)^2+\frac{(\log N)^2}{N}\right).\)
Both error terms tend to zero. This proves the asserted sharper asymptotic \(R_N(Q_N)=(1+o(1))/h_N\).
For the threshold statement, the same decomposition gives
\(\displaystyle 0\leq R_N(Q)-\bigl[1-(1-a)^Q\bigr]=\frac{(1-a)^Q}{h}+\left(1-\frac1h\right)b_Q\leq\frac1h+a.\)
This error tends to zero uniformly over budgets. If \(Qa\to c<\infty\), then
\(\displaystyle Q\log(1-a)=-Qa+O(Qa^2)\longrightarrow-c,\)
because \(Qa^2=(Qa)a\to0\). Thus \(R_N(Q_N)\to1-e^{-c}\). If \(Qa\to\infty\), then \((1-a)^Q\leq e^{-Qa}\to0\), giving ratio tending to one.
Accordingly, a sequence of ratios is bounded away from zero precisely when \(\liminf_{N\to\infty}Q_Nh_N/N>0\). The corresponding mass-budget threshold is of order \(1/h_N\).
Represent the public identities by indices in \([N]\), and put \(D=\min(Q,N-h)\).
Executing an optimal policy. Maintain the set of visited isolated identities in a binary trie, together with the smallest unvisited index. Trie operations take \(O(\log N)\) bit operations; across all visits, advancing the smallest-unvisited index requires at most one successful advancement per inserted identity.
The worst-case running time is
\(\displaystyle O\!\left(L+\tau+(Q+h)\log N\right)=O\!\left(L+\tau+(Q+\sqrt{m+1})\log N\right),\)
with auxiliary storage
\(\displaystyle O\!\left((D+1)\log N\right)\)
bits. Reading a discovered complete neighbor list contributes \(O(h\log N)\) time. If the binary encoding of the budget is excluded from \(L\), add \(O(\log(Q+1))\) for reading it.
Computing the exact ratio. The recurrence for \(A_{q,d}\) uses \(O((Q+1)(D+1))\) integer arithmetic operations and two rows of storage. To assemble an exact rational answer, use the common denominator
\(\displaystyle K=\prod_{d=0}^{D}(N-d).\)
All intermediate integers can be bounded by
\(\displaystyle B=O\!\left((Q+D+1)\log N\right)\)
bits. Schoolbook arithmetic therefore gives a bit-time bound of
\(\displaystyle O\!\left(L+\tau+(Q+1)(D+1)B^2\right)\)
and auxiliary storage \(O((D+1)B)\) bits. These bounds are polynomial in the numerical parameters \(N,Q\); they do not assert polynomial time in their binary encoding lengths alone.
Here \(\tau=2\) and \(m=\binom h2=\Theta((\log N)^2)\). Knowing the support exactly does not identify the clique’s labels, so the obstruction persists despite constant support size and few edges.
The logarithmic-clique construction and the vanishing approximation bound under \(O(N^{1-\epsilon})\) visits already appear in Theorem 1 of [Wilder et al., *Maximizing Influence in an Unknown Social Network*](https://cdn.aaai.org/ojs/11585/11585-13-15113-1-2-20201228.pdf). Their model uses uniform jumps, neighbor crawls, and visited-node query costs.
The calculation above resolves the exact budget-dependent optimum for the stated hidden-assignment distribution, including repeated-visit charges and unqueried seed selection. Scaling every identity’s influence and query cost by \(1/N\) preserves the approximation ratio.
⟨structured verdict parsed — rendered above⟩
The prover resolves the mathematical target: the exact ratio, optimal policy, sublinear-budget asymptotic, and threshold all follow from the argument. The issues are minor omissions in the implementation accounting.
For every \(N\geq4\), the defined parameters satisfy \(2\leq h<N\), so \(n=N-h\) is positive. Consequently, the occupancy distribution \(D_Q\) is well defined, including when \(Q=0\).
A clique identity has \(h-1>0\) neighbors; an isolated identity has none. Thus a visit distinguishes the two cases exactly.
With one seed and activation probability one, activated mass is \(h/N\) for a clique seed and \(1/N\) otherwise. Therefore both statements
\[
\mathrm{OPT}_N=\frac hN,\qquad
\frac{\mathbb E[F_A]}{\mathrm{OPT}_N}
=\frac1h+\left(1-\frac1h\right)p
\]
are correct. Maximizing the ratio is equivalent to maximizing the probability of choosing a clique identity.
The posterior argument is valid. Along a history containing only empty neighbor lists, every clique disjoint from the visited-label set produces identical observations. The policy’s decisions and uniform-jump probabilities cannot distinguish these candidate cliques. The conditional distribution therefore remains uniform over the \(h\)-subsets of the unvisited identities.
It follows that every unvisited identity has conditional clique probability \(h/(N-d)\), while every visited identity has probability zero. An unvisited identity always exists on such a history because \(d\leq N-h<N\).
Before discovery, crawling is unavailable because every surveyed identity is isolated. Every additional visit must therefore be an independent uniform jump. After discovery, selecting the visited clique identity achieves the fully informed optimum.
The stopping argument also stands: additional observations cannot reduce optimal conditional expected influence, since the previously intended seed remains available. This establishes that the specified policy attains the supremum over adaptive randomized policies.
No theorem beyond the elementary law of total expectation is needed for this part.
The hypothetical extension to \(Q\) jumps is legitimate: it uses independent jump randomness after the actual policy would have stopped, without charging those hypothetical visits.
For a fixed clique, the probability that all jumps avoid it is \((n/N)^Q\). Conditional on avoidance, the jump labels are independent uniform samples from the \(n\) isolated identities. Their distinct-label count therefore has the stated distribution.
On an avoidance history with \(d\) distinct labels, the posterior probability that the selected unvisited seed is isolated is
\[
\frac{n-d}{N-d}.
\]
This quantity depends only on \(d\), so averaging using \(D_Q\) is justified. Thus
\[
f_Q=\left(\frac nN\right)^Q
\mathbb E\left[\frac{n-D_Q}{N-D_Q}\right]
\]
is exactly the failure probability, and substituting it into the influence expression yields the boxed optimal ratio.
There is no zero denominator: \(D_Q\leq n<N\).
The recurrence
\[
A_{q+1,d}=dA_{q,d}+(n-d+1)A_{q,d-1}
\]
correctly separates extensions using an existing label from extensions introducing a new label. Its initialization and out-of-range convention cover \(q=0\), \(d=0\), and \(d=n\).
Since \(A_{Q,d}/n^Q\) is the occupancy probability, the finite-sum expression follows correctly.
The examples also check:
\[
R_N(0)=\frac1h+\frac{h-1}{N},
\qquad
R_N(1)=1-\frac{h-1}{h}\frac{n(n-1)}{N(N-1)}.
\]
In particular, the zero-budget expression correctly accounts for selecting a seed without querying it.
The decomposition
\[
p_Q=1-(1-a)^Q+b_Q
\]
correctly separates discovery from successful fallback selection.
The proof of \(b_Q\leq a\) is sound. The full jump sequence is independent of the hidden clique, and a fallback identity can be chosen from its complement using only that sequence. For a distinct-label set of size \(d<N\), the joint event of avoidance and fallback success has probability
\[
\frac{\binom{N-d-1}{h-1}}{\binom Nh}
\leq\frac hN.
\]
The write-up explicitly handles insufficient remaining identities and \(d=N\).
Combining this with the union bound gives the stated bounds for every nonnegative integer budget. Multiplication by \(h_N\) yields the claimed error terms when \(Q_N=O(N^{1-\epsilon})\). Both terms vanish, establishing
\[
R_N(Q_N)=\frac{1+o(1)}{h_N}=o(1).
\]
The threshold calculation is also correct. The identity
\[
R_N(Q)-[1-(1-a)^Q]
=\frac{(1-a)^Q}{h}+\left(1-\frac1h\right)b_Q
\]
gives the stated uniform error bound. Since \(a\to0\) and \(h\to\infty\), the logarithmic expansion applies for all sufficiently large \(N\). If \(Qa\to c<\infty\), its remainder \(O(Qa^2)\) vanishes. If \(Qa\to\infty\), the exponential upper bound forces the avoidance probability to zero.
The assertion about being bounded away from zero is consistent with these estimates, including sequences for which \(Qa\) does not converge. The mass-budget threshold follows from \(Qa=(Q/N)h\).
The described data structure correctly supports identifying an unvisited fallback seed. The smallest-unvisited index advances only over distinct inserted identities, so the total number of such advancements is bounded by the number of distinct isolated identities encountered.
The neighbor-list reading term \(O(h\log N)\) is appropriate. Replacing \(h\) by \(O(\sqrt{m+1})\) is valid because \(m=\binom h2\).
Two implementation details need clarification:
Minimum clarification: include the budget-control storage in the bound, or specify how the implementation meets the stated bound without it.
Minimum clarification: state the machine and oracle conventions under which the execution-time bound is measured, including how trie-node access and uniform jumps are charged.
These issues concern implementation accounting; they do not affect the optimality proof or ratio.
The recurrence uses the stated number of arithmetic operations and permits two-row storage.
The common denominator \(K\) is valid because each \(N-d\) divides it. The bit-size bound accommodates the occupancy counts, \(N^Q\), \(K\), and the accumulated numerator. Schoolbook arithmetic consequently supports the stated conservative bit-time and storage bounds.
The prover correctly distinguishes polynomial dependence on numerical \(N,Q\) from polynomial dependence on binary input length. No polynomial-time classification in \(L\) alone follows.
The attribution is accurate: Theorem 1 of [Wilder et al., *Maximizing Influence in an Unknown Social Network*](https://cdn.aaai.org/ojs/11585/11585-13-15113-1-2-20201228.pdf) uses a logarithmic clique with isolated vertices, one seed, and activation probability one to obtain the vanishing approximation bound. Its exploration model includes uniform jumps, neighbor crawls, and costs measured by visits.
The prover’s exact formula is established independently rather than inferred from that theorem. Scaling activation and visit costs by \(1/N\) preserves the ratio.
The adjudicated result is an exact approximation characterization and an information limitation. It establishes neither computational hardness nor polynomial time in the binary input length.
⟨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.