\section{Introduction}

A central problem in  three-dimensional  knot concordance theory in the smooth category consists of understanding  $\mathcal{T}$, the concordance group of topologically slice knots.  Freedman~\cites{MR1201584,MR679066} proved that the subgroup $\mathcal{T}^1$ generated by knots with Alexander polynomial one satisfies $\mathcal{T}^1 \subset \mathcal{T}$.  Early work proving that $\mathcal{T}^1$ is nontrivial includes that of Akbulut, Casson, and Cochran-Gompf~\cite{MR976591}; in~\cite{MR1334309}  it was shown that $\mathcal{T}^1$ contains an infinitely generated free subgroup.  Using  Heegaard Floer theory, in~\cite{MR3466802, MR2955197} it was shown that $\mathcal{T} / \mathcal{T}^1$ contains an infinitely generated free subgroup and infinite two-torsion.

Recently, Jae Choon Cha~\cite{arxiv:1910.14629}  has undertaken an in-depth investigation of  {\it primary decompositions} of $\mathcal{T}$.
One motivation for studying primary decompositions arises from Levine's work~\cite{MR0253348} in which it was shown that for all integers $n>0$ there is a homomorphism from the smooth concordance group of knotted $2n-1$ spheres in $S^{2n+1}$ to a group called the  {\it rational algebraic concordance group}:    $\psi_{2n-1} \colon\! \mathcal{C}_{2n-1} \to \mathcal{G}^{\mathbb Q}$.  It was also proved that there is a decomposition $\mathcal{G}^{\mathbb Q} \cong \oplus_{p\in \mathcal{A}}  \mathcal{G}^{\mathbb Q}_p$, where $\mathcal{A}$ is the set of irreducible Alexander polynomials.  Such a decomposition does not exist  using integer rather than  rational coefficients, but the failure was completely analyzed by Stoltzfus~\cite{MR0467764}.  In all odd higher dimensions $\psi_{2n-1}$ is injective, leading to decomposition theorems for knot concordance groups.  In the classical dimension, $n=1$, the map $\psi_1$ is not injective~\cite{MR900252}; the kernel is infinitely generated, contained the subgroup $\mathcal{T}$ of topologically slice knots.

To briefly summarize the perspective of Cha's work,  we  let  $\mathcal{Q} \subset {\mathbb Z}[t]$ be the set of irreducible  polynomials  $q(t)$ satisfying $q(1) = 1$.    Let
$$\mathcal{P} = \{ q(t)q(t^{-1})  \in {\mathbb Z}[t,t^{-1}] \ \big| \ q(t) \in \mathcal{Q}\}.$$  According to Fox and Milnor~\cite{MR0211392}, if a knot $K$ is smoothly  slice, then its Alexander polynomial is a product of elements in $\mathcal{P}$.  The same result holds for topologically locally flat slice knots, as proved   using the existence of normal bundles for locally flat disks (see Freedman-Quinn~\cite[Section 9.3]{MR1201584}).
According to Terasaka~\cite{MR0117736}, every product of elements in $\mathcal{P}$ is the Alexander polynomial of some slice knot.

Given any subset $\mathcal{P}_0 \subset \mathcal{P}$,  let $\mathcal{T}^{\mathcal{P}_0} \subset \mathcal{T}$ denote the subgroup generated by topologically slice knots with Alexander polynomial a product of polynomials  $p$ for  $p \in \mathcal{P}_0$.  In the case that $\mathcal{P}_0$ is a singleton  $\{p\}$, we write $\mathcal{T}^p$.  Hence, as above, $\mathcal{T}^1$ denotes the subgroup generated by knots with Alexander polynomial one.    Notice that for any pair of elements   $p, q  \in \mathcal{P}$, we have $\mathcal{T}^1 \subset \mathcal{T}^p \cap \mathcal{T}^q$.  Thus, in the following conjecture  it is necessary to consider the quotients $\mathcal{T}^p_\Delta = \mathcal{T}^p / \mathcal{T}^1$ and $\mathcal{T}_\Delta = \mathcal{T} / \mathcal{T}^1$.

\begin{conjecture} The canonical homomorphisms    $\mathcal{T}^p_\Delta \to \mathcal{T}_\Delta$  induce an isomorphism  $$\Phi \colon\! \Moplus_{p \in \mathcal{P}}\mathcal{T}^p_\Delta \to \mathcal{T}_\Delta.$$
\end{conjecture}

In~\cite{arxiv:1910.14629}, Cha identifies and studies a specific  infinite set $\mathcal{P}_0 \subset \mathcal{P}$ with two properties:  first, for all $p \in \mathcal{P}_0$, he proves that   $\mathcal{T}^p_\Delta$ contains an infinitely generated free subgroup $\mathcal{S}^p_\Delta$; second, he proves that the  restriction of $\Phi$ is injective on $\oplus_{p \in \mathcal{P}^0} \mathcal{S}^p_\Delta$.

The main goal of this paper is to provide a counterexample to a    splitting property related to the surjectivity of $\Phi$,  considered by Cha under the name {\it  strong existence} (see \cite[Appendix A]{arxiv:1910.14629}).
Although this does not provide a counterexample to the conjecture, it adds to the evidence  that the conjecture is false.  More specifically, it indicates  that $\Phi$ is probably not surjective.

\begin{theorem}\label{thm:main} There exists a set of three polynomials, $\mathcal{P}_0 = \{f_1, f_2,f_3\} \subset \mathcal{P}$, such that the natural homomorphism  $$\mathcal{T}^{f_1}_{\Delta}\oplus \mathcal{T}^{f_2}_{\Delta} \oplus \mathcal{T}^{f_3}_{\Delta} \to \mathcal{T}^{\mathcal{P}_0}_\Delta$$ is not surjective.
\end{theorem}

The use of three factors is an artifact of the proof.  It will be clear that without the restriction of irreducibility for elements in $\mathcal{Q}$, we could have used two factors, as was stated in the abstract.    To be more precise, there is the following statement.

