# Unraveling Proton Strangeness: Robust Determination of the Strangeness Sigma
Term with High Statistical Significance

Wei Kou<EMAIL_ADDRESS>Institute of Modern Physics, Chinese Academy of
Sciences, Lanzhou 730000, China  School of Nuclear Science and Technology,
University of Chinese Academy of Sciences, Beijing 100049, China  Xurong Chen
<EMAIL_ADDRESS>(Corresponding author) Institute of Modern Physics, Chinese
Academy of Sciences, Lanzhou 730000, China  School of Nuclear Science and
Technology, University of Chinese Academy of Sciences, Beijing 100049, China

###### Abstract

This study delves into the contribution of the strange quark within the
proton, which influences several fundamental proton properties. By
establishing a robust relationship between the proton’s quantum anomalous
energy and the sigma term, we successfully extract the strangeness sigma term
($\sigma_{sN}$) with a precise value of $420.1\pm 59.3$ MeV. Additionally, we
present novel results for the proton trace anomalous energy, observing a value
of $0.12\pm 0.02$. Our analysis integrates the most recent data from the Hall
C and GlueX collaborations, warranting a strong endorsement for the existence
of a non-zero strangeness component inside the proton, with a remarkable
statistical significance of $7.1\sigma$. Furthermore, we investigate the
possibility of scheme-independence in the extraction results and examine the
uniformity of sigma terms obtained from the datasets provided by the two
collaborations. Our analysis reveals compatibility between the extraction
results of the respective experiments.

###### pacs:

24.85.+p, 13.60.Hb, 13.85.Qk

_1\. Introduction_ — The parton model provides insight into the dynamics of
the internal components of the proton. Protons, as complex bound-state
particles comprising quarks and gluons, have been the subject of extensive
discussion regarding their external properties, such as charge, mass, charge
radius, and other attributes. Understanding how the contributions of
individual components of the proton manifest in its external properties is a
complex and ongoing issue. Notably, experimental evidence for the contribution
of partons other than up and down quarks remains insufficient. The role of
strange and charm quarks in protons continues to be a topic of significant
interest in the field Ball  _et al._ (2022); An  _et al._ (2006); Zou and
Riska (2005); Zou (2007); Sapozhnikov (2011). Studies investigating the
strangeness contribution to proton magnetic moments Zou and Riska (2005) have
provided valuable insights into the intrinsic strange quark within the proton.
Furthermore, there may be correlations between other properties of the proton
and the contributions of the quarks and gluons within it.

The contribution of quarks to the proton mass can be summarized by the quark
scalar matrix elements – sigma terms. They are defined as

$\sigma_{qN}=\langle N\mid m_{q}\bar{q}q\mid N\rangle,$ (1)

where $|N\rangle$ is proton state in the rest frame, $q(\bar{q})$ the quark
filed operators, $m_{q}$ the current quark mass of flavor $q$. For the u- and
d-flavor quark cases, the $\pi N$ sigma term is introduced and denoted by
$\sigma_{\pi N}=m_{l}\langle N|u\bar{u}+d\bar{d}|N\rangle$ with the average
mass of $u$, $d$ quarks $m_{l}$. The sigma terms of the nucleon are the main
source of uncertainty in the calculation of the scattering for spin-
independent nucleon with dark matter Ellis  _et al._ (2018), so it is
particularly important to measure them precisely from experiments. Previous
studies of the nucleon sigma terms can be found in Gasser  _et al._ (1991);
Pavan  _et al._ (2002); Ohki  _et al._ (2008); Toussaint and Freeman (2009);
Takeda  _et al._ (2011); Alarcon  _et al._ (2012); Durr  _et al._ (2012);
Horsley  _et al._ (2012); Bali  _et al._ (2012); Sapozhnikov (2011); Shanahan
_et al._ (2013); Ohki  _et al._ (2013); Gong  _et al._ (2013); Alvarez-Ruso
_et al._ (2013); Junnarkar and Walker-Loud (2013); An and Saghai (2015); Lutz
_et al._ (2014); Ren  _et al._ (2015); Yang  _et al._ (2016); Hoferichter  _et
al._ (2015); Abdel-Rehim  _et al._ (2016); Ruiz de Elvira  _et al._ (2018);
Varnhorst (2018). A recent determination from high-precision data gives the
value of the $\sigma_{\pi N}$ as $59.1\pm 3.5$ MeV Hoferichter  _et al._
(2015). The discussion of the contribution of strange quarks $\sigma_{sN}$ in
the scalar charge from the experimental perspective, which one currently has,
is still quite lacking. Fortunately there are many lattice QCD calculations as
well as results from chiral perturbation theory performances available to us.
In addition, we note that there is the work that suggests constraining the
strangeness component by measuring the mass shift of $\phi$ meson in nuclear
matter Gubler and Ohtani (2014). At this point we may consider that the
strangeness component of the proton mass can be linked to its corresponding
scalar charge or sigma term.

The sigma term is related to the QCD gauge invariant Hamiltonian
decomposition, which comes from Ji’s work Ji (1995a, b, 2021); Ji and Liu
(2021). The decomposition of QCD Hamiltonian is written as

$H_{QCD}=H_{q}+H_{g}+H_{m}+H_{a}.$ (2)

They represent, in order, the quark energy, the gluon field energy, the quark
condensation contribution, and the quantum anomalous energy

$\begin{gathered}\begin{aligned}
M_{q}=\frac{3}{4}\left(a-\frac{b}{1+\gamma_{m}}\right)M_{N},\ \ \
&M_{g}=\frac{3}{4}(1-a)M_{N},\end{aligned}\\\
M_{m}=\frac{4+\gamma_{m}}{4\left(1+\gamma_{m}\right)}bM_{N},\quad
M_{a}=\frac{1}{4}(1-b)M_{N},\end{gathered}$ (3)

with proton mass $M_{N}=\langle N|H|N\rangle/\langle N|N\rangle$ in the rest
frame. The parameters $a(\mu)$ is the momentum fraction carried by quarks in
the infinite momentum frame, and $b$ is related to the scalar charge of the
proton as $b=\langle
N|m_{u}\bar{u}u+m_{d}\bar{d}d+m_{s}\bar{s}s|N\rangle/M_{N}$. More specifically
it can be expressed as

$bM_{N}=\sigma_{\pi N}+\sigma_{sN}.$ (4)

According to the previously mentioned definition of the parameter $b$ , it is
determined by the scalar charge from $u$, $d$, and $s$ quarks. While more
precise experimental measurements of $\sigma_{\pi N}$ are already available,
as mentioned earlier, the direct experimental determination of the strangeness
component presents challenges. In addition to using measurements of the mass
shift of the $\phi$ meson in nuclear matter to determine the strangeness sigma
term Gubler and Ohtani (2014), there is another possible way to extract it
from experiments Wang  _et al._ (2020); Kou  _et al._ (2022); Duran  _et al._
(2023); Wang  _et al._ (2022) by obtaining the parameter $b$ discussed above.
The latter approach is related to the near-threshold photo-production process
of the ground-state charmonium Kharzeev (1996); Kharzeev  _et al._ (1999).
Fortunately, experimental measurements of the process Duran  _et al._ (2023);
Ali  _et al._ (2019); Adhikari  _et al._ (2023) have become substantial in
recent years. We use recent data for theoretical analysis and provide the
strangeness contribution to the proton sigma term. The discussion of details
is presented in the following sections.

_2\. Extraction methods and experiments_ — The near-threshold photo-production
process of $J/\psi$ is commonly used to extract the Gravitational Form factors
(GFFs) of the proton, which are related to the QCD Energy-Momentum-Tensor. The
GFFs of the proton can be utilized to reveal the mass distribution as well as
mechanical properties such as pressure inside the proton, as demonstrated by
Holographic QCD Mamo and Zahed (2020) or the Generalized Parton Distribution
Functions (GPDs) theory Guo  _et al._ (2021). These methods essentially
provide information about GFFs.

In Ref. Kharzeev  _et al._ (1999), the calculation of the differential cross
section of $J/\psi$ photo-production at near-threshold is presented as

$\displaystyle\left.\frac{d\sigma_{\gamma N\to J/\psi N}}{dt}\right|_{t=0}$
(5) $\displaystyle\left.=\frac{3\Gamma(J/\psi\to e^{+}e^{-})}{\alpha
m_{J/\psi}}\left(\frac{k_{J/\psi N}}{k_{\gamma
N}}\right)^{2}\frac{d\sigma_{J/\psi N\to J/\psi N}}{dt}\right|_{t=0},$

where $\begin{aligned}
k_{ab}^{2}=[s-(m_{a}+m_{b})^{2}][s-(m_{a}-m_{b})^{2}]/4s\end{aligned}$ denotes
the momentum square of the reaction in the center-of-mass frame, and $\Gamma$
stands for the partial $J/\psi$ decay width. Using the vector meson dominance
(VMD) approach, the differential cross section of $J/\psi-N$ at low energy is
expressed with the amplitude as

$\left.\frac{d\sigma_{J/\psi N\to J/\psi
N}}{dt}\right|_{t=0}=\frac{1}{64\pi}\frac{1}{m_{J/\psi}^{2}(\lambda^{2}-M_{N}^{2})}F_{J/\psi
N}^{2},$ (6)

where $\lambda=(pK/m_{J/\psi})$ is the nucleon energy in the quarkonium rest
frame, and $p$, $K$, are the four-momenta of the target nucleon, $J/\psi$,
respectively.

The $J/\psi-N$ elastic scattering amplitude $F_{J/\psi N}$, a key component of
this study, is determined using the heavy quark non-relativistic approximation
Kharzeev (1996). In this context, the ground state $J/\psi$ system is
considered to be governed by Coulomb-like interactions between positive and
negative charm quarks. Notably, the Bohr radius of the $J/\psi$ meson, given
by $r_{0}=4/(3\alpha_{s}m_{c})$, depends on the quark mass and strong
coupling. Following the expression in Ref. Kharzeev (1996), the $J/\psi-N$
scattering amplitude is given by

$\displaystyle
F_{{J/\psi}N}=r_{0}^{3}d_{2}\frac{8\pi^{2}}{27}(1-b)M_{N}^{2}m_{J/\psi},$ (7)

with $bM_{N}$ in Eq. (4). Here, $d_{n}$ represents the Wilson coefficient
defined in Peskin (1979). The second line of the above equation is derived
from the discussion surrounding Eq. (4). It is important to note that Eq. (7)
exhibits dimensional inconsistencies with the formulas in Refs. Wang  _et al._
(2020, 2022); Kharzeev (1996). Therefore, we adopt the correct dimensional
results as presented in Ref. Kharzeev  _et al._ (1999), consistent with our
prior work Kou  _et al._ (2022).

