# Advertising Competitions in Social Networks

Antonia Masucci, Alonso Silva

► To cite this version:

Antonia Masucci, Alonso Silva. Advertising Competitions in Social Networks. 2016. [hal-01352187](https://hal-inria HAL Id: hal-01352187)

https://inria.hal.science/hal-01352187

Preprint submitted on 9 Aug 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Advertising Competitions in Social Networks

Antonia Maria Masucci *<fnref n="1" /> and Alonso Silva †<fnref n="2" />

## Abstract

In the present work, we study the advertising competition of several marketing campaigns who need to determine how many resources to allocate to potential customers to advertise their products through direct marketing while taking into account that competing marketing campaigns are trying to do the same. Potential customers rank marketing campaigns according to the offers, promotions or discounts made to them. Taking into account the intrinsic value of potential customers as well as the peer influence that they exert over other potential customers we consider the network value as a measure of their importance in the market and we find an analytical expression for it.

We analyze the marketing campaigns competition from a game theory point of view, finding a closed form expression of the symmetric equilibrium offer strategy for the marketing campaigns from which no campaign has any incentive to deviate. We also present several scenarios, such as Winner-takes-all and Borda, but not the only possible ones for which our results allow us to retrieve in a simple way the corresponding equilibrium strategy.

## 1 INTRODUCTION

In the internet age, direct marketing, which promotes a product or service exclusively to potential customers likely to be profitable, has brought the attention of marketing campaigns replacing in some instances and complementing in others the traditional mass marketing which promotes a product or service indiscriminately to all potential customers.

In the context of direct marketing, Domingos and Richardson [1, 2] considered the *network value of a customer* by incorporating the influence of peers on the decision making process of potential customers deciding between different products or services promoted by competing marketing campaigns. If each potential customer makes a buying decision independently of every other potential customer, we should only consider his intrinsic value, i.e. the expected profit from sales to him. However, when we consider the often strong influence potential customers exert on their peers, friends, etc., we have to incorporate this influence to their network value.

Most of the existing state of the art considers that there is an incumbent that holds the market and a challenger who needs to allocate advertisement through direct marketing for certain individuals at a given cost of adoption to promote the challenger product or service. However, the cost of adoption is unknown for most potential customers.

In the present work, our focus is on how many resources to allocate to potential customers, while knowing that competing marketing campaigns are doing the same, for them to adopt one marketing campaign versus another. We are interested on the scenario when several competing marketing campaigns need to simultaneously and independently decide how many resources to allocate to potential customers to advertise their products while most of the state-of-the-art focus in only one marketing campaign (the non-simultaneous case is also analyzed). The process and dynamics by which influence is spread is given by the voter model.

### 1.1 Related Works

The general problem of influence maximization was first introduced by Domingos and Richardson [1, 2]. Based on the results of Nemhauser et al. [3], Kempe et

<footnote n="1">¹INRIA Paris-Rocquencourt, Domaine de Voluceau B.P. 105, 78153 Le Chesnay, France</footnote>

<footnote n="2">²Nokia Bell Labs, Centre de Villarceaux, Route de Villejust, 91620 Nozay, France</footnote>

<footnote>*Email: antonia.masucci@inria.fr</footnote>

<footnote>†Email: alonso.silva@nokia-bell-labs.com To whom correspondence should be addressed.</footnote>
al. [4, 5] provided a greedy $(1-1/e-\epsilon)$-approximation algorithm for the spread maximizing set. A slightly different model but with similar flavor, the voter model, was introduced by Clifford and Sudbury [6] and Holley and Liggett [7]. In that model of social networks, Even-Dar and Shapira [8] found an exact solution to the spread maximization set. In this work, we focus on this model of social networks since even if the solutions are not always simple, we can find them explicitly.

Competitive influence in social networks has been studied in other scenarios. Bharathi et al. [9] proposed a generalization of the independent cascade model of social networks and gave a $(1-1/e)$ approximation algorithm for computing the best response to an already known opponent's strategy. Sanjeev and Kearns [10] studied the case of two players simultaneously choosing some nodes to initially seed while considering two independent functions for the consumers denoted switching function and selection function. Borodin et al. [11] showed that for a broad family of competitive influence models is NP-hard to achieve an approximation that is better than the square root of the optimal solution. Chasparis and Shamma [12] found optimal advertising policies using dynamic programming on some particular models of social networks.

Within the general context of competitive contests, there is an extensive literature (see e.g. [13, 14, 15, 16]). To study competitive contests, we use recent advances of game theory, and in particular of Colonel Blotto games. The Colonel Blotto game, was first solved for the case of two generals and three battlefields by Borel [17, 18]. For the case of equally valued battlefields, also known as homogeneous battlefields case, this result was generalized for any number of battlefields by Gross and Wagner [13]. Gross [19] proved the existence and a method to construct the joint probability distribution. Laslier and Picard [20] provided alternative methods to construct the joint distribution by extending the method proposed by Gross and Wagner [13]. Roberson [14] focused on the case of two generals, homogeneous battlefields and different budgets (also known as asymmetric budgets case). Friedman [21] studied the Nash equilibrium and best response function for the asymmetric budgets case with two generals. The case of two generals and where for each distinct value there are at least three battlefields with the same value was stated and solved by Roberson [22] and Shwartz et al. [23]. In the context of voting systems, Myerson [24] found the so-

lution for the case for equally valued battlefields with ranking scores for any number of candidates.

The plan of this work is as follows. In Section 2 we describe the model that we are considering. In Section 3 we give the main results that we have obtained. In Section 4 we give simulations on some scenarios and in Section 5 we conclude and describe future extensions of our work.

## 2 MODEL

Consider the set of marketing campaigns $\mathcal{K} = \{1, 2, \dots, K\}$ that need to allocate a certain budget, denoted by $B$, across a set of potential customers $\mathcal{V} = \{1, 2, \dots, N\}$ through offers (or promotions or discounts). Each potential customer indicates his preferences through a ranking (defined in the following subsection) of the $\mathcal{K}$ products or services promoted by the marketing campaigns. For $n \in \mathcal{V}$, we denote by $w_n$ the intrinsic value of potential customer $n$ and by $W = \sum_{n \in \mathcal{V}} w_n$ the total intrinsic value of the set of potential customers. Similarly, we denote by $v_n$ the network value (to be determined) of potential customer $n \in \mathcal{V}$ and by $V = \sum_{n \in \mathcal{V}} v_n$ the total network value of the set of potential customers.

To avoid specifying the number of potential customers and dealing with the complexities of large finite numbers, we consider the number of potential customers to be essentially infinite. We should, however, interpret such an infinite model as an approximation to a large finite population with hundreds or thousands of potential customers. We assume that campaigns' offers are independent across individual potential customers, so that no potential customer's offers have any specific relationship with any other set of potential customers' offers. This offers' independence assumption greatly simplifies our analysis, because it allows us to completely characterize a marketing campaign's promises by the marginal distribution of his offers to potential customers, without saying anything more about the joint distribution of offers to various sets of potential customers. The infinite-population assumption (suggested and used in [24]) was introduced above essentially only to justify this simplifying assumption of offers' independence across potential customers.

Each marketing campaign's budget constraint is expressed as a constraint on the average offer per potential customer that a marketing campaign can promise. Specifically, we assume here that each mar-
keting campaign's offer distribution for potential customer $n$ must have mean $Bv_n/V$ to be considered credible by potential customer $n$. The reason is that budget $B$ should be allocated across $N$ potential customers and each potential customer $n$ has relative value $v_n/V$.

With a finite population of $N$ potential customers, and with a fixed budget of $B$ dollars to be allocated, marketing campaign promises could not be independent across all potential customers, because the offers to all potential customers would have to sum the given budget $B$. However, due to Kolmogorov's strong law of large numbers, as the number of potential customers $N$ increases, the sum of independently distributed offers with high probability will converge to the budget $B$. Indeed, if the mean of the campaign's offer distribution for potential customer $n \in \mathcal{V}$ is given by $Bv_n/V$ and the support of the distribution is bounded then, for any small positive number $\epsilon$, $N$ potential customers' offers that are drawn independently from the campaign's distribution would have probability less than $\epsilon$ of totalling more than $(1+\epsilon) \sum_{n \in \mathcal{V}} Bv_n/V = B(1+\epsilon)$, when $N$ is sufficiently large. Thus, taking the limit as the population goes to infinity, we can assume that each campaign makes independent offers to every potential customer and the budget constraint will hold with high probability.

The potential customers and their influence relationships can be modeled as an undirected graph with self-loops $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ where $\mathcal{V}$ is the set of nodes which represent the potential customers and $\mathcal{E}$ is the set of edges which represent the mutual influence between potential customers.

## Notation

Part of the notation is summarized in Table 1. We denote by $|\mathcal{A}|$ the cardinality of set $\mathcal{A}$. We denote by index $k$ one of the marketing campaigns and by index $-k$ the competing (or set of competing) marketing campaign(s) to $k$. For a potential customer $n \in \mathcal{V}$, we denote by $\mathcal{N}(n)$ the set of neighbors of $n$ in graph $\mathcal{G}$, i.e. $\mathcal{N}(n) = \{m \in \mathcal{V} : \{n, m\} \in \mathcal{E}\}$.

## 2.1 Normalized rank-scoring rules

We consider that each potential customer ranks the set of marketing campaigns $\mathcal{K}$ in order of their offers to her. We assume a normalized rank-scoring rule characterized by an ordered sequence of $K$ numbers, which we denote

by $s_1, s_2, \dots, s_K$, where $s_1 \ge s_2 \ge \dots \ge s_K = 0$ and such that $\sum_{k=1}^K s_k = 1$. We consider that each potential customer $n \in \mathcal{V}$ distributes her value $v_n$ across marketing campaigns according to this normalized rank-scoring rule $\mathbf{s} = (s_1, s_2, \dots, s_K)$ as follows: $v_n \mathbf{s} = (v_n s_1, v_n s_2, \dots, v_n s_K)$. Thus, potential customer $n \in \mathcal{V}$ gives the top-ranked marketing campaign $v_n s_1$ points, the second-ranked marketing campaign $v_n s_2$, and so on, with the $k$th ranked marketing campaign getting $v_n s_k$ for all $k \in \mathcal{K}$. Therefore, the payoff distributed is indeed $\sum_{k=1}^K v_n s_k = v_n \sum_{k=1}^K s_k = v_n$ where the last equality is coming from the normalization of the rank-scores. Each marketing campaign's payoff corresponds to the sum of the payoffs across all potential customers.

The previous assumption is not restrictive. Given any rank-scoring rule, where $s_1, s_2, \dots, s_K$, are not all equal and without loss of generality $s_1 \ge s_2 \ge \dots \ge s_K$, it can be normalized to fulfill the previous statement. Indeed, let $S = \sum_{j=1}^K (s_j - s_K)$. We observe that we can normalize the rank-scoring rule as follows ($s'_1, s'_2, \dots, s'_K) = (\frac{s_1-s_K}{S}, \frac{s_2-s_K}{S}, \dots, \frac{s_K-s_K}{S})$ so that $s'_K = 0$ and the sum of the rank-scores $S'$ is equal to 1.

## 2.2 Intrinsic payoff function

We assume that the intrinsic value of potential customer $n \in \mathcal{V}$ is given by $w_n \le U$ with $U$ finite and we denote by $\mathbf{w} = (w_1, w_2, \dots, w_N)$ the vector of intrinsic values of potential customers. We consider the matrix of offers of marketing campaigns to potential customers, denoted by $\mathbf{X} = (x_{k,n})$, where $x_{k,n}$ corresponds to the offer of marketing campaign $k \in \mathcal{K}$ to potential customer $n \in \mathcal{V}$. We denote by $\mathbf{x}_{k, \cdot} = (x_{k,1}, x_{k,2}, \dots, x_{k,N})$ the vector of offers of marketing campaign $k \in \mathcal{K}$. We consider the matrix of offers to potential customers but only of the competing marketing campaigns to $k$, denoted by $\mathbf{X}_{-k, \cdot}$.

For potential customer $n \in \mathcal{V}$, we consider a ranking function $u_n: \mathcal{K} \to \{1, 2, \dots, K\}$ which maps a given marketing campaign $k$ to its ranking given by that potential customer. For example, if marketing campaign $k$ is the top-ranked marketing campaign and $k'$ is the third-ranked marketing campaign for potential customer $n \in \mathcal{V}$ then $u_n(k) = 1$ and $u_n(k') = 3$.

The intrinsic payoff function for marketing campaign $k$ is given by

$$ \pi_k^{\text{INT}}(\mathbf{x}_{k, \cdot}, \mathbf{X}_{-k, \cdot}, \mathbf{w}) = \sum_{n=1}^{N} w_n s_{u_n(k)}, \quad (1) $$
<table><caption>Table 1: Notation</caption><tr><td>V = {1, 2, ..., N}</td><td>Set of potential customers</td></tr><tr><td>K = {1, 2, ..., K}</td><td>Set of marketing campaigns</td></tr><tr><td>B</td><td>Total budget of marketing campaigns</td></tr><tr><td>w<sub>n</sub></td><td>Intrinsic value of potential customer n</td></tr><tr><td>v<sub>n</sub></td><td>Network value of potential customer n</td></tr><tr><td>W = &sum;<sub>n&isin;V</sub> w<sub>n</sub></td><td>Total intrinsic value of potential customers</td></tr><tr><td>V = &sum;<sub>n&isin;V</sub> v<sub>n</sub></td><td>Total network value of potential customers</td></tr><tr><td>G = (V, E)</td><td>Graph of influence relationships</td></tr><tr><td>M</td><td>Normalized transition matrix of G</td></tr><tr><td>(s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>K</sub>) such that<br>s<sub>1</sub> &ge; s<sub>2</sub> &ge; ... &ge; s<sub>K</sub> = 0,<br>&sum;<sub>j&isin;K</sub> s<sub>j</sub> = 1</td><td>Normalized rank-scoring rule</td></tr><tr><td>x<sub>k,n</sub></td><td>Offer of campaign k to customer n</td></tr><tr><td>x<sub>k,.</sub></td><td>Vector of offers of marketing campaign k</td></tr><tr><td>X = {x<sub>k,n</sub>}<sub>k&isin;K, n&isin;V</sub></td><td>Matrix of offers</td></tr><tr><td>X<sub>-k,.</sub></td><td>Matrix of offers of competing campaigns</td></tr><tr><td>&pi;<sup>INT</sup></td><td>Intrinsic payoff function</td></tr><tr><td>&pi;</td><td>(Network) payoff function</td></tr><tr><td>u<sub>n</sub><sup>t</sup>(&middot;)</td><td>Ranking function</td></tr><tr><td>f<sup>0</sup>(&middot;)</td><td>Initial preferences</td></tr><tr><td>f<sup>t</sup>(&middot;)</td><td>Preferences at time t</td></tr></table>

where $s_{u_n(k)}$ corresponds to the rank-score given by potential customer $n$ for the ranking of marketing campaign $k$. We observe that $s_{u_n(k)}$ depends only on the offers made to potential customer $n$.

## 2.3 Evolution of the system

We consider that time is slotted and without loss of generality we consider that the initial time $t_0 = 0$. We consider the function $f^0: V \to K^K$ which maps a potential customer $n \in V$ to her initial preferences $f^0(n) = (f_1^0(n), f_2^0(n), \dots, f_K^0(n))$ where $f_1^0(n)$ corresponds to her initial top-ranked marketing campaign, $f_2^0(n)$ corresponds to her initial second-ranked marketing campaign, and so on. Similarly, for $t \ge 1$ we consider function $f^t: V \to K^K$ which maps a potential customer $n \in V$ to her preferences at time $t$, denoted by $f^t(n) = (f_1^t(n), f_2^t(n), \dots, f_K^t(n))$, where $f_1^t(n)$ corresponds to her top-ranked marketing campaign at time $t$, $f_2^t(n)$ corresponds to her second-ranked marketing campaign at time $t$, and so on.

The evolution of the system will be described by the voter model. Starting from any arbitrary initial preference assignment by the potential customers of $G$, at each time $t \ge 1$, each potential customer picks uniformly at random one of his neighbors and

adopts his opinion. Equivalently, $f^t(j) = f^{t-1}(j')$ with probability $1/|N(j)|$ if $j' \in N(j)$.

Similarly to the previous subsection, for $t \ge 0$ and potential customer $n \in V$, we consider function $u_n^t: K \to \{1, 2, \dots, K\}$ which for a given marketing campaign $k \in K$ gives you the ranking of the marketing campaign for potential customer $n$ at time $t$.

We are interested on the network value of a potential customer. Following the steps of [15], in the next section we compute this value.

# 3 RESULTS

## 3.1 Network value of a customer

We notice that in the voter model described in the previous section, the probability that potential customer $j$ adopts the opinion of one her neighbors $j'$ is precisely $1/|N(j')|$. Equivalently, this is the probability that a random walk of length 1 that starts at $j$ ends up in $j'$. Generalizing this observation by induction on $t$, we obtain the following proposition.

**Proposition 1** (Even-Dar and Shapira [8]). Let $p_{j,j'}^t$ denote the probability that a random walk of length $t$ starting at potential customer $j$ stops at potential customer $j'$. Then the probability that after $t$ iterations
of the voter model, potential customer j will adopt the opinion that potential customer j' had at time t = 0 is precisely $p_{j,j'}^t$.

By linearity of expectation, the expected network payoff for marketing campaign $k \in \mathcal{K}$ at target time $\tau$, denoted by $\pi_k^\tau$, is given by

$$\pi_k^\tau = \sum_{j \in \mathcal{V}} \sum_{j' \in \mathcal{V}} w_j p_{j,j'}^\tau s_{u_{j'}^\tau(k)}.$$

Let $M$ be the normalized transition matrix of $\mathcal{G}$, i.e., $M(j, j') = 1/|\mathcal{N}(j)|$ if $j' \in \mathcal{N}(j)$ and zero otherwise. The probability that a random walk of length $\tau$ starting at $j$ ends in $j'$ is given by the $(j, j')$-entry of the matrix $M^\tau$. Then

$$\pi_k^\tau = \sum_{j \in \mathcal{V}} \sum_{j' \in \mathcal{V}} w_j M^\tau(j, j') s_{u_{j'}^\tau(k)}.$$

Therefore, the expected network payoff is given by

$$\pi_k^\tau = \sum_{j' \in \mathcal{V}} v_{j'} s_{u_{j'}^\tau(k)}, \qquad (2)$$

where the network value of potential customer $j'$ at target time $\tau$ is given by

$$v_{j'} = \sum_{j \in \mathcal{V}} w_j M^\tau(j, j').$$

We can formalize this in the following statement.

**Theorem 1.** Under the rank-scoring rule with normalized ranking points $(s_1, s_2, \dots, s_K)$ and intrinsic values $(w_1, w_2, \dots, w_N)$, the network value of potential customer $j'$ at target time $\tau$ is given by

$$v_{j'} = \sum_{j \in \mathcal{V}} w_j M^\tau(j, j'),$$

where $M$ is the normalized transition matrix of $\mathcal{G}$.

We notice that both eqns. (1) and (2) are similar. The only difference is that one considers the intrinsic value and the other the network value (given by Theorem 1) of potential customers. From eqns. (1) and (2), we obtain that after determining the network value of potential customers, the problem of determining the resource allocation that maximizes the expected network payoff is similar to the problem of determining the resource allocation that maximizes the expected intrinsic payoff. Therefore, in the following we restrict ourselves to this problem.

## 3.2 Non-simultaneous allocations

In this subsection, we prove that the intrinsic payoff problem is easy to solve in the case where one marketing campaign can observe what competing marketing campaigns are offering and after that makes offers to potential customers. Indeed, even in the case of two marketing campaigns, if marketing campaign 2 could make offers after observing the offers made by marketing campaign 1, then marketing campaign 2 will always be preferred by the most valuable potential customers. For example, marketing campaign 2 could identify a small group of potential customers who are the least valuable between those who are promised strictly positive offers by marketing campaign 1 (e.g. the 5% of the distribution of marketing campaign 1), and offer nothing to this group. Then campaign 2 could offer to every other potential customer slightly more than campaign 1 has promised him, where the excess over campaign 1's offers is financed from the resources not given to the potential customers in the first group. Every potential customer outside of the first small group (5%) would prefer marketing campaign 2, who would win 95% of the most valuable potential customers. To avoid this simple outcome, we assume that both of the marketing campaigns must make their marketing campaign promises simultaneously. (We may think of scenarios in which it is important to make the first offers and in which there is a cost of delay by the response to the first offers, but those scenarios are outside the scope of this work.)

## 3.3 Family of scalable probability distributions

We seek a solution that can be written as a family of offer probability distributions with a scaling parameter. We want that offers scale with the value (intrinsic or network value depending on the context) of the potential customers. However, essentially we look for an offer distribution that has the same shape relative to this value. We consider that the representative offer distribution $F$ (the offer distribution with scale value 1) has a probability density function $f$ in a bounded support $I$. From the fundamental theorem of calculus, we have the following. Let $I \subseteq \mathbb{R}$ be an interval and $\varphi: [a_1, b_1] \to I$ be a continuously differentiable function. Suppose that $f: I \to \mathbb{R}$ is a continuous function. Then

$$\int_{\varphi(a_1)}^{\varphi(b_1)} f(x) dx = \int_{a_1}^{b_1} f(\varphi(t)) \varphi'(t) dt.$$
For potential customer $n \in \mathcal{V}$, we use function $\varphi(x) = x/v_n$ which is continuously differentiable and scales the offers by a factor $v_n$ and therefore if the probability density function of the representative offer density $f(x)$ has support $[a, b]$ the scaled offer density is given by $f(x/v_n)/v_n$ and it has support $[v_n a, v_n b]$.

We may represent marketing campaign $k$'s cumulative offer distribution by a family of probability distributions, with representative cumulative offer distribution $F^k(x; a, b)$, where $F_n^k(x) = F^k(x/v_n; v_n a, v_n b)$ denotes the fraction of potential customers to whom marketing campaign $k$ will offer less than value $x$. Each offer distribution for potential customer $n \in \mathcal{V}$ must have mean $Bv_n/V$ and so $F_n^k$ must be a non-decreasing function that satisfies

$$ \int_{0}^{\infty} x dF_{n}^{k}(x) = Bv_{n}/V, $$

as well as $F_n^k(x) = 0 \quad \forall x \le 0$, and

$$ \lim_{x \to +\infty} F_{n}^{k}(x) = 1. $$

## 3.4 Symmetric equilibrium

A symmetric equilibrium of the marketing campaign competition is a scenario in which every marketing campaign is expected to use the same offer distribution, and each marketing campaign finds that using this offer distribution maximizes its chances of winning when the other marketing campaigns are also simultaneously and independently allocating their offers according to this distribution (and all potential customers perceive that the $K$ marketing campaigns have the same probability of winning the market). In this work, we focus exclusively on finding such symmetric equilibria.

In the following, we prove that there is a symmetric equilibrium which corresponds to a family of probability distributions with scale parameter $v_n$ for potential customer $n \in \mathcal{V}$. Let $F(x) = F(x; a, b)$ denote the representative cumulative distribution function acting as the equilibrium strategy and let $F_n(x) := F(x/v_n; v_n a, v_n b)$ denote the cumulative distribution function representing the equilibrium offer distribution for potential customer $n \in \mathcal{V}$. $F_n(x)$ denotes the cumulative probability that a given potential customer $n$ will be offered less than $x$ by any other given marketing campaign, according to this equilibrium distribution.

Consider the situation faced by a given marketing campaign $k$ when it chooses its offer distribution,

assuming that every other marketing campaign will use the equilibrium offer distribution. When marketing campaign $k$ offers $x$ to potential customer $n$, the probability that this marketing campaign $k$ will be ranked in position $j$ by potential customer $n$ is given by $P(j, F_n(x))$ where we let

$$ P(j, q) = \binom{K-1}{j-1} q^{K-j} (1-q)^{j-1}. $$

That is, $P(j, q)$ denotes the probability that exactly $j-1$ of the $K-1$ competing marketing campaigns will offer more than $x$, given that each other marketing campaign has an independent probability $q$ of offering less than $x$ to this potential customer. Equivalently, $P(j, q)$ denotes the probability that exactly $K-j$ of the $K-1$ competing marketing campaigns will offer less than $x$.

If marketing campaign $k$ offers $x$ to potential customer $n$, then the expected value that this potential customer will give to this marketing campaign is $R_n(F_n(x))$ where

$$ R_n(q) = v_n \sum_{j=1}^{K} P(j, q) s_j. $$

Things could be more difficult if there were a positive probability of other marketing campaigns offering exactly $x$, but we can ignore such complications because we will prove (see Lemma 1) that the equilibrium distribution cannot assign positive probability to any single point. When all marketing campaigns independently use the same offer distribution, they must all get the same expected score from potential customer $n$ which must equal $v_n/K$.

**Theorem 2.** In a $K$-marketing campaign competition under the normalized rank-scoring rule $(s_1, s_2, \dots, s_K)$ and values $(v_1, v_2, \dots, v_N)$, there is a unique scalable symmetric equilibrium of the marketing campaigns' offer-distribution game. In this equilibrium, each marketing campaign chooses to generate offers according to a family of probability distributions, with scale parameter $v_n$ for potential customer $n$, that has support on the interval from 0 to $s_1 KBv_n/V$, and which has a cumulative distribution $F(\cdot)$ that satisfies the equation

$$ x = R_n(F_n(x))/(V/KB), \quad \forall x \in [0, s_1 KBv_n/V]. $$

The proof follows the steps of Theorem 2 in [24]. The following is a constructive proof and we decompose the proof in the next following lemmas.
**Lemma 1.** If there is a symmetric equilibrium distribution of offers, it must be continuous, i.e. it cannot have any points of positive probability.

*Proof.* If all marketing campaigns used a representative offer distribution $F(\cdot)$ that assigned a positive probability $\delta$ to some point $x > 0$, then there would be a positive fraction $\delta^K$ of potential customers who would be exactly indifferent among the marketing campaigns since they receive from each of them the same offer. Any marketing campaign could then increase his average point score among this group by giving an arbitrarily small increase (say, $\varepsilon$) to most of the potential customers to whom he was going to offer $x$ and the cost of this increase could be financed by moving an arbitrarily small fraction of this group down to zero. In other words, if the offer distribution had a positive mass at some point, then a marketing campaign could gain a positive group of potential customers by a transfer of resources that would lower his score from only an arbitrarily small number of potential customers. $\square$

**Lemma 2.** We have that

$$R_n(0) = s_K v_n = 0, \quad R_n(1) = s_1 v_n,$$

and $R_n(\cdot)$ is a continuous and strictly increasing function over the interval from 0 to 1.

*Proof.* These equations hold because $P(j, 0)$ equals 0 unless $j$ equals $K$, $P(j, 1)$ equals 0 unless $j$ equals 1, and $P(K, 0) = 1 = P(1, 1)$. Continuity of $R_n(\cdot)$ follows directly from the formulas, because $R_n(q)$ is polynomial in $q$. Let us show that $R_n(\cdot)$ is increasing. First, we verify that

$$R_n(q) = v_n \sum_{j=2}^{K} (s_{j-1} - s_j) \sum_{m<j} P(m, q),$$

using $s_K = 0$. We observe that $\sum_{m<j} P(m, q)$ denotes the probability that more than $K-j$ other marketing campaigns have made offers in an interval of probability $q$, and this probability must be a strictly increasing function of $q$. The ordering of the $s_j$ values guarantees that at least one term in this $R_n(q)$ expression must have a positive $(s_{j-1} - s_j)$ coefficient, and none can be negative. Therefore $R_n(\cdot)$ is an increasing function. $\square$

**Lemma 3.** The lowest permissible offer 0 must be in the support of the equilibrium distribution of offers.

*Proof.* The main idea is that, if the minimum of the support were strictly greater than zero, then a marketing campaign would be devoting positive resources to potential customers near the minimum of the support of the distribution. He would expect to get almost no value ($s_K = 0$) from these potential customers, because all other marketing campaigns would almost surely be promising them more. Thus, it would be better to reduce the offers to 0 for most of these potential customers in order to make serious offers for at least some of them.

The above argument can be formalized as follows. Because, as we have shown before, there are no points of positive probability, the cumulative offer distribution $F_n(\cdot)$ for potential customer $n$ is continuous. Let $z$ denote the minimum of the support of the equilibrium offer distribution for potential customer $n$, so $F_n(z) = 0$ but $F_n(z + \varepsilon) > 0$ for all positive $\varepsilon$. Now, select any fixed $y$ such that $y > z$ and $F_n(y) > 0$. For any $\varepsilon$ such that $0 < \varepsilon < y - z$, a marketing campaign might consider deviating from the equilibrium by promising either $y$ or $0$ to each potential customer $n$ in the group of potential customers whom he was supposed to offer between $z$ and $(z + \varepsilon)$, according to his $F_n$-distributed random-offer generator. The potential customers in this group were going to be given offers that averaged some amount between $z$ and $(z + \varepsilon)$, so he can offer $y$ dollars to at least a $z/y$ fraction of these potential customers without changing his offers to any other potential customer. Among this $z/y$ fraction of the group, he would get an average point score of $R_n(F_n(y))$, by outbidding the other marketing campaigns who are using the $F_n$ distribution; so the deviation would get him an average point score of at least $(z/y)R_n(F_n(y))$ from this group of potential customers (the potential customers moved down to zero in this deviation would give him $s_K v_n = 0$ points). If he follows the equilibrium, however, he gets at most $R_n(F_n(z + \varepsilon))$ as his average point score from this group of potential customers. So to deter such a deviation, we must have $(z/y)R_n(F_n(y)) \le R_n(F_n(z + \varepsilon))$, and so

$$z \le y \frac{R_n(F_n(z + \varepsilon))}{R_n(F_n(y))}.$$

But $R_n(F_n(z + \varepsilon))$ goes to $R_n(F_n(z)) = R_n(0) = 0$ as $\varepsilon$ goes to 0, and so $z$ must equal 0. $\square$

**Lemma 4.** There is some positive constant $\alpha$ such that

$$R_n(F_n(x)) = \alpha x.$$
**Proof.** Let $x$ and $y$ be any two numbers in the support of the equilibrium distribution for potential customer $n$ such that $0 < x < y$. A marketing campaign could deviate by taking a group of potential customers to whom he is supposed to give offers close to $x$, according to his equilibrium plan, and instead he could give them offers close to $y$ to an $x/y$ fraction of this group and he could offer 0 to the remaining $(1-x/y)$ fraction. Because the support of the representative distribution contains 0 as well as $x$ and $y$, neither this self-financing deviation nor its reverse (offering close to $x$ to a group of potential customers of whom an $x/y$ fraction were supported get close to $y$, and the remaining $(1-x/y)$ fraction were supposed to get close to 0) should increase the marketing campaign's expected average point score from this group of potential customers. Thus, we must have

$$R_n(F_n(x)) = (x/y)R_n(F_n(y)) + (1-x/y)R_n(F_n(0)).$$

But $R_n(F_n(0)) = R_n(0) = 0$, so we obtain

$$\frac{R_n(F_n(x))}{x} = \frac{R_n(F_n(y))}{y},$$

for all $x$ and $y$ in the support of the equilibrium offer distribution for potential customer $n$. So there is some positive constant $\alpha$ such that, for all $x$ in the support of the offer distribution for potential customer $n$, $R_n(F_n(x)) = \alpha x$.

**Lemma 5.** We have that the constant $\alpha = V/KB$.

**Proof.** The mean offer must equal $Bv_n/V$ under the $F_n$ distribution, therefore

$$\int_{0}^{s_{1}v_{n}/\alpha} x dF_{n}(x) = B\frac{v_{n}}{V}.$$

We also know that a marketing campaign who uses the same offer distribution $F_n$ as all the other marketing campaigns must expect the average point score $v_n/K$, so

$$\frac{v_n}{K} = \int_{0}^{s_1 v_n / \alpha} R_n(F_n(x)) dF_n(x) = \int_{0}^{s_1 v_n / \alpha} \alpha x dF_n(x) \\ = \alpha B \frac{v_n}{V}.$$

From the previous lemma, the support of the $F_n$ distribution is the interval from 0 to $s_1 v_n / \alpha = s_1 KB v_n / V$, and the cumulative distribution satisfies the formula

$$R_n(F_n(x)) = \frac{V}{KB}x, \quad \forall x \in [0, s_1 KB v_n / V].$$

**Lemma 6.** $F_n$ is an equilibrium.

**Proof.** In general, for any nonnegative $x$, we have $R_n(F_n(x)) \le \frac{V}{KB}x$, because when $x > s_1 KB v_n / V$, $R_n(F_n(x)) = R_n(1) = s_1 v_n < \frac{V}{KB}x$. So using any other distribution $G_n$, that has mean $Bv_n / V$ for potential customer $n \in V$ and is on the nonnegative numbers, would give to a marketing campaign an expected score

$$\int_{0}^{\infty} R_{n}(F_{n}(x)) dG_{n}(x) \leq \int_{0}^{\infty} \frac{V}{KB} x dG_{n}(x) \\ = \frac{V}{KB} \int_{0}^{\infty} x dG_{n}(x) = \frac{v_{n}}{K},$$

with equality if the support of $G_n$ is contained in the interval $[0, s_1 KB v_n / V]$. Thus, no marketing campaign can increase his expected score by deviating from $F_n$ to some other distribution, when all other marketing campaigns are using the distribution $F_n$. $\square$

Lemmas 1-6 are the proof of Theorem 2. The previous theorem provides us a method to obtain explicitly the cumulative offer distribution functions under different ranking-scores.

# 4 SIMULATIONS

## Winner-takes-all

We notice that our problem is more general than a simple pairwise competition between marketing campaigns. For the pairwise competition there already exists a solution (see e.g. [23]). However, a pairwise competition is not always what is needed. For example, consider the case when each customer chooses only one marketing campaign to buy a product (it could be for example buying a house, in which most of the potential customers will buy only one house). To see this, consider the example of three competing marketing campaigns X, Y, and Z and five equally valuable customers (for the sake of simplification). Consider the pure strategies

x = (0.2, 0.2, 0.2, 0.2, 0.2),

y = (0.0, 0.0, 0.0, 0.5, 0.5),

z = (0.5, 0.5, 0.0, 0.0, 0.0).

In that case, the pairwise competition gives that marketing campaign X captures 3 out of 5 potential customers to Y (the first three), and that X captures 3
out of 5 potential customers to Z (the last three), thus winning in a pairwise competition against both marketing competitors. However, since each customer will only choose one product, the final outcome will be 2 customers for Y, 2 customers for Z, while only 1 customer for X.

The case where the objective is to be the first evaluated marketing campaign and being second does not provide any value can be represented as follows:

$$s_1 = 1, \quad s_2 = 0, \quad \dots, \quad s_K = 0.$$

In that case $R_n(q) = v_n P(1, q) = v_n q^{K-1}$. Therefore from Theorem 2 the equilibrium cumulative distribution satisfies

$$x = (F(x))^{K-1} KBv_n/V, \quad \forall x \in [0, KBv_n/V],$$

and thus

$$F(x) = \left( \frac{x}{KBv_n/V} \right)^{1/(K-1)}, \quad \forall x \in [0, KBv_n/V].$$

When $K=2$ we recover the result of [23] for pairwise competition. It is also interesting to notice the similarity between this solution and the characterization of the solution for an all-pay auction with one object [25]. We notice that there is a tight relationship between this scenario, Colonel Blotto games and auctions. A Colonel Blotto game can be seen as a simultaneous all-pay auction of multiple items of complete information. An all-pay auction is an auction in which every bidder must forfeit its bid regardless of whether it wins the object which is awarded to the highest bidder. It is an auction of complete information since the value of the object is known to every bidder. In other contexts, this was already noted by Szentes and Rosenthal [26], Roberson [14] and Kvasov [27].

Figure 2(a) gives us the equilibrium offer distribution when we consider that the budget of each marketing campaign is 1000 dollars for three different competing scenarios:

* there are 2 marketing campaigns and the relative value of a customer is $v_n/V = 1/20$;

* there are 4 marketing campaigns and the relative value of a customer is $v_n/V = 1/40$;

* there are 6 marketing campaigns and the relative value of a customer is $v_n/V = 1/60$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Winner-takes-all equilibrium offer distribution when we consider a budget of 1000 dollars, $K=2$ and $v_n/V = 1/20$; $K=4$ and $v_n/V = 1/40$; and $K=6$ and $v_n/V = 1/60$ (for them to have the same support).</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Borda equilibrium offer distribution when we consider a budget of 1000 dollars, $K=2$, $K=4$ and $K=6$ and relative value $v_n/V = 1/20$. We notice that the equilibrium offer distribution of Borda is independent of the number of competing marketing campaigns.</figcaption></figure>
The chosen parameters in the three scenarios allow us to consider the same support of the offers distributions.

We observe that when there are two competing marketing campaigns, the equilibrium offers are made uniformly at random over the support interval from 0 to 100 dollars. However, increasing the number of competing marketing campaigns, we observe that marketing campaigns offers are skewed offering less than the average to most of the potential customers while offering much more than the average for a reduced number of potential customers. In particular, for four marketing campaigns, more than 50% of the potential customers receive offers of less than 14 dollars (the average offer is 25 dollars). This effect is even more pronounced for six marketing campaigns where more than 50% of potential customers receive offers of less than 4 dollars (the average offer is 17 dollars).

## Borda

Another interesting case is when the rank-scoring rule is linearly decreasing with the ranking (we denote it Borda for its similarity to Borda ranking votes). For example, it can be given by

$$s_1 = \frac{(K-1)}{S}, s_2 = \frac{(K-2)}{S}, s_3 = \frac{(K-3)}{S}, \dots, s_K = 0$$

where $S = \sum_{j=1}^{K} s_j = K(K-1)/2$.

The function $R_n(q)$ under that rule is given by

$$\begin{aligned}
R_n(q) &= v_n \sum_{j=1}^{K} P(j, q) \frac{2(K-j)}{K(K-1)} \\
&= \frac{2v_n}{K} \sum_{j=1}^{K} \binom{K-1}{j-1} q^{K-j} (1-q)^{j-1} \frac{K-j}{K-1} \\
&= \frac{2v_n}{K} \sum_{j=0}^{K'} \binom{K'}{j} q^{K'-j} (1-q)^j \left(1 - \frac{j}{K'}\right) \\
&= \frac{2v_n}{K} \left(1 - \frac{K'(1-q)}{K'}\right) = \frac{2v_n}{K} q
\end{aligned}$$

where we have made the change of variable $K' = K - 1$ and use the formula of the expected value of a binomial distribution.

Thus, by the previous theorem

$$\frac{V}{KB}x = \frac{2v_n}{K}F(x), \quad \forall x \in [0, 2Bv_n/V].$$

Therefore,

$$F(x) = \frac{x}{2Bv_n/V}, \quad \forall x \in [0, 2Bv_n/V].$$

Therefore, the equilibrium offer distribution under this rule is a uniform distribution over the interval from 0 to $2Bv_n/V$. We notice that the equilibrium offer distribution is independent of the number of competing marketing campaigns $K$.

Figure 2(b) gives us the equilibrium offer distribution when we consider that the budget for each marketing campaign is 1000 dollars, the relative value of a customer is $v_n/V = 1/20$ and we consider three scenarios with $K = 2, K = 4$, and $K = 6$.

We observe that in these three scenarios the equilibrium offer distribution is uniformly distributed over the support interval from 0 to 100 dollars and it is independent on the number of competing marketing campaigns.

The previously considered scenarios, Winner-takes-all and Borda, are two out of many possible scenarios that can be analyzed and to which our previous results can be applied.

# 5 Conclusions

In this work, we studied advertising competitions in social networks. In particular, we analyzed the scenario of several marketing campaigns determining to which potential customers to market and how many resources to allocate to these potential customers while taking into account that competing marketing campaigns are trying to do the same.

As a consequence of social network dynamics, the importance of every potential customer in the market can be expressed in terms of her network value which is a measure of the influence exerted among her peers and friends and of which we provided an analytical expression for the voter model of social networks.

Defining rank-scoring rules for potential customers and using tools from game theory, we have given a closed form expression of the symmetric equilibrium offer strategy for the marketing campaigns from which no campaign has any interesting to deviate. Moreover, we presented some interesting out of many possible scenarios to which our results can be applied.

## References

[1] P. Domingos and M. Richardson, “Mining the network value of customers,” in Proceedings of
*the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, (New York), pp. 57–66, ACM Press, Aug. 26–29 2001.

[2] M. Richardson and P. Domingos, “Mining knowledge-sharing sites for viral marketing,” in *Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, (New York), pp. 61–70, ACM Press, July 23-26 2002.

[3] G. Nemhauser, L. Wolsey, and M. Fisher, “An analysis of approximations for maximizing submodular set functions I,” *Mathematical Programming*, vol. 14, no. 1, pp. 265–294, 1978.

[4] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in *Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, (New York), pp. 137–146, ACM Press, Aug. 24–27 2003.

[5] D. Kempe, J. Kleinberg, and É. Tardos, “Influential nodes in a diffusion model for social networks,” in *ICALP: Annual International Colloquium on Automata, Languages and Programming*, 2005.

[6] P. Clifford and A. Sudbury, “A model for spatial conflict,” *Biometrika*, vol. 60, no. 3, pp. 581–588, 1973.

[7] R. A. Holley and T. M. Liggett, “Ergodic theorems for weakly interacting infinite systems and the voter model,” *The Annals of Probability*, vol. 3, no. 4, pp. 643–663, 1975.

[8] E. Even-Dar and A. Shapira, “A note on maximizing the spread of influence in social networks,” in *Proceedings of the 3rd International Conference on Internet and Network Economics (WINE’07)*, (Berlin, Heidelberg), pp. 281–286, Springer-Verlag, 2007.

[9] S. Bharathi, D. Kempe, and M. Salek, “Competitive influence maximization in social networks,” in *Internet and Network Economics* (X. Deng and F. Graham, eds.), vol. 4858 of *Lecture Notes in Computer Science*, pp. 306–311, Springer Berlin Heidelberg, 2007.

[10] S. Goyal and M. Kearns, “Competitive contagion in networks,” in *Proceedings of the 44th Symposium on Theory of Computing*, STOC ’12, (New York, NY, USA), pp. 759–774, ACM, 2012.

[11] A. Borodin, Y. Filmus, and J. Oren, “Threshold models for competitive influence in social networks,” in *Proceedings of the 6th International Conference on Internet and Network Economics*, WINE’10, (Berlin, Heidelberg), pp. 539–550, Springer-Verlag, 2010.

[12] G. C. Chasparis and J. Shamma, “Control of preferences in social networks,” in *Proceedings of the 49th IEEE Conference on Decision and Control (CDC)*, pp. 6651–6656, Dec 2010.

[13] O. Gross and R. Wagner, “A continuous colonel blotto game,” in *RAND Corporation RM-408*, 1950.

[14] B. Roberson, “The colonel blotto game.,” *Economic Theory*, vol. 29, no. 1, pp. 1 – 24, 2006.

[15] A. M. Masucci and A. Silva, “Strategic Resource Allocation for Competitive Influence in Social Networks,” in *52nd Annual Allerton Conference on Communication, Control, and Computing*, (Monticello, Illinois, United States), Oct. 1–3 2014.

[16] A. M. Masucci and A. Silva, “Defensive Resource Allocation in Social Networks,” in *54th IEEE Conference on Decision and Control (CDC)*, (Osaka, Japan), pp. 2927–2932, Dec. 15–18 2015.

[17] É. Borel, “La théorie du jeu et les équations intégrales à noyau symétrique,” *Comptes Rendus de l’Académie des Sciences*, vol. 173, pp. 1304–1308, 1921.

[18] É. Borel and J. Ville, *Application de la théorie des probabilités aux jeux de hasard*. 1938.

[19] O. Gross, “The symmetric blotto game,” in *RAND Corporation RM-424*, 1950.

[20] J.-F. Laslier and N. Picard, “Distributive politics and electoral competition,” *Journal of Economic Theory*, vol. 103, pp. 106–130, March 2002.

[21] L. Friedman, “Game-theory models in the allocation of advertising expenditures,” *Operations Research*, vol. 6, no. 5, pp. 699–709, 1958.

[22] B. Roberson, *Allocation Games*. John Wiley & Sons, Inc., 2010.
[23] G. Schwartz, P. Loiseau, and S. Sastry, “The Heterogeneous Colonel Blotto Game,” in *International Conference on Network Games, Control and Optimization (NETGCOOP)*, (Trento, Italy), Oct. 29–31 2014.

[24] R. B. Myerson, “Incentives to cultivate favored minorities under alternative electoral systems,” *The American Political Science Review*, vol. 87, no. 4, pp. 856–869, 1993.

[25] M. R. Baye, D. Kovenock, and C. G. d. Vries, “The all-pay auction with complete information,” *Economic Theory*, vol. 8, no. 2, pp. 291–305, 1996.

[26] B. Szentes and R. W. Rosenthal, “Three-object two-bidder simultaneous auctions: chopsticks and tetrahedra,” *Games and Economic Behavior*, vol. 44, no. 1, pp. 114–133, 2003.

[27] D. Kvasov, “Contests with limited resources,” *Journal of Economic Theory*, vol. 136, pp. 738–748, September 2007.