\begin{theorem}  There exist  Alexander polynomials $f_1(t)$ and $f_2(t)$ having no common factors and a topologically slice knot $K$ with $\Delta_K(t) = f_1(t)^2f_2(t)^2$ such that $K$ is not concordant to any connected sum of knots $K_1 \mathbin{\#} K_2$ where $\Delta_{K_i}(t) = f_i(t)^{n_i}$ and $n_1, n_2 \in {\mathbb Z}$.
\end{theorem}
Notice that it follows that $K$ is a topologically slice knot that is not smoothly concordant to a knot with Alexander polynomial one.  The first  examples of  such knots were described in~\cite{MR2955197}.  The example and proof here are closely related to that earlier work.

\vskip.05in
\noindent{\it Acknowledgments} Thanks are due to Jae Choon Cha for sharing with me    drafts of his ongoing work on primary decompositions and for his repeatedly offering thoughtful commentary on this note.  Discussions with Se-Goo Kim and Taehee Kim were also very helpful.

\section{Rational homology cobordism and the construction of an example}

The proof of Theorem~\ref{thm:main} can be  reduced to a result concerning rational homology cobordism, as we now describe.  Recall first that the Alexander polynomial of a knot determines the order of the first  homology of $M(K)$,  the 2--fold cyclic branched cover of $S^3$ branched over $K$: $\big| H_1(M(K))\big| = \big|\Delta_K(-1)\big|$. Also, 2--fold branched covers of concordant knots are rationally homology cobordant.

Figure~\ref{fig:knot} is a schematic diagram of a  topologically slice knot $K_n(J_n)$ (in the case of $n = 3$); we will be restricting to the case of  $n \equiv 3 \mod 4$.  These knots  bound       punctured Klein bottles in $S^3$.  In each, the left band  has framing 0,  there are   $n$ half-twists between the bands,  and the knot $J_n $ is the connected sum of $(3n-1)/4$ copies of the positive clasped untwisted double of the trefoil knot, $D(T(2,3))$.    Similar knots were used in~\cite{MR2955197} to prove the nontriviality of $\mathcal{T}_\Delta = \mathcal{T} /\mathcal{T}^1$.  Henceforth, will write $K_n$ for $K_{n}(J_{n})$.   A quick calculation in Section~\ref{sec:alex} will show   that if $n=pq$ for odd primes $p$ and $q$, then  $$\Delta_{K_n}(t) = \big(    \phi_{2p}(t) \phi_{2q}(t)\phi_{2pq}(t)  \big)^2,$$ where $\phi_k(t)$ denotes the $k$--cyclotomic polynomial.
\begin{figure}
\fig{.6}{figure1.pdf}
\caption{Knot}\label{fig:knot}
\end{figure}

\begin{theorem} If $n = pq$, then the homology of the 2--fold branched cover of $K_n$ satisfies $\big| H_1(M(K_n))\big| = n^2$.  If $K_n$ is concordant to a connected sum $L_1 \mathbin{\#} L_2 \mathbin{\#} L_3$, with $\Delta_{L_1}(t) =  \phi_{2p}(t)^{m_1}$,    $\Delta_{L_2}(t) =  \phi_{2q}(t)^{m_2}$, and $\Delta_{L_3}(t) = \phi_{2pq}(t)^{m_3}$, then $M(K_n) $ is rationally homology cobordant to a connected sum $M_1 \mathbin{\#} M_2 \mathbin{\#} M_3$, where $\big|H_1(M_1)\big| = p^{m_1}$,  $\big|H_1(M_2) \big| = q^{m_2}$ and  $\big|H_1(M_3) \big| = 1$.

\end{theorem}

\begin{proof}  These all follow  immediately from the facts that $  \phi_{2p}(-1) = p$,    $  \phi_{2q}(-1)  =q $, and $ \phi_{2pq}(-1) = 1$.  See Lemma~\ref{lemma:cyclotomic} for details.

\end{proof}

The topic of~\cite{MR3259765} was the general problem of finding a primary splitting  of the rational homology cobordism group.  We will show that the techniques used there can be applied to prove that for $n=15$, a rational homology  cobordism from $M(K_n)$ to such a connected sum, $M_1 \mathbin{\#} M_2 \mathbin{\#} M_3$, does not exist. Notice that if it did exist,  we could let $N_2 =M_2 \mathbin{\#} M_3$, and reduce  our  work  to obstructing the existence of a rational homology cobordism to a connected sum of two manifolds, $M_1 \mathbin{\#} N_2$.  Our goal will be to prove that $M(K_n)$ is not rational homology cobordant to any connected sum $M_1 \mathbin{\#} M_2$, where $\big|H_1(M_1)\big| = 3^{m_{1}}$ and   $\big|H_1(M_2)\big| = 5^{m_{2}}$ for some integers $m_1$ and $m_2$.

\section{Obstructions from $d$--invariants}

We use the following notation:  for any abelian group $G$ and prime integer $p$,   let $G_{(p)}$ denote the subgroup consisting of all elements of order $p^n$ for some $n$.

All the three-manifolds $M$ we will be   working with are ${\mathbb Z}_2$--homology three-spheres.  Since $H_1(M)$ is of odd order, there are natural identifications: $H_1(M)  \cong H^2(M) \cong \text{Spin}^c(M)$.  For $g \in H_1(M)$ we denote by $d(K, g)$ the Heegaard Floer correction term associated to $g$  viewed as a Spin$^c$--structure.   Basic results concerning $\text{Spin}^c(M)$, the $d$--invariant, and its basic properties are in~\cite{MR1957829}.   Further details and examples are provided in~\cite{MR3259765}.

If $M$ bounds a rational homology four-ball, then there is a subgroup $\mathcal{M} \subset H_1(M)$ such that: $\big|\mathcal{M}\big| ^2= \big|H_1(M)\big|$;  the nonsingular linking form vanishes on $\mathcal{M}$; and $d(M, g) = 0$ for all $g \in \mathcal{M}$.    We can equivalently view $\mathcal{M} \subset H^2(M)$.

\begin{theorem}\label{thm:main:d}  Let $p$ and $q$ be distinct odd primes and let $M$ be a three-manifold satisfying $H_1(M) \cong {\mathbb Z}_{p^2} \oplus {\mathbb Z}_{q^2}$,  generated by elements $a$ and $b$ of order $p^2$ and $q^2$, respectively.  If  $M$ is rationally homology cobordant  to a connected sum $ M_1 \mathbin{\#} M_2$ where $H_1(M_1)_{(q)} = 0$ and $H_1(M_2)_{(p)} = 0$, then the value of    $$d(K,ipa +jqb) - d(K,ipa) - d(K,jqb)$$ is independent of $i$ and $j$.
\end{theorem}

\begin{proof}  Since $M$ and $M_1 \mathbin{\#}  M_2$  are rationally homology  concordant, $M \mathbin{\#}  -M_1 \mathbin{\#}  -M_2$ bounds a           rational homology $4$--ball $W$.  The image of $H^2(W)$   in $H\!:= H^2(M \mathbin{\#} -M_1 \mathbin{\#} -M_2)$ is the desired  subgroup $\mathcal{M}$ satisfying $\big|\mathcal{M}\big|^2 = \big|H\big|$.  Furthermore, $\mathcal{M}$ is self-annihilating with respect to the nonsingular linking form.  The order of a self-annihilating subgroup of a group $G$ is of order at most $\sqrt{|G|}$; it follows that  the subgroup $\mathcal{M}_{(p)} \subset H(M)_{(p)} \oplus H(-M_1)_{(p)}$ cannot be contained in $H(-M_1)_{(p)}$.  In particular, some element of the form $(x_p, y_p) \in  H(M)_{(p)} \oplus H(-M_1)_{(p)}$ with $x_p \ne 0 \in Z_{p^2}$ is contained in $\mathcal{M}$.  By taking a multiple, we can assume $x_p = pa$.  Similarly, there is an element $(qb, y_q) \in  H(M) \oplus H(-M_2)$ in $\mathcal{M}_q$.

Notice that we are viewing $H_1(-M_1) \subset H_1(-M_1) \oplus H_1(-M_2)$, so in this sense  $y_p$ can be interpreted as an ordered pair $(y_p, 0) \in H_1(-M_1) \oplus H(-M_2)$; similarly, $y_q$ represents an ordered pair   $(0,y_q) \in H_1(-M_1) \oplus H_1(-M_2)$. The correction term is additive under connected sum and vanishes for elements in $\mathcal{M}$.  Thus for any $i$ and $j$:
$$d(M, ipa) - d(M_1, iy_p) - d(M_2,0)= 0,$$
$$d(M, jqb)- d(M_1,0) - d(M_2, jy_q) = 0,$$
and
$$d(M, ipa + jqb ) - d(M_1, iy_p)  - d(M_2, jy_q) = 0.$$
Subtracting the first two equations from the third shows that for all $i$ and $j$,
$$d(M, ipa + jqb ) - d(M, ipa)  - d(M, jqb) = -d(M_1, 0)   -d(M_2, 0).$$ The right hand side is independent of $i$ and $j$.

\end{proof}

\section{The knots $K_n(J_n)$  and their Alexander polynomials}\label{sec:alex}

As described in the introduction, we are considering the knots illustrated schematically in  Figure~\ref{fig:knot}.

\begin{theorem}  Let $K_n = K_n(J_n)$. For  $n$   odd, the Alexander polynomial is given by $$\Delta_{K_n}(t) = \left( \frac{ t^{n}+1}{t+ 1}\right)^2.$$ \end{theorem}

\begin{proof}
This knot is a winding number two companion of $J_n$.  Since $J_n$ has Alexander polynomial one, a  standard formula for the Alexander polynomial of a satellite knot~\cite{MR0035436} implies  that the Alexander polynomial of $K_n(J_n)$ is the same as that for $K_n(U)$, where $U$ is the unknot.  In this case, a simple manipulation shows that  $K_n(U) = P(n, -n, n-1)$,   a three-stranded pretzel knot, illustrated in the case of $n=3$ in Figure~\ref{fig:pretzel}.  To compute its Alexander polynomial, we consider instead the Conway polynomial $\nabla_{K_n}(z)$.  (Recall that for an arbitrary oriented knot $K$, $\Delta_K(t) = \nabla_K(t^{1/2} - t^{-1/2})$.)

\begin{figure}[h]
\fig{.5}{figure2.pdf}
\caption{The pretzel knot $P(3,-3,2)$}\label{fig:pretzel}
\end{figure}

The standard crossing change formula  for the Conway polynomial is $$\nabla_+(z) - \nabla_-(z) = -z \nabla_s(z),$$    where $\nabla_\pm$ denotes the Conway polynomial of  an oriented link with a specified crossing made positive or negative  and $\nabla_s$ is the Conway polynomial of the    link formed by smoothing that same crossing.  This can be applied to a crossing on the right-most band of the pretzel knot, indicated by the dot in Figure~\ref{fig:pretzel}.  Smoothing the crossing yields an unlink, which has  0 Conway polynomial.  Changing the crossing removes two half-twists.  Thus, $\nabla_{P(n, -n, n-1)}(z) =\nabla_{P(n, -n, n-3)}(z)$.  Since $n$ is odd, continuing in this way removes the right-most crossings, ultimately yielding the connected sum $-T(2,n) \mathbin{\#} T(2,n)$.   The Alexander polynomials of torus knots is well-known; in this case it is $$\Delta_{T(2,n)}(t) = \frac{(t^{2n} -1)(t-1)}{(t^2 - 1)(t^n -1)} = \frac{t^n +1}{t+1}.$$
\end{proof}

\begin{lemma}\label{lemma:cyclotomic} For distinct odd primes $p$ and $q$, there is the following identity, where the $\phi_i$ are cyclotomic polynomials.
$$ \frac{t^{pq} +1}{t+1} =  \phi_{2p}(t) \phi_{2q}(t) \phi_{2pq}(t).$$ Furthermore, $\phi_{2p}(-1) = p$, $\phi_{2q}(-1) = q$, and $\phi_{2pq}(-1) = 1$.
\end{lemma}

\begin{proof}  The polynomial $t^n -1$ has factors $\phi_d(t)$ for all divisors $d$ of $n$.  Thus

\begin{equation}{t^{2pq} -1} = \phi_{2pq}(t)\phi_{2p}(t)\phi_{2q}(t) \phi_{p}(t)\phi_{q}(t)\phi_2(t)\phi_1(t)
\end{equation}
and $${t^{ pq} -1} = \phi_{ pq}(t)\phi_{ p}(t)\phi_{ q}(t)\phi_1(t).$$ Dividing the first equation by the second, and then dividing by $\phi_2(t) = t +1$ yields   $$ \frac{t^{pq} +1}{t+1} =  \phi_{2pq}(t) \phi_{2p}(t) \phi_{2q}(t) .$$

L'Hopital's rule can be used to determine that the left hand side evaluated at $-1$ is $pq$.  Thus, if we show $\phi_{2p}(-1) = p$, and, similarly, $\phi_{q}(-1) = q$, we are done.  Proceeding as before, $$t^{2p} -1 = \phi_{2p}(t) \phi_p(t) \phi_2(t) \phi_1(t) $$ and $$t^{p} -1 =  \phi_p(t)  \phi_1(t). $$  Dividing yields   $$\frac{ {t^p +1}}{t+1}  =  \phi_{2p}(t). $$  In this case, L'Hopital's rule shows that $\phi_{2p}(-1) = p$.

\end{proof}

\begin{corollary} If $n = pq$, where $p$ and $q$ are distinct odd primes, then $\Delta_{K_n(J_n)}(t) =\big( \phi_{2p}(t)\phi_{2q}(t)\phi_{2pq}(t)\big)^2$, where the $\phi_k(t)$ are cyclotomic polynomials.  For $r$ an  odd prime,  $\phi_{2r}(-1) = r$ and for  a product of two distinct odd primes, $\phi_{2pq}(-1) = 1$.
\end{corollary}

\section{Computing $d(M(K), i)$; the completion of the proof of Theorem~\ref{thm:main}}

We will now restrict to the  case of $n = 15$.     The methods of~\cite{MR593626} apply to show that the  2--fold branched cover of $S^3$ branched over $K_n(J_n)$ is given by $15^{2}$--surgery on $T_{14,15} \mathbin{\#} 22D(T_{2,3})$.  We continue to denote $K_{15}(J_{15})$ by $K_{15}$  and denote its 2--fold  branched cover simply by $M$.  Note that $H_1(M) \cong {\mathbb Z}_{15^2}$.

Suppose now that $K_{15}$ were concordant to a connected sum of three knots, one with Alexander polynomial $ \phi_{6}(t) ^{m_1} $, one with Alexander polynomial   $ \phi_{10}(t) ^{m_2}$, and one with Alexander polynomial $   \phi_{30}(t) ^{m_3}$.   Then, as described in the introduction, $M$ would by rationally homology cobordant to $M_1 \mathbin{\#} M_2$, where $H_1(M_1)_{(5)} = 0$ and $H_1(M_2)_{(3)} = 0$.  Thus,  Theorem~\ref{thm:main:d} would apply.

In~\cite[Section 6]{MR2955197}, an algorithm is presented for computing the values of the $d$--invariants of $M(K_n(J_n))$.  Here is   the results of the computation; readers are referred to~\cite{MR2955197} for general background.  In Appendix~\ref{app:dcomp} we provide a summary of the details of this specific computation.  Since $H_1(M) \cong Z_{225}$, the order 9 subgroup is generated by $a = 25$ and the order 25 subgroup is generated by $b = 9$.   The values that result from the computation  of $d(M, ipa + jqb ) $ are as shown in Table~\ref{table:d}.

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
&     $i = 0  $        & $i=1$        &    $ i = 2$   \\
\hline
$j=0$         &          		22             &     		14       & 	14   \\
\hline
$j=1$         &              	18          &    		6       &  			20  \\
\hline
$j=2$         &           		10              &   		16      & 			22  \\
\hline
$j=3$         &          		10               &    	 22     & 		16   \\
\hline
$j=4$         &         		18                &     	20       	&	 	6   \\
\hline
\end{tabular}
\vskip.1in
\end{center}
\caption{Values of  $d(M, ipa + jqb )  $}\label{table:d}
\end{table}

The values of  $d(M, ipa + jqb ) - d(M, ipa)  - d(M, jqb)$ are as shown (with sign reversed for readability) in Table~\ref{table:d2};  they are not all equal.

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
&     $i = 0  $        & $i=1$        &    $ i = 2$   \\
\hline
$j=0$         &          		22             &     		22      & 	22  \\
\hline
$j=1$         &              	22          &    		26       &  			12  \\
\hline
$j=2$         &           		22             &   		8      & 			2  \\
\hline
$j=3$         &          		22              &    	 2     & 		8  \\
\hline
$j=4$         &         		22               &     	12       	&	 	26   \\
\hline
\end{tabular}
\vskip.1in
\end{center}
\caption{Values of  $-\big(d(M, ipa + jqb ) - d(M, ipa)  - d(M, jqb)\big)$}\label{table:d2}
\end{table}

\subsection{Infinite families}  Let $\{p_i\}$ be an infinite increasing sequence of  primes for which $p_i \equiv 3 \mod 4$ if and only if $i$ is odd.  Let $\mathcal{P}_0 = \cup_{i =1  }^\infty  \{\phi_{2p_i -1 }(t), \phi_{2p_i  }(t), \phi_{2 p_{2i-1} p_{2i}}(t)\}$.  Most of the previous argument is easily generalized.  The only step that we have not been able to complete in general is the computation of the $d$--invariants.   Our expectation is that this would lead to the conclusion that $$ \oplus_{p \in \mathcal{P}_0} \mathcal{T}^p_\Delta \to  \mathcal{T}^{\mathcal{P}_{0}}_\Delta$$ is not surjective.


\section{Introduction}
The \emph{influence maximization problem} ({\sc InfMax}\xspace) is an optimization problem that asks which seeds a viral marketing campaign should target (e.g. by giving free products) so that propagation from these seeds influences the most people in a social network.
That is, given a graph, a \emph{stochastic diffusion model} defining how each node is infected by its neighbors, and a limited budget $k$, how to pick $k$ seeds such that the expected number of total infected nodes in this graph at the end of the diffusion is maximized.
This problem has significant applications in viral marketing, outbreak detection, rumor controls, etc, and has been extensively studied (cf.~\citet{chen2013information,li2018influence}).

For {\sc InfMax}\xspace, most of the existing work has considered \emph{submodular} diffusion models, especially the \emph{independent cascade model} and the \emph{linear threshold model}~\cite{KempeKT03}.  Likewise, we also focus on submodular diffusion models.  In submodular diffusion models, a vertex $v$'s marginal probability of becoming infected after a new neighbor $t$ is infected given $S$ as the set of $v$'s already infected neighbors is at least the marginal probability that $v$ is infected after $t$ is newly infected given $T\supseteq S$ as the set of $v$'s already infected neighbors
(see the paragraph before Theorem~\ref{thm:submodular} for more details).   Intuitively, this means that the influence of infected nodes are substitutes and never have synergy.

When submodular {\sc InfMax}\xspace is considered, nearly all the known algorithms/heuristics are based on a greedy algorithm that iteratively picks the seed that has the largest marginal influence.
Some of them improve the running time of the original greedy algorithm by skipping vertices that are known to be suboptimal~\cite{leskovec2007cost,goyal2011celf++}, while the others improve the scalability of the greedy algorithm by using more scalable algorithms to approximate the expected total influence~\cite{borgs2014maximizing,tang2014influence,tang2015influence,cheng2013staticgreedy,ohsaka2014fast} or computing a score of the seeds that is closely related to the expected total influence~\cite{chen2009efficient,chen2010scalable,ChenYZ10,goyal2011simpath,jung2012irie,galhotra2016holistic,tang2018online,schoenebeck2019influence}.
\citet{arora2017debunking} benchmark most of the aforementioned variants of the greedy algorithms.

In this paper, we study the \emph{adaptive influence maximization problem}, where seeds are selected iteratively and feedback is given to the seed-picker after selecting each seed.
Two different feedback models have been studied in the past: the \emph{full-adoption feedback model} and the \emph{myopic feedback model}~\cite{golovin2011adaptive}.
In the full-adoption feedback model, the seed-picker sees the entire diffusion process of each selected seed, and in the myopic feedback model the seed-picker only sees whether each neighbor of the chosen seed is infected.

Past literature focused on the \emph{adaptivity gap}---the ratio between the performance of the \emph{optimal} adaptive algorithm and the performance of the \emph{optimal} non-adaptive algorithm~\cite{golovin2011adaptive,peng2019adaptive,chen2019adaptivity}.
However, even in the non-adaptive setting, {\sc InfMax}\xspace is known to be APX-hard~\cite{KempeKT03,schoenebeck2019influence}.
As a result, in practice, it is not clear whether the adaptivity gap can measure how much better an adaptive algorithm can do.

In this paper, we define and consider the \emph{greedy adaptivity gap}, which is the ratio between the performance of the adaptive greedy algorithm and the non-adaptive greedy algorithm.
We focus on the gap between the greedy algorithms for three reasons.
First, as we mentioned, the APX-hardness of {\sc InfMax}\xspace renders the practical implications of the adaptivity gap unclear.
Second, as we remarked at the beginning, the greedy algorithm is used almost exclusively in the context of influence maximization.
Third, the iterative nature of the original greedy algorithm naturally extends to the adaptive setting.

\subsection{Our Results}
We show that, for the general submodular diffusion models, with both the full-adoption feedback model and the myopic feedback model, the infimum of the greedy adaptivity gap is exactly $(1-1/e)$.
In addition, this result can be extended to the two well-studied submodular diffusion models: the independent cascade model and the linear threshold model.
This is proved in two steps.

In the first step, we show that there are {\sc InfMax}\xspace instances where the adaptive greedy algorithm can only produce $(1-1/e)$ fraction of the influence of the solution output by the non-adaptive greedy algorithm.
This result is surprising: one would expect that the adaptivity is always helpful, as the feedback provides more information to the seed-picker, which makes the seed-picker refine the seed choices in future iterations.
Our result shows that this is not the case, and the feedback, if overly used, can make the seed-picker act in a more myopic way, which is potentially harmful.

In the second step, we show that the adaptive greedy algorithm always achieves a $(1-1/e)$-approximation of the non-adaptive optimal solution, so its performance is always at least a $(1-1/e)$ fraction of the performance of the non-adaptive greedy algorithm.
In particular, combining the two steps, we see that when the adaptive greedy algorithm output only obtains a (nearly) $(1-1/e)$-fraction of the performance of the non-adaptive greedy algorithm, the non-adaptive greedy algorithm is (almost) optimal.
This worst-case guarantee indicates that the adaptive greedy algorithm will never be too bad.

As the second result, we show that the supremum of the greedy adaptivity gap is infinity, for the general submodular diffusion model with full-adoption feedback.
This indicates that the adaptive greedy algorithm can perform significantly better than its non-adaptive counterpart.
We also show, with almost the same proof, that the adaptivity gap in this setting (general submodular model with full-adoption feedback) is also unbounded.

Finally, we propose a risk-free but more conservative variant of the adaptive greedy algorithm, which always performs at least as well as the non-adaptive greedy algorithm.
We recommend both the adaptive greedy algorithm and this variant.

\subsection{Related Work}
The influence maximization problem was initially posed by \citet{DomingosR01,RichardsonD02}.
\citet{KempeKT03} proposed the linear threshold model and the independent cascade model, and show that they are submodular.
Whenever a diffusion model is submodular, the greedy algorithm was shown to obtains a $(1-1/e)$-approximation to the optimal number of infections~\cite{Nemhauser78,KempeKT03,KempeKT05,MosselR10}.

For adaptive {\sc InfMax}\xspace, \citet{golovin2011adaptive} showed that {\sc InfMax}\xspace with the independent cascade model and full-adoption feedback is \emph{adaptive submodular}, which implies that the adaptive greedy algorithm obtains a $(1-1/e)$-approximation to the adaptive optimal solution.
On the other hand, {\sc InfMax}\xspace for the independent cascade model with myopic feedback, as well as {\sc InfMax}\xspace for the linear threshold model with both feedback models, are not adaptive submodular.
In particular, the adaptive greedy algorithm fails to obtain a $(1-1/e)$-approximation for the independent cascade model with myopic feedback~\cite{peng2019adaptive}.
\citet{peng2019adaptive} showed that the adaptivity gap for the independent cascade model with myopic feedback is at most $4$ and at least $e/(e-1)$, and they also showed that both the adaptive and non-adaptive greedy algorithms perform a $0.25(1-1/e)$-approximation to the adaptive optimal solution.
The adaptivity gap for the independent cascade model with full-adoption feedback, as well as the adaptivity gap for the linear threshold model with both feedback models, are still open problems, although there is some partial progress~\cite{chen2019adaptivity}.

Our paper is not the first work studying the adaptive greedy algorithm.
Previous work focused on improving the running time of the adaptive greedy algorithm~\cite{han2018efficient}.
However, to the best of our knowledge, our work is the first one that compares the adaptive greedy algorithm to its non-adaptive counterpart.

Finally, we remark that there do exist {\sc InfMax}\xspace algorithms that are not based on greedy~\cite{BKS07,GL13,angell2016don,schoenebeck2017beyond,toct2019beyond,RANDOM19paperBootstrap}, but they are typically for non-submodular diffusion models.

We summarize the existing results about the adaptivity gap and our new results about the greedy adaptivity gap in Table~\ref{tab:results}.

\begin{table}[t]
    \centering
    \begin{tabular}{l||l|l|l}
    model & AG & GAG inf & GAG sup \\
    \hline
    \texttt{ICM}\xspace, full-adoption  & at least $e/(e-1)$~\cite{chen2019adaptivity} &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & unknown\\
    \texttt{ICM}\xspace, myopic  & at least $e/(e-1)$, at most $4$~\cite{peng2019adaptive} &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & unknown\\
    \texttt{LTM}\xspace, full-adoption & unknown &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & unknown\\
    \texttt{LTM}\xspace, myopic & unknown &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & unknown\\
    GSDM, full-adoption & $\infty$ (Thm~\ref{thm:adaptivityGap}) &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & $\infty$ (Thm~\ref{thm:sup_gap})\\
    GSDM, myopic & at least $e/(e-1)$ (implied by~\cite{peng2019adaptive}) &  $1-1/e$ (Thm~\ref{thm:inf_gap}) & unknown
    \end{tabular}
    \caption{Results for the adaptivity gap (AG), the infimum of the greedy adaptivity gap (GAG inf) and the supremum of the greedy adaptivity gap (GAG sup), where GSDM stands for general submodular diffusion model.}
    \label{tab:results}
\end{table}

\section{Preliminary}
All graphs in this paper are simple and directed.
Given a graph $G=(V,E)$ and a vertex $v\in V$, let $\Gamma(v)$ and $\deg(v)$ be the set of in-neighbors and the in-degree of $v$ respectively.

\subsection{Triggering Model}
We consider the well-studied \emph{triggering model}~\cite{KempeKT03}, which is commonly used to capture ``general'' submodular diffusion models.
A more general way to capture submodular diffusion models is the \emph{general threshold model}~\cite{KempeKT03} with \emph{submodular local influence functions}. All our results hold under this setting as well. We will discuss this in Appendix~\ref{append:GTM}.
\begin{definition}[\citet{KempeKT03}]\label{def:GTM}
  The \emph{triggering model}, $I_{G,F}$, is defined by a graph $G=(V,E)$ and for each vertex $v$
  a distribution $\mathcal{F}_v$ over the subset of its in-neighbors $\{0,1\}^{|\Gamma(v)|}$.
  Let $F=\{\mathcal{F}_v\mid v\in V\}$.

  On an input seed set $S \subseteq V$,  $I_{G,F}(S)$ outputs a set of infected vertices as follows:
  \begin{enumerate}[noitemsep,nolistsep]
    \item[1.] Initially, only vertices in $S$ are infected. Each vertex $v$ samples a subset of its in-neighbors $T_v\subseteq\Gamma(v)$ from $\mathcal{F}_v$ independently. We call $T_v$ the \emph{triggering set} of $v$.
    \item[2.]  In each subsequent round, a vertex $v$ becomes infected if a vertex in $T_v$ is infected in the previous round.
    \item[3.] After a round where no additional vertices are infected, the set of infected vertices is the output.
  \end{enumerate}
\end{definition}

$I_{G,F}$ in Definition~\ref{def:GTM} can be viewed as a random function $I_{G,F}:\{0,1\}^{|V|}\to\{0,1\}^{|V|}$.
In addition, if the triggering set $T_v$ is fixed for each vertex $v$, then $I_{G,F}$ is deterministic.
Given $v$, its triggering set $T_v$, and an in-neighbor $u\in\Gamma(v)$, we say that the edge $(u,v)$ is \emph{live} if $u\in T_v$, and we say that $(u,v)$ is \emph{blocked} if $u\notin T_v$.
It is easy to see that, when the triggering sets for all vertices are sampled, $I_{G,F}(S)$ is the set of all vertices that are reachable from $S$ when removing all blocked edges from the graph.

We define a \emph{realization} of a graph $G=(V,E)$ as a function $\phi:E\to\{{\texttt L},{\texttt B}\}$ such that $\phi(e)={\texttt L}$ if $e\in E$ is live and $\phi(e)={\texttt B}$ if $e\in E$ is blocked.
Let $I_{G,F}^\phi:\{0,1\}^{|V|}\to\{0,1\}^{|V|}$ be the deterministic function corresponding to the triggering model $I_{G,F}$ with vertices' triggering sets following realization $\phi$.
We write $\phi\sim F$ to indicate that a realization $\phi$ is sampled according to $F=\{\mathcal{F}_v\}$.

The triggering model captures the well-known independent cascade and linear threshold models.
In the two definitions below, we define the two models in terms of the triggering model, which is sufficient for this paper.
In Appendix~\ref{append:originaldefinition}, we present the original definitions and give some intuitions for the two models for those readers who are not familiar with them.

\begin{definition}\label{def:ICM}
  The \emph{independent cascade model} \texttt{ICM}\xspace is a special case of the triggering model $I_{G,F}$ where $G=(V,E,w)$ is an edge-weighted graph with $w(u,v)\in(0,1]$ for each $(u,v)\in E$ and $\mathcal{F}_v$ is the distribution such that each $u\in\Gamma(v)$ is included in $T_v$ with probability $w(u,v)$ independently.
\end{definition}

\begin{definition}\label{def:LTM}
  The \emph{linear threshold model} \texttt{LTM}\xspace is a special case of the triggering model $I_{G,F}$ where $G=(V,E,w)$ is an edge-weighted graph with $w(u,v)>0$ for each $(u,v)\in E$ and $\sum_{u\in\Gamma(v)}w(u,v)\leq1$ for each $v\in V$, and $\mathcal{F}_v$ is the distribution defined as follows: order $v$'s in-neighbors $u_1,\ldots,u_{T}$ arbitrarily, sample a real number $r$ in $[0,1]$ uniformly, and
  $$T_v=\left\{\begin{array}{ll}
      \{u_t\} & \mbox{if }r\in\left[\sum_{i=1}^{t-1}w(u_i,v),\sum_{i=1}^tw(u_i,v)\right) \\
      \emptyset & \mbox{if }r\geq\sum_{i=1}^Tw(u_i,v)
  \end{array}\right..$$
  Intuitively, $T_v$ includes at most one of $v$'s in-neighbors such that each $u_t$ is included with probability $w(u_t,v)$.
\end{definition}

Given a triggering model $I_{G,F}$, let $\sigma_{G,F}:\{0,1\}^{|V|}\to{\mathbb R}_{\geq0}$ be the \emph{global influence function} defined as $\sigma_{G,F}(S)=\E_{\phi\sim F}[|I_{G,F}^\phi(S)|]$.
We drop the subscripts $G,F$ and write the global influence function as $\sigma(\cdot)$ when there is no ambiguity.

A function $f$ mapping from a set of elements to a non-negative value is \emph{submodular} if $f(A\cup\{v\})-f(A)\geq f(B\cup\{v\})-f(B)$ for any two sets $A,B$ with $A\subsetneq B$ and any element $v\notin B$.

\begin{theorem}[\citet{KempeKT03}]\label{thm:submodular}
For any triggering model $I_{G,F}$, $\sigma_{G,F}(\cdot)$ is submodular. In particular, $\sigma_{G,F}(\cdot)$ is submodular for both \texttt{ICM}\xspace and \texttt{LTM}\xspace.
\end{theorem}

\subsection{{\sc InfMax}\xspace and Adaptive {\sc InfMax}\xspace}
\label{sect:Prelim_infmax}
\begin{definition}\label{def:infmax}
  The \emph{influence maximization problem} ({\sc InfMax}\xspace) is an optimization problem which takes inputs $G=(V,E)$, $F$, and $k\in{\mathbb Z}^+$, and outputs a seed set $S$ that maximizes the expected total number of infections: $S\in\argmax_{S \subseteq V: |S| \leq k} \sigma(S)$.
\end{definition}

In the remaining part of this subsection, we define the adaptive version of the influence maximization problem.
We will define two different models: the \emph{full-adoption feedback model} and the \emph{myopic feedback model}.
Suppose a seed set $S\subseteq V$ is chosen by the seed-picker, and an underlying realization $\phi$ is given but not known by the seed-picker.
Informally, in the full-adoption feedback model, the seed-picker sees all the vertices that are infected by $S$ in all future iterations, i.e., the seed-picker sees $I_{G,F}^\phi(S)$. In the myopic feedback model, the seed-picker only sees the states of $S$'s neighbors, i.e., whether each vertex in $\{v\mid \exists s\in S:s\in\Gamma(v)\}$ is infected.

Define a \emph{partial realization} as a function $\varphi:E\to\{{\texttt L},{\texttt B},{\texttt U}\}$ such that $\phi(e)={\texttt L}$ if $e$ is known to be live, $\phi(e)={\texttt B}$ if $e$ is known to be blocked, and $\phi(e)={\texttt U}$ if the status of $e$ is not yet known.
We say that a partial realization $\varphi$ \emph{is consistent with} the full realization $\phi$, denoted by $\phi\simeq\varphi$, if $\phi(v)=\varphi(v)$ whenever $\varphi(v)\neq{\texttt U}$.
For the ease of notation, for an edge $(u,v)\in E$, we will write $\phi(u,v),\varphi(u,v)$ instead of $\phi((u,v)),\varphi((u,v))$.

\begin{definition}\label{def:fulladoption}
  Given a triggering model $I_{G=(V,E),F}$ with a realization $\phi$, the \emph{full-adoption feedback} is a function $\Phi_{G,F,\phi}^{{\mathfrak f}}$ mapping a seed set $S\subseteq V$ to a partial realization $\varphi$ such that
  \begin{itemize}
      \item $\varphi(u,v)=\phi(u,v)$ for each $u\in I_{G,F}^\phi(S)$, and
      \item $\varphi(u,v)={\texttt U}$ for each $u\notin I_{G,F}^\phi(S)$.
  \end{itemize}
\end{definition}

\begin{definition}\label{def:myopic}
  Given a triggering model $I_{G=(V,E),F}$ with a realization $\phi$, the \emph{myopic feedback} is a function $\Phi_{G,F,\phi}^{\mathfrak m}$ mapping a seed set $S\subseteq V$ to a partial realization $\varphi$ such that
  \begin{itemize}
      \item $\varphi(u,v)=\phi(u,v)$ for each $u\in S$, and
      \item $\varphi(u,v)={\texttt U}$ for each $u\notin S$.
  \end{itemize}
\end{definition}

An \emph{adaptive policy} $\pi$ is a function that maps a seed set $S$ and a partial realization $\varphi$ to a vertex $v=\pi(S,\varphi)$, which corresponds to the next seed the policy $\pi$ would choose given $\varphi$ and $S$ being the set of seeds that has already been chosen.
Naturally, we only care about $\pi(S,\varphi)$ when $\varphi=\Phi_{G,F,\phi}^{\mathfrak f}(S)$ or $\varphi=\Phi_{G,F,\phi}^{\mathfrak m}(S)$, although we define $\pi$ that specifies an output for any possible inputs $S$ and $\varphi$.
Notice that we have defined $\pi$ as a deterministic policy for simplicity, and our results hold for randomized policies.
Let $\Pi$ be the set of all possible adaptive policies.

Notice that an adaptive policy $\pi$ completely specifies a seeding strategy in an iterative way.
Given an adaptive policy $\pi$ and a realization $\phi$, let ${\mathcal S}^{\mathfrak f}(\pi,\phi,k)$ be the first $k$ seeds selected according to $\pi$ with the underlying realization $\phi$ under the full-adoption feedback model.
By on our definition, ${\mathcal S}^{\mathfrak f}(\pi,\phi,k)$ can be computed as follows:
\begin{enumerate}
    \item initialize $S=\emptyset$;
    \item update $S=S\cup\{\pi(S,\Phi_{G,F,\phi}^{\mathfrak f}(S))\}$ for $k$ iterations;
    \item output ${\mathcal S}^{\mathfrak f}(\pi,\phi,k)=S$.
\end{enumerate}
Define ${\mathcal S}^{\mathfrak m}(\pi,\phi,k)$ similarly for the myopic feedback model, where $\Phi_{G,F,\phi}^{\mathfrak m}(S)$ instead of $\Phi_{G,F,\phi}^{\mathfrak f}(S)$ is used in Step~2 above.

Let $\sigma^{\mathfrak f}(\pi,k)$ be the expected number of infected vertices given that $k$ seeds are chosen according to $\pi$, i.e., $\sigma^{\mathfrak f}(\pi,k)=\E_{\phi\sim F}[|I_{G,F}^\phi({\mathcal S}^{\mathfrak f}(\pi,\phi,k))|]$.
Define $\sigma^{\mathfrak m}(\pi,k)$ similarly for the myopic feedback model.

\begin{definition}\label{def:infmax_adaptive}
  The \emph{adaptive influence maximization problem} (adaptive {\sc InfMax}\xspace) is an optimization problem which takes as inputs $G=(V,E)$, $F$, and $k\in{\mathbb Z}^+$, and outputs an adaptive policy $\pi$ that maximizes the expected total number of infections: $\pi\in\argmax_{\pi\in\Pi} \sigma^{\mathfrak f}(\pi,k)$ or $\pi\in\argmax_{\pi\in\Pi} \sigma^{\mathfrak m}(\pi,k)$ (depending on the feedback model used).
\end{definition}

\subsection{Adaptivity Gap and Greedy Adaptivity Gap}
\label{sect:prelim_AG}
The adaptivity gap is defined as the ratio between the performance of the optimal adaptive policy and the performance of the optimal non-adaptive seeding strategy.
In this paper, we only consider the adaptivity gap for triggering models.

\begin{definition}\label{def:adaptivitygap}
  The \emph{adaptivity gap with full-adoption feedback} is
  $$\sup_{G,F,k}\frac{\max_{\pi\in\Pi}\sigma^{\mathfrak f}(\pi,k)}{\max_{S\subseteq V,|S|\leq k}\sigma(S)}.$$
  The \emph{adaptivity gap with myopic feedback} is defined similarly.
\end{definition}

The (non-adaptive) \emph{greedy algorithm} iteratively picks a seed that has the maximum marginal gain to the objective function $\sigma(\cdot)$:
\begin{enumerate}
    \item initialize $S=\emptyset$;
    \item update for $k$ iterations $S=S\cup\{s\}$, where $s\in\argmax_{s\in V}\sigma(S\cup\{s\})$ with tie broken in an arbitrarily consistent order;
    \item return $S$.
\end{enumerate}
Let $S^g(k)$ be the set of $k$ seeds output by the (non-adaptive) greedy algorithm.

The \emph{greedy adaptive policy} $\pi^g$ is defined as $\pi^g(S,\varphi)=s$ such that
$$s\in\argmax_{s\in V}\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi\left(S\cup\{s\}\right)\right|\right],$$
with tie broken in an arbitrary consistent order.

\begin{definition}\label{def:adaptivitygreedygap}
  Given a triggering model $I_{G,F}$ and $k\in{\mathbb Z}^+$, the \emph{greedy adaptivity gap with full-adoption feedback} is
  $\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}$.
  The \emph{greedy adaptivity gap with myopic feedback} is defined similarly.
\end{definition}

Notice that, unlike the adaptivity gap in Definition~\ref{def:adaptivitygap}, we leave $G,F,k$ unspecified (instead of taking a supremum over them) when defining the greedy adaptivity gap.
This is because we are interested in both supremum and infimum of the ratio $\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}$.
Notice that the infimum of the ratio $\frac{\max_{\pi\in\Pi}\sigma^{\mathfrak f}(\pi,k)}{\max_{S\subseteq V,|S|\leq k}\sigma(S)}$ in Definition~\ref{def:adaptivitygap} is $1$: the optimal adaptive policy is at least as good as the optimal non-adaptive policy, as the non-adaptive policy can be viewed as a special adaptive policy; on the other hand, it is easy to see that there are {\sc InfMax}\xspace instances such that the optimal adaptive policy is no better than non-adaptive one (for example, a graph containing $k$ vertices but no edges).
For this reason, we only care about the supremum of this ratio.

\section{Infimum of Greedy Adaptivity Gap}
In this section, we show that the infimum of the greedy adaptivity gap for the triggering model is exactly $(1-1/e)$, for both the full-adoption feedback model and the myopic feedback model.
This implies that the greedy adaptive policy can perform even worse than the conventional non-adaptive greedy algorithm, but it will never be significantly worse.
Moreover, we show that this result also holds for both
\texttt{ICM}\xspace (Definition~\ref{def:ICM}) and \texttt{LTM}\xspace (Definition~\ref{def:LTM}).

\begin{theorem}\label{thm:inf_gap}
For the full-adoption feedback model,
$$\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{ICM}\xspace}}\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}=\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{LTM}\xspace}}\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}
=\inf_{G,F,k}\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}=1-\frac1e.$$
The same result holds for the myopic feedback model.
\end{theorem}
In Sect.~\ref{sect:inf_gap_tight}, we show by providing examples that the greedy adaptive policy in the worst case will only achieves $(1-1/e+\varepsilon)$-approximation of the expected number of infected vertices given by the non-adaptive greedy algorithm, for both \texttt{ICM}\xspace and \texttt{LTM}\xspace.