We will conduct our analysis utilizing the recently published differential
cross-section data by the Hall C and GlueX Collaborations at JLab Duran  _et
al._ (2023); Adhikari  _et al._ (2023). As outlined in Eqs. (5-7), the forward
differential cross-section for each experimental energy set is required for
our analysis. In this communication, we opt for the exponential form
$d\sigma/dt=Ae^{-Bt}$ to fit the data, where $A=d\sigma/dt|_{t=0}$ represents
the forward differential cross-section.

Different photon energies that lead to $J/\psi$ production near the threshold
are expected to result in distinct forward scattering cross-sections. Previous
studies Wang  _et al._ (2020, 2022) relied on experimental data from Ali  _et
al._ (2019) with only one energy point, making it challenging to determine
whether the anomalous energy trace in protons was scale-dependent. However,
recently published experimental data Duran  _et al._ (2023) and research on
extracting proton mass radii and trace anomalous energy have revealed
perplexing energy dependencies. Despite the expectation that these
observations should not be scale-or scheme-dependent, we aim to address these
questions in the following sections.

_3\. Numerical results and discussions_ — The exponential fits to the
differential cross-section $d\sigma/dt$ utilizing data from the Hall C and
GlueX collaborations are presented in Figures 1 and 2. The corresponding
fitting parameters are detailed in Tables 1 and 2. To extract the proton trace
anomaly and sigma term, we adopt the charm quark mass with $r_{0}$ in Eq. (7)
as $m_{c}=1.69$ GeV Wang  _et al._ (2020); Kou  _et al._ (2022). The strong
coupling $\alpha_{s}$ is cited from Deur  _et al._ (2016, 2023).

Figure 1: Exponential fit to the differential cross section $d\sigma/dt$ using
the data from Hall C collaboration Duran  _et al._ (2023). The orange band
shows its uncertainty. The parameters are listed in Table 1. Figure 2:
Exponential fit to the differential cross section $d\sigma/dt$ using the data
from GlueX collaboration Adhikari  _et al._ (2023). The light blue band shows
its uncertainty. The parameters are listed in Table 2. Table 1: Exponential
fit to the differential cross section $d\sigma/dt$ using the data from Hall C
collaboration Deur  _et al._ (2023). Fitting parameters, trace anomaly and
strangeness sigma term.

$E_{\gamma}$ (GeV) |  $A$ (nb/GeV2) |  $B$ (GeV-2) | $M_{a}/M_{N}$ |  $\sigma_{sN}$ (MeV)
---|---|---|---|---
$9.1\sim 9.25$ | $0.57\pm 0.23$ | $0.90\pm 0.30$ | $0.10\pm 0.02$ | $493.54\pm 76.81$
$9.25\sim 9.4$ | $0.42\pm 0.10$ | $0.57\pm 0.17$ | $0.08\pm 0.01$ | $563.89\pm 36.94$
$9.4\sim 9.55$ | $0.96\pm 0.19$ | $1.00\pm 0.18$ | $0.12\pm 0.01$ | $427.03\pm 43.73$
$9.55\sim 9.7$ | $1.20\pm 0.23$ | $1.06\pm 0.20$ | $0.12\pm 0.01$ | $413.24\pm 47.35$
$9.7\sim 9.85$ | $1.82\pm 0.49$ | $1.52\pm 0.25$ | $0.15\pm 0.02$ | $311.95\pm 75.82$
$9.85\sim 10.0$ | $1.54\pm 0.41$ | $1.31\pm 0.24$ | $0.13\pm 0.02$ | $377.74\pm 67.12$
$10.0\sim 10.15$ | $1.41\pm 0.25$ | $1.05\pm 0.15$ | $0.12\pm 0.01$ | $418.21\pm 41.29$
$10.15\sim 10.3$ | $1.67\pm 0.26$ | $1.17\pm 0.15$ | $0.13\pm 0.01$ | $395.97\pm 37.04$
$10.3\sim 10.45$ | $1.63\pm 0.39$ | $1.28\pm 0.29$ | $0.12\pm 0.01$ | $417.89\pm 55.16$
$10.45\sim 10.6$ | $1.97\pm 0.47$ | $1.39\pm 0.30$ | $0.13\pm 0.02$ | $389.26\pm 58.02$

Table 2: Exponential fit to the differential cross section $d\sigma/dt$ using
the data from GlueX collaboration Adhikari  _et al._ (2023). Fitting
parameters, trace anomaly and strangeness sigma term.

$E_{\gamma}$ (GeV) |  $A$ (nb/GeV2) |  $B$ (GeV-2) | $M_{a}/M_{N}$ |  $\sigma_{sN}$ (MeV)
---|---|---|---|---
$8.92\sim 9.28$ | $0.63\pm 0.21$ | $1.10\pm 0.19$ | $0.12\pm 0.02$ | $431.19\pm 75.41$
$9.28\sim 10.36$ | $1.20\pm 0.15$ | $0.92\pm 0.07$ | $0.12\pm 0.01$ | $429.97\pm 27.81$
$10.36\sim 11.44$ | $2.21\pm 0.24$ | $1.11\pm 0.07$ | $0.13\pm 0.01$ | $391.58\pm 26.95$

Figure 3 illustrates the extracted strangeness sigma terms of the proton using
data sets from the Hall C (blue circles) and GlueX (red squares)
collaborations Duran  _et al._ (2023); Adhikari  _et al._ (2023). The shaded
regions of the corresponding colors indicate the standard deviations of each
data set at different energy settings. The combined standard deviation of the
two data sets is $\sigma=59.3$ MeV. Notably, Fig. 3 suggests that there is
minimal energy dependence of the proton strangeness sigma term extracted from
the data of the two collaborations. Based on these results, we infer that the
strangeness sigma term for the proton has a significance of $7.1\sigma$,
indicating that it is not zero.

Figure 3: The extracted strangeness sigma terms of proton with the experiments
data from Hall C (blue points) and GlueX (red squares) collaborations Duran
_et al._ (2023); Adhikari  _et al._ (2023). The blue and red shades present
the corresponding standard deviations of data sets. The difference between the
mean of all extractions and zero is $7.1$ times combined standard deviation

Furthermore, we conduct the Kolmogorov-Smirnov (KS) test Eadie  _et al._
(1971) on the sigma term distributions extracted from the two sets of
experimental data. Initially, we test the difference between the distributions
of the two sets of sigma terms and the ZERO values, yielding a p-value of
$0.0$ for both. Additionally, we test the similarity of the two distributions
themselves and obtained a p-value of approximately 0.5, indicating that the
two sets of experimental data cannot be dismissed as being the same
distribution. It is important to note that, due to the relatively small number
of sample points, the results of the KS test serve solely as a reference and
do not definitively determine the conclusions we propose regarding the KS
test.

We proceed to discuss the disparities between our approach and the previous
works Wang  _et al._ (2020, 2022). Firstly, the dimensional analysis of the
$J/\psi-N$ scattering amplitude in Eq. (7) differs from that of the previous
works. We have modified it in accordance with the approach detailed in Ref.
Kharzeev  _et al._ (1999). Secondly, we have developed a new running coupling
constant energy scale tailored to the different experimental data energy
settings. Specifically, we utilize the discrepancy between the energy of the
center-of-mass system of the photon-proton and the mass of the final-state
proton and $J/\psi$ as the $\alpha_{s}(\mu)$ energy scale, i.e.,
$\mu=W-M_{N}-m_{J/\psi}$. This approach reduces the process of photon coupling
to vector mesons as described by the VMD approach. However, in the non-
relativistic approximation, photon energies may impact the binding of charm
quark pairs into $J/\psi$, subsequently affecting the Bohr radius $r_{0}$. The
center-of-mass energy of the system can be derived from the photon energy as
input, and the energy remaining after removing the mass of the particles
produced in the final state can be roughly understood as the binding energy
required for the quasi-meson to meson process.

Lastly, our extracted sigma term values are larger than those presented in
other works. While larger uncertainties in the experimental extraction cannot
be disregarded, we have assumed the contribution of only three flavor quarks
inside the proton throughout the extraction process, based on which we obtain
a strangeness sigma term of about 400 MeV. Building on these assumptions, we
have obtained relatively centralized distributions of the proton trace anomaly
and strangeness sigma term.

_4\. Conclusions_ — In conclusion, we have successfully extracted the
strangeness sigma term for the proton from experimental data for the first
time, establishing its scale and scheme independence. This marks the inaugural
instance of a non-zero contribution to the intrinsic strangeness of the proton
being quantified in terms of the proton mass contribution. The strangeness
sigma term is determined to be $\sigma_{sN}=420.1\pm 59.3$ MeV, demonstrating
a significance of at least 7.1 times the standard deviation between its value
and zero. From our perspective, the strangeness component is not entirely
absent, at least in terms of its contribution to the proton mass, as evidenced
by the extraction of $\sigma_{sN}$. Furthermore, there are substantial
uncertainties in the available experimental data, including those introduced
by the photon energy bins. The high-precision data anticipated from Electron-
Ion Colliders in the United States Accardi  _et al._ (2016); Abdul Khalek  _et
al._ (2022) and China Chen (2018); Chen  _et al._ (2020); Anderle  _et al._
(2021) will be more emergent in the future.

###### Acknowledgements.

We are grateful to Dr. Rong Wang for discussions and comments on the
manuscript. This work is supported by the Strategic Priority Research Program
of Chinese Academy of Sciences (Grant NO. XDB34030301).

