\section{Introduction}\label{sec:intro}
\input{sec-intro}

\vspace{-1mm} 
\section{Background \& Related Work}\label{sec:related}
\input{sec-related}

\vspace*{-1ex} 
\section{UIC\xspace Model under competition}\label{sec:model}
\input{sec-model}

\vspace{-1mm} 
\section{Properties of UIC\xspace}\label{sec:prop}
\input{sec-properties}


\vspace{-2mm} 
\section{Approximation Algorithms}\label{sec:algo}
\input{sec-algos1}\label{sec:msgrd}
\input{sec-algos3}
\input{sec-algos2}
\input{sec-algos4}

\vspace*{-1ex} 
\section{Experiments}\label{sec:exp}
\input{sec-exp}

\eat{ 
\vspace*{-1ex} 
\section{Summary \& Discussion}\label{sec:concl}
\input{sec-concl}
} 

\clearpage  
{
\bibliographystyle{abbrv}


\subsection{{\rm MaxSeqGRD}\xspace Algorithm} \label{sec:msgrd}



\eat{
\spara{Pure competition}

Notice that UIC\xspace encompasses any arbitrary degree of competition. 
{\em Pure competition} is a special case on the utility functions such that each node can adopt at most one item. 
If a node has not adopted any item and multiple items are desired at the same timestep, then it chooses the best utility item among those desired. Once an item is adopted, the adoption set does not change throughout the propagation. Pure competition arises naturally for items of the same category, e.g., smartphone. Users typically adopt one phone and once they adopt a phone, the adoption does not change soon.

Lastly we show an important property of utility under competition. When value is submodular and price is additive, the utility is strictly subadditive i.e., the utility of a bundle will be at most the sum of the utilities of its constituent items. We formalize this in the next lemma.

\begin{lemma}\label{lem:subaddu}
When value is submodular and price is additive, the utility is subadditive
\end{lemma}
\begin{proof}
simple algebra. left as TODO
\end{proof}
}

\begin{algorithm}
\caption{${\rm MaxSeqGRD}\xspace(G, \epsilon, \ell, \mathbfcal{S}^P, I_2, \bvec)$} \label{alg:msgrd}
\begin{algorithmic}[1] 
\State $S^P \leftarrow$ Seed nodes of the allocation $\mathbfcal{S}^P$
\State $S^{\it Grd} \leftarrow \textsf{PRIMA}^+(G, \epsilon, \ell, S^P, \bvec)$ \label{lin:msgrd_PRIMM}
\State $\mathbfcal{S}^{\it Grd} \leftarrow {\rm SeqGRDProc}\xspace(G, \mathbfcal{S}^P, I_2, \bvec, S^{\it Grd})$ \label{lin:msgrd_sgrd}
\If{$\mathbfcal{S}^P = \emptyset$}
\State $\mathbfcal{S}^{\it Max} \leftarrow {\rm MaxGRDProc}\xspace(G, I_2, \bvec, S^{\it Grd})$ \label{lin:msgrd_mgrd}
	\If{ $\rho(\mathbfcal{S}^{\it Max}) > \rho(\mathbfcal{S}^{\it Grd}) $ }
		\State $\mathbfcal{S}^{\it Grd} \leftarrow \mathbfcal{S}^{\it Max}$
	\EndIf 
\EndIf 
\State Return $\mathbfcal{S}^{\it Grd}$ as the final allocation 
\vspace{0.7mm}
\hrule

\Procedure{${\rm SeqGRDProc}\xspace$}{$G, \mathbfcal{S}^P, I_2, \bvec, S^{\it Grd}$}
\State $\mathbfcal{S}^{\it Seq} \leftarrow \emptyset$ 
\State Sort $I_2$ in decreasing order of the expected truncated utility \label{lin:sgrdp_sort}
\State ${\it Added} \leftarrow \emptyset$
\For{$i \in I_2$}
\State $S^{\it Grd}_i \leftarrow \text{ top } b_i \text{ nodes from } S^{\it Grd}$ \label{lin:msgrd_assign2}
\If{$\rho(\mathbfcal{S}^{\it Seq} \mid \mathbfcal{S}^P) < \rho((\mathbfcal{S}^{\it Seq} \cup (S^{\it Grd}_i \times \{i\})) \mid \mathbfcal{S}^P)$} \label{lin:msgrd_positives}
\State $\mathbfcal{S}^{\it Seq} \leftarrow \mathbfcal{S}^{\it Seq} \cup (S^{\it Grd}_i \times \{i\})$
\State Remove those $b_i$ nodes from $S^{\it Grd}$
\State ${\it Added} \leftarrow {\it Added} \cup \{i\} $
\EndIf \label{lin:msgrd_positivee}
\EndFor	
\For{$i \in I_2 \setminus {\it Added} $}\label{lin:msgrd_randoms}
\State $S^{\it Grd}_i \leftarrow \text{ top } b_i \text{ nodes from } S^{\it Grd}$ 
\State $\mathbfcal{S}^{\it Seq} \leftarrow \mathbfcal{S}^{\it Seq} \cup (S^{\it Grd}_i \times \{i\})$
\State Remove those $b_i$ nodes from $S^{\it Grd}$
\EndFor	\label{lin:msgrd_randomse}
\State Return $\mathbfcal{S}^{\it Seq}$
\EndProcedure

\vspace{0.7mm}
\hrule

\Procedure{${\rm MaxGRDProc}\xspace$}{$G, I_2, \bvec, S^{\it Grd}$}
	\State $S^{\it Grd}_i \leftarrow \text{top $b_i$ nodes of $S^{\it Grd}$}$, $\forall i\in I_2$; $i_{max} \leftarrow 0$
    \State $i_{max} \leftarrow \argmax_{i \in I_2}\{ \rho(S^{\it Grd}_i \times \{i\})  \}$\label{lin:mgrd}
    \State Return $S^{\it Grd}_{i_{max}} \times \{ i_{max} \}$
\EndProcedure

\end{algorithmic}
\end{algorithm}

We are now ready to present our approximation algorithm ${\rm MaxSeqGRD}\xspace$ shown in Algorithm \ref{alg:msgrd}. 
Given a graph $G$, to-be-allocated itemset $I_2$, 
	item budget vector $\bvec$ of the items in $I_2$, accuracy parameter $\epsilon$, tolerance parameter $\ell$, the partial allocation $\mathbfcal{S}^P$, set of items to be allocated $I_2$, and item budget vector $\bvec$ 
	${\rm MaxSeqGRD}\xspace$ first selects $\overline{b}$ seeds where $\overline{b} = \sum_{i \in I_1\cup I_2} b_i$ (line \ref{lin:msgrd_PRIMM}). To select the seeds it uses an algorithm, called $\textsf{PRIMA}^+$, that have \textit{prefix preserving on the marginal} property. We explain this property formally and present the $\textsf{PRIMA}^+$ algorithm in \textsection \ref{sec:algod}.
After selecting the seeds, {\rm MaxSeqGRD}\xspace finds the first allocation, $\mathbfcal{S}^{\it Grd}$, by invoking a procedure ${\rm SeqGRDProc}\xspace$, line \ref{lin:msgrd_sgrd}. ${\rm SeqGRDProc}\xspace$ allocates items in a particular \textit{sequence} determined by items' truncated utility.  Then it selects a second allocation, $\mathbfcal{S}^{\it Max}$ using another procedure ${\rm MaxGRDProc}\xspace$ (line \ref{lin:msgrd_mgrd}). 
Roughly speaking ${\rm MaxGRDProc}\xspace$ selects the item that produces the \textit{maximum} marginal gain in social welfare w.r.t. the existing allocation $\mathbfcal{S}^P$. Between $\mathbfcal{S}^{\it Grd}$ and $\mathbfcal{S}^{\it Max}$, the one that produces higher welfare, is returned as the final allocation. 
We will explain {\rm SeqGRDProc}\xspace and {\rm MaxGRDProc}\xspace in details soon. Before that we present the following main result of ${\rm MaxSeqGRD}\xspace$ algorithm.

\begin{theorem} \label{thm:main}
Let $\mathbfcal{S}^{\it Grd}$ be the output allocation generated by ${\rm MaxSeqGRD}\xspace$ and $\mathbfcal{S}^{\it OPT}$ be the optimal allocation. 
Given $\epsilon, \ell >0$ and a partial allocation $\mathbfcal{S}^P$, with probability at least $1 - \frac{1}{|V|^{\ell}}$, 
\begin{equation} \label{eq:approx1}
\rho(\mathbfcal{S}^{\it Grd} \cup \mathbfcal{S}^P) \geq \left(1 - \frac{1}{e} - \epsilon \right) \frac{u_{min}}{u_{max}} \rho(\mathbfcal{S}^{\it OPT} \cup \mathbfcal{S}^P).
\end{equation}

Further, when $\mathbfcal{S}^P = \emptyset$,
\begin{equation} \label{eq:approx2}
\rho(\mathbfcal{S}^{\it Grd} \cup \mathbfcal{S}^P) \geq \left(1 - \frac{1}{e} - \epsilon \right) \max \left\lbrace \frac{1}{m}, \frac{u_{min}}{u_{max}} \right\rbrace  \rho(\mathbfcal{S}^{\it OPT} \cup \mathbfcal{S}^P).
\end{equation}

 
\end{theorem} 

This theorem is a direct consequence of the bounds that the two procedure ${\rm SeqGRDProc}\xspace$ and ${\rm MaxGRDProc}\xspace$ individually attain. We analyze the performance of the two procedures in isolation next.

}

\subsection{MaxGrd Algorithm}

Our next algorithm {\rm MaxGRD}\xspace provides  $\frac{1}{m}(1-\frac{1}{e})$-approximation, when $\mathbfcal{S}^P = \emptyset$, i.e., no prior allocation.
\eat{ 
\note[Laks]{The pseudocode doesn't match this description. There is no marginal there. 
Did you want to only use {\rm MaxGRD}\xspace when there is no previous allocation? In this case, use of $I_2$ w/o 
any explanation is confusing. 
In general, there is a confusing array of notation used in the paper which may annoy a reviewer: e.g., $S, S_i, S^{\mathbfcal{S}}, S^{Grd}$, 
to mention a few. I am not sure if all of these are necessary. Look for ways to consolidate notation. \red{Addressed}} 
} 
The pseudocode is shown in Algorithm \ref{alg:mgrd}. Like {\rm SeqGRD}\xspace, {\rm MaxGRD}\xspace also selects its seedset $S^{\it Max}$ using $\textsf{PRIMA}^+$, but the size of the seedset  is different: $\bmax := \max_{i \in I_2} b_i$, i.e., the maximum budget of any unallocated item (line \ref{lin:mgrd_PRIMM}). Then for every item $i \in I_2$, it computes the expected marginal social welfare of the allocation $\rho( (S^{\it Max}_i \times \{i\}) \mid \mathbfcal{S}^P)$, where $S^{\it Max}_i$ is the set of first $b_i$ nodes of $S^{\it Max}$. It returns the allocation with the maximum welfare (line \ref{lin:mgrd}). 

\begin{algorithm}
\caption{${\rm MaxGRD}\xspace(G, \epsilon, \ell, \mathbfcal{S}^P, I_2, \bvec)$} \label{alg:mgrd}
\begin{algorithmic}[1] 
\State $S^{\it Max} \leftarrow  \textsf{PRIMA}^+(G, \epsilon, \ell, S^P, \bvec, \max_{i \in I_2} b_i)$  \label{lin:mgrd_PRIMM} 
\State $S^{\it Max}_i \leftarrow \text{top $b_i$ nodes of $S^{\it Max}$}$, $\forall i\in I_2$
    \State $i_{max} \leftarrow \argmax_{i \in I_2}\{ \rho(S^{\it Max}_i \times \{i\} \mid \mathbfcal{S}^P)  \}$\label{lin:mgrd}
    \State Return $S^{\it Max}_{i_{max}} \times \{ i_{max} \}$
\end{algorithmic}
\end{algorithm}

{Notice that {\rm MaxGRD}\xspace is applicable even when $S^p \neq \emptyset$, so we have provided the algorithm for this general case. However, it enjoys an approximation bound only for the special case, when $S^p=\emptyset$. } 
We prove the following lemma under this constraint, which is instrumental in the proof of the approximation bound. A key observation is that given a possible world $w$, the utility function $\mathcal{U}\xspace_w(\cdot)$ in that possible world is submodular. This follows from the fact that valuation is submodular and price and noise, being additive are both modular. 
\vspace{-2mm}
\eat{ 
\begin{lemma}\label{lem:bound3}
In any arbitrary allocation $\mathbfcal{S}^A$, let $S_i$ be the seed nodes of item $i$, then when $\mathbfcal{S}^P = \emptyset$\eat{or under pure competition}, $\rho(\cup_{i=1}^m (S_i \times \{i\}) \cup \mathbfcal{S}^P ) \leq \sum_{i=1}^m \rho( (S_i \times \{i\}) \cup \mathbfcal{S}^P)$.
\end{lemma}
} 

\begin{lemma}\label{lem:bound3}
Let  $\mathbfcal{S} := \cup_{i=1}^m (S_i \times \{i\})$ be an arbitrary allocation, where $S_i$ is the set of seed nodes of item $i$. Then  $\rho(\cup_{i=1}^m (S_i \times \{i\})) \leq \sum_{i=1}^m \rho( (S_i \times \{i\}))$.
\end{lemma} 