In Sect.~\ref{sect:inf_lower_bound}, we shows that the greedy adaptive policy has performance at least $(1-1/e)$ of the performance of the non-adaptive optimal seeds (Theorem~\ref{thm:lowerbound}).
Theorem~\ref{thm:lowerbound} provides a lower bound on the greedy adaptivity gap for the triggering model and is also interesting on its own.
At the end of Sect.~\ref{sect:inf_lower_bound}, we prove Theorem~\ref{thm:inf_gap} by putting the results from Sect.~\ref{sect:inf_gap_tight} and Sect.~\ref{sect:inf_lower_bound} together.

\subsection{Tight Examples}
\label{sect:inf_gap_tight}
In this subsection, we show that the adaptive greedy algorithm can perform worse than the non-adaptive greedy algorithm by a factor of $(1-1/e+\varepsilon)$, for both \texttt{ICM}\xspace and \texttt{LTM}\xspace and any $\varepsilon>0$.
This may be surprising, as one would expect that the feedback provided to the seed-picker will refine the seed choices in the future iterations.
Here, we provide some intuitions why adaptivity can sometimes hurt.
Suppose there are two promising sequences of seed selections, $\{s,u_1,\ldots,u_k\}$ and $\{s,v_1,\ldots,v_k\}$, such that
\begin{itemize}
    \item $s$ is the best seed which will be chosen first;
    \item $\{s,u_1,\ldots,u_k\}$ has a better performance;
    \item the influence of $u_1,\ldots,u_k$ are non-overlapping, the influence of $v_1,\ldots,v_k$ are non-overlapping, but the influence of $u_i,v_j$ overlaps for each $i,j$; moreover, if $u_1$ is picked as the second seed, the greedy algorithm, adaptive or not, will continue to pick $u_2,\ldots,u_k$, and if $v_1$ is picked as the second seed, $v_2,\ldots,v_k$ will be picked next;