## References

  * Ball  _et al._ (2022) R. D. Ball, A. Candido, J. Cruz-Martinez, S. Forte, T. Giani, F. Hekhorn, K. Kudashkin, G. Magni, and J. Rojo (NNPDF), Nature 608, 483 (2022), arXiv:2208.08372 [hep-ph] .
  * An  _et al._ (2006) C. S. An, D. O. Riska, and B. S. Zou, Phys. Rev. C 73, 035207 (2006), arXiv:hep-ph/0511223 .
  * Zou and Riska (2005) B. S. Zou and D. O. Riska, Phys. Rev. Lett. 95, 072001 (2005), arXiv:hep-ph/0502225 .
  * Zou (2007) B. S. Zou, Nucl. Phys. A 790, 110 (2007), arXiv:nucl-th/0610062 .
  * Sapozhnikov (2011) M. G. Sapozhnikov, Few Body Syst. 50, 145 (2011).
  * Ellis  _et al._ (2018) J. Ellis, N. Nagata, and K. A. Olive, Eur. Phys. J. C 78, 569 (2018), arXiv:1805.09795 [hep-ph] .
  * Gasser  _et al._ (1991) J. Gasser, H. Leutwyler, and M. E. Sainio, Phys. Lett. B 253, 252 (1991).
  * Pavan  _et al._ (2002) M. M. Pavan, I. I. Strakovsky, R. L. Workman, and R. A. Arndt, PiN Newslett. 16, 110 (2002), arXiv:hep-ph/0111066 .
  * Ohki  _et al._ (2008) H. Ohki, H. Fukaya, S. Hashimoto, H. Matsufuru, J. Noaki, T. Onogi, E. Shintani, and N. Yamada (JLQCD), PoS LATTICE2008, 126 (2008), arXiv:0810.4223 [hep-lat] .
  * Toussaint and Freeman (2009) D. Toussaint and W. Freeman (MILC), Phys. Rev. Lett. 103, 122002 (2009), arXiv:0905.2432 [hep-lat] .
  * Takeda  _et al._ (2011) K. Takeda, S. Aoki, S. Hashimoto, T. Kaneko, J. Noaki, and T. Onogi (JLQCD), Phys. Rev. D 83, 114506 (2011), arXiv:1011.1964 [hep-lat] .
  * Alarcon  _et al._ (2012) J. M. Alarcon, J. Martin Camalich, and J. A. Oller, Phys. Rev. D 85, 051503 (2012), arXiv:1110.3797 [hep-ph] .
  * Durr  _et al._ (2012) S. Durr _et al._ (BMW), Phys. Rev. D 85, 014509 (2012), [Erratum: Phys.Rev.D 93, 039905 (2016)], arXiv:1109.4265 [hep-lat] .
  * Horsley  _et al._ (2012) R. Horsley, Y. Nakamura, H. Perlt, D. Pleiter, P. E. L. Rakow, G. Schierholz, A. Schiller, H. Stuben, F. Winter, and J. M. Zanotti (QCDSF-UKQCD), Phys. Rev. D 85, 034506 (2012), arXiv:1110.4971 [hep-lat] .
  * Bali  _et al._ (2012) G. S. Bali _et al._ (QCDSF), Phys. Rev. D 85, 054502 (2012), arXiv:1111.1600 [hep-lat] .
  * Shanahan  _et al._ (2013) P. E. Shanahan, A. W. Thomas, and R. D. Young, Phys. Rev. D 87, 074503 (2013), arXiv:1205.5365 [nucl-th] .
  * Ohki  _et al._ (2013) H. Ohki, K. Takeda, S. Aoki, S. Hashimoto, T. Kaneko, H. Matsufuru, J. Noaki, and T. Onogi (JLQCD), Phys. Rev. D 87, 034509 (2013), arXiv:1208.4185 [hep-lat] .
  * Gong  _et al._ (2013) M. Gong _et al._ (XQCD), Phys. Rev. D 88, 014503 (2013), arXiv:1304.1194 [hep-ph] .
  * Alvarez-Ruso  _et al._ (2013) L. Alvarez-Ruso, T. Ledwig, J. Martin Camalich, and M. J. Vicente-Vacas, Phys. Rev. D 88, 054507 (2013), arXiv:1304.0483 [hep-ph] .
  * Junnarkar and Walker-Loud (2013) P. Junnarkar and A. Walker-Loud, Phys. Rev. D 87, 114510 (2013), arXiv:1301.1114 [hep-lat] .
  * An and Saghai (2015) C. S. An and B. Saghai, Phys. Rev. D 92, 014002 (2015), arXiv:1404.2389 [hep-ph] .
  * Lutz  _et al._ (2014) M. F. M. Lutz, R. Bavontaweepanya, C. Kobdaj, and K. Schwarz, Phys. Rev. D 90, 054505 (2014), arXiv:1401.7805 [hep-lat] .
  * Ren  _et al._ (2015) X.-L. Ren, L.-S. Geng, and J. Meng, Phys. Rev. D 91, 051502 (2015), arXiv:1404.4799 [hep-ph] .
  * Yang  _et al._ (2016) Y.-B. Yang, A. Alexandru, T. Draper, J. Liang, and K.-F. Liu (xQCD), Phys. Rev. D 94, 054503 (2016), arXiv:1511.09089 [hep-lat] .
  * Hoferichter  _et al._ (2015) M. Hoferichter, J. Ruiz de Elvira, B. Kubis, and U.-G. Meißner, Phys. Rev. Lett. 115, 092301 (2015), arXiv:1506.04142 [hep-ph] .
  * Abdel-Rehim  _et al._ (2016) A. Abdel-Rehim, C. Alexandrou, M. Constantinou, K. Hadjiyiannakou, K. Jansen, C. Kallidonis, G. Koutsou, and A. Vaquero Aviles-Casco (ETM), Phys. Rev. Lett. 116, 252001 (2016), arXiv:1601.01624 [hep-lat] .
  * Ruiz de Elvira  _et al._ (2018) J. Ruiz de Elvira, M. Hoferichter, B. Kubis, and U.-G. Meißner, J. Phys. G 45, 024001 (2018), arXiv:1706.01465 [hep-ph] .
  * Varnhorst (2018) L. Varnhorst (BMW), Nucl. Part. Phys. Proc. 300-302, 107 (2018).
  * Gubler and Ohtani (2014) P. Gubler and K. Ohtani, Phys. Rev. D 90, 094002 (2014), arXiv:1404.7701 [hep-ph] .
  * Ji (1995a) X.-D. Ji, Phys. Rev. Lett. 74, 1071 (1995a), arXiv:hep-ph/9410274 [hep-ph] .
  * Ji (1995b) X.-D. Ji, Phys. Rev. D52, 271 (1995b), arXiv:hep-ph/9502213 [hep-ph] .
  * Ji (2021) X. Ji, Front. Phys. (Beijing) 16, 64601 (2021), arXiv:2102.07830 [hep-ph] .
  * Ji and Liu (2021) X. Ji and Y. Liu, Sci. China Phys. Mech. Astron. 64, 281012 (2021), arXiv:2101.04483 [hep-ph] .
  * Wang  _et al._ (2020) R. Wang, J. Evslin, and X. Chen, Eur. Phys. J. C 80, 507 (2020), arXiv:1912.12040 [hep-ph] .
  * Kou  _et al._ (2022) W. Kou, R. Wang, and X. Chen, Eur. Phys. J. A 58, 155 (2022), arXiv:2103.10017 [hep-ph] .
  * Duran  _et al._ (2023) B. Duran _et al._ , Nature 615, 813 (2023), arXiv:2207.05212 [nucl-ex] .
  * Wang  _et al._ (2022) X.-Y. Wang, J. Bu, and F. Zeng, Phys. Rev. D 106, 094029 (2022), arXiv:2210.01994 [hep-ph] .
  * Kharzeev (1996) D. Kharzeev, Proc. Int. Sch. Phys. Fermi 130, 105 (1996), arXiv:nucl-th/9601029 .
  * Kharzeev  _et al._ (1999) D. Kharzeev, H. Satz, A. Syamtomov, and G. Zinovjev, Eur. Phys. J. C 9, 459 (1999), arXiv:hep-ph/9901375 .
  * Ali  _et al._ (2019) A. Ali _et al._ (GlueX), Phys. Rev. Lett. 123, 072001 (2019), arXiv:1905.10811 [nucl-ex] .
  * Adhikari  _et al._ (2023) S. Adhikari _et al._ (GlueX), Phys. Rev. C 108, 025201 (2023), arXiv:2304.03845 [nucl-ex] .
  * Mamo and Zahed (2020) K. A. Mamo and I. Zahed, Phys. Rev. D 101, 086003 (2020), arXiv:1910.04707 [hep-ph] .
  * Guo  _et al._ (2021) Y. Guo, X. Ji, and Y. Liu, Phys. Rev. D 103, 096010 (2021), arXiv:2103.11506 [hep-ph] .
  * Peskin (1979) M. E. Peskin, Nucl. Phys. B 156, 365 (1979).
  * Deur  _et al._ (2016) A. Deur, S. J. Brodsky, and G. F. de Teramond, Nucl. Phys. 90, 1 (2016), arXiv:1604.08082 [hep-ph] .
  * Deur  _et al._ (2023) A. Deur, S. J. Brodsky, and C. D. Roberts, (2023), arXiv:2303.00723 [hep-ph] .
  * Eadie  _et al._ (1971) W. T. Eadie, D. Drijard, F. E. James, M. Roos, and B. Sadoulet,  _Statistical methods in experimental physics; 1st ed._ (North-Holland, Amsterdam, 1971).
  * Accardi  _et al._ (2016) A. Accardi _et al._ , Eur. Phys. J. A 52, 268 (2016), arXiv:1212.1701 [nucl-ex] .
  * Abdul Khalek  _et al._ (2022) R. Abdul Khalek _et al._ , Nucl. Phys. A 1026, 122447 (2022), arXiv:2103.05419 [physics.ins-det] .
  * Chen (2018) X. Chen, PoS DIS2018, 170 (2018), arXiv:1809.00448 [nucl-ex] .
  * Chen  _et al._ (2020) X. Chen, F.-K. Guo, C. D. Roberts, and R. Wang, Few Body Syst. 61, 43 (2020), arXiv:2008.00102 [hep-ph] .
  * Anderle  _et al._ (2021) D. P. Anderle _et al._ , Front. Phys. (Beijing) 16, 64701 (2021), arXiv:2102.09222 [nucl-ex] .


# Pricing strategies for viral marketing on Social Networks

David Arthur 111Department of Computer Science, Stanford University Rajeev
Motwani ††footnotemark:  Aneesh Sharma222Institute for Computational and
Mathematical Engineering, Stanford University Ying Xu333Work done when author
was a student at the Department of Computer Science, Stanford University
<EMAIL_ADDRESS>
###### Abstract

We study the use of viral marketing strategies on social networks to maximize
revenue from the sale of a single product. We propose a model in which the
decision of a buyer to buy the product is influenced by friends that own the
product and the price at which the product is offered. The influence model we
analyze is quite general, naturally extending both the Linear Threshold model
and the Independent Cascade model, while also incorporating price information.
We consider sales proceeding in a cascading manner through the network, i.e. a
buyer is offered the product via recommendations from its neighbors who own
the product. In this setting, the seller influences events by offering a
cashback to recommenders and by setting prices (via coupons or discounts) for
each buyer in the social network.

Finding a seller strategy which maximizes the expected revenue in this setting
turns out to be NP-hard. However, we propose a seller strategy that generates
revenue guaranteed to be within a constant factor of the optimal strategy in a
wide variety of models. The strategy is based on an influence-and-exploit
idea, and it consists of finding the right trade-off at each time step
between: generating revenue from the current user versus offering the product
for free and using the influence generated from this sale later in the
process. We also show how local search can be used to improve the performance
of this technique in practice.

##  1 Introduction

