## 3 Preliminaries
### Competitive Linear Threshold (\(\mathsf{CLT}\)) Model  
In this model, a social network is abstracted by a directed graph \(G=(V,E)\), where \(V\) is the set of nodes (or vertices) representing users and \(E\) is the set of edges representing links among users. There are two competitors \(A\) and \(B\) who want to promote their products in a social network \(G\). Each edge \((u,v)\in E\) has two weights \(w_{A}(u,v)\) and \(w_{B}(u,v)\) representing the influence of \(A\) and \(B\) on edge \((u,v)\), respectively. The weights satisfy conditions  
\[\sum_{u\in N_{-}(v)}w_{A}(u,v)\leq 1\,\sum_{u\in N_{-}(v)}w_{B}(u,v)\leq 1, \forall v\in V\]  
Each node can choose one of three status: _A-active, B-active_, and _inactive_, which represent the nodes that have been successfully activated by \(A\), activated by \(B\), and have not been activated by either \(A\) or \(B\). Each node \(v\) picks two independent thresholds \(\theta_{A}(v),\theta_{B}(v)\)_uniformly_ from \([0,1]\), called _A-threshold_ and _B-threshold_. The propagation process happens in discrete steps \(t=0,1,\ldots\)\(S_{A}\) and \(S_{B}\) are the seed sets of competitors \(A\) and \(B\) (\(S_{A}\cap S_{B}=\emptyset\)). \(A_{t}\) and \(B_{t}\) are the set of _A-active_ and _B-active_ nodes at step \(t\), respectively. The process of propagation operates as follows:  
* At step \(t=0\), \(A_{0}=S_{A},B_{0}=S_{B}\). * At step \(t\geq 1\), it first sets \(A_{t}=A_{t-1}\) and \(B_{t}=B_{t-1}\). Each node \(v\
otin A_{t-1}\cup B_{t-1}\) becomes \(A\)-active if \[ \begin{cases}\sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)\geq\theta_{A}(v)\\ \sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)<\theta_{B}(v)\end{cases} \] (2) Node \(v\) becomes \(B\)-active if \[ \begin{cases}\sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)\geq\theta_{B}(v)\\ \sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)<\theta_{A}(v)\end{cases} \] (3) in the case when node \(u\) that has the total influence weight of two competitors are greater than corresponding thresholds. [PERSON] et al. [21] summarized tie-breaking rules can be used to determine whether \(v\) is \(A\)-active or \(B\)-active. \begin{table}
\begin{tabular}{l l} \hline \hline
**Notations** & **Descriptions** \\ \hline \(n,m\) & the number of nodes and the number of edges \\ \hline \(N_{-}(v),N_{+}(v)\) & the sets of incoming, and outgoing neighbor nodes of \(v\) \\ \hline \(S_{A},S_{B}\) & seed sets of \(A\) and \(B\), respectively \\ \hline \(n_{0}\) & \(n-|S_{B}|\) \\ \hline \(\mathbb{I}(\cdot),\mathbb{L}(\cdot),\mathbb{U}(\cdot)\) & The expected number of \(A\)-active nodes, its lower bound and its upper bound, respectively \\ \hline \(\mathbb{\hat{U}}_{c}(S_{A}),\mathbb{\hat{U}}_{t}(S_{A})\) & Estimations of \(\mathbb{U}(S_{A})\) over set \(\mathcal{R}_{c}\) and \(\mathcal{R}_{t}\), respectively \\ \hline \(S_{A}^{*},S_{L}^{*},S_{U}^{*}\) & Optimal solution for BCIM, optimal solution for maximizing \(\mathbb{L}(\cdot)\), and \(\mathbb{U}(\cdot)\) \\ \hline OPT, OPT\({}_{I}\), OPT\({}_{\text{\tiny{$I$}}}\) & \(\mathbb{I}(S^{*}),\mathbb{L}(S_{L}^{*}),\mathbb{U}(S_{U}^{*})\) \\ \hline Y\((\epsilon,\delta)\) & \(1+(1+\epsilon)(2+\frac{2}{3}\epsilon)\ln\frac{2}{\delta}\frac{1}{\epsilon^{2}}\) \\ \hline \(\mathsf{Cov}_{B}(S)\) & number of LRR (or URR) sets \(R_{j}\) be covered by \(S\) \\ \hline \(k_{max}\) & \(\max\{k:\exists A\subseteq V,c(A)\leq L\}\) \\ \hline \(\alpha\), \(\beta\) & \((1-\frac{1}{\sqrt{\epsilon}})\sqrt{\ln(\frac{2}{3})}\), \(\sqrt{\left(1-\frac{1}{\sqrt{\epsilon}}\right)\left(\ln\frac{2}{3}+\ln\left( \frac{n}{k_{max}}\right)\right)}\) \\ \hline \(N(\epsilon,\delta)\) & \(2n\left(\alpha+\beta\right)^{2}\frac{1}{\epsilon^{2}\mathsf{OPT}_{I}}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. Fixed probability tie-breaking rule (TB-FP): TB-FP means that with a fixed probability \(p\), \(u\) becomes \(A\)-active with probability \(p\) and becomes \(B\)-active with probability \(1-p\). The special cases of this rule include TB-FP(A)-competitor \(A\)'s dominance, TB-FP(B)-competitor \(B\)'s dominance.