\end{itemize}
Now, suppose there is a vertex $t$ elsewhere which can be infected by both $s$ and $v_1$, such that
\begin{itemize}
    \item if $t$ is infected by $s$, which slightly reduces the marginal influence of $v_1$, $v_1$ will be less promising than $u_1$;
    \item if $t$ is not infected by $s$, $v_1$ is more promising than $u_1$;
    \item in average, when there is no feedback, $v_1$ is still less promising than $u_1$, even after adding the increment in $t$'s infection probability to $v_1$'s expected marginal influence.
\end{itemize}
In this case, the non-adaptive greedy algorithm will ``go to the right trend'' by selecting $u_1$ as the second seed; the adaptive greedy algorithm, if receiving feedback that $t$ is not infected by $s$, will ``go to the wrong trend'' by selecting $v_1$ next.

As a high-level description of the lesson we learned, both versions of the greedy algorithms are intrinsically myopic, and the feedback received by the adaptive policy may make the seed-picker act in a more myopic way, which could be more hurtful to the final performance.

We will assume in the rest of this section that vertices can have positive integer weights, as justified in the following remark.
\begin{remark}
For both \texttt{ICM}\xspace and \texttt{LTM}\xspace, we can assume without loss of generality that each vertex has a positive integer weight, so that, in {\sc InfMax}\xspace, we are maximizing the expected total weight of the infected vertices instead of maximizing the expected number of infected vertices as before.
Suppose we want to make a vertex $v$ have weight $W\in{\mathbb Z}^+$.
We can construct $W-1$ vertices $w_1,\ldots,w_{W-1}$, and create $W-1$ directed edges $(v,w_1),\ldots,(v,w_{W-1})$ with weight $1$. (Recall from Definition~\ref{def:ICM} and Definition~\ref{def:LTM} that the graphs in both \texttt{ICM}\xspace and \texttt{LTM}\xspace are edge-weighted, and the weights of edges completely characterize the collection of triggering set distributions $F$.)
It is straightforward from Definition~\ref{def:ICM} and Definition~\ref{def:LTM} that, for both \texttt{ICM}\xspace and \texttt{LTM}\xspace, each of $w_1,\ldots,w_{W-1}$ will be infected with probability $1$ if $v$ is infected.
In addition, both the greedy algorithm and the greedy adaptive policy will never pick any of $w_1,\ldots,w_{W-1}$ as seeds, as seeding $v$ is strictly better.
Therefore, we can consider the subgraph consisting of $v,w_1,\ldots,w_{W-1}$ as a gadget that representing a vertex $v$ having weight $W$.
\end{remark}