Social networks such as Facebook, Orkut and MySpace are free to join, and they
attract vast numbers of users. Maintaining these websites for such a large
group of users requires substantial investment from the host companies. To
help recoup these investments, these companies often turn to monetizing the
information that their users provide for free on these websites. This
information includes both detailed profiles of users and also the network of
social connections between the users. Not surprisingly, there is a widespread
belief that this information could be a gold mine for targeted advertising and
other online businesses. Nonetheless, much of this potential still remains
untapped today. Facebook, for example, was valued at $15 billion by Microsoft
in 2007 [13], but its estimated revenue in 2008 was only $300 million [17].
With so many users and so much data, higher profits seem like they should be
possible. Facebook’s Beacon advertising system does attempt to provide
targeted advertisements but it has only obtained limited success due to
privacy concerns [16].

This raises the question of how companies can better monetize the already
public data on social networks without requiring extra information and thereby
compromising privacy. In particular, most large-scale monetization
technologies currently used on social networks are modeled on the sponsored
search paradigm of contextual advertising and do not effectively leverage the
networked nature of the data.

Recently, however, people have begun to consider a different monetization
approach that is based on selling products through the spread of influence.
Often, users can be convinced to purchase a product if many of their friends
are already using it, even if these same users would be hard to convince
through direct advertising. This is often a result of personal recommendations
– a friend’s opinion can carry far more weight than an impersonal
advertisement. In some cases, however, adoption among friends is important for
even more practical reasons. For example, instant messenger users and cell
phone users will want a product that allows them to talk easily and cheaply
with their friends. Usually, this encourages them to adopt the same instant
messenger program and the same cell phone carrier that their friends have. We
refer the reader to previous work and the references therein for further
explanations behind the motivation of the influence model [6, 4].

In fact, many sellers already do try to utilize influence-and-exploit
strategies that are based on these tendencies. In the advertising world, this
has recently led to the adoption of viral marketing, where a seller attempts
to artificially create word-of-mouth advertising among potential customers [8,
9, 14]. A more powerful but riskier technique has been in use much longer: the
seller gives out free samples or coupons to a limited set of people, hoping to
convince these people to try out the product and then recommend it to their
friends. Without any extra data, however, this forces sellers to make some
very difficult decisions. Who do they give the free samples to? How many free
samples do they need to give out? What incentives can they afford to give to
recommenders without jeopardizing the overall profit too much?

In this paper, we are interested in finding systematic answers to these
questions. In general terms, we can model the spread of a product as a process
on a social network. Each node represents a single person, and each edge
represents a friendship. Initially, one or more nodes is “active”, meaning
that person already has the product. This could either be a large set of nodes
representing an established customer base, or it could be just one node – the
seller – whose neighbors consist of people who independently trust the seller,
or who are otherwise likely to be interested in early adoption.

At this point, the seller can encourage the spread of influences in two ways.
First of all, it can offer cashback rewards to individuals who recommend the
product to their friends. This is often seen in practice with “referral
bonuses” – each buyer can optionally name the person who referred them, and
this person then receives a cash reward. This gives existing buyers an
incentive to recommend the product to their friends. Secondly, a seller can
offer discounts to specific people in order to encourage them to buy the
product, above and beyond any recommendations they receive. It is important to
choose a good discount from the beginning here. If the price is not acceptable
when a prospective buyer first receives recommendations, they might not bother
to reconsider even if the price is lowered later.

After receiving discount offers and some set of recommendations, it is up to
the prospective buyers to decide whether to actually go through with a
purchase. In general, they will do so with some probability that is influenced
by the discount and by the set of recommendations they have received. The form
of this probability is a parameter of the model and it is determined by
external factors, for instance, the quality of the product and various
exogenous market conditions. While it is impossible for a seller to calculate
the form of these probability exactly, they can estimate it from empirical
observations, and use that estimate to inform their policies. One could
interpret the probabilities according to a number of different models that
have been proposed in the literature (for instance, the Independent Cascade
and Linear Threshold models), and hence it is desirable for the seller to be
able to come up with a strategy that is applicable to a wide variety of
models.

Now let us suppose that a seller has access to data from a social network such
as Facebook, Orkut, or MySpace. Using this, the seller can estimate what the
real, true, underlying friendship structure is, and while this estimate will
not be perfect, it is getting better over time, and any information is better
than none. With this information in hand, a seller can model the spread of
influence quite accurately, and the formerly inscrutable problems of who to
offer discounts to, and at what price, become algorithmic questions that one
can legitimately hope to solve. For example, if a seller knows the structure
of the network, she can locate individuals that are particularly well
connected and do everything possible to ensure they adopt the product and
exert their considerable influence.

In this paper, we are interested in the algorithmic side of this question:
Given the network structure and a model of the purchase probabilities, how
should the seller decide to offer discounts and cashback rewards?

###  1.1 Our contributions

We investigate seller strategies that address the above questions in the
context of expected revenue maximization. We will focus much of our attention
on non-adaptive strategies for the seller: the seller chooses and commits to a
discount coupon and cashback offer for each potential buyer before the cascade
starts. If a recommendation is given to this node at any time, the price
offered will be the one that the seller committed to initially, irrespective
of the current state of the cascade.

A wider class of strategies that one could consider are adaptive strategies,
which do not have this restriction. For example, in an adaptive strategy, the
seller could choose to observe the outcome of the (random) cascading process
up until the last minute before making very well informed pricing decisions
for each node. One might imagine that this additional flexibility could allow
for potentially large improvements over non-adaptive strategies.
Unfortunately, there is a price to be paid, in that good adaptive strategies
are likely to be very complicated, and thus difficult and expensive to
implement. The ratio of the revenue generated from the optimal adaptive
strategy to the revenue generated from the optimal non-adaptive strategy is
termed the “adaptivity gap”.

Our main theoretical contribution is a very efficient non-adaptive strategy
whose expected revenue is within a constant factor of the optimal revenue from
an adaptive strategy. This guarantee holds for a wide variety of probability
functions, including natural extensions of both the Linear Threshold and
Independent Cascade models444More precisely, the strategy achieves a constant-
factor approximation for any fixed model, independent of the social network.
If one changes the model, the approximation factor does vary, as made precise
in Section 3.. Note that a surprising consequence of this result is that the
adaptivity gap is constant, so one can make the case that not much is lost by
restricting our attention to non-adaptive policies. We also show that the
problem of finding an optimal non-adaptive strategy is NP-hard, which means an
efficient approximation algorithm is the best theoretical result that one
could hope for.

Intuitively, the seller strategy we propose is based on an influence-and-
exploit idea, and it consists of categorizing each potential buyer as either
an influencer or a revenue source. The influencers are offered the product for
free and the revenue sources are offered the product at a pre-determined
price, chosen based on the exact probability model. Briefly, the
categorization is done by finding a spanning tree of the social network with
as many leaves as possible, and then marking the leaves as revenue sources and
the internal nodes as influencers. We can find such a tree in near-linear time
[7, 10]. Cashback amounts are chosen to be a fixed fraction of the total
revenue expected from this process. The full details are presented in section
3.

In practice, we propose using this approach to find a strategy that has good
global properties, and then using local search to improve it further. This
kind of combination has been effective in the past, for example on the k-means
problem [1]. Indeed, experiments (see section 4) show that combining local
search with the above influence-and-exploit strategy is more effective than
using either approach on its own.

###  1.2 Related work

The problem of social contagion or spread of influence was first formulated by
the sociological community, and introduced to the computer science community
by Domingos and Richardson [2]. An influential paper by Kempe, Kleinberg and
Tardos [5] solved the target set selection problem posed by [2] and sparked
interest in this area from a theoretical perspective (see [6]). This work has
mostly been limited to the influence maximization paradigm, where influence
has been taken to be a proxy for the revenue generated through a sale.
Although similar to our work in spirit, there is no notion of price in this
model, and therefore, our central problem of setting prices to encourage
influence spread requires a more complicated model.

A recent work by Hartline, Mirrokni and Sundararajan [4] is similar in flavor
to our work, and also considers extending social contagion ideas with pricing
information, but the model they examine differs from our model in a several
aspects. The main difference is that they assume that the seller is allowed to
approach arbitrary nodes in the network at any time and offer their product at
a price chosen by the seller, while in our model the cascade of
recommendations determines the timing of an offer and this cannot be directly
manipulated. In essence, the model proposed in [4] is akin to advertising the
product to arbitrary nodes, bypassing the network structure to encourage a
desired set of early adopters. Our model restricts such direct advertising as
it is likely to be much less effective than a direct recommendation from a
friend, especially when the recommender has an incentive to convince the
potential buyer to purchase the product (for instance, the recommender might
personalize the recommendation, increasing its effectiveness). Despite the
different models, the algorithms proposed by us and [4] are similar in spirit
and are based on an influence-and-exploit strategy.

This work has also been inspired by a direction mentioned by Kleinberg [6],
and is our interpretation of the informal problem posed there. Finally, we
point out that the idea of cashbacks has been implemented in practice, and new
retailers are also embracing the idea [8, 9, 14]. We note that some of the
systems being implemented by retailers are quite close to the model that we
propose, and hence this problem is relevant in practice.

##  2 The Formal Model

Let us start by formalizing the setting stated above. We represent the social
network as an undirected graph $G(V,E)$, and denote the initial set of
adopters by $S^{0}\subseteq V$. We also denote the active set at time $t$ by
$S^{t-1}$ (we call a node active if it has purchased the product and inactive
otherwise). Given this setting, the recommendations cascade through the
network as follows: at each time step $t\geq 1$, the nodes that became active
at time $t-1$ (i.e. $S^{0}$ for $t=1$, and $u\in S^{t-1}\setminus S^{t-2}$ for
$t\geq 2$) send recommendations to their currently inactive friends in the
network: $N^{t-1}=\\{v\in V\setminus S^{t-1}|(u,v)\in E,u\in S^{t-1}\setminus
S^{t-2}\\}$. Each such node $v\in N^{t-1}$ is also given a price
$c_{v,t}\in\mathbb{R}$ at which it can purchase the product. This price is
chosen by the seller to either be full price or some discounted fraction
thereof.

The node $v$ must then decide whether to purchase the product or not (we
discuss this aspect in the next section). If $v$ does accept the offer, a
fixed cashback $r>0$ is given to a recommender $u\in S^{t-1}$ (note that we
are fixing the cashback to be a positive constant for all the nodes as the
nodes are assumed to be non-strategic and any positive cashback provides
incentive for them to provide recommendations). If there are multiple
recommenders, the buyer must choose only one of them to receive the cashback;
this is a system that is quite standard in practice. In this way, offers are
made to all nodes $v\in N^{t-1}$ through the recommendations at time $t$ and
these nodes make a decision at the end of this time period. The set of active
nodes is then updated and the same process is repeated until the process
quiesces, which it must do in finite time since any step with no purchases
ends the process.

In the model described above, the only degree of freedom that the seller has
is in choosing the prices and the cashback amounts. It wants to do this in a
way that maximizes its own expected revenue (the expectation is over
randomness in the buyer strategies). Since the seller may not have any control
over the seed set, we are looking for a strategy that can maximize the
expected revenue starting from any seed set on any graph. In most online
scenarios, producing extra copies of the product has negligible cost, so
maximizing expected revenue will also maximize expected profit.