\begin{proof}[Sketch] 
Consider an arbitrary but fixed possible world $w$ and an arbitrary item $i\in I_2$.
Let $v$ be any node that adopts $i$ in  $w$ under the allocation $\cup_{i=1}^m (S_i \times \{i\})$. 
We can show
that $v$ must also adopt $i$ in $w$ when the allocation is only $(S_i \times \{i\})$. The lemma follows from this. 
\eat{ 
This is sufficient to prove the lemma.
\eat{
We first consider the case of pure competition.
Since $v$ adopts $i$ in $w$ under the allocation $\cup_{i=1}^m (S_i \times \{i\}) \cup \mathbfcal{S}^P$,
	we know that the shortest path from any seed node for any item in $I_1\cup I_2$ to $v$ in the possible world $w$ is some path from a seed node in $S_i$ to $v$, 
	because otherwise another item will arrive $v$ first and by the nature of pure competition $v$ will no longer have chance to adopt $i$.
Let $P$ be this shortest path.
Moreover, if any other item $j$ reaches $v$ through some other shortest paths of the same length as $P$, then $j$ must be inferior of $v$, i.e. $j$'s utility is less than $i$ in the possible world $w$.
Now let the new allocation be $(S_i \times \{i\})  \cup \mathbfcal{S}^P$. 
Under the same possible world $w$, path $P$ still exists, and is still the shortest path from any seed node for items in $\{i\} \cup I_1$ to $v$, and $i$ would still be superior to any other item that could arrive at $v$
	at the same time as $i$, therefore $v$ would still adopt $i$.
}

Since $v$ adopts $i$ in $w$ under the allocation $\mathbfcal{S} = \cup_{i=1}^m (S_i \times \{i\})$, there is a path $P$ from some seed node in $S_i$ to $v$ such that all nodes on $P$ adopts $i$.
For any node $u$ on this path, let $\mathcal{A}^{\mathbfcal{S}}_w(u) $ be the set of items $u$ adopts at the same propagation step when $u$ adopts $i$.
The fact that $u$ adopts $i$ means that $\mathcal{U}\xspace_w(i \mid \mathcal{A}^{\mathbfcal{S}}_w(u)\setminus \{i\}) = \mathcal{U}\xspace_w(\mathcal{A}^{\mathbfcal{S}}_w(u))  - \mathcal{U}\xspace_w(\mathcal{A}^{\mathbfcal{S}}_w(u)\setminus \{i\}) \ge 0$.
Since $\mathcal{U}\xspace_w$ is submodular, we know that $\mathcal{U}\xspace_w(i) \ge 0$.
Therefore, when the allocation is only $S_i \times \{i\}$, all nodes in the path $P$ would still adopt $i$, including node $v$.} 
\end{proof} 
\vspace{-2mm}






\eat{
\weic{Note that I use notation $\mathcal{U}\xspace_w$. Please check before for consistency. Also for a possible world, we should consistently use $w$ or $W$.}

\weic{The old proof did not clearly distinguish the pure competition case and the case of $\mathbfcal{S}^P = \emptyset$. Thus 
	the old argument used something like (a) $i$ arrives $v$ first, but this may not be true in the soft competition, since $i$ can arrive later, as long as it is compatible with the earlier items; and (b) other items arriving at $v$ at the same
	item must be inferior to $i$, but this is also not true under soft competition. So I am changing the arguments in this proof.}
	
}


\eat{ 
Using Lemma \ref{lem:bound3}, we can now prove the following approximation bound, which holds when $\mathbfcal{S}^P = \emptyset$. 
} 
\begin{theorem}\label{lem:mgrd_bound}
	Suppose that $\mathbfcal{S}^P = \emptyset$.
Let $\mathbfcal{S}^{\it Max}$ be the allocation produced by {\rm MaxGRD}\xspace. Given $\epsilon, \ell >0$,  we have $\rho(\mathbfcal{S}^{\it Max}) \geq \frac{1}{m}(1-\frac{1}{e}- \epsilon)\rho(\mathbfcal{S}^A)$ w.p. at least $1 - \frac{1}{|V|^\ell}$, where $\mathbfcal{S}^A$ is any arbitrary allocation.
\end{theorem}

\begin{proof}
Recall that item $i$ has a budget $b_i$ and expected utility $u_i$. 
Since in an arbitrary allocation $|S^A_i| \leq b_i$, from the prefix preserving property of $\textsf{PRIMA}^+$  we have,
\begin{equation} \label{eq:2Soft}
\sigma(S^{\it Max}_i) \geq \left(1 - \frac{1}{e} - \epsilon \right) \sigma(S^A_i).
\end{equation}
Let $\mathbb{E}[\mathcal{U}\xspace^+(i)]$ be the expected positive utility of item $i$.
We have $\rho(S^{\it Max}_i \times \{i\}) = \mathbb{E}[\mathcal{U}\xspace^+(i)]\cdot \sigma(S^{\it Max}_i) $ and
	$\rho(S^A_i \times \{i\}) = \mathbb{E}[\mathcal{U}\xspace^+(i)]\cdot \sigma(S^A_i)$.
Therefore, from Eq.\eqref{eq:2Soft} we have
\begin{equation} \label{eq:welfare2pure}
\rho(S^{\it Max}_i \times \{i\}) \geq \left(1 - \frac{1}{e} - \epsilon \right) \rho(S^A_i \times \{i\}) .
\end{equation}
When $\mathbfcal{S}^P = \emptyset$, using Eq. \ref{eq:welfare2pure} and Lemma \ref{lem:bound3}, we have 
\begin{align*}
&\rho(\mathbfcal{S}^{\it Max} \cup \mathbfcal{S}^P) = \rho(\mathbfcal{S}^{\it Max}) = \max_{i \in I_2}\{\rho(S^{\it Max}_i \times \{i\})\}		\\
&\ge  \frac{1}{m} \sum_{i=1}^m \rho(S^{\it Max}_i \times \{i\})\geq \frac{1}{m} \left(1-\frac{1}{e}- \epsilon \right) \sum_{i=1}^m \rho(S^A_i \times \{i\} )\\
&\geq \frac{1}{m} \left(1-\frac{1}{e}- \epsilon \right)  \rho(\cup_{i=1}^m (S^A_i \times \{i\}) )= \frac{1}{m} \left(1-\frac{1}{e}- \epsilon \right) \rho(\mathbfcal{S}^A).
\end{align*}
\end{proof}


\eat{
\weic{
The pure competition case may have a problem when $\mathbfcal{S}^P \ne \emptyset$.
Similar to the above we need to show that 
\begin{equation} \label{eq:welfare2Soft}
\rho( (S^{\it Max}_i \times \{i\}) \cup \mathbfcal{S}^P) \geq \left(1 - \frac{1}{e} - \epsilon \right) \rho( (S^A_i \times \{i\}) \cup \mathbfcal{S}^P) .
\end{equation}
But this cannot be derived directly from Eq.~\eqref{eq:welfare2pure}.
I do not see how to show the above.

Note that if we consider the marginal version, the following is still incorrect:
\begin{equation} \label{eq:welfare2Softmargin}
\rho( (S^{\it Max}_i \times \{i\}) \mid \mathbfcal{S}^P) \geq \left(1 - \frac{1}{e} - \epsilon \right) \rho( (S^A_i \times \{i\}) \mid \mathbfcal{S}^P) .
\end{equation}
This is because, first, $S^{\it Max}_i$ is not selected based on such marginal; second, it is possible that
	$\rho( (S^{\it Max}_i \times \{i\}) \mid \mathbfcal{S}^P) = 0$  while $\rho( (S^A_i \times \{i\}) \mid \mathbfcal{S}^P) > 0$.
We need to discuss and find a solution here.
}
}

\textbf{Can {\rm MaxGRD}\xspace produce better welfare than {\rm SeqGRD}\xspace?} 
{Hypothetically, there can be situations where {\rm MaxGRD}\xspace can produce better welfare than {\rm SeqGRD}\xspace.  E.g., consider a network with nodes $\{u, v, w, x\}$ and edges $\{(u,v), (v,w), (x,w)\}$ where all edge probabilities are $1$. There are two items $i, j$, with  all noise terms being $0$. The utilities are $\mathcal{U}\xspace(\{i\}) = 10, \mathcal{U}\xspace(\{j\})=1, \mathcal{U}\xspace(\{i,j\})=0$ and both items $i$ and $j$ have a budget of $1$. Then {\rm SeqGRD}\xspace\ will yield the allocation $\mathbfcal{S}^{Seq} = \{(u,i), (x,j)\}$, resulting in a social welfare of $2\times 10 + 1\times 2 = 22$. On the other hand, {\rm MaxGRD}\xspace\ will only allocate $u$ to $i$, resulting in a social welfare of $3\times 10 = 30$. } 

{In our experiments, however, we find that situations where {\rm MaxGRD}\xspace\ dominates {\rm SeqGRD}\xspace\ are rare. We hypothesize that this is because in a large network, with a number of seeds that is a small fraction of the network size $n$, blocking caused by the allocation of seeds to additional items by {\rm SeqGRD}\xspace\ is less likely to occur. } 
\eat{The highest utility item is $i_1$ (utility $10$). Both $i_2$ and $i_3$ (each with utility $1$) exhibit pure competition against $i_1$, however between themselves they exhibit soft competition: $\mathcal{U}\xspace(\{i_2,i_3\}) = 1.5$

Hence throwing away $i_2$ and $i_3$ altogether is not ideal. Thus in {\rm SeqGRD}\xspace, every allocation of the $i_2$ and $i_3$ blocks the propagation of $i_1$ and hence produces negative marginal. {\rm SeqGRD}\xspace will still allocate $i_2$ and $i_3$ (Line 14), resulting in a drop in the welfare from the allocation of those. However, {\rm MaxGRD}\xspace will allocate only one item, $i_1$. Consequently, the negative marginal producing allocation will be avoided. Such a situation is rare in real networks because the budget is typically much less than the network size, hence it is not possible to reach all the nodes by allocating one item. Hence in our experiments (\textsection \ref{sec:exp}) we always find {\rm SeqGRD}\xspace to produce better welfare.}  

{Note that the approximation guarantee of  {\rm SeqGRD}\xspace  holds also when $\mathbfcal{S}^p = \emptyset$. Thus running both {\rm SeqGRD}\xspace and {\rm MaxGRD}\xspace individually and returning the allocation with higher welfare 
would achieve a $max\{\frac{{u_{\rm min}} \xspace}{{u_{\rm max}} \xspace},\frac{1}{m}\}(1-\frac{1}{e})$-approximation, as a consequence of
 Theorems \ref{lem:sgrd_bound} and \ref{lem:mgrd_bound}.} 


\eat{
\spara{Proof of Theorem \ref{thm:main}}

Let $allalloc^A$ be any arbitrary allocation. $\mathbfcal{S}^{\it Max}$ is allocation {\rm SeqGRDProc}\xspace produces.
From Lemma \ref{lem:sgrd_bound} w.p. at least $1 - \frac{1}{|V|^{\ell}}$, $$\rho(\mathbfcal{S}^{\it Max} \cup \mathbfcal{S}^P) \geq \left(1 - \frac{1}{e} - \epsilon \right) \frac{u_{min}}{u_{max}} \rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P)$$ 

Further let $\mathbfcal{S}^{\it Max}$ be the allocation of {\rm MaxGRD}\xspace. When $\mathbfcal{S}^P = \emptyset$, from Lemma \ref{lem:mgrd_bound} w.p. at least $1 - \frac{1}{|V|^{\ell}}$, $$\rho(\mathbfcal{S}^{\it Max} \cup \mathbfcal{S}^P) \geq \frac{1}{m}(1-\frac{1}{e}- \epsilon)\rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P)$$

Since {\rm MaxSeqGRD}\xspace returns the maximum of the two welfares produced by $\mathbfcal{S}^{\it Max}$ and $\mathbfcal{S}^{\it Max}$ and setting $\mathbfcal{S}^A = \mathbfcal{S}^{\it OPT}$, we have the result of Theorem \ref{thm:main}.
}

\eat{
This above guarantee, however, does not hold when $\mathbfcal{S}^P \neq \emptyset$ and we do not have pure competition among items. In particular Lemma \ref{lem:bound3} fails as we show in the following counter example.
}


\eat{

\weic{the formula on expected truncated utility $\mathbb{E}(\mathcal{U}\xspace^+(i)) = P(\mathcal{N}\xspace(i)\geq 0) \times \mathcal{U}\xspace^D(i)$ is wrong, where deterministic utility $\mathcal{U}\xspace^D(i) = \mathcal{V}\xspace(i) - \mathcal{P}\xspace(i)$.
	The correct one is an integral related to the noise distribution.
	But we do not need such a formula.
}

\weic{Need to confirm whether we only know that Lemma \ref{lem:bound3} fails, or we also know that the approximation guarantee fails. If only the former, we cannot say that Lemma~\ref{lem:greedBoundSoft} does not hold.}

\weic{My edits stop here.}

}


\subsubsection{$\textsf{PRIMA}^+$}\label{sec:algod}

We now present our $\textsf{PRIMA}^+$ algorithm used by {\rm SeqGRD}\xspace and {\rm MaxGRD}\xspace to select seeds. 
First, we formally present the property of prefix preservation on marginals.

\eat{ 
\note[Laks]{Make sure notations are used consistently, e.g., the right symbol, font, etc. \red{Addressed}}
} 

\begin{definition}{\sc (Prefix Preservation on Marginals).\ } \label{def:PRIMM}
	Given $G$ $=$ $(V,E,p)$, budget vector $\bvec$, the number of seeds to be selected $\bmax$ and a fixed seed set $S^P$, an influence maximization algorithm $\mathbb{A}$
	is prefix-preserving on marginals w.r.t. $\bvec$ and $S^P$, 
	if for any $\epsilon$ $>$ $0$ and $\ell$ $>$ $0$, 
	$\mathbb{A}$  returns an ordered set $S$ of size $\bmax$, 
	such that   w.p.  at least $1$ $-$ $\frac{1}{|V|^{\ell}}$, $\sigma(S \mid S^P)$ $\geq$ $(1-\frac{1}{e} - \epsilon)$ ${\it OPT}_{\bmax \mid S^P}$ and
	for every $b_i$ $\in$ $\bvec$, the first $b_i$ nodes of $S$, denoted $S_{i}$, satisfies $\sigma(S_{i} \mid S^P)$ $\geq$ $(1-\frac{1}{e} - \epsilon)$ ${\it OPT}_{b_i \mid S^P} $,
	where
	${\it OPT}_{b \mid S^P}$ is the optimal marginal expected spread of $b$ nodes on top the existing seeds $S^P$.
\end{definition}

\eat{ \note[Laks]{Saying that the top-$b_i$ nodes need to satisfy something means you always get to use the TOP $b_i$ nodes as opposed to the NEXT $b_i$ nodes after previous seeds are committed. \red{Addressed}} } 