\begin{lemma}\label{lem:tightICM}
For any $\varepsilon$, there exists $G,F,k$ such that $I_{G,F}$ is an \texttt{ICM}\xspace and
$$\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}\leq1-\frac1e+\varepsilon,\qquad\frac{\sigma^{\mathfrak m}(\pi^g,k)}{\sigma(S^g(k))}\leq1-\frac1e+\varepsilon.$$
\end{lemma}
\begin{proof}
We will construct an {\sc InfMax}\xspace instance $(G=(V,E,w),k+1)$ with $k+1$ seeds allowed.
Let $W\in{\mathbb Z}^+$ be a sufficiently large perfect square divisible by $k^{2k}$ and whose value are to be decided later.
The vertex set $V$ contains the following weighted vertices:
\begin{itemize}
    \item a vertex $s$ that has weight $2W$;
    \item a vertex $t$ that has weight $\sqrt{W}/k$;
    \item $2k$ vertices $u_1,\ldots,u_k,v_1,\ldots,v_k$ that have weight $1$;
    \item $k(k+1)$ vertices $\{w_{ij}\mid i=1,\ldots,k+1;j=1,\ldots,k\}$
    \begin{itemize}
        \item $w_{11},\ldots,w_{1k}$ have weight $\frac Wk$;
        \item $w_{i1},\ldots,w_{ik}$ have weight $\frac1k(1-\frac1k)^{i-1}W+\sqrt{W}$ for each $i=2,\ldots,k$;
        \item $w_{(k+1)1},\ldots,w_{(k+1)k}$ have weight $(1-\frac1k)^kW+\frac{\sqrt{W}-k}k-(k-1)\sqrt{W}$.
    \end{itemize}
\end{itemize}
The edge set $E$ is specified as follow:
\begin{itemize}
    \item create two edges $(v_1,t)$ and $(s,t)$;
    \item for each $i=1,\ldots,k$, create $k+1$ edges $(u_i,w_{1i}),(u_i,w_{2i}),\ldots,(u_i,w_{(k+1)i})$, and create $k$ edges $(v_i,w_{i1}),(v_i,w_{i2}),\ldots,(v_i,w_{ik})$.
\end{itemize}
For the weights of edges, all the edges have weight $1$ except for the edge $(s,t)$ which has weight $2k/\sqrt{W}$.

It is straightforward to check that $\sigma(\{s\})=2W+\frac{2k}{\sqrt{W}}\overline{w}(t)=2W+2$, $\sigma(\{u_i\})=1+\sum_{j=1}^{k+1}\overline{w}(w_{ji})=1+W+\frac{\sqrt{W}-k}k$ for each $u_i$, $\sigma(\{v_1\})=1+\overline{w}(t)+\sum_{j=1}^k\overline{w}(w_{1j})=1+\frac{\sqrt{W}}k+W$, $\sigma(\{v_i\})=1+\sum_{j=1}^k\overline{w}(w_{ij})=1+(1-\frac1k)^{i-1}W+k\sqrt{W}$ for each $v_2,\ldots,v_k$, and the influence of the remaining vertices are significantly less than these.

Since $s$ has the highest influence, both the greedy algorithm and the greedy adaptive policy will choose $s$ as the first seed.

For the non-adaptive greedy algorithm, the next seed will be one of $u_1,\ldots,u_k$, each of which contributes $1+W+\frac{\sqrt{W}-k}k$ infected vertices.
To see this, the only seed that is comparable to $u_1,\ldots,u_k$ is $v_1$.
However, since $t$ will be infected by $s$ (which has already been chosen as a seed) with probability $\frac{2k}{\sqrt{W}}$, the marginal contribution of $v_1$ will be slightly less than $\sigma(\{v_1\})$, and it will be $1+W+(1-\frac{2k}{\sqrt{W}})\frac{\sqrt{W}}k=1+W+\frac{\sqrt{W}-2k}{k}$, which is less than the marginal contribution of each of $u_1,\ldots,u_k$.
Since the influence of $u_1,\ldots,u_k$ are non-overlapping, it is straightforward to check that the non-adaptive greedy algorithm will choose $\{s,u_1,\ldots,u_k\}$, which will infect vertices with a total weight of
$$\overline{w}(s)+\frac{2k}{\sqrt{W}}\overline{w}(t)+k+\sum_{i=1}^{k+1}\sum_{j=1}^k\overline{w}(w_{ij})=(k+2)W+O\left(\sqrt{W}\right)$$
in expectation.

The second seed picked by the greedy adaptive policy will depend on whether $t$ is infected by $s$.
Notice that the status of $t$ is available to the policy in both the full-adoption feedback model and the myopic feedback model, so the arguments here, as well as the remaining part of this proof, apply to both feedback models.
By straightforward calculations, the greedy adaptive policy will pick $v_1$ as the next seed if $t$ is not infected by $s$, and the policy will pick a seed from $u_1,\ldots,u_k$ otherwise.

In the latter case, the policy will eventually pick the seed set $\{s,u_1,\ldots,u_k\}$, which will infect vertices with a total weight of
$$\overline{w}(s)+\overline{w}(t)+k+\sum_{i=1}^{k+1}\sum_{j=1}^k\overline{w}(w_{ij})=(k+2)W+O\left(\sqrt{W}\right)$$
with probability $1$ (notice that we are in the scenario that $t$ has been infected by $s$).

In the former case, we can see that the third seed picked by the policy will be $v_2$ instead of any of $u_1,\ldots,u_k$.
In particular, $v_2$ contributes $(1-\frac1k)W+k\sqrt{W}$ infected vertices.
On the other hand, since $w_{11},\ldots,w_{ik}$ have already been infected by $v_1$, the marginal contribution for each $u_i$ is $\sigma(\{u_i\})-\overline{w}(w_{1i})=(1-\frac1k)W+1+\frac{\sqrt{W}-k}{k}$, which is less than the contribution of $v_2$.
By similar analysis, we can see that the greedy adaptive policy in this case will pick the seed set $\{s,v_1,\ldots,v_k\}$, which will infect vertices with a total weight of
$$\overline{w}(s)+\overline{w}(t)+k+\sum_{i=1}^k\sum_{j=1}^k\overline{w}(w_{ij})=
\left(2+k\left(1-\left(1-\frac1k\right)^k\right)\right)W+O\left(\sqrt{W}\right)$$
in expectation (notice that $w_{(k+1)1},\ldots, w_{(k+1)k}$ are not infected).

Since $t$ will be infected with probability $\frac{2k}{\sqrt{W}}$, the expected weight of infected vertices for the greedy adaptive policy is
$$\frac{2k}{\sqrt{W}}\left((k+2)W+O\left(\sqrt{W}\right)\right)+\left(1-\frac{2k}{\sqrt{W}}\right)\cdot\left(\left(2+k\left(1-\left(1-\frac1k\right)^k\right)\right)W+O\left(\sqrt{W}\right)\right)$$
$$\qquad=\left(2+k\left(1-\left(1-\frac1k\right)^k\right)\right)W+O\left(k^2\sqrt{W}\right).$$

Putting together, both $\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}$ and $\frac{\sigma^m(\pi^g,k)}{\sigma(S^g(k))}$ in this case equal to
$$\frac{\left(2+k\left(1-\left(1-\frac1k\right)^k\right)\right)W+O\left(k^2\sqrt{W}\right)}{(k+2)W+O\left(\sqrt{W}\right)},$$
which has limit $1-1/e$ when both $W$ and $k$ tend to infinity.
\end{proof}