Now we can formally state the problem of finding a revenue maximizing strategy
as follows:

######  Problem 1.

Given a connected undirected graph $G(V,E)$, a seed set $S^{0}$, a fixed
cashback amount $r$, and a model M for determining when nodes will purchase a
product, find a strategy that maximizes the expected revenue from the
cascading process described above.

We are particularly interested in non-adaptive policies, which correspond to
choosing a price for each node in advance, making the price independent of the
time of the recommendation and the state of the cascade at the time of the
offer. Our goal will be threefold: (1) to show that this problem is NP-hard
even for simple models M, (2) to construct a constant-factor approximation
algorithm for a wide variety of models, and (3) to show that restricting to
non-adaptive policies results in at most a constant factor loss of profit.

To simplify the exposition, we will assume the cashback $r=0$ for now. At the
end of Section 4, we will show how the results can be generalized to work for
positive $r$, which should be sufficient incentive for buyers to pass on
recommendations.

###  2.1 Buyer decisions

In this section, we discuss how to model the probability that a node will
actually buy the product given a set of recommendations and a price. We use a
very general model in this work that naturally extends the most popular
traditional models proposed in the influence maximization literature,
including both Independent Cascade and Linear Threshold.

Consider an abstract model M for determining the probability that a node will
buy a product given a price and what recommendations it has received. We allow
M to take on virtually any form, imposing only the following conditions:

  1. 1.

The seller has full information about M. This is a standard assumption, and it
can be approximated in practice by running experiments and observing people’s
behavior.

  2. 2.

A node will never pay more than full price for the product (we assume this
full price is 1 without loss of generality). Without an assumption like this,
the seller could potentially achieve unbounded revenue on a single network,
which makes the problem degenerate.

  3. 3.

A node will always accept the product and recommend it to friends if it
receives a recommendation with price 0 (i.e. if a friend offers the product
for free). Since nodes are given positive cash rewards for making
recommendations, this condition is true for any rational buyer.

  4. 4.

If the social network is a single line graph with $S^{0}$ being the two
endpoints, the maximum expected revenue is at most a constant $L$.
Intuitively, this states that each prospective buyer on a social network
should have some chance of rejecting the product (unless it’s given to them
for free), and therefore the maximum revenue on a line is bounded by a
geometric series, and is therefore constant.

  5. 5.

There exist constants $f$, $c$, $q$ so that if more than fraction $f$ of a
given node’s neighbors recommend the product to the node at cost $c$, the node
will purchase the product with probability $q$. This rules out extreme
inertia, for example the case where no buyer will consider purchasing a
product unless almost all of its neighbors have already done so.

The fourth and fifth conditions here are used to parametrize how complicated
the model is, and our final approximation bound will be in terms of this model
“complexity”, which is defined to be $\frac{L}{(1-f)cq}$. While it may not be
obvious that all these conditions are met in general, we will show that they
are for both the Independent Cascade and Linear Threshold models, and indeed,
the arguments there extend naturally to many other cases as well.

In the traditional Independent Cascade model, there is a fixed probability $p$
that a node will purchase a product each time it is recommended to them. These
decisions are made independently for each recommendation, but each node will
buy the product at most once.

To generalize this to multiple prices, it is natural to make $p$ a function
$[0,1]\rightarrow[0,1]$ where $p(x)$ represents the probability that a node
will buy the product at price $x$. For technical reasons, however, it is
convenient to work with the inverse of $p$, which we call $C$.555It is
sometimes useful to consider functions $p(\cdot)$ that are not one-to-one.
These functions have no formal inverse, but in this case, $c$ can still be
formally defined as $C(x)=\max_{y}|p(y)|\geq x$. Our general conditions on the
model reduce to setting $C(0)=1$ and $C(1)=0$ in this case. To ensure bounded
complexity, we also impose a minor smoothness condition.

######  Definition 1.

Fix a cost function $C:[0,1]\rightarrow[0,1]$ with $C(0)=1,C(1)=0$ and with
$C$ differentiable at 0 and 1. We define the Independent Cascade Model ICMc as
follows:
Every time a node receives a recommendation at price $C(x)$, it buys the
product with probability $x$ and does nothing otherwise. If a node receives
multiple recommendations, it performs this check independently for each
recommendation but it never purchases the product more than once.

######  Lemma 1.

Fix a cost function $C$. Then:

  1. 1.

ICMC has bounded (model) complexity.

  2. 2.

If $C$ has maximum slope $m$ (i.e. $|C(x)-C(y)|\leq m|x-y|$ for all $x,y$),
then $ICM_{C}$ has $O(m^{2})$ complexity.

  3. 3.

If $C$ is a step function with $n$ regularly spaced steps (i.e. $C(x)=C(y)$ if
$\lfloor\frac{x}{n}\rfloor=\lfloor\frac{y}{n}\rfloor$), then ICMC has
$O(n^{2})$ complexity.

###### Proof.

We show that the complexity of ICMC can be bounded in terms of the maximum
slope of $C$ near 0 and 1. Recall that if $C$ is differentiable at 0, then, by
definition, there exists $\epsilon>0$ so that
$\frac{|C(x)-C(0)|}{x}\leq|C^{\prime}(0)|+1$ for $x<\epsilon$. A similar
argument can be made for $x=1$, and thus we can say formally that there exist
$m$ and $\epsilon>0$ such that:

$\displaystyle C(x)\geq 1-mx$ $\displaystyle\textrm{ for
}x\leq\epsilon,\textrm{and}$ $\displaystyle C(x)\leq m(1-x)$
$\displaystyle\textrm{ for }x\geq 1-\epsilon.$

In this case, we will show that ICMC has complexity at most
$8\max(\frac{1}{\epsilon},m)^{2}$, proving part 1. Note that parts 2 and 3 of
the lemma will also follow immediately.

We begin by analyzing $L_{n}$, the maximum expected revenue that can be
achieved on a path of length $n$ if one of the endpoints is a seed. Note that
$L\leq 2\max_{n}L_{n}$ since selling a product on a line graph with two seeds
can be thought of as two independent sales, each with one seed, that are cut
short if the sales ever meet. Now we have:

$\displaystyle L_{n}=\max_{x}x(C(x)+L_{n-1}).$

This is because offering the product at cost $C(x)$ will lead to a purchase
with probability $x$, and in that case, we get $C(x)$ revenue immediately and
$L_{n-1}$ expected revenue in the future. Since $L_{n}$ is obviously
increasing in $n$, this can be simplified further:

$\displaystyle L_{n}\leq\max_{x}x(C(x)+L_{n})$ $\displaystyle\implies$
$\displaystyle L\leq 2L_{n}\leq\max_{0<x<1}\frac{2x\cdot C(x)}{1-x}$

For $x\geq 1-\epsilon$, we have $\frac{2x\cdot C(x)}{1-x}\leq\frac{2x\cdot
m(1-x)}{1-x}\leq 2m$, and for $x<1-\epsilon$, we have $\frac{2x\cdot
C(x)}{1-x}\leq\frac{2}{\epsilon}$. Either way, $L\leq
2\max(\frac{1}{\epsilon},m)$.

It remains to choose $f,c$ and $q$ as per the first complexity condition. We
use $f=0$, $q=\min(\epsilon,\frac{1}{2m})$ and $c=C(q)\geq\frac{1}{2}$.
Indeed, if a node has more than 0 active neighbors, it will accept a
recommendation at cost $C(q)$ with probability $q$.

Thus ICMc has complexity at most $\frac{L}{(1-f)cq}\leq
8\max(\frac{1}{\epsilon},m)^{2}$, as required. ∎

In the traditional Linear Threshold model, there are fixed influences
$b_{v,w}$ on each directed edge $(v,w)$ in the network. Each node
independently chooses a threshold $\theta$ uniformly at random from $[0,1]$,
and then purchases the product if and when the total influence on it from
nodes that have recommended the product exceeds $\theta$.

To generalize this to multiple prices, it is natural to make $b_{v,w}$ a
function $[0,1]\rightarrow[0,1]$ where $b_{v,w}(x)$ indicates the influence
$v$ exerts on $w$ as a result of recommending the product at price $x$. To
simplify the exposition, we will focus on the case where a node is equally
influenced by all its neighbors. (This is not strictly necessary but removing
this assumptions requires rephrasing the definition of $f$ to be a weighted
fraction of a node’s neighbors.) Finally, we assume for all $v,w$ that
$b_{v,w}(0)=1$ to satisfy the second general condition for models.

######  Definition 2.

Fix a max influence function $B:(0,1]\rightarrow[0,1]$, not uniformly 0. We
define the Linear Threshold Model LTMB as follows:
Every node independently chose a threshold $\theta$ uniformly at random from
$[0,1]$. A node will buy the product at price $x>0$ only if
$B(x)\geq\frac{\alpha}{\theta}$ where $\alpha$ denotes the fraction of the
node’s neighbors that have recommended the product. A node will always accept
a recommendation if the product is offered for free.

######  Lemma 2.

Fix a max influence function $B$ and let $K=\max_{x}x\cdot B(x)$. Then LTMB
has complexity $O(\frac{1}{K})$.

We omit the proof since it is similar to that of Lemma 1. In fact, it is
simpler since, on a line graph, a node either gets the product for free or it
has probability at most $\frac{1}{2}$ of buying the product and passing on a
recommendation.

##  3 Approximating the Optimal Revenue

In this section, we present our main theoretical contribution: a non-adaptive
seller strategy that achieves expected revenue within a constant factor of the
revenue from the optimal adaptive strategy. We show the problem of finding the
exact optimal strategy is NP-hard (see section 8.1 in the appendix), so this
kind of result is the best we can hope for. Note that our approximation
guarantee is against the strongest possible optimum, which is perhaps
surprising: it is unclear a priori whether such a strategy should even exist.

The strategy we propose is based on computing a maximum-leaf spanning tree
(MAXLEAF) of the underlying social network graph, i.e., computing a spanning
tree of the graph with the maximum number of leaf nodes. The MAXLEAF problem
is known to be NP-Hard, and it is in fact also MAX SNP-Complete, but there are
several constant-factor approximation algorithms known for the problem [3, 7,
10, 15]. In particular, one of these is nearly linear-time [10], making it
practical to apply on large online social network graphs. The seller strategy
we attain through this is an influence-and-exploit strategy that offers the
product to all of the interior nodes of the spanning tree for free, and
charges a fixed price from the leaves. Note that this strategy works for all
the buyer decision models discussed above, including multi-price
generalizations of both Independent Cascade and Linear Threshold.