In \cite{ban2019}, the authors proposed a seed selection algorithm called $\textsf{PRIMA}$ that is prefix-preserving in spread, using the Reverse Reachable Sets (RR-sets), as proposed in IMM \cite{tang15}. Here, we  modify the standard RR-set construction slightly to account for the presence of existing seed set $S^P$: Given an existing allocation $\mathbfcal{S}^P$, we construct a marginal RR-set as follows. Choose a root node $v\in V$ uniformly at random, add it to $R_v$ and start a BFS from $v$. Whenever $u\in R_v$, sample each incoming edge $(u',u)$
w.p. $p_{u'u}$ and add it to $R_v$. Stop when no new nodes are added to $R_v$; if at any stage $R_v$ overlaps $S^P$, i.e., if $R_v\cap S^P\ne\emptyset$, then set $R_v := \emptyset$. That is, whenever a generated RR-set ``hits" $S^P$, just set it to $\emptyset$. Algorithm \ref{alg:marsample} shows the pseudo code of this marginal RR-set sampling process. Given graph $G$, a number $\theta$ denoting how many RR-sets needs to be sampled and a fixed seed nodes $S^P$, $Marginal\_Sampling$ generates $\theta$ number of RR-sets to $\mathcal{R}$ from $G$, based on the marginal on $S^P$.

 
\begin{algorithm}
\caption{$Marginal\_Sampling(G, \mathcal{R}, \theta, S^P)$} \label{alg:marsample}
\begin{algorithmic}[1] 
\While {$|\mathcal{R}| \leq \theta$}
    \State Select $v$ from $G$ uniformly at random
    \State $R \leftarrow BFS(v)$
    \If {$R \cap S^P \neq \emptyset$}
        \State $R \leftarrow \emptyset$
    \EndIf
    \State $\mathcal{R} \leftarrow \mathcal{R} \cup R$
\EndWhile
\State Return $\mathcal{R}$
\end{algorithmic}
\end{algorithm}

$\textsf{PRIMA}^+$ using $Marginal\_Sampling$, achieves the property of prefix preservation on marginals. Its pseudo code is shown in Algorithm \ref{alg:primap}.

\begin{algorithm}
\caption{$\textsf{PRIMA}$ $( G, \epsilon, \ell, S^P, \bvec, \bmax )$} \label{alg:primap}
\begin{algorithmic}
\State Initialize $\mathcal{R} = \emptyset$, $s = 1$, $n = |V|$, $i = 1$, $\epsilon^\prime = \sqrt{2} \cdot \epsilon$, ${\it budgetSwitch} = {\bf false}, \bvec = \bvec \cup \bmax$
\State $\ell = \ell  + \log 2 / \log n $, $\ell^\prime = \log_n(n^{\ell} \cdot |\bvec|)$ \label{lin:ellb}
\While {$i \leq \log_2(n) - 1$ and $s \leq |\bvec|$}
	\State $k = b_s$, $LB =1$
	\State $x = \frac{n}{2^i}$; $\theta_i = \lambda^\prime_k/x$, where $\lambda^\prime_k$ is defined in Eq. \eqref{eq:lambdap}
	\State $Marginal\_Sampling(G,\mathcal{R}, \theta_i, S^P)$
	\If {${\it budgetSwitch}$}
		\State $S_k = $ the first $k$ nodes in the ordered set $S_{b_{s-1}}$ returned from
		the previous call to $\textit{NodeSelection}$
	\Else
		\State $S_k =\textit{NodeSelection}(\mathcal{R}, k)$
	\EndIf
	\If {$n \cdot F_{\mathcal{R}}(S_k) \geq (1 + \epsilon^\prime)\cdot x$} \label{lin:cov}
		\State $LB = n \cdot F_{\mathcal{R}(S_k)} / (1+\epsilon^\prime) $
		\State $\theta_k = \lambda^\ast_k / LB$, where $\lambda^\ast_k$ is defined in Eq. \eqref{eq:lambdaa} \label{lin:suc1}
		\State $Marginal\_Sampling(G,\mathcal{R}, \theta_k, S^P)$
		\State $s = s + 1 $; ${\it budgetSwitch} = {\bf true}$	
	\Else 
	\State $i= i+1$; ${\it budgetSwitch} = {\bf false}$ \label{lin:fail}
	\EndIf
	
\EndWhile
\If {$s \leq |\bvec|$}
	\State $\theta_k = \lambda^\ast_{b_s}/LB$ \label{lin:final}	
\EndIf	
\State $\mathcal{R} = \emptyset$
\State $Marginal\_Sampling(G,\mathcal{R}, \theta_k, S^P)$
\State $S_{\bmax} = \textit{NodeSelection}(\mathcal{R}, \bmax)$ \label{lin:nodes}
\textbf{return} $S_{\bmax}$ as the final seed set;
\end{algorithmic}
\end{algorithm}


It runs in time $O((\bmax+\ell + \log_n |\bvec|)(n+m)\log \ n \cdot \epsilon^{-2})$, where $\bmax := \sum_{i \in I_2} b_i$ for {\rm SeqGRD}\xspace and $\bmax := \max_{i \in I_2} b_i$, for {\rm MaxGRD}\xspace. 

\eat{

\weic{
I have to use the marginal version of $\textsf{PRIMA}^+$, and go through the marginal above to get the result. 
If we go with the old one, not using $\textsf{PRIMA}^+$ on the marginal given $\mathbfcal{S}^P$, 
	there would be yet another issue: $S^p$ may not be in the greedy seed set $S^{\it Seq}$. If it is some obscure seed set with small influence, we are in trouble.
Our intention is to show that 
\begin{align*}
&\rho(\mathbfcal{S}^{Seq} \cup \mathbfcal{S}^P) \ge u_{min} \cdot \sigma(S^{Seq} \cup S^p) \\
& \ge u_{min} \cdot (1-1/e - \epsilon) \cdot \sigma(S^A \cup S^p) \\
&\ge \frac{{u_{\rm min}} \xspace}{{u_{\rm max}} \xspace}(1-\frac{1}{e}- \epsilon) \rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P).
\end{align*}
 But the second inequality holds only when $S^{Seq} \cup S^p$ are really the top seeds selected in $S^{\it Seq}$. If $S^p$ is some obscure seed set
 not in $S^{\it Seq}$, the second inequality above does not hold, and we cannot get the approximation ratio.
}

}



\subsection{SeqGrd Algorithm}
\eat{ 
We first present algorithm {\rm SeqGRD}\xspace and show that under the general setting, 
{\rm SeqGRD}\xspace achieves a  $\frac{{u_{\rm min}} \xspace}{{u_{\rm max}} \xspace}(1 - \frac{1}{e})$ approximation. } 
The pseudocode of our first algorithm {\rm SeqGRD}\xspace is shown in Algorithm~\ref{alg:sgrd}.

\begin{algorithm}
\caption{${\rm SeqGRD}\xspace(G, \epsilon, \ell, \mathbfcal{S}^P, I_2, \bvec)$} \label{alg:sgrd}
\begin{algorithmic}[1]
\State $S^P \leftarrow$ Seed nodes of the allocation $\mathbfcal{S}^P$ 
\State $S^{\it Seq} \leftarrow  \textsf{PRIMA}^+(G, \epsilon, \ell, S^P, \bvec, \sum_{i \in I_2} b_i)$  \label{lin:sgrd_PRIMM} 
\State $\mathbfcal{S}^{\it Seq} \leftarrow \emptyset$ 
\State Sort $I_2$ in decreasing order of the expected truncated utility \label{lin:sgrdp_sort}
\State ${\it Added} \leftarrow \emptyset$
\For{$i \in I_2$}
\State $S^{\it Seq}_i \leftarrow \text{ top } b_i \text{ nodes from } S^{\it Seq}$ \label{lin:msgrd_assign2}
\If{$\rho(\mathbfcal{S}^{\it Seq} \mid \mathbfcal{S}^P) < \rho((\mathbfcal{S}^{\it Seq} \cup (S^{\it Seq}_i \times \{i\})) \mid \mathbfcal{S}^P)$} \label{lin:msgrd_positives}
\State $\mathbfcal{S}^{\it Seq} \leftarrow \mathbfcal{S}^{\it Seq} \cup (S^{\it Seq}_i \times \{i\})$
\State Remove those $b_i$ nodes from $S^{\it Seq}$
\State ${\it Added} \leftarrow {\it Added} \cup \{i\} $
\EndIf \label{lin:msgrd_positivee}
\EndFor	
\For{$i \in I_2 \setminus {\it Added} $}\label{lin:msgrd_randoms}
\State $S^{\it Seq}_i \leftarrow \text{ top } b_i \text{ nodes from } S^{\it Seq}$ 
\State $\mathbfcal{S}^{\it Seq} \leftarrow \mathbfcal{S}^{\it Seq} \cup (S^{\it Seq}_i \times \{i\})$
\State Remove those $b_i$ nodes from $S^{\it Seq}$
\EndFor	\label{lin:msgrd_randomse}
\State Return $\mathbfcal{S}^{\it Seq}$
\end{algorithmic}
\end{algorithm}


Algorithm {\rm SeqGRD}\xspace\ considers the general setting where a set of items have already been seeded and 
$\mathbfcal{S}^P$ corresponds to this partial allocation. Let $S^P := \{v \mid (v,i)\in \mathbfcal{S}^P\}$  be the seed set allocated in $\mathbfcal{S}^P$ and  let $I_2$ denote the remaining items which 
have yet to be allocated. The algorithm takes  a graph $G$, to-be-allocated itemset $I_2$, 
	item budget vector $\bvec$ for the items in $I_2$, accuracy parameter $\epsilon$, tolerance parameter $\ell$, the partial allocation $\mathbfcal{S}^P$ as input.
	It first selects a seedset $S^{\it Seq}$ of size $\overline{b}$, where $\overline{b} := \sum_{i \in I_2} b_i$ \footnote{We assume  $I_1 \cap I_2 = \emptyset$.} 
	\eat{If $I_1\cap\ I_2\ne\emptyset$, $\overline{b} := \sum_{i \in I_1 \cup I_2} b_i$.
	\weic{Why do we want to consider $I_1 \cap I_2 \ne \emptyset$? I feel that we should only consider the case that $I_1 \cap I_2 = \emptyset$.}} 
	(line \ref{lin:sgrd_PRIMM}). To select the seeds it uses an algorithm, called $\textsf{PRIMA}^+$, which delivers a set of seeds that are approximately optimal w.r.t. the marginal gain $\sigma(S | S^P)$. \eat{and has a property called \textit{prefix preservation on the marginals}.} We \eat{explain this property formally and} present the $\textsf{PRIMA}^+$ algorithm in \textsection \ref{sec:algod} and establish its properties. 
	
{\rm SeqGRD}\xspace then sorts the items based on their truncated utility (line \ref{lin:sgrdp_sort}). Starting from the item $i$ having the highest truncated utility, it tries to allocate the item to the top $b_i$ nodes of $S^{\it Seq}$, $S^{\it Seq}_i$.
If the allocation $S^{\it Seq}_i \times \{i\}$ yields a positive marginal welfare, it is added to the existing allocation and nodes of $S^{\it Seq}_i$ are removed for future considerations (Lines \ref{lin:msgrd_positives}-\ref{lin:msgrd_positivee}).
The items that are not allocated in this iteration are appended following an arbitrary order (lines \ref{lin:msgrd_randoms}-\ref{lin:msgrd_randomse}) and allocated at the end. 
\eat{
\note[Laks]{Random or arbitrary order? \red{arbitrary. addressed}} We now prove the approximation bound of this algorithm.
} 

Let $\Gamma_w(S)$ be the set of nodes reachable from a seed set $S$ in the possible world $w$.
We first establish  the following lemma.
\begin{lemma} \label{lem:condexpinq}
	Let $\mathbfcal{S}$ be an allocation, $S$ be its seedset, 
	let $w$ be a random possible world. Then
	for any node $v\in V$, we have
	\[{u_{\rm min}} \xspace \le {\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \mid v\in \Gamma_w(S)\right] \le {u_{\rm max}} \xspace.\]
\end{lemma}
\begin{proof}
	Let $w=(w_1, w_2)$ where $w_1$ is the edge possible world and $w_2$ is the noise possible world.
	Note that, (a) reachable set $\Gamma_w(S)$ is only determined by the edge possible world $w_1$, so we can use $\Gamma_{w_1}(S)$ to represent it;
	(b) utility function $\mathcal{U}_w(\cdot)$ is only determined by the noise possible world $w_2$, so we can use $\mathcal{U}_{w_2}(\cdot)$ to represent it; and
	(c) adoption set $\mathcal{A}^{\mathbfcal{S}}_w(v)$ is determined by both $w_1$ and $w_2$, so we use $\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(v)$ to represent it.
	\begin{align}
	& {\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \mid v\in \Gamma_w(S)\right]  \nonumber \\
	& = {\mathbb{E}}\xspace_{w_1} \left[ {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(v)) \mid v\in \Gamma_{w_1}(S)\right] \right]. \label{eq:condexp}
	\end{align}
	We first prove the lower bound ${u_{\rm min}} \xspace$.
	To do so, we prove that for any fixed edge possible world $w_1$ and conditioned on $v \in \Gamma_{w_1}(S)$, we have 
	${\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(v))\right] \ge {u_{\rm min}} \xspace = \min_i {\mathbb{E}}\xspace[\mathcal{U}^+(i)] = \min_i {\mathbb{E}}\xspace_{w_2}[\mathcal{U}^+_{w_2}(i)] $.
	Once this is proved, from Eq.~\eqref{eq:condexp}, we immediately have 
	${\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \mid v\in \Gamma_w(S)\right] \ge {\mathbb{E}}\xspace_{w_1}[ {u_{\rm min}} \xspace ] = {u_{\rm min}} \xspace$.
	
	Consider first a seed $u\in S$.
	Let $\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1)$ be the set of items adopted by $u$ initially at time $1$ before the propagation starts. 
	Let $I^u$ be the set of items allocated to $u$ in $\mathbfcal{S}$. 
	Note that $I^u$ is determined purely by the fixed allocation $\mathbfcal{S}$ and is not affected by the noise or edge possible world.
	By our model, node $u$ will select the best item bundle in $I^u$ and adopt them as $\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1)$. 
	Then we know that $\mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1)) \ge \max_{i\in I^u} \mathcal{U}_{w_2}^+(i) $.
	Therefore, we have
	\begin{align*}
	& {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1)) \right] \ge {\mathbb{E}}\xspace_{w_2} \left[ \max_{i\in I^u} \mathcal{U}_{w_2}^+(i) \right] \\
	& \ge  \max_{i\in I^u}  {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}^+(i) \right] \ge \min_{i\in \mathbf{I}} {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}^+(i) \right] = {u_{\rm min}} \xspace.
	\end{align*}