\begin{lemma}\label{lem:tightLTM}
For any $\varepsilon$, there exists $G,F,k$ such that $I_{G,F}$ is an \texttt{LTM}\xspace and
$$\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}\leq1-\frac1e+\varepsilon,\qquad\frac{\sigma^{\mathfrak m}(\pi^g,k)}{\sigma(S^g(k))}\leq1-\frac1e+\varepsilon.$$
\end{lemma}
\begin{proof}
We will construct an {\sc InfMax}\xspace instance $(G=(V,E,w),k+1)$ with $k+1$ seeds allowed.
Let $W\in{\mathbb Z}^+$ be a sufficiently large perfect square divisible by $k^{2k}$ and whose value are to be decided later.
The vertex set $V$ contains the following weighted vertices:
\begin{itemize}
    \item a vertex $s$ that has weight $2W$;
    \item a vertex $t$ that has weight $\sqrt{W}/k$;
    \item $k$ vertices $u_1,\ldots,u_k$ that have weight $1$;
    \item $k$ vertices $v_1,\ldots,v_k$ such that $\overline{w}(v_1)=W+1$ and $\overline{w}(v_i)=W(1-\frac1k)^{i-1}+\sqrt{W}$ for each $i=2,\ldots,k$;
    \item $k$ vertices $v_{k+1},\ldots,v_{2k}$ such that $v_{k+1},\ldots,v_{2k-1}$ have weight $W(1-\frac1k)^k$ and $\overline{w}(v_{2k})=W(1-\frac1k)^k+\sqrt{W}-k-(k-1)\sqrt{W}-1$.
\end{itemize}
The edge set $E$ and the weights of edges are specified as follow:
\begin{itemize}
    \item create two edges $(v_1,t)$ and $(s,t)$ with weights $1-\frac{2k}{\sqrt{W}}$ and $\frac{2k}{\sqrt{W}}$ respectively;
    \item create $2k^2$ edges $\{(u_i,v_j)\mid i=1,\ldots,k;j=1,\ldots,2k\}$, each of which has weight $\frac1k$.
\end{itemize}
It is easy to check that the weights of the incoming edges for each vertex $v$ satisfy $\sum_{u\in\Gamma(v)}w(u,v)\leq1$, as required in Definition~\ref{def:LTM}.

The remaining part of the analysis is similar to the proof of Lemma~\ref{lem:tightICM}.
The first seed chosen by both algorithms is $s$.
After this, each $u_i$ has marginal influence $1+\frac1k\sum_{i=1}^{2k}\overline{w}(v_i)=1+W+\frac{\sqrt{W}-k}k$.
Since $t$ is infected by $s$ with probability $\frac{2k}{\sqrt{W}}$, the marginal influence of $v_1$ without any feedback is $(1-\frac{2k}{\sqrt{W}})\overline{w}(t)+\overline{w}(v_1)=1+W+\frac{\sqrt{W}-2k}{k}$.
If $t$ is known to be infected, the marginal influence of $v_1$ is $1+W$; if $t$ is known to be uninfected, the marginal influence of $v_1$ is $1+W+\frac{\sqrt{W}}k$.
By comparing these values, the non-adaptive greedy algorithm will pick one of $u_1,\ldots,u_k$ as the second seed, and the greedy adaptive policy will pick $v_1$ as the second seed if $t$ is not infected and one of $u_1,\ldots,u_k$ as the second seed if $t$ is infected.
(Notice that $\overline{w}(v_1)>\overline{w}(v_2)>\cdots>\overline{w}(v_k)>\overline{w}(v_{k+1})=\cdots=\overline{w}(v_{2k-1})>\overline{w}(v_{2k})$.)

Simple analyses show that the non-adaptive greedy algorithm will choose seeds $\{s,u_1,\ldots,u_k\}$, which will infect all of $v_1,\ldots,v_{2k}$ with probability $1$, and the adaptive greedy policy will choose $\{s,v_1,\ldots,v_k\}$ with a very high probability $1-\frac{2k}{\sqrt{W}}$, which will leave $v_{k+1},\ldots,v_{2k}$ uninfected.
Since $s,v_1,\ldots,v_{2k}$ are the only vertices with weight $\Theta(W)$ and we have both $\sum_{i=1}^k\overline{w}(v_i)=(1-(1-\frac1k)^k)W+O(\sqrt{W})$ and $\sum_{i=1}^{2k}\overline{w}(v_i)=W+O(\sqrt{W})$, the lemma follows by taking the limit $W\rightarrow\infty$ and $k\rightarrow\infty$.
\end{proof}

\subsection{Lower Bound}
\label{sect:inf_lower_bound}
\begin{theorem}\label{thm:lowerbound}
For a triggering model $I_{G,F}$, we have both
$$\sigma^{\mathfrak f}(\pi^g,k)\geq\left(1-\frac1e\right)\max_{S\subseteq V,|S|\leq k}\sigma(S)\qquad\mbox{and}\qquad
\sigma^{\mathfrak m}(\pi^g,k)\geq\left(1-\frac1e\right)\max_{S\subseteq V,|S|\leq k}\sigma(S).$$
\end{theorem}
For a high-level idea of the proof, let $S$ with $|S|=i$ be the seeds picked by $\pi^g$ for the first $i$ iterations and $S^\ast$ be the optimal non-adaptive seed set: $S^\ast\in\argmax_{|S'|\leq k}\sigma(S')$.
Given $S$ as the existing seeds and any feedback (myopic or full-adoption) corresponding to $S$, we can show that the marginal increment to the expected influence caused by the $(i+1)$-th seed picked by $\pi^g$ is at least $1/k$ of the marginal increment to the expected influence caused by $S^\ast$.
Then, a standard argument showing that the greedy algorithm can achieve a $(1-1/e)$-approximation for any submodular monotone optimization problem can be used to prove this theorem.

Theorem~\ref{thm:lowerbound} is implied by the following three propositions.
In the remaining part of this section, we let $S^\ast$ be an optimal seed set for the non-adaptive {\sc InfMax}\xspace: $S^\ast\in\max_{S\subseteq V,|S|\leq k}\sigma(S)$.

We first show that the global influence function after fixing a partial seed set $S$ and any possible feedback of $S$ is still submodular.

\begin{proposition}\label{prop:partial_submodular}
Given a triggering model $I_{G,F}$, any $S\subseteq V$, any feedback model (either full-adoption or myopic) and any partial realization $\varphi$ that is a valid feedback of $S$ (i.e., $\exists\phi:\varphi=\Phi_{G,F,\phi}^f(S)$ or $\exists\phi:\varphi=\Phi_{G,F,\phi}^m(S)$, depending on the feedback model considered), the function $\mathcal{T}:\{0,1\}^{|V|}\to{\mathbb R}_{\geq0}$ defined as $\mathcal{T}(X)=\E_{\phi\simeq\varphi}[|I_{G,F}^\phi(S\cup X)|]$ is submodular.
\end{proposition}
\begin{proof}
Fix a feedback model, $S\subseteq V$ and $\varphi$ that is a valid feedback of $S$.
Let $\overline{S}$ be the set of infected vertices indicated by the feedback of $S$.
Formally, $\overline{S}$ is the set of all vertices that are reachable from $S$ by only using edges $e$ with $\varphi(e)={\texttt L}$.

We consider a new triggering model $I_{G',F'}$ defined as follows:
\begin{itemize}
    \item $G'$ shares the same vertex set with $G$;
    \item The edge set of $G'$ is obtained by removing all edges $e$ in $G$ with $\varphi(e)\neq{\texttt U}$;
    \item The distribution $\mathcal{F}_v'$ is normalized from $\mathcal{F}_v$. Specifically, for each $T_v\subseteq\Gamma(v)$, let $p(T_v)$ be the probability that $T_v$ is chosen as the triggering set under $\mathcal{F}_v$. Let $\Gamma'(v)$ be the set of $v$'s in-neighbors in $G'$, and we have $\Gamma'(v)\subseteq\Gamma(v)$ by our construction. Then, $\mathcal{F}_v'$ is defined such that $T_v\subseteq\Gamma'(v)$ is chosen as the triggering set with probability $p(T_v)/\sum_{T_v'\subseteq\Gamma'(v)}p(T_v')$.
\end{itemize}

A simple coupling argument reveals that
\begin{equation}\label{eqn:coupling}
    \mathcal{T}(X)=\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup X)\right|\right]=
    \sigma_{G',F'}(\overline{S}\cup X).
\end{equation}
We define a coupling of a realization $\phi$ of $G$ with $\phi\simeq\varphi$ to a realization $\phi'$ of $G'$ in a natural way: $\phi(e)=\phi'(e)$ for all edges $e$ in $G'$.
From our construction of $F'=\{\mathcal{F}_v'\}$, it is easy to see that, when $\phi$ is coupled with $\phi'$, the probability that $\phi$ is sampled under $I_{G,F}$ conditioning on $\phi\simeq\varphi$ equals to the probability that $\phi'$ is sampled under $I_{G',F'}$.
Under this coupling, it is easy to see that $u$ is reachable from $S$ by live edges under $\phi$ if and only if it is reachable from $\overline{S}$ by live edges under $\phi'$.
This proves Eqn.~(\ref{eqn:coupling}).

Finally, by Theorem~\ref{thm:submodular}, $\sigma_{G',F'}(\cdot)$ is submodular.
Therefore, for any two vertex sets $A,B$ with $A\subsetneq B$ and any $u\notin B$,
$$\mathcal{T}(A\cup\{u\})-\mathcal{T}(A)=\sigma_{G',F'}(\overline{S}\cup A\cup\{u\})-\sigma_{G',F'}(\overline{S}\cup A)$$
is weakly larger than
$$\mathcal{T}(B\cup\{u\})-\mathcal{T}(B)=\sigma_{G',F'}(\overline{S}\cup B\cup\{u\})-\sigma_{G',F'}(\overline{S}\cup B)$$
if $u\notin\overline{S}$,
and
$$\mathcal{T}(A\cup\{u\})-\mathcal{T}(A)=\mathcal{T}(B\cup\{u\})-\mathcal{T}(B)=0$$
if $u\in\overline{S}$.
In both case, the submodularity of $\mathcal{T}(\cdot)$ holds.
\end{proof}

Next, we show that the marginal gain to the global influence function after selecting one more seed according to $\pi^g$ is at least $1/k$ fraction of the marginal gain of including all the vertices in $S^\ast$ as seeds.

\begin{proposition}\label{prop:marginal}
Given a triggering model $I_{G,F}$, any $S\subseteq V$, any feedback model and any partial realization $\varphi$ that is a valid feedback of $S$, let $s=\pi^g(S,\varphi)$ be the next seed chosen by the greedy policy.
We have
$$\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{s\})\right|\right]-\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]
\geq\frac1k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast)\right|\right]-\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right).$$
\end{proposition}
\begin{proof}
Let $S^\ast=\{s_1^\ast,\ldots,s_k^\ast\}$.
By the greedy nature of $\pi^g$, we have
$$\forall v:\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{s\})\right|\right]\geq\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{v\})\right|\right],$$
and this holds for $v$ being any of $s_1^\ast,\ldots,s_k^\ast$ in particular.

Let $S^\ast_i=\{s_1^\ast,\ldots,s_i^\ast\}$ for each $i=1,\ldots,k$ and $S^\ast_0=\emptyset$, the proposition concludes from the following calculations
\begin{align*}
    &\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{s\})\right|\right]-\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\\
 \geq&\frac1k\sum_{i=1}^k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{s_i^\ast\})\right|\right]-\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right)\\
 \geq&\frac1k\sum_{i=1}^k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast_{i-1}\cup \{s_i^\ast\})\right|\right]
 -\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast_{i-1})\right|\right]\right)\tag{Proposition~\ref{prop:partial_submodular}}\\
 =&\frac1k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast)\right|\right]-\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right),
\end{align*}
where the last equality is by a telescoping sum, by noticing that $S^\ast_i=S^\ast_{i-1}\cup\{s_i^\ast\}$ and $S^\ast=S^\ast_k$.
\end{proof}