We consider the setting of Problem 1, where we are given an undirected social
network graph $G(V,E)$, a seed set $S^{0}\subseteq V$ and a buyer decision
model M. Throughout this section, we will let $L$, $f$, $c$ and $q$ denote the
quantities that parametrize the model complexity, as described in Section 2.1.
To simplify the exposition, we will assume for now that the seed set is a
singleton node (i.e., $|S^{0}|=1$). If this is not the case, the seed nodes
can be merged into a single node, and we can make much the same argument in
that case. We will ignore cashbacks for now, and return to address them at the
end of the section.

The exact algorithm we will use is stated below:

  * •

Use the MAXLEAF algorithm [10] to compute an approximate max-leaf spanning
tree $T$ for $G$ that is rooted at $S_{0}$.

  * •

Offer the product to each internal node of $T$ for free.

  * •

For each leaf of $T$ (excluding $S_{0}$), independently flip a biased coin.
With probability $\frac{1+f}{2}$, offer the product to the node for free. With
probability $\frac{1-f}{2}$, offer the product to the node at cost $c$.

We henceforth refer to this strategy as STRATEGYMAXLEAF.

Our analysis will revolve around what we term as “good” vertices, defined
formally as follows:

######  Definition 3.

Given a graph $G(V,E)$, we define the good vertices to be the vertices with
degree at least 3 and their neighbors.

On the one hand, we show that if $G$ has $g$ good vertices, then the MAXLEAF
algorithm will find a spanning tree with $\Omega(g)$ leaves. We then show that
each leaf of this tree leads to $\Omega(1)$ revenue, implying STRATEGYMAXLEAF
gives $\Omega(g)$ revenue overall. Conversely, we can decompose $G$ into at
most $g$ line-graphs joining high-degree vertices, and the total revenue from
these is bounded by $gL=O(g)$ for all policies, which gives the constant-
factor approximation we need.

We begin by bounding the number of leaves in a max-leaf spanning tree. For
dense graphs, we can rely on the following fact [7, 10]:

######  Fact 1.

The max-leaf spanning tree of a graph with minimum degree at least 3 has at
least $n/4+2$ leaves [7, 10].

In general graphs, we cannot apply this result directly. However, we can make
any graph have minimum degree 3 by replacing degree-1 vertices with small,
complete graphs and by contracting along edges to remove degree-2 vertices. We
can then apply Fact 1 to analyze this auxiliary graph, which leads to the
following result:

######  Lemma 3.

Suppose a connected graph $G$ has $n_{3}$ vertices with degree at least $3$.
Then $G$ has a spanning tree with at least $\frac{n_{3}}{8}+1$ leaves.

###### Proof.

Let $n_{1}$ and $n_{2}$ denote the number of vertices of degree 1 and 2
respectively, and let $M$ denote the number of leaves in a max-leaf spanning
tree of $G$. If $n_{1}=n_{2}=0$, the result follows from Fact 1.

Now, suppose $n_{2}=0$ but $n_{1}>0$. Clearly, every spanning tree has at
least $n_{1}$ leaves, so the result is obvious if
$n_{1}\geq\frac{n_{3}}{8}+1$. Otherwise, we replace each degree-1 vertex with
a copy of $K_{4}$ (the complete graph on 4 vertices), one of whose vertices
connects back to the rest of the graph. Let $G^{\prime}$ denote the resulting
graph. Then $G^{\prime}$ has $4n_{1}+n_{3}$ vertices, and they are all at
least degree 3, so $G^{\prime}$ has a spanning tree $T^{\prime}$ with at least
$n_{1}+\frac{n_{3}}{4}+2$ leaves.

We can transform this into a spanning tree $T$ on $G$ by contracting each copy
of $K_{4}$ down to a single point. Each contraction could transform up to 3
leaves into a single leaf, but it will not affect other leaves. Since there
are exactly $n_{1}$ contractions that need to be done altogether, $T$ has at
least $n_{1}+\frac{n_{3}}{4}+2-2n_{1}\geq\frac{n_{3}}{8}+1$ leaves, as
required.

We now prove the result holds in general by induction on $n_{2}$. We have
already shown the base case $(n_{2}=0)$. For the inductive step, we will
define an auxiliary graph $G^{\prime}$ with $n_{2}^{\prime},n_{3}^{\prime}$
and $M^{\prime}$ defined as for $G$. We will then show
$n_{2}^{\prime}<n_{2},n_{3}^{\prime}\geq n_{3}$, and for every spanning tree
$T^{\prime}$ on $G^{\prime}$, there is a spanning tree $T$ on $G$ with at
least as many leaves. This implies $M^{\prime}\leq M$, and using the inductive
hypothesis, it follows that $M\geq
M^{\prime}\geq\frac{n_{3}^{\prime}}{8}+1\geq\frac{n_{3}}{8}+1$, which will
complete the proof.

Towards that end, suppose $v$ is a degree-2 vertex in $G$, and let its
neighbors be $u$ and $w$. If $u$ and $w$ are not adjacent, we let $G^{\prime}$
be the graph attained by contracting along the edge $(u,v)$. Then
$n_{2}^{\prime}=n_{2}-1$ and $n_{3}^{\prime}=n_{3}$. Any spanning tree
$T^{\prime}$ on $G^{\prime}$ can be extended back to a spanning tree $T$ on
$G$ by uncontracting the edge $(u,v)$ and adding it to $T$. This does not
decrease the number of leaves in the tree, so we are done.

Next, suppose instead that $u$ and $w$ are adjacent. We cannot contract
$(u,v)$ here since it will create a duplicate edge in $G^{\prime}$. However, a
different construction can be used. If the entire graph is just these 3
vertices, the lemma is trivial. Otherwise, let $G^{\prime}$ be the graph
attained by adding a degree-1 vertex $x$ adjacent to $v$. Then
$n_{2}^{\prime}=n_{2}-1$ and $n_{3}^{\prime}=n_{3}+1$. Now consider a spanning
tree $T^{\prime}$ of $G^{\prime}$. We can transform this into a spanning tree
$T$ on $G$ by removing the edge $(v,x)$ that must be in $T^{\prime}$. This
removes the leaf $x$ but if $v$ has degree 2 in $T^{\prime}$, it makes $v$ a
leaf. In this case, $T$ and $T^{\prime}$ have the same number of leaves, so we
are done.

Otherwise, $(u,v)$ and $(v,w)$ are also in $T^{\prime}$, and since $G$ was
assumed to have more than 3 vertices, $u$ and $w$ cannot both be leaves in
$T^{\prime}$. Assume without loss of generality that $u$ is not a leaf. We
then further modify $T$ by replacing $(v,w)$ with $(u,w)$. Now, $v$ is a leaf
in $T$ and the only vertex whose degree has changed is $u$, which is not a
leaf in either $T$ or $T^{\prime}$. Therefore, $T$ and $T^{\prime}$ again have
the same number of leaves, and we are once again done.

The result now follows from induction, as discussed above. ∎

We must further extend this to be in terms of the number of good vertices $g$,
rather than being in terms of $n_{3}$:

######  Lemma 4.

Given an undirected graph $G$ with $g$ good vertices, the MAXLEAF algorithm
[10] will construct a spanning tree with $\max(\frac{g}{50}+0.5,2)$ leaves.

###### Proof.

If $g=0$, the result is trivial. Otherwise, let $n_{3}$ denote the number of
vertices in $G$ with degree at least 3, and let $M$ denote the number of
leaves in a max-leaf spanning tree of $G$. By Lemma 3, we know
$M\geq\frac{n_{3}}{8}+1$.

Now consider constructing a spanning tree as follows:

  * 1.

Let $A$ denote the set of vertices in $G$ with degree at least 3.

  * 2.

Set $T$ to be a minimal subtree of $G$ that connects all vertices in $A$.

  * 3.

Add all remaining vertices in $G$ to $T$ one at a time. If a vertex $v$ could
be connected to $T$ in multiple ways, connect it to a vertex in $A$ if
possible.

To analyze this, note that $G-A$ can be decomposed into a collection of
“primitive” paths. Given a primitive path $P$, let $g_{P}$ denote the number
of good vertices on $P$ and let $l_{P}$ denote the number of leaves $T$ has on
$P$.

In Step 2 of the algorithm above, exactly $n_{3}-1$ of these paths are added
to $T$. For each such path $P$, we have $g_{P}\leq 2$ and $l_{P}=0$. On the
remaining paths, we have $g_{P}=l_{P}$. Therefore, the total number of leaves
on $T$ is at least

$\displaystyle\sum_{P}l_{P}=(g-n_{3})+\sum_{P}(l_{P}-g_{P})$
$\displaystyle\geq$ $\displaystyle(g-n_{3})-2(n_{3}-1).$

Thus,

$\displaystyle M$ $\displaystyle\geq$
$\displaystyle\max\left(\frac{n_{3}}{8}+1,g-3n_{3}+1\right)$
$\displaystyle\geq$
$\displaystyle\frac{24}{25}\cdot\left(\frac{n_{3}}{8}+1\right)+\frac{1}{25}\cdot(g-3n_{3}+1)=\frac{g}{25}+1$

The result now follows from the fact that the MAXLEAF algorithm gives a
2-approximation for the max-leaf spanning tree, and that every non-degenerate
tree has at least two leaves. ∎

We can now use this to prove a guarantee on the performance of STRATEGYMAXLEAF
in terms of the number of good vertices on an arbitrary graph:

######  Lemma 5.

Given a social network $G$ with $g$ good vertices, STRATEGYMAXLEAF guarantees
an expected revenue of $\Omega((1-f)cq\cdot g)$.

###### Proof.

Let $T$ denote the spanning tree found by the MAXLEAF algorithm. Let $U$
denote the set of interior nodes of $T$, and let $V$ denote the leaves of $T$
(excluding $S_{0}$). Since we assumed $|S_{0}|=1$, Lemma 4 guarantees
$|V|\geq\max(\frac{g}{50}-0.5,1)=\Omega(g)$.

Note every vertex can be reached from $S_{0}$ by passing through nodes in $U$,
each of which is offered the product for free. These nodes are guaranteed to
accept the product, and therefore, they will collectively pass on at least one
recommendation to each vertex.

Now consider the expected revenue from a vertex $v\in V$. Let $M$ be the
random variable giving the fraction of $v$’s neighbors in $V$ that were not
offered the product for free. We know $E[M]=\frac{1-f}{2}$, so with
probability $\frac{1}{2}$, we have $M\leq 1-f$.

In this case, $v$ is guaranteed to receive recommendations from a fraction $f$
of its neighbors in $V$, as well as all of its neighbors in $U\cup S_{0}$ (of
which there is at least 1). If we charge $v$ a total of $c$ for the product,
it will then purchase the product with probability at least $q$, by the
original definitions of $f$, $c$ and $q$. Furthermore, independent of $v$’s
neighbors, we will ask this price from $v$ with probability $\frac{1-f}{2}$.
Therefore, our expected revenue from $v$ is at least $\frac{1}{2}\cdot
q\cdot\frac{1-f}{2}\cdot c$.