\eat{ 	
	\note[Laks]{The above derivation leaves me wondering if we could tighten the lower bound: e.g., we relax from $\max_{i\in I^u}  {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}^+(i) \right]$ to $\min_{i\in \mathbf{I}} {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}^+(i) \right]$. \red{Not Addressed}}
	
	\weic{For Laks' comment above, perhaps we cannot tighten the bound, because $I^u$ is an arbitrary allocation on node $u$, and it could only contain the minimum utility item.}
	} 
	
	This means that for the initial seed adoption, we have that their expected utility is at least ${u_{\rm min}} \xspace$.
	Now for any $v \in \Gamma_{w_1}(S)$, $v$ is reachable from some seed node $u \in S$ via some shortest path in the edge possible world $w_1$.
\eat{ 
	\note[Laks]{There are multiple errors below: firstly time begins at $t=1$ not $0$ and secondly $\mathcal{A}$ takes time as an argument not as a subscript, based on earlier definitions.\red{Addressed}} 
	} 
	By the propagation model, then the utility of $v$'s final adoption $\mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(v))$ should be at least the utility of $u$'s initial 
	adoption, $\mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1))$.
	Then we have ${\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(v))\right] \ge {\mathbb{E}}\xspace_{w_2} \left[ \mathcal{U}_{w_2}(\mathcal{A}^{\mathbfcal{S}}_{w_1,w_2}(u,1)) \right] \ge {u_{\rm min}} \xspace$.
	This concludes the proof.
	
	The proof of the upper bound ${u_{\rm max}} \xspace$  is straightforward:
	${\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \mid v\in \Gamma_w(S)\right] \le {\mathbb{E}}\xspace_w \left[ \max_{I\subseteq \mathbf{I}} \mathcal{U}^+(I) \mid v\in \Gamma_w(S)\right]
	= {\mathbb{E}}\xspace_w \left[ \max_{I\subseteq \mathbf{I}} \mathcal{U}^+(I)\right] = {u_{\rm max}} \xspace$. \qed 
\end{proof}

\begin{lemma} \label{lem:lowerupper}
Let $\mathbfcal{S}$ be an allocation and $S$ its corresponding seed nodes. Then ${u_{\rm min}} \xspace \cdot \sigma(S) \le \rho(\mathbfcal{S}) \le {u_{\rm max}} \xspace \cdot \sigma(S)$. 
	
\end{lemma}
\eat{ 
\note[Laks]{We used $S^{\mathbfcal{S}}$ previously to denote the seeds of an allocation. But we could perhaps 
use that opportunity to simplify notation. See Sec. 3 (pink), e.g. \red{Addressed}} 
} 
\begin{proof}
The lower bound is derived below:
\begin{align*}
&\rho(\mathbfcal{S}) = {\mathbb{E}}\xspace_w\left[\sum_v \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \right] = \sum_v {\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \right]\\
& = \sum_v \Pr_w[v\in \Gamma_w(S) ] \cdot {\mathbb{E}}\xspace_w \left[ \mathcal{U}_w(\mathcal{A}^{\mathbfcal{S}}_w(v)) \mid v\in \Gamma_w(S)\right] \\
& \ge \sum_v \Pr_w[v\in \Gamma_w(S) ] \cdot {u_{\rm min}} \xspace  = {u_{\rm min}} \xspace \cdot \sigma(S),
\end{align*}
where the inequality is by Lemma~\ref{lem:condexpinq}.
The upper bound can be shown in a similar way. \qed 
\end{proof}



We are now ready to prove the following bound for ${\rm SeqGRD}\xspace$. 

\begin{theorem}\label{lem:sgrd_bound}
Let $\mathbfcal{S}^{\it Seq}$ be the allocation returned by the Algorithm {\rm SeqGRD}\xspace. Given $\epsilon, \ell >0$, we have $\rho(\mathbfcal{S}^{\it Seq} \cup \mathbfcal{S}^P) \geq \frac{{u_{\rm min}} \xspace}{{u_{\rm max}} \xspace}(1-\frac{1}{e}- \epsilon)\rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P)$ w.p. at least $1 - \frac{1}{|V|^\ell}$, where $\mathbfcal{S}^A$ is any arbitrary allocation of items in $I_2$
	respecting the budget constraint.
\end{theorem}
\begin{proof}
Let $S^{Seq}$, $S^A$ and $S^P$ be the seed sets of the allocations $\mathbfcal{S}^{\it Seq}$, $\mathbfcal{S}^A$ and $\mathbfcal{S}^P$ respectively.
Then $|S^A| \le \sum_{i\in I_2} b_i$.
By {\rm SeqGRD}\xspace, $S^{Seq}$ exhausts all budgets for items in $I_2$, 
\eat{thus
 the total number of seeds in the allocation $\mathbfcal{S}^{Seq}$ is} so  $|S^{Seq}| = \sum_{i\in I_2} b_i$.
Since $S^{Seq}$ are the top seeds returned by $\textsf{PRIMA}^+$, we have that w.p. at least $1 - \frac{1}{|V|^\ell}$, 
$$\sigma(S^{Seq} \mid S^P) \geq (1 - \frac{1}{e} - \epsilon) \sigma(S^A \mid S^P).$$
From this, it follows that 
$$\sigma(S^{Seq} \cup  S^P) \geq (1 - \frac{1}{e} - \epsilon) \sigma(S^A \cup S^P).$$
Therefore, we have
\begin{align*}
&\rho(\mathbfcal{S}^{Seq} \cup \mathbfcal{S}^P) \ge {u_{\rm min}} \xspace \cdot \sigma(S^{Seq} \cup S^P) \\
& \ge {u_{\rm min}} \xspace \cdot (1-1/e - \epsilon) \cdot \sigma(S^A \cup S^P) \\
&\ge \frac{{u_{\rm min}} \xspace}{{u_{\rm max}} \xspace}(1-\frac{1}{e}- \epsilon) \rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P),
\end{align*}
where the first and the last inequality follow from Lemma~\ref{lem:lowerupper}, while the 
middle inequality follows from using $\textsf{PRIMA}^+$.  
\end{proof}

We note that the property of $\textsf{PRIMA}^+$ that is exploited in the proof above is its ability to select seed nodes $S$ 
such that they are approximately optimal w.r.t. the marginal gain over an existing seed set $S^P$. The prefix 
preserving on marginals property of $\textsf{PRIMA}^+$ is not needed in the above proof. However, our next algorithm {\rm MaxGRD}\xspace relies on 
	the prefix-preserving property. 


\hspace*{2ex} 

\noindent
{\bf  {\rm SeqGRD{\text -}NM}\xspace\ \ Algorithm}

The proof of the approximation bound above does not rely on marginal check (Algorithm~\ref{alg:sgrd}, line \ref{lin:msgrd_positives}).  \eat{Thus, the approximation guarantee of {\rm SeqGRD}\xspace\  holds without the marginal check. } 
	\eat{Thus even when we do not perform the marginal check, the same approximation holds.} 
	We call the  version of {\rm SeqGRD}\xspace that does not perform marginal check  {\rm SeqGRD{\text -}NM}\xspace (No Marginal). 
	Specifically, {\rm SeqGRD{\text -}NM}\xspace simply sorts the items based on their truncated utility, allocates item $i$ to the first $b_i$ nodes of $S^{Grd}$, where $S^{Grd}$ is selected using $\textsf{PRIMA}^+$, and removes those $b_i$ nodes from $S^{Grd}$.

Computing  marginals involves sampling, which takes significant time in large networks. On the other hand, the marginal check avoids the phenomenon of items with lower (truncated) utility blocking those with higher utility,  to some extent. Thus even though {\rm SeqGRD{\text -}NM}\xspace is  faster than {\rm SeqGRD}\xspace and has the same approximation guarantee, under certain utility configurations, \eat{when avoiding this sort of item blocking is essential,} the welfare  produced by  {\rm SeqGRD{\text -}NM}\xspace  can be worse than that of {\rm SeqGRD}\xspace. We explore this  in our experiments in \textsection{\ref{sec:exp}}.
On the other hand, we still append all items in the end to exhaust the budget in {\rm SeqGRD}\xspace (lines~\ref{lin:msgrd_randoms}--\ref{lin:msgrd_randomse}).
To really discard a certain itemset, we need to exhaustively search through all itemset combinations, which is time-consuming. So we only do a simple marginal check in {\rm SeqGRD}\xspace, and append all items at the end to ensure the theoretical guarantee.


\subsection{SupGrd Algorithm} \label{sec:alg_supgrd}
Our third algorithm {\rm SupGRD}\xspace  provides a constant $(1-\frac{1}{e})$-approximation. The bound holds under more restrictive conditions as given below. 

\spara{Conditions required for {\rm SupGRD}\xspace approximation bound}
(i) There exists a superior item (defined in \textsection \ref{sec:msgrd}) $i_m$ in the item set: i.e., under any noise possible world $w_2$, $\mathcal{U}\xspace_{w_2} (i_m)> \mathcal{U}\xspace_{w_2}(i), \forall i \in \mathbf{I} \setminus \{i_m\}$. (ii) Seeds for all the inferior items are fixed: that is, $I_2 = \{i_m\}$ is the only item for which an allocation needs to be found; and (iii) There is pure competition between all items: every node can adopt at most one item.
Under these conditions, we first show that the social welfare is monotone and submodular. 

\begin{lemma} \label{lem:superiormonotone}
Given $\mathbfcal{S}^P$ and $I_2$, let $\mathbfcal{S}_1$ and $\mathbfcal{S}_2$ be two allocations over $I_2$ such that $\mathbfcal{S}_1 \subseteq \mathbfcal{S}_2$. Then $\rho(\mathbfcal{S}_1 \cup \mathbfcal{S}^P) \leq \rho(\mathbfcal{S}_2 \cup \mathbfcal{S}^P)$.
\end{lemma}

\begin{proof}
In an arbitrary but fixed possible world $w= (w_1, w_2)$, $\mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_1 \cup \mathbfcal{S}^P}_{w_1, w_2}(v)) \leq \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_2 \cup \mathbfcal{S}^P}_{w_1, w_2}(v))$. This is because if $v$ changes its adoption between the two allocations, then it must change it to $i_m$ since all other inferior item seeds are fixed. Since $i_m$ is the superior item, the claim holds.
\eat{ 
Now,
\begin{align*}
\rho_{w = (w_1,w_2)}(\mathbfcal{S}_1 \cup \mathbfcal{S}^P) &= \sum_{v \in V} \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_1 \cup \mathbfcal{S}^P}_{w_1, w_2}(v)) \\
&\leq \sum_{v \in V} \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_2 \cup \mathbfcal{S}^P}_{w_1, w_2}(v)) \\
&= \rho_{w = (w_1,w_2)}(\mathbfcal{S}_2 \cup \mathbfcal{S}^P)
\end{align*}
}
Since this holds for every $w$, the lemma follows.
\end{proof}

\begin{lemma}
Given $\mathbfcal{S}^P$ and $I_2$, let $\mathbfcal{S}_1$ and $\mathbfcal{S}_2$ be two allocations over $I_2$ such that $\mathbfcal{S}_1 \subseteq \mathbfcal{S}_2$. Let $s = (u, i_m) \notin \mathbfcal{S}_2$ be an allocation pair. Then $\rho(s \mid \mathbfcal{S}_1 \cup \mathbfcal{S}^P) \geq \rho(s \mid \mathbfcal{S}_2 \cup \mathbfcal{S}^P)$.
\end{lemma}

\begin{proof} 
Let $w = (w_1, w_2)$ be a arbitrary but fixed possible world. Let $C_i$ denote the set of all nodes that adopt $i_m$ under allocation $s$ but \emph{not} under $\mathbfcal{S}_i \cup \mathbfcal{S}^P$, $i = 1, 2$. Then $C_2 \subseteq C_1$. Thus,
\begin{align*}
\rho_{w_1,w_2}(s \mid \mathbfcal{S}_2 \cup \mathbfcal{S}^P) &= \sum_{v \in C_2} (\mathcal{U}\xspace_{w_2}(\{i_m\}) - \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_2 \cup \mathbfcal{S}^P}_{w_1, w_2}(v))) \\
&\leq \sum_{v \in C_1} (\mathcal{U}\xspace_{w_2}(\{i_m\}) - \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_1 \cup \mathbfcal{S}^P}_{w_1, w_2}(v)))\\ 
& = \rho_{w_1,w_2}(s \mid \mathbfcal{S}_1 \cup \mathbfcal{S}^P)
\end{align*}
\eat{ 
\begin{align*}
\rho_{w_1,w_2}(s \mid \mathbfcal{S}_2 \cup \mathbfcal{S}^P) &= \sum_{v \in C} (\mathcal{U}\xspace_{w_2}(\{i_m\}) - \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_2 \cup \mathbfcal{S}^P}_{w_1, w_2}(v))) \\
&\geq \sum_{v \in C} (\mathcal{U}\xspace_{w_2}(\{i_m\}) - \mathcal{U}\xspace_{w_2}( \mathcal{A}^{\mathbfcal{S}_1 \cup \mathbfcal{S}^P}_{w_1, w_2}(v)))\\ 
&  \text{,using monotonicity}\\
&\geq \rho_{w_1,w_2}(s \mid \mathbfcal{S}_1 \cup \mathbfcal{S}^P)
\end{align*}
} 

Since this holds for every $w$, the lemma follows.
\end{proof}

Since social welfare is monotone and submodular, a standard greedy selection based on the marginal welfare will have $(1 - \frac{1}{e})$-approximation. However since computing spread itself is \#P-hard, computing the exact marginal is not feasible. In IM, sampling using RR-sets has been used to achieve state of the art performance. In what follows, by extending IMM \cite{tang15}, we adopt a martingale approach for seed selection in {\rm SupGRD}\xspace. Given $\epsilon$ and $\ell$,  {\rm SupGRD}\xspace returns a seed set that has a $(1-\frac{1}{e} - \epsilon)$-approximation w.p. at least $1 - \frac{1}{n^\ell}$.