Finally, we prove the following proposition which is a more general statement than Theorem~\ref{thm:lowerbound}.

\begin{proposition}\label{prop:generallowerbound}
For a triggering model $I_{G,F}$ and any $\ell\in{\mathbb Z}^+$, we have $\sigma^f(\pi^g,\ell)\geq(1-(1-1/k)^\ell)\sigma(S^\ast)$, and the same holds for the myopic feedback model.
\end{proposition}
\begin{proof}
We will only consider the full-adoption feedback model, as the proof for the myopic feedback model is identical.
We prove this by induction on $\ell$.
The base step for $\ell=1$ holds trivially by Proposition~\ref{prop:marginal} by considering $S=\emptyset$ in the proposition.

Suppose the inequality holds for $\ell=\ell_0$.
We investigate the expected marginal gain to the global influence function by selecting the $(\ell_0+1)$-th seed.
For a seed set $S\subseteq V$ with $|S|=\ell_0$ and a partial realization $\varphi$, let $P(S,\varphi)$ be the probability that the policy $\pi^g$ chooses $S$ as the first $\ell_0$ seeds and $\varphi$ is the feedback.
That is,
$P(S,\varphi)=\Pr_{\phi\sim F}\left({\mathcal S}^f\left(\pi^g,\phi,\ell_0\right)=S\land\Phi_{G,F,\phi}^f(S)=\varphi\right).$
The mentioned expected marginal gain is
\begin{align*}
    &\sigma^f\left(\pi^g,\ell_0+1\right)-\sigma^f\left(\pi^g,\ell_0\right)\\
 =&\sum_{S,\varphi:|S|=\ell_0}P(S,\varphi)\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup\{\pi^g(S,\varphi)\})\right|\right]
 -\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right)\\
 \geq&\sum_{S,\varphi:|S|=\ell_0}P(S,\varphi)\cdot\frac1k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast)\right|\right]
 -\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right)\tag{Proposition~\ref{prop:marginal}}\\
 \geq&\sum_{S,\varphi:|S|=\ell_0}P(S,\varphi)\cdot\frac1k\left(\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S^\ast)\right|\right]
 -\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S)\right|\right]\right)\\%\tag{since $\displaystyle\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S\cup S^\ast)\right|\right]\geq\E_{\phi\simeq\varphi}\left[\left|I_{G,F}^\phi(S^\ast)\right|\right]=\sigma(S^\ast)$}\\
 =&\frac1k\sigma(S^\ast)-\frac1k\sigma^f(\pi^g,\ell_0),
\end{align*}
where the last equality follows from the law of total probability.

By rearranging the above inequality and the induction hypothesis,
\begin{align*}
    \sigma^f\left(\pi^g,\ell_0+1\right)&\geq\frac1k\sigma(S^\ast)+\frac{k-1}k\sigma^f\left(\pi^g,\ell_0\right)\\
    &\geq\left(\frac1k+\frac{k-1}k\left(1-\left(1-\frac1k\right)^{\ell_0}\right)\right)\sigma(S^\ast)\\
    &=\left(1-\left(1-\frac1k\right)^{\ell_0+1}\right)\sigma(S^\ast),
\end{align*}
which concludes the inductive step.
\end{proof}

By taking $\ell=k$ and noticing that $1-(1-1/k)^k>1-1/e$,
it is easy to see that Proposition~\ref{prop:generallowerbound} implies Theorem~\ref{thm:lowerbound}.

Finally, putting Theorem~\ref{thm:lowerbound}, Lemma~\ref{lem:tightICM} and Lemma~\ref{lem:tightLTM} together, Theorem~\ref{thm:inf_gap} can be concluded easily.

\begin{proof}[Proof of Theorem~\ref{thm:inf_gap}]
Since \texttt{ICM}\xspace and \texttt{LTM}\xspace are special cases of triggering models,
we have
$$\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{ICM}\xspace}}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}
\geq
\inf_{G,F,k}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}
$$
and
$$
\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{LTM}\xspace}}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}
\geq
\inf_{G,F,k}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}.$$
Lemma~\ref{lem:tightICM} and Lemma~\ref{lem:tightLTM} show that both
$$\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{ICM}\xspace}}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}
\qquad\mbox{and}\qquad
\inf_{G,F,k:\mbox{ }I_{G,F}\text{ is \texttt{LTM}\xspace}}\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}
$$
are at most $1-1/e$.
On the other hand, Theorem~\ref{thm:lowerbound} implies
$$\frac{\sigma^f(\pi^g,k)}{\sigma(S^g(k))}\geq\frac{\sigma^f(\pi^g,k)}{\sigma(S^\ast)}\geq1-\frac1e$$
for any triggering model $I_{G,F}$ and any $k$, where $S^\ast$, as usual, denotes the optimal seeds in the non-adaptive setting.

Putting together, Theorem~\ref{thm:inf_gap} concludes for the full-adoption feedback model.
Since all those inequalities hold for the myopic feedback model as well, Theorem~\ref{thm:inf_gap} concludes for all feedback models.
\end{proof}

\section{Supremum of Greedy Adaptivity Gap}
\label{sect:sup}
In this section, we show that, for the full-adoption feedback model, both the adaptivity gap and the supremum of the greedy adaptivity gap are unbounded.
As a result, in some cases, the adaptive version of the greedy algorithm can perform significantly better than its non-adaptive counterpart.

\begin{theorem}\label{thm:sup_gap}
The greedy adaptivity gap with full-adoption feedback is unbounded: there exists a triggering model $I_{G,F}$ and $k$ such that
$$\frac{\sigma^{\mathfrak f}(\pi^g,k)}{\sigma(S^g(k))}=2^{\Omega(\log\log |V|/\log\log\log |V|)}.$$
\end{theorem}

\begin{theorem}\label{thm:adaptivityGap}
The adaptivity gap for the general triggering model with full-adoption feedback is infinity.
\end{theorem}

In Sect.~\ref{sect:prescribed}, we consider a variant of {\sc InfMax}\xspace such that the seeds can only be chosen among a prescribed vertex set $\overline{V}\subseteq V$, where $\overline{V}$ is specified as an input to the {\sc InfMax}\xspace instance.
We show that, under this setting with \texttt{LTM}\xspace, both the adaptivity gap and the supremum of the greedy adaptivity gap with the full-adoption feedback model are unbounded (Lemma~\ref{lem:ltm_precribed}).
Since it is common in practice that only a subset of nodes in a network is visible or accessible to the seed-picker, Lemma~\ref{lem:ltm_precribed} is also interesting on its own.
In Sect.~\ref{sect:proofs}, we show that how Lemma~\ref{lem:ltm_precribed} can be used to prove Theorem~\ref{thm:sup_gap} and Theorem~\ref{thm:adaptivityGap}.
Notice that Theorem~\ref{thm:sup_gap} and Theorem~\ref{thm:adaptivityGap} hold for the standard {\sc InfMax}\xspace setting without a prescribed set of seed candidates, but we do not know if they hold for \texttt{LTM}\xspace (instead, they are for the more general triggering model).

We first present the following lemma revealing a special additive property for \texttt{LTM}\xspace, which will be used later.
\begin{lemma}\label{lem:additive}
Suppose $I_{G,F}$ is \texttt{LTM}\xspace. If $U_1,U_2\subseteq V$ with $U_1\cap U_2=\emptyset$ satisfy that there is no path from any vertices in $U_1$ to any vertices in $U_2$ and vice versa, then $\sigma(U_1)+\sigma(U_2)=\sigma(U_1\cup U_2)$.
\end{lemma}
\begin{proof}
For any seed set $S\subseteq V$, $\sigma(S)$ can be written as follows:
\begin{equation}\label{eqn:sum_g}
\sigma(S)=\sum_{\phi}\Pr(\phi\mbox{ is sampled})\cdot\left|I_{G,F}^\phi(S)\right|.
\end{equation}

For $U_1$ and $U_2$ in the lemma statement, since each vertex can only have at most one incoming live edge (in Definition~\ref{def:LTM}, each $T_v$ has size at most $1$), under any realization $\phi$, each vertex $v\in V\setminus(U_1\cup U_2)$ that is reachable from vertices in $U_1\cup U_2$ is reachable from either vertices in $U_1$ or vertices in $U_2$, but not both.
Therefore, $|I_{G,F}^\phi(U_1)|+|I_{G,F}^\phi(U_2)|=|I_{G,F}^\phi(U_1\cup U_2)|$ for any $\phi$, and the lemma follows from considering the decomposition of $\sigma(U_1)$ and $\sigma(U_2)$ according to (\ref{eqn:sum_g}).
\end{proof}

\subsection{On \texttt{LTM}\xspace with Prescribed Seed Candidates}
\label{sect:prescribed}
\begin{definition}\label{def:infmax_v}
  The \emph{influence maximization problem with prescribed seed candidates} is an optimization problem which takes as inputs $G=(V,E)$, $F$, $k\in{\mathbb Z}^+$, and $\overline{V}\subseteq V$, and outputs a seed set $S\subseteq\overline{V}$ that maximizes the expected total number of infections: $S\in\argmax_{S \subseteq\overline{V}: |S| \leq k} \sigma(S)$.
  The \emph{adaptive influence maximization problem with prescribed seed candidates} has the same definition as it is in Definition~\ref{def:infmax_adaptive}, with the exception that the range of the function $\pi$ is now $\overline{V}$, and $\Pi$ is the set of all such policies.
\end{definition}

\begin{lemma}\label{lem:ltm_precribed}
For {\sc InfMax}\xspace with prescribed seed candidates with \texttt{LTM}\xspace and full-adoption feedback, the adaptivity gap is infinity, and the greedy adaptivity gap is $2^{\Omega(\log |V|/\log\log|V|)}$.
\end{lemma}
\begin{proof}
For $d,W\in{\mathbb Z}^+$ with $d$ being sufficiently large and $W\gg d^{d+1}$, we construct the following (adaptive) {\sc InfMax}\xspace instance with prescribed seed candidates:
\begin{itemize}
    \item the edge-weighted graph $G=(V,E,w)$ consists of an $(d+1)$-level directed full $d$-ary tree with the root node being the sink
     (i.e., an in-arborescence) and $W$ vertices each of which is connected \emph{from} the root node of the tree; the weight of each edge in the tree is $1/d$, and the weight of each edge connecting from the root to those $W$ vertices is $1$;
    \item the number of seeds is given by $k=2(\frac{d+1}2)^d$;
    \item the prescribed set for seed candidates $\overline{V}$ is the set of all the leaves in the tree.
\end{itemize}

Since the leaves are not reachable from one to another, Lemma~\ref{lem:additive} indicates that choosing any $k$ vertices among $\overline{V}$, i.e., the leaves, infects the same number of vertices in expectation.
It is easy to see that a single seed among the leaves will infect the root node with probability $1/d^d$, and those $W$ vertices will be infected with probability $1$ if the root of the tree is infected.
Thus, for any seed set $S\subseteq\overline{V}$, by assuming all vertices in the tree are infected (in the sake of finding an upper bound for $\sigma(S)$), we have
$\sigma(S)\leq\frac1{d^d}\cdot|S|\cdot W+\sum_{i=0}^dd^i<\frac{|S|W}{d^d}+d^{d+1}.$
This gives an upper bound for the performance of both the non-adaptive greedy algorithm and the non-adaptive optimal seed set.

Now, we consider the greedy adaptive policy.
If the root is not infected, there always exists a path from a certain leaf to the root such that all vertices on the path are not infected.
This is because, if all children of an internal node $w$ are infected, $w$ will be infected with probability $1$ (as $f_w=d\times\frac1d=1$ which will always be no smaller than $\theta_w$). In other words, if an internal node is uninfected, at least one of its children is uninfected.
It is easy to see that, before the root is infected, the greedy adaptive policy will always choose a leaf such that all vertices on the path between the leaf and the root are uninfected.