The result now follows from linearity of expectation. ∎

Now that we have computed the expected revenue from STRATEGYMAXLEAF, we need
to characterize the optimal revenue to bound the approximation ratio. This
bound is given by the following lemma.

######  Lemma 6.

The maximum expected revenue achievable by any strategy (adaptive or not) on a
social network $G$ with $g$ good vertices is $O(L\cdot g)$.

###### Proof.

Let $A$ denote the set of vertices in $G$ with degree at least 3, and let
$n_{3}=|A|$. Clearly, no strategy can achieve more than $n_{3}$ revenue
directly from the nodes in $A$.

As observed in the proof of Lemma 4, however, $G-A$ can be decomposed into a
collection of primitive paths. Since each primitive path contains at least one
unique good vertex with degree less than 3, there is at most $g-n_{3}$ such
paths. Even if each endpoint of a path is guaranteed to recommend the product,
the total revenue from the path is at most $L$.

Therefore, the total revenue from any strategy on such a graph is at most
$n_{3}+(g-n_{3})L=O(L\cdot g)$. ∎

Now, we can combine the above lemmas to state the main theorem of the paper,
which states that STRATEGYMAXLEAF provides a constant factor approximation
guarantee for the revenue.

######  Theorem 1.

Let $K$ denote the complexity of our buyer decision model M. Then, the
expected revenue generated by STRATEGYMAXLEAF on an arbitrary social network
is $O(K)$-competitive with the expected revenue generated by the optimal
(adaptive or not) strategy.

###### Proof.

This follows immediately from Lemmas 5 and 6, as well as the fact that
$K=\frac{L}{(1-f)cq}$. ∎

As a corollary, we get the fact that the adaptivity gap is also constant:

######  Corollary 1.

Let $K$ denote the complexity of our buyer decision model M. Then the
adaptivity gap is $O(K)$.

Now we briefly address the issue of cashbacks that were ignored in this
exposition. We set the cashback $r$ to be a small fraction of our expected
revenue from each individual $r_{0}$, i.e. $r=z\cdot r_{0}$, where $z<1$.
Then, our total profit will be $n\cdot r_{0}\cdot(1-z)$. Adding this cashback
decreases our total profit by a constant factor that depends on $z$, but
otherwise the argument now carries through as before, and nodes now have a
positive incentive to pass on recommendations.

In light of Corollary 1, one might ask whether the adaptivity gap is not just
1. In other words, is there any benefit at all to be gained from using non-
adaptive strategies? In fact, there is. For example, consider a social network
consisting of 4 nodes $\\{v_{1},v_{2},v_{3},v_{4}\\}$ in a cycle, with $v_{3}$
connected to two other isolated vertices. Suppose furthermore that a node will
accept a recommendation with probability 0.5 unless the price is 0, in which
case the node will accept it with probability 1. On this network, with seed
set $S^{0}=\\{v_{1}\\}$, the optimal adaptive strategy is to always demand
full price unless exactly one of $v_{2}$ and $v_{4}$ purchases the product
initially, in which case $v_{3}$ should be offered the product for free. This
beats the optimal non-adaptive strategy by a factor of 1.0625.

##  4 Local Search

In this section, we discuss how an arbitrary seller strategy can be tweaked by
the use of a local search algorithm. Taken on its own, this technique can
sometimes be problematic since it can take a long time to converge to a good
strategy. However, it performs very well when applied to an already good
strategy, such as STRATEGYMAXLEAF. This approach of combining theoretically
sound results with local search to generate strong techniques in practice is
similar in spirit to the recent k-means++ algorithm [1].

Intuitively, the local search strategy for pricing on social networks works as
follows:

  * •

Choose an arbitrary seller strategy $S$ and an arbitrary node $v$ to edit.

  * •

Choose a set of prices $\\{p_{1},p_{2},\ldots,p_{k}\\}$ to consider.

  * •

For each price $p_{i}$, empirically estimate the expected revenue $r_{i}$ that
is achieved by using the price $p_{i}$ for node $v$.

  * •

If any revenue $r_{i}$ beats the current expected revenue (also estimated
empirically) by some threshold $\epsilon$, then change $S$ to use the price
$p_{i}$ for node $v$.

  * •

Repeat the preceding steps for different nodes until there are no more
improvements.

Henceforth, we call this the LOCALSEARCH algorithm for improving seller
strategies.

To empirically estimate the revenue from a seller strategy, we can always just
simulate the entire process. We know who has the product initially, we know
what price each node will be offered, and we know the probability each node
will purchase the product at that price after any number of recommendations.
Simulating this process a number of times and taking the average revenue, we
can arrive at a fair approximation at how good a strategy is in practice. In
fact, we can prove that performing local search on any input policy will
ensure that the seller gets at least as much revenue as the original policy
with high probability. The proof of this fact holds for any simulatable input
policy, and proceeds by induction on the evolution tree of the process. The
proof is somewhat technical, so we will skip it, and instead focus on the
empirical question of the advantage provided by local search.

In light of the fact that local search can only improve the revenue (and never
hurt it), it seems that one should always implement local search for any
policy. There is a important technical detail that complicates this, however.
Suppose we wish to evaluate strategies $S_{1}$ and $S_{2}$, differing only on
one node $v$. If we independently run simulations for each strategy, it could
take thousands of trials (or more!) before the systematic change to one node
becomes visible over the noise resulting from random choices made by the other
nodes. It is impractical to perform these many simulations on a large network
every time we want to change the strategy for a single node.

Fortunately, it is possible to circumvent this problem using an observation
first noted in [5]. Let us consider the Linear Threshold model LTMB. In this
case, all randomness occurs before the process begins when each node chooses a
threshold that encodes how resistant it is to buying the product. Once these
thresholds have been fixed, the entire sales process is deterministic. We can
now change the strategy slightly and maintain the same thresholds to isolate
exactly what effect this strategy change had. Any model, including Independent
Cascade, can be rephrased in terms of thresholds, making this technique
possible.

The LOCALSEARCH algorithm relies heavily on this observation. While comparing
strategies, we choose several threshold lists, and simulate each strategy
against the same threshold lists. If these lists are not representative, we
might still make a mistake drawing conclusions from this, but we will not lose
a universally good signal or a universally bad signal under the weight of
random noise.