In the classical setting, RR-set samples are used to compute an unbiased estimation of the spread. In our case we need to estimate the \emph{marginal welfare} using the RR-sets. 
Towards that we define a notion of weight for every RR-set. The weight of an RR-set $R_v$ denotes the marginal gain in the expected social welfare achieved by activating the root $v$ of the RR-set $R_v$. 
Thus it is the difference between the expected truncated utility of the item that the root $v$ adopts under the existing partial allocation $\mathbfcal{S}^P$ and that of $i_m$. 
To ensure that the root $v$ indeed adopts $i_m$, the path from some seed of $i_m$ to $v$ should be no longer than that from any seed of $\mathbfcal{S}^P$ to $v$. Thus, a weighted RR-set is constructed as follows. 

\begin{definition} \label{def:rrset}
(Weighted Reverse Reachable Set). For a given fixed allocation $\mathbfcal{S}^P$ and a
node $v \in G$, a weighted RR-set of $v$, $R_v$ is obtained by starting with $R_v=\{v\}$ and starting a BFS from $v$ such that: for $u\in R_v$, sample each incoming edge $(u',u)$
w.p. $p_{u',u}$ and add it to $R_v$; stop when either no new nodes are added or $R_v$ overlaps $S^P$ 
(so the distance from any node in $R_v$ to $v$ along the reversely generated edges is 
	at most the distance from $S^P$ to $v$).
Then, the weight of $R_v$ is $w(R_v) = \mathcal{U}^+\xspace(\{i_m\}) -  max_{i \in I^s \mid s \in S^P \cap R(v)} \mathcal{U}^+\xspace(i)$, where $I^s$ denotes the items allocated to node $s$ in \eat{$S^P$, seeds of} the allocation $\mathbfcal{S}^P$.
\end{definition}

{\rm SupGRD}\xspace samples RR-sets using an early termination as described in Definition \ref{def:rrset}. This construction ensures that if any member of a {weighted} RR-set is seeded with $i_m$, the root of the RR-set, $v$, will adopt $i_m$. In what follows, we first  establish the connection between marginal social welfare and weighted RR-sets and then present efficient seed selection and RR-set sampling algorithms to maximize the marginal social welfare. \eat{When the context is clear, we drop $S^P$ from the notation for simplicity.} 

 For a node set $S$, let $\mathbb{I}[.]$ be an indicator function denoting whether $S$ covers the (weighted) RR set $R$, i.e., $\mathbb{I}(S \cap R \ne \emptyset) = 1$, if $S \cap R_v \neq \emptyset$, $0$ otherwise. Also let $\mathcal{L}(G)$ denote the distribution of all the live edge graphs, then extending the result of Borg et al., we now prove the following lemma for  weighted RR-sets.

\begin{lemma} \label{lem:borgs}
For given seed sets $S$ and $S^P$, we have
$\mathbb{E}_{w_1 \sim G}[\rho_{w_1}(S \mid S^P)] = n \cdot \mathbb{E}_{ v \sim V, w_1 \sim G} [\mathbb{I}(S \cap R_v \ne \emptyset) \cdot w(R_v)]$
where $n = |V|$ is the number of nodes in $G$.
\end{lemma}

\begin{proof}

\begin{align*}
\mathbb{E}_{w_1 \sim \mathcal{L}(G)}\rho_{w_1}(S \mid S^P)
&= \mathbb{E}_{w_1 \sim \mathcal{L}(G)} \left[\sum_{v \in V} \mathbb{I}(S \cap R_v \ne \emptyset) \cdot w(R_v) \right] \\
&= n \cdot \mathbb{E}_{ v \sim V, w_1 \sim \mathcal{L}(G)} [ \mathbb{I}(S \cap R_v = 1) \cdot w(R_v)]
\end{align*}
\end{proof}

We now extend the RR-set based efficient approximation IM algorithm, IMM, for maximizing welfare. Similar to IMM, our algorithm ${\rm SupGRD}\xspace$ has two key phases, namely, $NodeSelection$ and $Sampling$. The $NodeSelection$ phase is similar to that of IMM, except we consider the weight of  RR-sets while selecting  seed nodes.  \eat{using $coverage$.} For a node set $S$ and  a collection of weighted RR-sets $\mathcal{R}$, define 
$M_{\mathcal{R}}(S) := \sum_{R \in \mathcal{R}} \mathbb{I}[S \cap R \ne \emptyset] \cdot w(R)$. Let $b' = b_{i_m}$ be the budget of the superior item $i_m$. Given a set $\mathcal{R}$, $NodeSelection$ selects $b'$ seeds that maximizes $M_{\mathcal{R}}$ (Algorithm \ref{alg:NS}). 

\begin{algorithm}[t!]

\caption{$NodeSelection(\mathcal{R}, b')$} \label{alg:NS}
\begin{algorithmic}[1]
\State Initialize $S_{b'} = \emptyset, i=1$
\While{$i \leq b'$}
	\State Select $v \in V \setminus S_{b'}$ which has the highest $M_{\mathcal{R}}(S_{b'} \cup v) - M_{\mathcal{R}}(S_{b'})$
	\State $S_{b'} \leftarrow S_{b'} \cup \{v\}$
	\State Remove $R$ from $\mathcal{R}$ if $v \in R$ 

\EndWhile
\State \textbf{return} $S_{b'}$ as the final seed set
\end{algorithmic}
\end{algorithm}


Next, the goal of the $Sampling$ phase (Algorithm \ref{alg:sam}) is to generate $\mathcal{R}$ such that $|\mathcal{R}| \geq \lambda /OPT$, where $OPT$ is the optimal welfare, and $\lambda$ is defined as follows,
\begin{equation}\label{eq:lambdaa}
\lambda = 2n \cdot ((1 - 1/e)\cdot \alpha + \beta)^2 \cdot \epsilon^{-2}, 
\end{equation} 
where, $\alpha = \sqrt{\ell \log n + \log 2}$ and \\ 
$\beta = \sqrt{(1 - 1/e) \cdot (\log \tbinom{n}{b'}+\ell \log \ n + \log 2)}$.

Since $OPT$ is unknown, the $Sampling$ first ensures that it finds a lower bound to $OPT$ w.h.p. For that it deploys a statistical test using a binary search on the range of $OPT$. The maximum possible value of the welfare $OPT$ is $UB = n \times {u_{\rm max}} \xspace$, when every node in the network adopts the superior item $i_m$, ${u_{\rm max}} \xspace$ is the utility of $i_m$. Thus the binary search ranges from $1$ to $UB$ (Line \ref{lin:loop}).

\begin{algorithm}[t!]
\caption{$Sampling(G, k, \epsilon, \ell)$} \label{alg:sam}
\begin{algorithmic}[1]
\State Initialize $\mathcal{R} = \emptyset$, $LB = 1$, $UB = |V| \times {u_{\rm max}} \xspace$, $i = 1$, $\epsilon^\prime = \sqrt{2} \cdot \epsilon$, $\ell = \ell + log \ 2/log \ n$. \label{lin:init}
\For{$i = 1$ to $log_2 UB -1$ } \label{lin:loop}
	\State $x = n / 2^i$, $\theta_i = \lambda' / x$
	\While{$|\mathcal{R}| \leq \theta_i$}
		\State Add a random RR set to $\mathcal{R}$
	\EndWhile
	\State $S_i = NodeSelection(\mathcal{R}, k)$
	\If{$\frac{n}{\theta} \cdot M_{\mathcal{R}}(S_i) \geq (1 + \epsilon') \cdot x$} \label{lin:lb}
		\State $LB = \frac{n}{\theta} \cdot M_{\mathcal{R}} / (1 + \epsilon') $
		\State Break;
	\EndIf
\EndFor
\State $\mathcal{R} = \emptyset$ \label{lin:rrfinal}
\While{$|\mathcal{R}| \leq \lambda / LB$}
	\State Add a random RR set to $\mathcal{R}$
\EndWhile
\end{algorithmic}
\end{algorithm}

A good lower bound is found when the condition of Line \ref{lin:lb} is satisfied. Different from \cite{tang15}, this condition directly operates on welfare. This is a key step in the correctness of the algorithm, hence we prove it explicitly in Lemma \ref{lem:lb}.

\begin{lemma} \label{lem:lb}
Let $x \in [1, UB], \epsilon'$ and $\delta \in (0,1)$, then if we invoke $NodeSelection$ with $|\mathcal{R}|=\theta$, where 
\begin{equation}
\theta \geq \frac{(2+ \frac{2}{3} \epsilon') \cdot (log \tbinom{n}{b'} + log (1/\delta))}{\epsilon'^2} \cdot \frac{n}{x}
\end{equation}
and $S$ is the output $NodeSelection$ returns,
then if $OPT <x$, $\frac{n}{\theta} \cdot M_{\mathcal{R}}(S) < (1 + \epsilon') \cdot x $, w.p. at least $(1 - \delta)$. 
\end{lemma}

\begin{proof}
Let $x_i$ be a random variable for each $R_i \in \mathcal{R}$ defined as, $x_i = \frac{w(R_i) \cdot \mathbb{I}(S \cap R_i \neq \emptyset)}{w_{max}}$, where $w_{max}$ is the maximum weight possible for any RR set. Thus, $0 \leq x_i \leq 1$, which ensures the martingle property.
Now let $F_{\mathcal{R}}(S) = \frac{M_{\mathcal{R}}(S)}{w_{max}}$, $p = \mathbb{E}[F_{\mathcal{R}}(S)]$ and $\alpha = \frac{(1+\epsilon')\cdot x}{np \cdot w_{max}} - 1$, Using Lemma \ref{lem:borgs} and linearity of expectation,

\begin{align*}
p&= \mathbb{E}[F_{\mathcal{R}}(S)] = \mathbb{E}[\frac{M_{\mathcal{R}}(S)}{w_{max} }] = \mathbb{E}[\rho(S \mid S^p)]/(w_{max} ) \\
&\leq OPT /(w_{max}  \cdot n) \leq x/(w_{max} \cdot n)
\end{align*}

Consequently $\alpha > \epsilon' \cdot x/(np) $ and from Lemma 6 of \cite{tang15},

\begin{align*}
&Pr[\frac{n}{\theta} \cdot M_{\mathcal{R}}(S) \geq (1+\epsilon') \cdot x] \leq \delta/ \tbinom{n}{b'} 
\end{align*}
Finally by applying union bound we get $\frac{n}{\theta} \cdot M_{\mathcal{R}}(S) < (1 + \epsilon') \cdot x $, w.p. at least $(1 - \delta)$.
\end{proof}

Thus by setting $\lambda'$ using Eq. \eqref{eq:lambdap}, we get Theorem 2 of \cite{tang15}

\begin{equation}\label{eq:lambdap}
\lambda^\prime = \frac{(2+\frac{2}{3}\epsilon^\prime) \cdot (\log {n \choose b'} + \ell^\prime \cdot \log \ n+\log\log_{2} \ n )\cdot n}{\epsilon^{\prime 2}},
\end{equation}

The rest of the proof is similar to that of \cite{tang15}, which gives us the following result.

\begin{theorem}\label{lem:supgrd_bound}
Let $\mathbfcal{S}^P$ be a partial allocation on the inferior items.
Let $\mathbfcal{S}^{\it Grd}$ be the allocation of the superior item produced by {\rm SupGrd}. Given $\epsilon, \ell >0$, we have $\rho(\mathbfcal{S}^{\it Grd} \cup \mathbfcal{S}^P) \geq (1-\frac{1}{e}- \epsilon)\rho(\mathbfcal{S}^A \cup \mathbfcal{S}^P)$ w.p. at least $1 - \frac{1}{|V|^\ell}$, where $\mathbfcal{S}^A$ is any arbitrary allocation.
\end{theorem}

\eat{
\begin{proof}
From Theorem 1 of \cite{tang15}, $NodeSelection$ returns a seed set  which provides a $(1-1/e-\epsilon)$-approximate marginal welfare  w.p.  at least $1-1/n^\ell$. However, following the fix proposed in \cite{chen2018issue}, we need to generate all the RR-sets afresh as done in Line \ref{lin:rrfinal}. Then from Lemma \ref{lem:lb}, and  union bound, by setting $\ell = \ell + log \ 2/log \ n$ in line \ref{lin:init}, we bound the failure probability to at most $\frac{1}{|V|^\ell}$. The Lemma follows. 
\end{proof}
}

\noindent
{\bf Running time: }
Let $w_{min}$ be the minumum weight of an RR set. Then
using Lemma $9$ of \cite{tang15}, the expected total time to generate $\mathcal{R}$ is determined by,
\begin{align*}\label{eq:rtime}
\mathbb{E}[\sum_{R \in \mathcal{R}}wid(R)] &= \mathbb{E}[|\mathcal{R}|] \cdot EPT \nonumber \\
& \leq O((b'+\ell)n\log \ n \cdot \epsilon^{-2})/OPT \cdot \frac{m}{n} OPT/w_{min} \\
&= O((b'+\ell)(n+m)\log \ n \cdot \epsilon^{-2}/w_{min})
\end{align*}

Notice that generating an RR-set from scratch for the final node selection (line \ref{lin:rrfinal}), following the fix of \cite{chen2018issue}, only adds a multiplicative factor of $2$. Hence the overall asymptotic running time to generate $\mathcal{R}$ remains unaffected. 


\subsection{ $\textsf{PRIMA}^+$ algorithm}
In this section we present the $\textsf{PRIMA}^+$ algorithm that {\rm SeqGRD}\xspace and {\rm MaxGRD}\xspace use to select the seed nodes. Before that we present the prefix preserving on marginal property formally.

\begin{definition}{\sc (Prefix-Preserving on Marginal Property).\ } \label{def:PRIMM}
	\fixedspaceword[.75]{Given $G$ $=$ $(V,E,p)$, budget vector $\bvec$ and a fixed seed set $S^P$, an influence maximization algorithm $\mathbb{A}$
	is prefix-preserving on marginal w.r.t. $\bvec$ and $S^P$, 
	if for any $\epsilon$ $>$ $0$ and $\ell$ $>$ $0$, 
	$\mathbb{A}$  returns an ordered set $S^{\it Grd}_{\bmax}$ of size $\bmax = \sum_{b_i \in \bvec} b_i$, 
	such that  with probability  at least $1$ $-$ $\frac{1}{|V|^{\ell}}$, 
	for every $b_i$ $\in$ $\bvec$, the top-$b_i$ nodes of $S^{\it Grd}_{\bmax}$, denoted $S^{\it Grd}_{b_i}$, satisfies $\sigma(S^{\it Grd}_{b_i} \mid S^P)$ $\geq$ $(1-\frac{1}{e} - \epsilon)$ ${\it OPT}_{b_i \mid S^P} $,
	where
	${\it OPT}_{b_i \mid S^P}$ is the optimal marginal expected spread of $b_i$ nodes on top the existing seeds $S^P$.}
\end{definition}


\begin{algorithm}[t!]

\caption{$\textsf{PRIMA}^+(G, \epsilon, \ell, S^P, \bvec)$} \label{alg:primap}
\begin{algorithmic}[1]
\State Initialize $\mathcal{R} = \emptyset$, $s = 1$, $n = |V|$, $i = 1$, $\epsilon^\prime = \sqrt{2} \cdot \epsilon$, ${\it budgetSwitch} = {\bf false}$; 
\State $\ell = \ell  + \log 2 / \log n $, $\ell^\prime = \log_n(n^{\ell} \cdot |\bvec|)$;  \label{lin:ellb}
\While{$i \leq \log_2(n) - 1$ and $s \leq |\bvec|$} 
	\State $k = b_s$, $LB =1$; 
	\State $x = \frac{n}{2^i}$; $\theta_i = \lambda^\prime_k/x$, where $\lambda^\prime_k$ is defined in Eq. \eqref{eq:lambdap} \label{lin:lambdap} 
	\While{$|\mathcal{R}| \leq \theta_i$}                                   \label{lin:genr1}
		\State Generate an RR set $R$ for a randomly selected node $v$ of $G$
		 \State If $R$ does not contain any node of $S^P$, insert $R$ in $\mathcal{R}$; \label{lin:genr2}
	\EndWhile
	\If{${\it budgetSwitch}$}
		\State $S_k = $ the first $k$ nodes in the ordered set $S_{b_{s-1}}$ returned from
		the previous call to $\textit{NodeSelection}$
	\Else 
		\State $S_k =\textit{NodeSelection}(\mathcal{R}, k)$
	\EndIf
	\If{$n \cdot F_{\mathcal{R}}(S_k) \geq (1 + \epsilon^\prime)\cdot x$}  \label{lin:cov}
		\State $LB = n \cdot F_{\mathcal{R}(S_k)} / (1+\epsilon^\prime) $ 
		\State $\theta_k = \lambda^\ast_k / LB$, where $\lambda^\ast_k$ is defined in Eq. \eqref{eq:lambdaa} \label{lin:suc1}
		\While{$|\mathcal{R}|<\theta_k$} 
			\State Generate an RR $R$ set for a randomly selected node $v$ of $G$
			\State If $R$ does not contain any node of $S^P$, insert $R$ in $\mathcal{R}$    \label{lin:suc2}
		\EndWhile
		\State $s = s + 1 $; ${\it budgetSwitch} = {\bf true}$	
	
	\Else 
		\State $i= i+1$; ${\it budgetSwitch} = {\bf false}$
	\EndIf
	
\EndWhile
\If{$s \leq |\bvec|$}
	\State $\theta_k = \lambda^\ast_{b_s}/LB$ \label{lin:final}	
\EndIf	
\State $\mathcal{R} = \emptyset$
\While{$|\mathcal{R}|<\theta_k$}    \label{lin:weinote}
		\State Generate an RR $R$ set for a randomly selected node $v$ of $G$
			\State If $R$ does not contain any node of $S^P$, insert $R$ in $\mathcal{R}$
\EndWhile
\State $S_{\bmax} = \textit{NodeSelection}(\mathcal{R}, \bmax)$ \label{lin:nodes}
\State \textbf{return} $S_{\bmax}$ as the final seed set
\end{algorithmic}
\end{algorithm}

We now present the $\textsf{PRIMA}^+$ algorithm that have the prefix preserving on marginal property. Pseudo code of $\textsf{PRIMA}^+$ is shown in Algorithm \ref{alg:primap}. 
In \cite{ban2019} authors proposed a prefix preserving IMM algorithm $\textsf{PRIMA}$. For the given budget vector $\bvec$, $\textsf{PRIMA}$ generates enough RR sets so that for any budget $k \in \bvec$, $|\mathcal{R}|\geq \lambda^\ast_k / {\it OPT}_k$, with probability at least $1 - 1/n^{\ell^\prime}$. $\lambda^\ast_k$ and $\lambda'$ of Line \ref{lin:lambdap} is defined as follows,
\begin{equation}\label{eq:lambdap}
\lambda^\prime_k = \frac{(2+\frac{2}{3}\epsilon^\prime) \cdot (\log {n \choose k} + \ell^\prime \cdot \log \ n+\log\log_{2} \ n )\cdot n}{\epsilon^{\prime 2}},
\end{equation} 
\vspace*{-2mm}
\begin{gather}\label{eq:lambdaa}
\lambda^\ast_k = 2n \cdot ((1 - 1/e)\cdot \alpha + \beta_k)^2 \cdot \epsilon^{-2}, 
\end{gather} 
where, $\alpha = \sqrt{\ell' \log n + \log 2}$ is a constant independent of $k$, and 
$\beta_k = \sqrt{(1 - 1/e) \cdot (\log \tbinom{n}{k}+\ell^\prime \log \ n+ \log 2)}$.
Further since $OPT_k$ is unknown, $\textsf{PRIMA}$ derives lower bounds $LB_k$ by iterating over $\bvec$ to find $|\mathcal{R}| = max_{k \in \bvec}\lambda^\ast_k/LB_k$. Finally the using $\mathcal{R}$, the seed nodes are selected 
solving the coverage problem greedily using $\textit{NodeSelection}(\mathcal{R},k)$ \cite{tang15}. We extend $\textsf{PRIMA}$ for the marginal case.

The difference between $\textsf{PRIMA}$ and $\textsf{PRIMA}^+$ lies in type of RR set they use. While $\textsf{PRIMA}$ includes RR set starting from any random node of $G$, $\textsf{PRIMA}^+$ includes only those RR sets that are not covered by the nodes of the existing seed set $S^P$. Therefore the approximation guarantee of $\textsf{PRIMA}^+$ holds on the graph that is not reached by the existing allocation. 

Correctness of $\textsf{PRIMA}^+$ follows from the proof of $\textsf{PRIMA}$ \cite{ban2019}. In short, by selecting seeds from the uncovered portion of the graph, $\textsf{PRIMA}^+$ achieves the prefix preserving on marginal property. Theorem \ref{thm:main} follows from Lemmas \ref{lem:sgrd_bound}, \ref{lem:mgrd_bound}, \ref{lem:supgrd_bound} and the correctness of $\textsf{PRIMA}^+$.

\spara{Running time}

The running time of $\textsf{PRIMA}^+$ also follows the similar analysis of \cite{ban2019}. From Lemma $9$ of \cite{tang15}, we have for any budget $k$, the set of RR sets generated for that budget $\mathcal{R}_k$ satisfies, 

\begin{align*}
\mathbb{E}[|\mathcal{R}_k|] &\leq \frac{3 max\{ \lambda^\ast_k, \lambda^\prime_k\} \cdot (1+\epsilon^\prime)^2}{(1 - 1/e)\cdot {\it OPT}_k}.
\end{align*}

Different from \cite{ban2019}, $OPT_k$ here is the marginal spread, instead of the absolute spread.
Since $\lambda^\prime_k$ and $\lambda^\ast_k$ are both monotone in $k$ (Eq. (\eqref{eq:lambdap}) and (\eqref{eq:lambdaa})), we know their maximums are achieved for $k = \bmax$, where $\bmax$ is the maximum budget in the budget vector. 
 
Further let ${\it OPT}_{min} := {\it OPT}_{b_{|{\bf I}|}}$ be the minimum possible value of the optimal expected marginal spread for any budget in the budget vector, then for any $\mathcal{R}_k$,
\begin{align*}
\mathbb{E}[|\mathcal{R}_k|] &\leq \frac{3 max\{ \lambda^\ast_{\bmax}, \lambda^\prime_{\bmax}\} \cdot (1+\epsilon^\prime)^2}{(1 - 1/e)\cdot {\it OPT}_{min}} \\
& = O((\bmax+\ell^\prime)n\log \ n \cdot \epsilon^{-2} / {\it OPT}_{min}).
\end{align*}

Further since $\textsf{PRIMA}^+$ reuses the RR sets instead of generating them from scratch for every budget, for the RR set $\mathcal{R}$ generated by $\textsf{PRIMA}^+$,

\begin{align}\label{eq:rsize}
\mathbb{E}[|\mathcal{R}|] &= max_{k \in \bvec}\{ \mathbb{E}[|\mathcal{R}_k|] \} \nonumber \\ 
& = O((\bmax+\ell^\prime)n\log \ n \cdot \epsilon^{-2} / {\it OPT}_{min}).
\end{align}

For an RR set $R \in \mathcal{R}$, let $w(R)$ denote the number of edges in $G$ pointing to nodes in $R$. If $EPT$ is the expected value of $w(R)$. Since we build RR set only using uncovered nodes, $n \cdot EPT \leq m \cdot {\it OPT}_{min}$ \cite{tang15}. Hence using Eq.~\eqref{eq:rsize}, the expected total time to generate $\mathcal{R}$ is determined by,
\begin{align}\label{eq:rtime}
\mathbb{E}[\sum_{R \in \mathcal{R}}w(R)] &= \mathbb{E}[|\mathcal{R}|] \cdot EPT \nonumber \\
& = O((\bmax+\ell^\prime)(n+m)\log \ n \cdot \epsilon^{-2}).
\end{align}
Since $\textit{NodeSelection}$ involves one pass over all RR set, on a given input $\mathcal{R}_i$, it takes $O(\sum_{R \in \mathcal{R}_i} |R|)$ time. Recall $|\mathcal{R}_i|$ doubles with every increment of $i$. Hence it is a geometric sequence with a common ratio of $2$. Thus $\ell' = \ell + \log_n |\bvec|$. Hence the overall running time of $\textsf{PRIMA}^+$ is,
$$O((\bmax+\ell + \log_n |\bvec|)(n+m)\log \ n \cdot \epsilon^{-2})$$.
\subsection{Experiment Setup}

All our experiments are run on a Linux machine with Intel Xeon $2.6$ GHz CPU and $128$ GB RAM.

\spara{6.1.1 Networks} 
Our experiments were conducted on five real social networks: \mbox{NetHEPT}\xspace, {Douban\mbox{-}Book}\xspace, {Douban\mbox{-}Movie}\xspace, \mbox{Twitter}\xspace, and \mbox{Orkut}\xspace, whose characteristics are summarized in~Table \ref{tab:datasets}. Of these, \mbox{NetHEPT}\xspace, {Douban\mbox{-}Book}\xspace, and {Douban\mbox{-}Movie}\xspace are benchmarks in IM literature \cite{lu2015arxiv}, while \mbox{Twitter}\xspace and \mbox{Orkut}\xspace are two of the largest public networks available at \cite{twitter}.


\spara{6.1.2 Algorithms compared}
In the experiments our four algorithms -- {\rm SeqGRD}\xspace, {\rm SeqGRD{\text -}NM}\xspace, {\rm MaxGRD}\xspace, and {\rm SupGRD}\xspace are compared against three baselines --  {\rm TCIM}\xspace, {\rm Balance{\text -}C}\xspace and \gm. 
There is no previous work that can deal with both arbitrary degree of competition and multiple items in propagation.
Our first two baselines each covers one aspect. 
{\rm TCIM}\xspace \cite{lin2015analyzing} in particular assumes a propagation model which is an extension of the IC model under pure competition. It can, however, handle more than two items. Given fixed seed sets of other competing items, {\rm TCIM}\xspace selects seeds of an item under a budget constraint, such that the number of adoptions of that item is maximized. When we run {\rm TCIM}\xspace for multiple items, we select seeds for each of the items one by one, while keeping the seeds of other items fixed and then report the allocation that produces the maximum welfare.

In contrast, {\rm Balance{\text -}C}\xspace \cite{garimella2017balancing} does not assume pure competition, but it works only when number of items in propagation is two. Given an initial seed placement of the two items, {\rm Balance{\text -}C}\xspace chooses the remaining seeds such that at the end of the propagation, the number of nodes seeing either both the items or none, is maximized. Thus for competing ideas, {\rm Balance{\text -}C}\xspace ensures that there is a balanced exposure of the two ideas to the most number of nodes. It is non-trivial to extend {\rm Balance{\text -}C}\xspace for more than two items hence we compare against it only in two item set up. 

Both {{\rm TCIM}\xspace} and {\rm Balance{\text -}C}\xspace aim to maximize adoption count, not social welfare. Our third baseline \gm maximizes the social welfare directly. It greedily selects iteratively the (node, item) pair that maximizes the marginal social welfare, till the budgets are exhausted. Below, by deterministic utility of an itemset $I$, we mean $\mathcal{V}\xspace(I) - \mathcal{P}\xspace(I)$, i.e., its utility with the noise term ignored. 


\spara{6.1.3 Default parameters}
Following previous works \cite{Huang2017,Nguyen2016} we set probability of edge $e = (u,v)$ to $1/d_{in}(v)$, where $d_{in}(v)$ is the in-degree of node $v$.
Unless otherwise specified, we use $\epsilon = 0.5$ and $\ell = 1$ as our default in all the algorithms that use these parameters. 
We test the algorithms across a wide variety of utility configurations to cover different aspects of competition. We will describe the configurations as we present the corresponding experiments. Whenever marginal gains are required, we run 5000 simulations and take the average result. 
\vspace{-2mm}
\subsection{Experiments with two items}

For our first set of experiments we restrict the number of items to two so that we can compare against all of the mentioned baselines. We also consider four different configurations to capture different kinds of competition. The details of the configurations are given in Table \ref{tab:configs}. 
In configurations C1 and C2, the items exhibit pure competition. In C1, items have comparable individual utility.
In C2, the difference between individual utility is high:  $i$'s deterministic utility is $1$, 10 times higher than that of $j$. 
C3 and C4 exhibit soft competition. 
Except for C4, in all  configurations we consider the same budget for both items (uniform); budget is varied from 10 to 50 in steps of 10. In C4, we fix the budget of $i$ to 50 and vary $j$'s budget (non-uniform) from 30 to 100 in steps of 20. We assume $\mathbfcal{S}^p = \emptyset$ in these configurations. Since it does not meet constraints required by {\rm SupGRD}\xspace, we defer the comparison until \textsection 6.2.3.

\spara{6.2.1 Running time}
First we compare the running time of the algorithms using C1 as a representative case. Fig. \ref{fig:time} shows the result on four networks. {\rm SeqGRD{\text -}NM}\xspace is orders of magnitude faster than other algorithms in every network. The reason is that {\rm SeqGRD{\text -}NM}\xspace does not compute any marginal. 
Each marginal computation requires iterating over 5000 samples, which significantly increases the running time. For the same reason \gm and {\rm Balance{\text -}C}\xspace exhibit exorbitantly high running time: they do not in fact complete in 6 hours on a large network like \mbox{Orkut}\xspace. Hence they are not included in Fig. \ref{fig:time}(d). Except for {\rm SeqGRD{\text -}NM}\xspace, none of the other algorithms scale to the largest network \mbox{Twitter}\xspace. We will compare {\rm SeqGRD{\text -}NM}\xspace and {\rm SupGRD}\xspace on \mbox{Twitter}\xspace later. Performance on other configurations show similar trends, and hence omitted for brevity.

\begin{table}[t!]
\begin{tabular}{|c|c|l|c|l|}
\hline
No & Price                                                                                           & \multicolumn{1}{c|}{Value}                                                            & \multicolumn{1}{l|}{Noise}                                                                                  & Budget     \\ \hline
C1  & \multirow{4}{*}{\begin{tabular}[c]{@{}c@{}}$i = 3$\\ \\ $j = 4$\\ \\ $\{i, j\} = 7$\end{tabular}} & \begin{tabular}[c]{@{}l@{}}$i=4$, $j=4.9$\\ $\{i,j\}=4.9$\end{tabular}                  & \multirow{4}{*}{\begin{tabular}[c]{@{}c@{}}$i: N(0,1)$\\ \\ \\ \\ $j: N(0,1)$\\ \\\end{tabular}} & Uniform    \\ \cline{1-1} \cline{3-3} \cline{5-5} 
C2  &                                                                                                 & \begin{tabular}[c]{@{}l@{}}$i=4, j=4.1$\\ $\{i,j\}=4.1$\end{tabular}                  &                                                                                                             & Uniform    \\ \cline{1-1} \cline{3-3} \cline{5-5} 
C3  &                                                                                                 & \multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}$i=4, j=4.9$\\ $\{i,j\}=8.7$\end{tabular}} &                                                                                                             & Uniform    \\ \cline{1-1} \cline{5-5} 
C4  &                                                                                                 &                                                                                       &                                                                                                             & Nonuniform \\ \hline
\end{tabular}
\caption{Two item configurations}
\vspace{-2mm}
\label{tab:configs}
\end{table}


\spara{6.2.2 Social welfare}
We now compare the expected social welfare achieved by the algorithms on the four configurations
(Fig. \ref{fig:welfare}). We show the results only for Douban-Movie , since the trend of the results is similar on other networks. In all configuration {\rm SeqGRD}\xspace, {\rm SeqGRD{\text -}NM}\xspace and \gm outperform all other algorithms. 
The difference in welfare is up to 3$\times$  higher. {\rm MaxGRD}\xspace in particular allocates just one of the two items. 
Thus when items exhibit soft competition (C3 and C4), 
	,{\rm MaxGRD}\xspace performs significantly worse. {\rm Balance{\text -}C}\xspace performs comparatively better under soft competition (C3), however for a non-uniform budget again its performance drops. 
{\rm TCIM}\xspace on the other hand aims to maximize the adoption count of the item being allocated. Thus it also ends up allocating both the items in same seed nodes. This reduces the overall social welfare for configuration such C1, where both {\rm Balance{\text -}C}\xspace and {\rm TCIM}\xspace perform comparatively worse. Social welfare produced by \gm is consistently good, but its running time is exorbitantly high, which prohibits its applicability on any decently sized network. {\rm SeqGRD{\text -}NM}\xspace on the other hand is the fastest algorithm, which produces similar welfare across all these four configurations. However, notice that in none of these four configurations, item blocking is effective. We will show later in \textsection 6.3.2 that in the presence of multiple items, when avoiding item blocking is critical, the performance of {\rm SeqGRD{\text -}NM}\xspace deteriorates.

\spara{6.2.3 Comparison against {\rm SupGRD}\xspace}
In this experiment we compare {\rm SupGRD}\xspace and {\rm SeqGRD{\text -}NM}\xspace on the two largest  networks, \mbox{Orkut}\xspace and \mbox{Twitter}\xspace. We use utility configurations of C1 and C2, but adopt the seed placements needed to meet the constraints required for {\rm SupGRD}\xspace. Recall that for {\rm SupGRD}\xspace the seeds for the inferior items need to be fixed. Hence we select the top 50 nodes using IMM and set them as seeds of $j$. Then, the seeds of $i$ are selected using {\rm SupGRD}\xspace and {\rm SeqGRD{\text -}NM}\xspace with the budget being varied from 10 to 50 in steps of 10. We call these new configurations C5 and C6 respectively.

Since the top nodes in terms of the spread are given to $j$, these two cases pose a unique challenge of dealing with arbitrary degree of competition when maximizing welfare. When items' utilities are similar, in C5, new seeds of $i$ should be chosen in a way that minimizes $i$'s overlap with $j$ propagation. Instead in C6, when $i$ has much higher utility, it should be allocated to the top seed nodes. That way, the number of nodes that can be reached by $i$ is much higher and that helps boost the overall social welfare. As can be seen from our results next, that {\rm SupGRD}\xspace can navigate through these varied "strategies", while  {\rm SeqGRD{\text -}NM}\xspace cannot.

Fig. \ref{fig:exp_supgrd} (a) and (b) shows the result on the expected social welfare on \mbox{Orkut}\xspace and \mbox{Twitter}\xspace respectively. ``{\rm SeqGRD{\text -}NM}\xspace -C5'' (resp. ``{\rm SupGRD}\xspace -C5'') refers to {\rm SeqGRD{\text -}NM}\xspace (resp. {\rm SupGRD}\xspace) on C5 and ``{\rm SeqGRD{\text -}NM}\xspace -C6'' (resp. ``{\rm SupGRD}\xspace -C6'') on C6. Notice that  in C5 the welfare produced by the two algorithms are comparable. However in C6, where the gap between the individual utilities of the two items is higher, difference between the welfare of {\rm SupGRD}\xspace and {\rm SeqGRD{\text -}NM}\xspace is also larger. The reason for that is as follows. {\rm SeqGRD{\text -}NM}\xspace uses $\textsf{PRIMA}^+$ to select the seeds of $i$. Consequently to maximize the marginal gain in spread, it minimizes the overlap in the spread of $i$ and $j$ and hence allocates $i$ to lower ranked nodes in terms of spread. However $i$ is the superior item, so allocating  lower ranked nodes to $i$ decreases the overall welfare.

Fig. \ref{fig:exp_supgrd}(c) and (d) compares the running time of the two algorithms on \mbox{Orkut}\xspace and \mbox{Twitter}\xspace. Both the algorithms scale on these large networks. Unlike {\rm SeqGRD{\text -}NM}\xspace, running time {\rm SupGRD}\xspace depends on the utility configurations as well. As our running time analysis (\textsection \ref{sec:alg_supgrd}) suggests, when the minimum utility of an item is lower, the running time of {\rm SupGRD}\xspace is higher. However as can be seen, even on large networks, the difference in the running times is not very high: e.g., in configuration C6, the running time of {\rm SupGRD}\xspace is only a 2$\times$  that of {\rm SeqGRD{\text -}NM}\xspace, whereas in C5 the running times are similar. To summarize, {\rm SupGRD}\xspace addresses this unique challenge of dealing with an arbitrary degree of competition, with a slightly higher running time.

\subsection{More than two items}

Except for {\rm Balance{\text -}C}\xspace, all the  algorithms can deal with multiple items. In this section, we study their performances when the number of items is more than two. First, we show the impact of increasing the number of items on the running time and social welfare produced. Then we study how the algorithms behave under some challenging configurations designed using multiple items.

\spara{6.3.1 Impact of number of items}
For this experiment, the configuration we test is as follows. Each individual item has expected utility of $1$ and the items exhibit pure competition. Every item has budget $50$ and $\mathbfcal{S}^p = \emptyset$.

Fig. \ref{fig:assorted}(a) and (b) show respectively, the running time and social welfare produced by the five algorithms. Since {\rm Balance{\text -}C}\xspace cannot run on more than two items, it is omitted. Running time of algorithms \gm, {\rm TCIM}\xspace, {\rm MaxGRD}\xspace, and {\rm SeqGRD}\xspace increases significantly w.r.t the number of items. As the number of items increase, the number of times marginal check is needed for these algorithms, also increases. The marginal check is the most time consuming portion in their running time.
{\rm SeqGRD{\text -}NM}\xspace on the other hand relies solely on RR-sets and does not do any marginal checks. Hence the growth in running time is not high. With higher number items, the difference between the running time of {\rm SeqGRD{\text -}NM}\xspace and other algorithms, increases.

In terms of social welfare, {\rm TCIM}\xspace and {\rm MaxGRD}\xspace perform worse than the other algorithms. {\rm MaxGRD}\xspace selects only one item in the final allocation, hence it misses out on the additional welfare that could come from allocating the remaining items. Similarly {\rm TCIM}\xspace tries to maximize the spread of the last allocated item, at cost of  propagation of other items. Thus their welfare does not increase with more items, unlike the other algorithms.

\begin{table}[]
\begin{tabular}{|l|l|}
\hline
$\mathcal{U}\xspace(i) = 2$       & $\mathcal{U}\xspace(\{i, j\}) \textless 0$                                                                 \\ \hline
$\mathcal{U}\xspace(\{j\}) = 0.11 $    & $\mathcal{U}\xspace(\{j, k\}) \textless 0$                                                                 \\ \hline
$\mathcal{U}\xspace(\{k\}) = 0.1$     & \multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}$\mathcal{U}\xspace(\{i, j, k\})$\\ $\textless{}0$\end{tabular}} \\ \cline{1-1}
$\mathcal{U}\xspace(\{i, k\}) = 2.1$ &                                                                                    \\ \hline
\end{tabular}
\vspace{-2mm}
\caption{Three item configuration}
\label{tab:configs_3}
\end{table}

\begin{table}
\begin{tabular}{|r|c|c|c|}
 	\hline
	 item & $p$ & $q$ & $\mathcal{U}\xspace_D$ \\ \hline
	$\{indie\}$ 		& $0.107$  & $na$	& $7.0$ \\
	$\{rock\}$			& $0.091$ & $na$	& $6.8$ \\  
	 $\{industrial\}$     & $0.015$ & $na$ & $5.0$\\ 
	 $\{progressive\_metal\}$            &  $0.011$  & $na$ & $4.7$ \\ 
	 \hline
	\end{tabular} 
	\caption{Learned parameters} \label{tab:real_utils}
\end{table}
\spara{6.3.2 Effect of marginal check}
In our experiments so far, social welfare of {\rm SeqGRD{\text -}NM}\xspace has been similar to other algorithms that perform marginal checks. One exception being {\rm SupGRD}\xspace (\textsection 6.2.3), but {\rm SupGRD}\xspace assumes specific constraints that are not general. By not performing the marginal check, {\rm SeqGRD{\text -}NM}\xspace runs much faster compared to other algorithms. This begs the question if there is any advantage of using the marginal check altogether. In this experiment we show how marginal check helps avoid item-blocking that {\rm SeqGRD{\text -}NM}\xspace fails to circumvent. 

For this experiment, we consider three items in the propagation. Their expected utilities are specified in Table \ref{tab:configs_3}. $i$ has the highest expected utility, followed by $j$ and $k$ has the least. $i$ and $k$ exhibit soft competition hence bundle $\{i, k\}$ has a positive utility, but all other item bundles have negative utilities, exhibiting pure competition. We set the budget of $i$ to 500, and increase the budget of $j$ and $k$ from 100 to 500 each in steps of 100 and study the effect on the welfare produced by {\rm SeqGRD{\text -}NM}\xspace and {\rm SeqGRD}\xspace.

Fig. \ref{fig:assorted}(c) shows the result on the NetHept network. 
Both algorithms first allocate $i$ as it has the highest individual utility. Then {\rm SeqGRD{\text -}NM}\xspace allocates $j$ next, however this allocation is "adjacent" to $i$ \pink{since NetHept is small,} and blocks propagation of $i$ more. Since the utility of $i$ is significantly higher than $j$, allocating $j$ this way in fact causes a negative marginal. {\rm SeqGRD}\xspace, using marginal check, postpones allocation of $j$. After $i$, it instead allocates $k$. Although $k$ also has a low individual utility, because of soft competition, it does not block propagation of $i$ and the marginal is non-negative. It later allocates $j$, which is now further apart from $i$, hence cannot block $i$'s propagation. Thus {\rm SeqGRD}\xspace produces a social welfare which is higher than that of {\rm SeqGRD{\text -}NM}\xspace. Further, as the budget of $j$ increases, the amount of blocking also increases, hence the welfare difference between the two algorithms also goes up.

\spara{6.3.3 Scalability of {\rm SeqGRD{\text -}NM}\xspace}
Our next experiment shows the impact of network size on ${\rm SeqGRD{\text -}NM}\xspace$ using $\mbox{Orkut}\xspace$ with two types of edge probabilities: (1) $1/d_{in}(v)$ and (2) fixed $0.01$.  
We use a uniform budget of $50$ for all three items. Instead of using the full network, we use breadth-first-search to progressively increase the network size so that it includes a certain percentage of the total nodes in the network. At $100\%$, the full network is used. Fig. \ref{fig:assorted}(d) shows the results. ``{\rm SeqGRD{\text -}NM}\xspace, time 1'' and ``{\rm SeqGRD{\text -}NM}\xspace, time 2'' depict the running time of {\rm SeqGRD{\text -}NM}\xspace on the two types of edge probabilites respectively. As the network size increases, the running time in both cases roughly has a linear increase.





\subsection{Real item experiments}

In this section, we learn the utilities of items from real dataset instead of the synthetic utilities used in earlier experiments. 
The dataset used is the $\mbox{LastfmGenres}\xspace$ generated from the listening behavior of users of the music streaming service Last.fm  \cite{lastfm1k-data,lastfmtags-data}. 
This dataset was used in \cite{benson2018discrete} to learn the adoption probabilities of different items, where each genre is treated as an item. 
This dataset also echos our first motivating example in the introduction.
We next establish the connection between the adoption probabilities and the utilities, which enables us to learn the parameters using \cite{benson2018discrete}.



\spara{6.4.1 Learning the utilities}
In \cite{benson2018discrete}, every item $i$ is associated with an adoption probability $p_i$. Adoption probability of an itemset $I = \{i, ..., k\}$ is $p_{I} = \gamma_{|I|} \prod_{j \in I}p_{j} + q_{I}$, where $q_{I}$ is a correction received depending on the way  items in  $I$ interact with each other: if the items are complementary, then the correction is positive, if competing then it is negative, and $0$ if the items are independent. These probabilities and corrections are learnt in \cite{benson2018discrete} from the dataset of how frequently items are selected together by the users. 

According to Observation 2.2 of \cite{benson2018discrete}, $ p_i = e^{v_i} / \sum_j e^{v_j} $, where $v_i$ is the expected utility of item $i$ as per our utility model. 
Given a set of learnt $p_i$, we first set $\sum_j e^{v_j} = 10000$. Then for every $i$, we set $v_i = \ln(10000 \cdot p_i)$. We choose the number $10000$ to ensure that the corresponding utilities are positive. Finally we set the expected utility of item $i$, $\mathcal{U}\xspace(i) = v_i$.
Next for an itemset $I = \{i, ..., k\}$, \cite{benson2018discrete} learns two parameters $\gamma_{|I|}$ and $q'_{I}$. By using $q_{I} = \gamma \cdot q_{I}'$ the probability of adopting the bundle, $p_{I}$ is derived. The expected utility of the bundle is similarly set to be $\mathcal{U}\xspace(I) = \ln(10000 \cdot p_{I})$. Notice that the exact values of utilities are not as important as the relative order of utilities of different itemsets. The way utilities are learnt is in correspondence with the adoption probabilities learned in [7]. 

Table \ref{tab:real_utils} shows the utilities of four different items (i.e., genres) in the dataset: \textit{rock, indie, industrial and progressive\_metal},  learned using the above described method. 
Larger bundles are either not present in the dataset or have smaller learned utilities compared to the individual items in the bundle,
	suggesting that items are in pure competition in our utility model.

\eat{
\begin{table}[t!]
	\scriptsize

\subfloat[Three item configuration] \label{tab:configs_3}
{	\begin{tabular}{|l|l|}
\hline
$\mathcal{U}\xspace(i) = 2$       & $\mathcal{U}\xspace(\{i, j\}) \textless 0$                                                                 \\ \hline
$\mathcal{U}\xspace(\{j\}) = 0.11 $    & $\mathcal{U}\xspace(\{j, k\}) \textless 0$                                                                 \\ \hline
$\mathcal{U}\xspace(\{k\}) = 0.1$     & \multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}$\mathcal{U}\xspace(\{i, j, k\})$\\ $\textless{}0$\end{tabular}} \\ \cline{1-1}
$\mathcal{U}\xspace(\{i, k\}) = 2.1$ &                                                                                    \\ \hline
\end{tabular}
}
\subfloat[Learnt parameters] \label{tab:real_utils}{
	\begin{tabular}{r|c|c|c|}
	 item & $p$ & $q$ & $\mathcal{U}\xspace_D$ \\ \hline
	$\{indie\} (i)$ 		& $0.107$  & $na$	& $7.0$ \\
	$\{rock\} (j)$			& $0.091$ & $na$	& $6.8$ \\  
	 $\{industrial\} (k)$     & $0.015$ & $na$ & $5.0$\\ 
	 $\{progressive\_metal\} (l)$            &  $0.011$  & $na$ & $4.7$ \\ 
	 $\{indie, progressive\_metal\}$ &$.0006$ &$-0.0009$ &$1.7$ \\
	 $\{indie, industrial\}$ & $0.0014$ & $-0.0006$ & $2.6$ \\ \hline
	\end{tabular}
	}
}

\captionsetup[table]{font=normalsize}
\begin{table*}[h]
\centering
\resizebox{\linewidth}{!}{%
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
\multirow{2}{*}{Network} & \multirow{2}{*}{Budget} & \multirow{2}{*}{Algorithm} & \multicolumn{5}{l|}{Real Utility Configuration (as shown in Table~\ref{tab:real_utils})} & \multicolumn{4}{l|}{Synthetic Utility Configuration (as shown in Table~\ref{tab:configs_3})} \\ 
\cline{4-12}
 &  &  & indie & rock & industrial & progressive\_metal & welfare & i & j & k & welfare \\ 
\hline
\multirow{3}{*}{NetHEPT} & \multirow{3}{*}{10} & RR & 203 & 217 & 191 & 196 & 4473.08 & 277 & 244 & 234 & 513.2 \\ 
\cline{3-12}
 &  & Snake & 204(+0.005) & 201(-0.081) & 207(+0.083) & 195(-0.005) & 4458.64(-0.003) & 258(-0.068) & 246(+0.008) & 261(+0.115) & 478.4(-0.068) \\ 
\cline{3-12}
 &  & SGRD-NM & 255(+0.252) & 199(-0.082) & 188(-0.016) & {\color{green}\textbf{165(-0.158)}} & 4951.8 (+0.112) & 306(+0.105) & 220(-0.098) & 227(-0.030) & 577.4(+0.125) \\ 
\hline
\multirow{3}{*}{NetHEPT} & \multirow{3}{*}{40} & RR & 496 & 493 & 491 & 475 & 10795.3 & 667 & 576 & 645 & 1227.3 \\ 
\cline{3-12}
 &  & Snake & 483(-0.026) & 496(+0.006) & 488(-0.004) & 488(+0.027) & 10758.2(-0.003) & 648(-0.028) & 581(+0.009) & 669(+0.037) & 1194.5(-0.027) \\ 
\cline{3-12}
 &  & SGRD-NM & 673(+0.357) & 499(+0.012) & 419(-0.147) & {\color{green}\textbf{365(-0.189)}} & 11264.5(+0.043) & 800(+0.199) & 510(-0.114) & 514(-0.203) & 1510.6(+0.230) \\ 
\hline
\multirow{3}{*}{Orkut} & \multirow{3}{*}{10} & RR & 37790 & 38888 & 38331 & 34711 & 828368.2 & 69151 & 49730 & 67405 & 110032.5 \\ 
\cline{3-12}
 &  & Snake & 38241(+0.012) & 37401(-0.038) & 39818(+0.039) & 34260(-0.013) & 828235.4(-0.002) & 67648(-0.021) & 50511(+0.016) & 68510(+0.016) & 107227.7(-0.026) \\ 
\cline{3-12}
 &  & SGRD-NM & 50800(+0.344) & 40837(+0.050) & 31189(-0.186) & 26895(-0.225) & 864154.3(+0.040) & 76784(+0.110) & 50219(+0.010) & 57199(-0.151) & 124210.9(+0.129) \\ 
\hline
\multirow{3}{*}{Orkut} & \multirow{3}{*}{40} & RR & 58142 & 58586 & 59939 & 54607 & 1276650.6 & 119039 & 83291 & 113359 & 183853.2 \\ 
\cline{3-12}
 &  & Snake & 57211(-0.016) & 56922(-0.028) & 61603(+0.028) & 55538(+0.017) & 1272190.7(-0.035) & 117454(-0.013) & 82937(-0.043) & 115338(+0.018) & 180269.4(-0.020) \\ 
\cline{3-12}
 &  & SGRD-NM & 106876(+0.838) & 54909(-0.063) & 42218(-0.296) & {\color{green}\textbf{27272(-0.501)}} & 1397770.8(+0.095) & 150926(+0.268) & {\color{green}\textbf{63577(-0.237)}} & 87480(-0.228) & {\color{green}\textbf{253427.9(+0.378)}} \\
\hline
\end{tabular}
}
\caption{Adoption count of different items and the overall social welfare}\label{tab:utilvsadopt}
\end{table*}
\spara{6.4.2 Results using real parameters}

We use the learned utility configuration to compare the social welfare produced by the algorithms on two networks, namely \mbox{NetHEPT}\xspace and \mbox{Orkut}\xspace. For the experiment we set uniform budget for all the four items, which varies from 10 to 40 in steps of 10. The algorithms compared are ${\rm TCIM}\xspace, {\rm MaxGRD}\xspace, {\rm SeqGRD}\xspace$ and ${\rm SeqGRD{\text -}NM}\xspace$. The results are shown in Fig \ref{fig:real_exp}.


In terms of running time the results are similar to our previous experiments (Fig \ref{fig:real_exp}(a)-(b)). ${\rm SeqGRD{\text -}NM}\xspace$ outperforms the other algorithms by orders of magnitude, since it does not require the time consuming marginal gain computation. For social welfare, notice that the real utility configuration exhibits pure competition. 
As noted earlier, under pure competition, social welfare produced by ${\rm SeqGRD}\xspace$ and ${\rm SeqGRD{\text -}NM}\xspace$ coincide. ${\rm MaxGRD}\xspace$ and ${\rm TCIM}\xspace$ on the other hand typically encourage the adoption of one single item. 
Hence the difference in social welfare produced by these algorithms compared to ${\rm SeqGRD{\text -}NM}\xspace$ is higher since the number of items are also more than the previous configurations we used. 



\spara{6.4.3 Social welfare vs adoption}

Our final set of experiments compare the relationship between the social welfare and item adoptions. In particular, we want to investigate whether maximizing welfare for competing items could result in a significant drop in the number of item adoptions. For this experiment, we focus on two utility configurations -- (i) Real utility of Table \ref{tab:real_utils}, which exhibits pure competition and (ii) Synthetic utility of Table \ref{tab:configs_3}, which exhibits a mix of partial and pure competition. NetHEPT and \mbox{Orkut}\xspace are the two networks used and each item's budget is set to two different values, 10 and 40. 

We compare our algorithm ${\rm SeqGRD{\text -}NM}\xspace$ against two baselines. After selecting the seed nodes, the first baseline allocates items to the nodes in a round robin manner, hence it is called $Round-robin$. 
The second baseline, called $Snake$, is similar to Round-robin, but it flips the order for every successive sequence of allocations. 
To illustrate, if there are 4 seed nodes $s_1, ..., s_4$, in order, and two items $i, j$, ${\rm SeqGRD{\text -}NM}\xspace$ allocates as $s_1\colon i,s_2\colon i,s_3\colon j,s_4\colon j$, {Round-robin} allocates as $s_1\colon i,s_2\colon j,s_3\colon i,s_4\colon j$ and {Snake} allocates as $s_1\colon i,s_2\colon j,s_3\colon j,s_4\colon i$. 
Table \ref{tab:utilvsadopt} shows the adoption count of each item and the social welfare produced by these algorithms under different configurations.

In terms of the social welfare objective, ${\rm SeqGRD{\text -}NM}\xspace$ dominates across all different configurations. {Round-robin} produces the next highest welfare. Hence we report the fractional change ($+$ denotes increase and $-$ denotes decrease), in comparison to {Round-robin}, next to each entry of the table. The entries that deserve more attention are highlighted in green.

As can be seen, the total number of adoptions of all the items remains the same across all three algorithms. However, {\rm SeqGRD{\text -}NM}\xspace generally increases the adoption of the superior product to increase the welfare, while reducing the adoption of the inferior item. On NetHEPT, for budget 10, the maximum drop in adoptions happens for the most inferior item (progressive\_metal), by  $15.8\%$. For a higher budget, the drop increases (to $18.9\%$), because when budget increases for the superior item, ${\rm SeqGRD{\text -}NM}\xspace$ allocates lower ranked seeds for the inferior item.

The highest drop in adoption i.e., $50.1\%$, also happens for the item progressive\_metal for budget 40 on Orkut. This is because when items are purely competing, number of items is high and each item has a large budget, the inferior items' seeds are in fact much lower ranked. However, if it exhibits partial competition with a superior item, then leveraging it the adoption does not decrease that much. That is why in Orkut even when the budget is 40, for the synthetic utility configuration, the highest drop in adoptions for the inferior items is only $23.7\%$. Also notice ${\rm SeqGRD{\text -}NM}\xspace$ produces significantly higher social welfare compared to the baselines, the increase being up to $37.8\%$.  
In summary, we see that our welfare maximization algorithm  provide more adoptions to the superior items and fewer adoptions to the inferior
	items, but the amount of change is not too drastic. We argue that this is the "price" of enhancing  the overall user satisfaction; also the drop in the adoptions of the inferior items is exactly because they are not as competitive. 



 




To conclude this section, we generally observe that:
(a) when the conditions required by {\rm SupGRD}\xspace are met, it is the best option providing the best social welfare and competitive running time;
(b) in the general case, {\rm SeqGRD{\text -}NM}\xspace performs well in most cases and has the best running time, but when item blocking is significant, its marginal-checking version {\rm SeqGRD}\xspace 
	could provide better social welfare, at the cost of higher running time; 
(c) {\rm MaxGRD}\xspace could be used to enhance the theoretical guarantee when the utility difference is high, but its superiority is not typically observed in large networks; 
(d) our algorithms outperform all baselines on social welfare and running time and scale to large networks. Our algorithms achieve superior welfare at the expense of a reasonable drop in the adoption count of inferior items, keeping the total adoption count unchanged. 

\vspace{-3mm}
\section{Conclusions and future work} \label{sec:concl} 

In this paper, we study the problem of maximizing social welfare over competing items under the UIC  model. The problem is not only NP-hard but  is also NP-hard to approximate within a constant factor. Further we find that due to conflicting requirements, it is challenging to design a single algorithm that can work effectively for all different utility configurations. 
Yet we propose a cohort of efficient algorithms that not only provide approximation guarantees but also scale well to real large networks, and their performance  is validated through extensive experiments on real-world networks.

Although  welfare maximization under competition ensures that users' total  utility from adoptions is maximized, it does not directly ensure fairness. For a campaigner who often pays for advertising, ensuring that her item is seen at least by a certain number of users is critical. While fairness in IM  has been studied recently,   incorporating fairness in social welfare maximization will be an interesting  challenge. Further, this paper and \cite{ban2019} studied competition and complementarity in isolation. Designing algorithms for an arbitrary mix of competing and complementary items is an intriguing  problem.