Next, we evaluate the expected number of seeds required to infect the root, under the greedy adaptive policy.
Suppose the tree only has two levels (i.e., a star).
The number of seeds among the leaves required to infect the root is a random variable with uniform distribution on $\{1,\ldots,d\}$, with expectation $\frac{d+1}2$.
By induction on the number of levels of the tree, with a $d$-level tree as it is in our case, the expected number of seeds required to infect the root is $(\frac{d+1}2)^d$, which equals to $\frac{k}2$.
By Markov's inequality, the $k$ seeds chosen according to the greedy adaptive policy will infect the root with probability at least $1/2$.
Therefore, $\sigma^{\mathfrak f}(\pi^g,k)\geq\frac12W$, and the optimal adaptive policy can only be better: $\max_{\pi\in\Pi}\sigma^{\mathfrak f}(\pi,k)\geq\sigma^{\mathfrak f}(\pi^g,k)\geq\frac12W$.

Putting together, both the adaptivity gap and the supremum of the greedy adaptivity gap is at least
$$\frac{\frac12W}{\frac{kW}{d^d}+d^{d+1}}=\frac{\frac12W}{\frac1{2^{d-1}}(1+\frac1d)^dW+d^{d+1}\cdot}=\Omega\left(2^{d}\right),$$
if setting $W=d^{d+10}\gg d^{d+1}$.
The lemma concludes by noticing $d=\Omega(\frac{\log|V|}{\log\log|V|})$ (in particular, $|V|=W+o(W)=d^{d+10}+o(d^{d+10})$, so $\log|V|=d\log d+o(d\log d)$, $\log\log|V|=\log d +o(\log d)$, and $d=\Omega(\frac{\log|V|}{\log\log|V|})$ as claimed).
\end{proof}

\subsection{Proof of Theorem~\ref{thm:sup_gap}, \ref{thm:adaptivityGap}}
\label{sect:proofs}
To prove Theorem~\ref{thm:sup_gap} and Theorem~\ref{thm:adaptivityGap}, we construct an {\sc InfMax}\xspace instance with a special triggering model $I_{G,F}$ which is a combination of \texttt{ICM}\xspace and \texttt{LTM}\xspace.

\begin{definition}\label{def:LTMc}
The \emph{mixture of \texttt{ICM}\xspace and \texttt{LTM}\xspace} is a triggering model $I_{G,F}$ where $G=(V,E,w)$ is an edge-weighted graph with $w(u,v)\in(0,1]$ for each $(u,v)\in E$ and each vertex $v$ is labelled either \textbf{IC} or \textbf{LT} such that $T_v$ is sampled according to $\mathcal{F}_v$ described in Definition~\ref{def:ICM} if $v$ is labelled \textbf{IC} and $T_v$ is sampled according to $\mathcal{F}_v$ described in Definition~\ref{def:LTM} if $v$ is labelled \textbf{LT}.
In addition, each vertex $v$ labelled \texttt{L} satisfies $\sum_{u\in\Gamma(v)}w(u,v)\leq1$.
\end{definition}

To conclude Theorem~\ref{thm:sup_gap} and Theorem~\ref{thm:adaptivityGap}, we construct an edge-weighted graph $G=(V,E,w)$ on which the greedy adaptive policy significantly outperforms the non-adaptive greedy algorithm.
Let $M\gg d^{d+1}$ be a large integer.
We reuse the graph with a tree and $W$ vertices in the proof of Lemma~\ref{lem:ltm_precribed}.
We create $M$ such graphs and name them $T_1,\ldots,T_M$.
Let $L=d^d$ be the number of leaves in each $T_i$.
Let ${\mathbb Z}_L=\{1,\ldots,L\}$ and ${\mathbb Z}_L^M$ be the set of all $M$-dimensional vectors whose entries are from ${\mathbb Z}_L$.
For each ${\mathbf z}=(z_1,\ldots,z_M)\in{\mathbb Z}_L^M$, create a vertex $a_{{\mathbf z}}$ and create a directed edge from $a_{{\mathbf z}}$ to the $z_i$-th leaf of the tree $T_i$ for each $i=1,\ldots,M$.
The weight of each such edge is $1$.
Let $A=\{a_{{\mathbf z}}\mid{\mathbf z}\in{\mathbb Z}_L^M\}$.
Notice that $|A|=L^M$ and each $a_{{\mathbf z}}\in A$ is connected to $M$ vertices from $T_1,\ldots,T_M$ respectively.
The leaves of $T_1,\ldots,T_M$ are labelled as \textbf{IC}, and the remaining vertices are labelled as \textbf{LT}.
Finally, set $k=2(\frac{d+1}2)^d$ as before.

Due to that $M$ is large, it is more beneficial to seed a vertex in $A$ than a vertex elsewhere.
In particular, seeding a root in certain $T_i$ infects $W$ vertices, while seeding a vertex in $A$ will infects $M\cdot(\frac1d)^dW\gg W$ vertices in expectation.

It is easy to see that, in the non-adaptive setting, the optimal seeding strategy is to choose $k$ seeds from $A$ such that they do not share any out-neighbors, in which case the $k$ chosen seeds will cause the infection of exactly $k$ leaves in each $T_i$.
This is also what the non-adaptive greedy algorithm will do.
As before, to find an upper bound for any seed set $S$ with $|S|=k$, we assume that all vertices in each $T_i$ are infected, and we have
$\sigma(S)\leq M\left(k\cdot\frac1{d^d}W+\sum_{i=0}^dd^i\right).$

For the similar reason as it is in the proof of Lemma~\ref{lem:ltm_precribed}, the greedy adaptive policy would iteratively pick a seed $a_{{\mathbf z}}\in A$ such that, for each $i=1,\ldots,M$, if the root in $T_i$ is not yet infected, the path from $z_i$-th leaf to the root in $T_i$ contains no infected vertices.
By the same analysis in the proof of Lemma~\ref{lem:ltm_precribed}, by choosing $k$ seeds among $A$ as described above, which is equivalent as choosing $k$ leaves in each of $T_1,\ldots,T_M$ simultaneously, the root in each $T_i$ is infected with probability at least $\frac12$.
Therefore, the expected total number of infected vertices is at least
$M\cdot\frac12W$.

It may seem problematic that the greedy adaptive policy may start to seed the roots among $T_1,\ldots,T_M$ when it sees that there are already a lot of infected roots (so seeding a root is better than seed a vertex in $A$). However, we can always choose $M$ to be large enough such that, after choosing $k$ seeds adaptively from $A$, the total number of uninfected roots is still significantly more than $d^d$ with high probability, so that seeding a vertex from $A$ is still more beneficial. This is always possible: supposing $p$ is the probability that a root is infected with $k$ adaptive seeds from $A$, we only need to choose $M$ such that $M\cdot(1-p)\gg d^d$.

Putting together as before, both the adaptivity gap and the supremum of the greedy adaptivity gap is at least
$$\frac{M\cdot\frac12W}{M(\frac{kW}{d^d}+d^{d+1})}=\frac{\frac12W}{\frac1{2^{d-1}}(1+\frac1d)^dW+d^{d+1}\cdot}=\Omega\left(2^d\right),$$
if fixing $W=d^{d+10}\gg d^{d+1}$.
Theorem~\ref{thm:adaptivityGap} concludes by letting $d\rightarrow\infty$.
To conclude Theorem~\ref{thm:sup_gap}, we need to show that $d=\Omega(\log\log|V|/\log\log\log|V|)$.
To see this, we set $M=d^{d+10}$ which is sufficiently large for our purpose.
Since we have $L=d^d$, we have $|V|=L^M+o(L^M)=d^{d^{d+11}}+o(d^{d^{d+11}})$, which implies $d=\Omega(\log\log|V|/\log\log\log|V|)$.

\section{A Variant of Greedy Adaptive Policy}
\label{append:variant}
Although we have seen that the adaptive version of the greedy algorithm can perform worse than its non-adaptive counterpart,
    in general, we would still recommend the use of it as long as it is feasible,
as it can also perform significantly better than the non-adaptive greedy algorithm (Theorem~\ref{thm:sup_gap}) while never being too bad (Theorem~\ref{thm:lowerbound}).
As we remarked, the adaptivity may be harmful because exploiting the feedback may make the seed-picker too myopic.
In this section, we propose a less aggressive risk-free version of the greedy adaptive policy, $\pi^{g-}$, in that it balances between
    the exploitation of the feedback and the focus on the average in the conventional non-adaptive greedy algorithm.

First, we apply the non-adaptive greedy algorithm with $|V|$ seeds to obtain an order $\mathcal{L}$ on all vertices.
Then for any $S\subseteq V$ and any partial realization $\varphi$, $\pi^{g-}(S,\varphi)$ is defined to be the first vertex $v$ in $\mathcal{L}$ that is not known to be infected.
Formally, $v$ is the first vertex in $\mathcal{L}$ that are not reachable from $S$ when removing all edges $e$ with $\varphi(e)\in\{{\texttt B},{\texttt U}\}$.
This finishes the description of the policy.

This adaptive policy is always no worse than the non-adaptive greedy algorithm, as it is easy to see that
those seeds chosen by $\pi^g$ are either seeded or infected by previously selected seeds in $\pi^{g-}$.

However, $\pi^{g-}$ can sometimes be conservative.
It is possible that $\pi^{g-}$ has the same performance as the non-adaptive greedy algorithm, but $\pi^g$ is much better.
Especially, when there is no path between any two vertices among the first $k$ vertices in $\mathcal{L}$, $\pi^{g-}$ will make the same choice as the non-adaptive greedy algorithm.
The {\sc InfMax}\xspace instance in Sect.~\ref{sect:proofs} is an example of this.

We have seen that $\pi^{g-}$ sometimes performs better than $\pi^g$ (e.g., in those instances constructed in the proofs of Lemma 3.2 and Lemma 3.3) and sometimes performs worse than the $\pi^g$ (e.g., in the instance constructed in Sect.~\ref{sect:proofs}).
Therefore, given a \emph{particular} {\sc InfMax}\xspace instance, for deciding which of $\pi^{g-}$ and $\pi^g$ to be used (we should never consider the non-adaptive greedy algorithm if adaptivity is available, as it is always weakly worse than $\pi^{g-}$), we recommend a comparison of the two policies by simulations.
Notice that the seed-picker can randomly sample a realization $\phi$ and simulate the feedback the policy will receive.
Thus, given $I_{G,F}$, both $\pi^{g-}$ and $\pi^g$ can be estimated by taking an average over the numbers of infected vertices in a large number of simulations.

\section{Conclusion and Open Problems}
We have seen that the infimum of the greedy adaptivity gap is exactly $(1-1/e)$ for \texttt{ICM}\xspace, \texttt{LTM}\xspace, and general triggering models with both the full-adoption feedback model and the myopic feedback model.
We have also seen that the supremum of this gap is infinity for the full-adoption feedback model.
One natural open problem is to find the supremum of the greedy adaptivity gap for the myopic feedback model.
Another natural open problem is to find the supremum of the greedy adaptivity gap for the more specific \texttt{ICM}\xspace and \texttt{LTM}\xspace.

The greedy adaptivity gap studied in this paper is closely related to the adaptivity gap studied in the past.
Since the non-adaptive greedy algorithm is always a $(1-1/e)$-approximation of the non-adaptive optimal solution, a constant adaptivity gap implies a constant greedy adaptivity gap.
For example, the adaptivity gap for \texttt{ICM}\xspace with myopic feedback is at most $4$ \cite{peng2019adaptive}, so the greedy adaptivity gap in the same setting is at most $\frac4{1-1/e}$.
In addition, the greedy adaptive policy is known to achieve a $(1-1/e)$-approximation to the adaptive optimal solution for \texttt{ICM}\xspace with full-adoption feedback~\cite{golovin2011adaptive},
so the adaptivity gap and the greedy adaptivity gap could either be both constant or both unbounded for \texttt{ICM}\xspace with full-adoption feedback model, but it remains open which case is true.
The adaptivity gap for \texttt{ICM}\xspace with full-adoption feedback, as well as the adaptivity gap for \texttt{LTM}\xspace with both feedback models, are all important open problems.
We believe these problems can be studied together with the greedy adaptivity gap.

\bibliographystyle{plainnat}