With this implementation, empirical tests (see the next section) show the
LOCALSEARCH algorithm does do its job: given enough time, it will improve
virtually any strategy enough to be competitive. It is not a perfect solution,
however. First of all, it can still make small mistakes while doing the random
estimates, possibly causing a strategy to become worse over time666Note that
if we choose $\epsilon$ and the number of trials carefully, we can make this
possibility vanishingly small (this is also the intuition behind the local
search guarantee, as we had mentioned earlier. In practice, however, it is
usually better to run fewer trials and accept the possibility of regressing
slightly.. Secondly, it is possible to end up with a sub-optimal strategy that
simply cannot be improved by any local changes. Finally, the LOCALSEARCH
algorithm can often take many steps to improve a bad strategy, making it
occasionally too slow to be useful in practice.

Nonetheless, these drawbacks really only becomes a serious problem if one
begins with a bad strategy. If one begins with a relatively good strategy –
for example STRATEGYMAXLEAF – the LOCALSEARCH algorithm performs well, and is
almost always worth doing in practice. We justify this claim in the next
section.

###  4.1 Experimental Results

In this section, we provide experimental evidence for the efficacy of the
LOCALSEARCH algorithm in improving the revenue guarantee. Note that in these
experiments, we need to assume a benchmark strategy as finding the optimal
strategy is NP-hard (see section 8.1). We pick a very simple strategy
RANDOMPRICING, which picks a random price independently for each node. The
results demonstrate that even this naive strategy can be coupled with the
LOCALSEARCH algorithm to do well in practice.

(a) Random preferential attachment graph

(b) Youtube subgraph

Figure 1: The variation in revenue generated by RANDOMPRICING and
STRATEGYMAXLEAF with the iterations of the LOCALSEARCH algorithm. The data is
averaged over $10$ runs of a $1000$ node random preferential attachment graph
1(a) or a $10000$ node subgraph of YouTube 1(b), starting with a random seed
each time.

We simulate the cascading process on two kind of graphs. The first graph we
study is a randomly generated graph, based on the preferential attachment
model that is a popular model for representing social networks [12]. We
generate a $1000$ node preferential attachment graph at random, and simulate
the cascading process by picking a random node as the seed in the network. The
probability model we examine is a step function (see the second example given
in Lemma 1) of probabilities. We note that the function is necessarily
arbitrary. The result of one particular parameter settings are shown in figure
1(a), which plots average revenue obtained by the two pricing strategies:
RANDOMPRICING and STRATEGYMAXLEAF. Each point on the figure is obtained by
average revenue over 10 runs on the same graph but with a different (random)
seed. The horizontal axis indicates the number of LOCALSEARCH iterations that
were done on the graph, where each iteration consisted of simulating the
process 50 times, and choosing the best value over the runs. It is clear from
the graph that STRATEGYMAXLEAF does quite well even without the addition of
LOCALSEARCH, although the addition of LOCALSEARCH does increase the revenue.
On the other hand, the RANDOMPRICING strategy performs poorly on its own, but
its revenue increases steadily with the iterations of the LOCALSEARCH
algorithm. We note that the difference between the revenue from the two
policies does vary (as expected) with the probability model, and the
difference between the revenue is not as large in all the different runs. But
the difference does persist across the runs, especially when the strategies
are run without the local search improvement.

We also conduct a similar simulation with a real-world network, namely the
links between users of the video-sharing site YouTube.777The network can be
freely downloaded; see [11] for details. The YouTube network has millions of
nodes, and we only study a subset of $10,000$ nodes of the network. We
simulate the random process as earlier, and the results are shown in figure
1(b). Again, we note that STRATEGYMAXLEAF does very well on its own, easily
beating the revenue of RANDOMPRICING. The RANDOMPRICING strategy does improve
a lot with LOCALSEARCH, but it fails to equalize the revenue of
STRATEGYMAXLEAF. The large size of the YouTube graph and the expensive nature
of the LOCALSEARCH algorithm restrict the size of the experiments we can
conduct with the graph, but the results from the above does experiments do
offer some insights. In particular, STRATEGYMAXLEAF succeeds in extracting a
good portion of the revenue from the graph, if we consider the revenue
obtained from STRATEGYMAXLEAF combined with LOCALSEARCH based improvements to
be the benchmark. Further, LOCALSEARCH can improve the revenue from any
strategy by a substantial margin, though it may not be able to attain enough
revenue when starting with a sub-optimal strategy such as RANDOMPRICING.
Finally, we observe that the combination of STRATEGYMAXLEAF and LOCALSEARCH
generates the best revenue among our strategies, and it is an open question as
to whether this is the optimal adaptive strategy.

##  5 Conclusions

In this work, we discussed pricing strategies for sellers distributing a
product over social networks through viral marketing. We show that computing
the optimal (one that maximizes expected revenue) non-adaptive strategy for a
seller is NP-Hard. In a positive result, we show that there exists a non-
adaptive strategy for the seller which generates expected revenue that is
within a constant factor of the expected revenue generated by the optimal
adaptive strategy. This strategy is based on an influence-and-exploit policy
which computes a max-leaf spanning tree of the graph, and offers the product
to the interior nodes of the spanning tree for free, later on exploiting this
influence by extracting its profit from the leaf nodes of the tree. The
approximation guarantee of the strategy holds for fairly general conditions on
the probability function.

##  6 Open Questions

The added dimension of pricing to influence maximization models poses a host
of interesting questions, many of which are open. An obvious direction in
which this work could be extended is to think about influence models stronger
than the model examined here. It is also unclear whether the assumptions on
the function $C(\cdot)$ are the minimal set that is required, and it would be
interesting to remove the assumption that there exists a price at which the
probability of acceptance is 1. A different direction of research would be to
consider the game-theoretic issues involved in a practical system. Namely, in
the model presented here, we think of each buyer as just sending the
recommendations to all its friends and ignore the issue of any “cost” involved
in doing so, thereby assuming all the nodes to be non-strategic. It would be
very interesting to model a system where the nodes were allowed to behave
strategically, trying to maximize their payoff, and characterize the optimal
seller strategy (especially w.r.t. the cashback) in such a setting.

##  7 Acknowledgments

Supported in part by NSF Grant ITR-0331640, TRUST (NSF award number
CCF-0424422), and grants from Cisco, Google, KAUST, Lightspeed, and Microsoft.
The third author is grateful to Mukund Sundararajan and Jason Hartline for
useful discussions.

## References

  * [1] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035, Philadelphia, PA, USA, 2007\. Society for Industrial and Applied Mathematics.
  * [2] P. Domingos and M. Richardson.  Mining the network value of customers.  Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 57–66, 2001.
  * [3] M.R. Garey and D.S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  WH Freeman & Co. New York, NY, USA, 1979.
  * [4] J. Hartline, V. Mirrokni, and M. Sundararajan.  Optimal Marketing Strategies over Social Networks.  Proceedings of the 17th international conference on World Wide Web, 2008.
  * [5] D. Kempe, J. Kleinberg, and É. Tardos.  Maximizing the spread of influence through a social network.  Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003.
  * [6] J. Kleinberg.  Cascading Behavior in Networks: Algorithmic and Economic Issues.  In N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press New York, NY, USA, 2007.
  * [7] D.J. Kleitman and D.B. West.  Spanning Trees with Many Leaves.  SIAM Journal on Discrete Mathematics, 4:99, 1991.
  * [8] J. Leskovec, A. Singh, and J. Kleinberg.  Patterns of influence in a recommendation network.  Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
  * [9] Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman.  The dynamics of viral marketing.  ACM Trans. Web, 1(1):5, 2007.
  * [10] H.I. Lu and R. Ravi.  Approximating Maximum Leaf Spanning Trees in Almost Linear Time.  Journal of Algorithms, 29(1):132–141, 1998.
  * [11] A. Mislove, M. Marcon, K.P. Gummadi, P. Druschel, and B. Bhattacharjee.  Measurement and analysis of online social networks.  In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pages 29–42. ACM New York, NY, USA, 2007.
  * [12] MEJ Newman, DJ Watts, and SH Strogatz.  Random graph models of social networks, 2002.
  * [13] BBC News.  Facebook valued at $15 billion.  http://news.bbc.co.uk/2/hi/business/7061042.stm, 2007.
  * [14] Erick Schonfeld.  Amiando makes tickets go viral and widgetizes event management.  http://www.techcrunch.com/2008/07/17/amiando-makes-tickets-go-viral-and%-widgetizes-event-management-200-discount-for-techcrunch-readers/, 2008.
  * [15] R. Solis-Oba.  2-Approximation Algorithm for finding a Spanning Tree with Maximum Number of leaves.  Proceedings of the Sixth European Symposium on Algorithms, pages 441–452, 1998.
  * [16] Wikipedia.  The beacon advertisement system.  http://en.wikipedia.org/wiki/Facebook_Beacon, 2008.
  * [17] Wikipedia.  Facebook revenue in 2008.  http://en.wikipedia.org/wiki/Facebook, 2008.

##  8 Appendix

###  8.1 Hardness of finding the optimal strategy

In this section, we show that Problem 1 is NP-hard even for a very simple
buyer model M by a reduction from vertex cover with bounded degree (see [3]
for the hardness of bounded-degree vertex cover). Letting $d$ denote the
degree bound, and letting $p=\frac{1}{4d}$, we will use an Independent Cascade
Model ICMC with:

$\displaystyle C(x)=\left\\{\begin{array}[]{ll}1&\textrm{ if }x<p,\\\
0&\textrm{ if }x\geq p\end{array}\right.$

Intuitively, the seller has to partition the nodes into “free” nodes and
“full-price” nodes. In the former case, nodes are offered the product for
free, and they accept it with probability 1 as soon as they receive a
recommendation. In the latter case, nodes are offered the product for price 1,
and they accept each recommendation with probability $p$. (Note that the
seller is allowed to use other prices between $0$ and $1$ but a price of $1$
is always better.)

We are going to use a special family of graphs illustrated in Figure 2. The
graph consists of four layers:

  * •

A singleton node $s$, which we will use as the only initially active node
(i.e., $S^{0}=\\{s\\}$);

  * •

$s$ links to a set of $n$ nodes, denoted by $V_{1}$;

  * •

Nodes in $V_{1}$ also link to another set of nodes, denoted by $V_{2}$. Each
node in $V_{1}$ will be adjacent to $d$ nodes in $V_{2}$, and each node in
$V_{2}$ will be adjacent to $2$ nodes in $V_{1}$ (so $|V_{2}|=dn/2$);

  * •

Each node $v\in V_{2}$ also links to $k=20d$ new nodes, denoted by $W_{v}$;
these $k$ nodes do not link to any other nodes. The union of all $W_{v}$’s is
denoted by $V_{3}$.

Figure 2: Reducing Bounded-Degree Vertex Cover to Optimal Network Pricing

We first sketch the idea of the hardness proof. The connection between $V_{1}$
and $V_{2}$ will be decided by the vertex cover instance: given a vertex cover
instance $G^{\prime}(V,E)$ with bounded degree $d$, we construct a graph $G$
as above where $V_{1}=V$ and $V_{2}=E$, adding an edge between $V_{1}$ and
$V_{2}$ if the corresponding vertex is incident to the corresponding edge in
$G^{\prime}$. The key lemma is that, in the optimal pricing strategy for $G$,
the subset of nodes in $V_{1}$ that are given the product for free is the
minimum set that covers $V_{2}$ (i.e., a minimum vertex cover of
$G^{\prime}$).

To formalize this, first note that, in an optimal strategy, all nodes in
$V_{3}$ should be full-price. Giving the product to them for free gets 0
immediate revenue, and offers no long-term benefit since nodes in $V_{3}$
cannot recommend the product to anyone else. If the nodes are full-price, on
the other hand, there is at least a chance at some revenue.

On the other hand, we show the optimal strategy must also ensure each vertex
in $V_{2}$ eventually becomes active with probability 1.

######  Lemma 7.

In an optimal strategy, every node $v\in V_{2}$ is free, and can be reached
from $s$ by passing through free nodes.

###### Proof.

Suppose, by way of contradiction, that the optimal strategy has a node $v\in
V_{2}$ that does not satisfy these conditions. Let $u_{1}$ and $u_{2}$ be the
two neighbors of $v$ in $V_{1}$, and let $q$ denote the probability that $v$
eventually becomes active.

We first claim that $q<2dp$. Indeed, if $v$ is full-price, then even if
$u_{1}$ and $u_{2}$ become active, the probability that $v$ becomes active is
$1-(1-p)^{2}<2p$. Otherwise, $u_{1}$ and $u_{2}$ are both full-price. Since
$u_{1}$ and $u_{2}$ connect to at most $2d$ edges other than $v$, the
probability that one of them becomes active before $v$ is at most
$1-(1-p)^{2d}<2dp$. Thus, $q<2dp$.

It follows that the total revenue that this strategy can achieve from $u_{1}$,
$v$, and $W_{v}$ is $2+kqp<2+2kdp^{2}=4.5$. Conversely, if we make $u_{1}$ and
$v$ free, we can achieve $kp=5$ revenue from the same buyers. Furthermore,
doing this cannot possibly lose revenue elsewhere, which contradicts the
assumption that our original strategy was optimal. ∎

It follows that, in an optimal strategy, all of $V_{3}$ is full-price, all of
$V_{2}$ is free, and every node in $V_{2}$ is adjacent to a free node in
$V_{1}$. It remains only to determine $C$, the nodes in $V_{1}$, that an
optimal strategy should make free. At this point, it should be intuitively
clear that $C$ should correspond to a minimum vertex-cover of $V_{2}$. We now
formalize this as follows:

######  Lemma 8.

Let $C$ denote the set of free nodes in $V_{1}$, as chosen by an optimal
strategy. Then $C$ corresponds to a minimum vertex cover of $G^{\prime}$.

###### Proof.

As noted above, every node in $V_{2}$ must be adjacent to a node in $C$, which
implies $C$ does indeed correspond to a vertex cover in $G^{\prime}$.

Now we know an optimal strategy makes every node in $V_{2}$ free, and every
node in $V_{3}$ full-price. Once we know $C$, the strategy is determined
completely. Let $x_{C}$ denote the expected revenue obtained by this strategy.
Since all nodes in $V_{2}$ are free and are activated with probability $1$, we
know the strategy achieves 0 revenue from $V_{2}$ and $p|V_{3}|$ expected
revenue from $V_{3}$.

Among nodes in $V_{1}$, the strategy achieves 0 revenue for free nodes, and
exactly $1-(1-p)^{d+1}$ expected revenue for each full-price node. This is
because each full-price node is adjacent to exactly $d+1$ other nodes, and
each of these nodes is activated with probability 1. Therefore,
$x_{C}=(|V_{1}|-|C|)(1-(1-p)^{d+1})+p|V_{3}|$, which is clearly minimized when
$C$ is a minimum-vertex cover. ∎

Therefore, optimal pricing, even in this limited scenario, can be used to
calculate the minimum-vertex cover of any bounded-degree graph, from which NP-
hardness follows.

######  Theorem 2.

Two Coupon Optimal Strategy Problem is NP-Hard.