Source-linked AI summary
Pricing strategies for viral marketing on Social Networks
David Arthur, Rajeev Motwani, Aneesh Sharma, Ying Xu
TL;DR
Sellers seek to monetize social-network product recommendations by choosing prices and incentives, but optimal strategy computation is NP-hard. The paper proposes a non-adaptive influence-and-exploit strategy with a constant-factor revenue guarantee, and reports that local search improves it in experiments.
Problem
Sellers using viral marketing face difficult choices about whom to incentivize and what rewards to offer while seeking revenue from social-network recommendations.
Source: §1 · pp. 1–2Method
The proposed non-adaptive influence-and-exploit strategy gives free products to spanning-tree interior nodes and seeks revenue from its leaves.
Source: §5 · p. 13Results
Computing the optimal non-adaptive strategy is NP-hard, while the proposed strategy guarantees expected revenue within a constant factor of optimal adaptive revenue.
Source: §5 · p. 13Takeaways & Limitations
In the reported experiments, adding local search increases revenue over the influence-and-exploit strategy alone.
Source: §4.1 · p. 13The model assumes buyers send recommendations to all friends and ignores any cost of doing so.
Source: §6 · p. 13
Abstract
from arXiv · showhide
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
The paper studies how sellers can use social-network recommendations, prices, and cashback incentives to monetize products while accounting for buyers’ responses to friends and offers. It presents an influence-and-exploit strategy, analyzes its guarantees, and relates the model to earlier influence and pricing work.
1 Introduction
- Social-network data offer targeted monetization potential, but contextual-advertising approaches do not leverage network ties and viral campaigns leave difficult incentive and allocation choices.The choices include whom to sample, how many samples to distribute, and what recommender rewards sellers can afford.Source: §1 · pp. 1–2
1.1 Our contributions
- A non-adaptive strategy achieves expected revenue within a constant factor of the optimal adaptive strategy for a wide variety of buyer models, while finding an optimal non-adaptive strategy is NP-hard.The guarantee includes natural extensions of the Linear Threshold and Independent Cascade models.Source: §1.1 · p. 3
- The influence-and-exploit strategy offers free products to influencer nodes and charges selected revenue sources, using a maximum-leaf spanning tree to divide those roles.Cashback amounts are set as a fixed fraction of expected revenue.Source: §1.1 · p. 3
- In practice, combining local search with the influence-and-exploit strategy outperforms using either approach alone in the reported experiments.The experiments also report that the strategy performs well without local search.Source: §1.1 · p. 3
1.2 Related work
- Unlike influence-maximization work that treats influence as a proxy for revenue without pricing, this model lets recommendation cascades determine offer timing, unlike the arbitrary-node offers in.Both approaches use influence-and-exploit ideas, despite their different models.Source: §1.2 · pp. 3–4
2 The Formal Model
The formal model represents sales as a recommendation cascade in which the seller chooses prices and cashback to maximize expected revenue. Buyer decisions generalize Independent Cascade and Linear Threshold models, subject to assumptions that also parameterize model complexity.
2 The Formal Model
- New buyers receive offers when newly active neighbors recommend the product, decide whether to buy at the offered price, and may trigger a cashback to one recommender.The cascade repeats until a step produces no purchases.Source: §2 · p. 4
- The seller seeks a revenue-maximizing strategy for a given graph and seed set; non-adaptive policies commit to each buyer’s price before the cascade begins.The stated goals include proving NP-hardness, constructing a constant-factor approximation, and bounding the loss from non-adaptivity.Source: §2 · p. 4
- The exposition initially sets cashback to zero, with the authors stating that results can be generalized to positive cashback.A positive cashback is intended to incentivize buyers to pass on recommendations.Source: §2 · p. 4
2.1 Buyer decisions
- The model assumes known buyer behavior, a full price normalized to 1, and acceptance of free offers, which also prompt buyers to recommend the product.The paper says buyer behavior can be estimated through experiments and observed behavior.Source: §2.1 · p. 5
- The approximation’s model-complexity parameter uses bounded expected revenue on a seeded line and a condition ensuring some purchase probability at a price when enough neighbors recommend.These conditions rule out extreme buyer inertia and are shown to hold for Independent Cascade and Linear Threshold models.Source: §2.1 · p. 5
- The model allows broad buyer-decision rules, including price-dependent Independent Cascade variants in which an offer at C(x) is accepted with probability x.Repeated recommendations are checked independently, but a buyer purchases at most once.Source: §2.1 · p. 5
- ICMC has bounded model complexity: maximum slope m (|C(x) − C(y)| ≤ m|x − y| for all x,y) gives O(m^2), while n regularly spaced steps give O(n^2) complexity.The step-function result applies when C is a step function with n regularly spaced steps.Source: §2.1 · p. 6
- The price-dependent Linear Threshold variant uses random thresholds and influence that depends on price; a buyer accepts a free offer, while positive-price acceptance depends on neighbors’ recommendations.The exposition focuses on equal influence from neighbors.Source: §2.1 · pp. 6–7
3 Approximating the Optimal Revenue
The section presents STRATEGYMAXLEAF, a non-adaptive influence-and-exploit strategy, and proves it achieves revenue within a model-dependent constant factor of the optimal adaptive strategy. Its guarantee rests on a maximum-leaf spanning tree and bounds relating good vertices to both the strategy’s revenue and the network’s revenue ceiling.
3 Approximating the Optimal Revenue
- STRATEGYMAXLEAF uses a maximum-leaf spanning tree, offering the product free to interior nodes and charging leaves.The MAXLEAF algorithm has a nearly linear-time constant-factor approximation, making the approach practical for large social-network graphs.Source: §3 · p. 7
- The analysis bounds the strategy by showing MAXLEAF finds Ω(g) leaves and decomposes the network into paths whose revenue is bounded by O(L · g).Together, the lower and upper bounds yield the constant-factor guarantee.Source: §3 · pp. 7, 10
- With g good vertices, STRATEGYMAXLEAF earns expected revenue Ω((1 − f)cq · g), while any strategy earns at most O(L · g).Good vertices are vertices of degree at least 3 and their neighbors; the strategy’s revenue comes from the spanning tree’s leaves.Source: §3 · pp. 7, 9
- O(K)-competitive revenue: STRATEGYMAXLEAF’s expected revenue is within a model-complexity-dependent factor of the optimal adaptive or non-adaptive strategy.The section also states that the adaptivity gap is O(K).Source: §3 · p. 10
- Cashbacks can be set as a fraction of expected revenue, reducing total profit by a constant factor while incentivizing recommendations.The analysis otherwise carries through as before.Source: §3 · p. 10
4 Local Search
Local search refines seller strategies by testing node-level price changes, and shared randomness helps compare alternatives. Experiments show it improves revenue, especially when paired with a strong starting strategy, while weak starts and noisy estimates remain concerns.
4 Local Search
- LOCALSEARCH tests candidate prices for one node at a time and changes that node’s price when estimated revenue exceeds the current estimate by a threshold.It repeats across nodes until no further improvements are found.Source: §4 · p. 10
- Comparisons reuse the same threshold lists across strategies, reducing noise from independent random outcomes, though unrepresentative lists can still mislead.The method reframes randomness as thresholds fixed before the sales process.Source: §4 · p. 11
- LOCALSEARCH can make estimation mistakes, settle at a strategy no local change improves, or take many steps from a poor start; it works well from STRATEGYMAXLEAF.The authors report that local search can improve revenue with high probability for simulatable input policies.Source: §4 · p. 11
4.1 Experimental Results
- Experiments compare RANDOMPRICING, which assigns each node a random price, with STRATEGYMAXLEAF, using a 1,000-node preferential-attachment graph and a 10,000-node YouTube subgraph.The preferential-attachment simulation uses a random seed and a step-function probability model; the YouTube network has millions of nodes, but only a subset is tested.Source: §4.1 · pp. 11, 13
- STRATEGYMAXLEAF outperformed RANDOMPRICING before refinement; LOCALSEARCH improved both, but RANDOMPRICING still failed to match it on the 10,000-node YouTube subset.The comparison also appears on a 1,000-node preferential-attachment graph; Figure 1 plots revenue across LOCALSEARCH iterations.Source: Figure 1 · p. 12, §4.1 · p. 13
5 Conclusions
The paper establishes that optimal non-adaptive revenue maximization is NP-hard, but gives a non-adaptive influence-and-exploit strategy with a constant-factor guarantee against the optimal adaptive strategy under fairly general probability conditions.
5 Conclusions
- A max-leaf spanning-tree strategy offers interior nodes the product for free and extracts profit from leaves, achieving revenue within a constant factor of the optimal adaptive strategy under fairly general probability conditions.Computing the optimal revenue-maximizing non-adaptive strategy is NP-hard.Source: §5 · p. 13
6 Open Questions
The paper identifies open questions about extending the influence model, relaxing assumptions on purchase probabilities, and accounting for strategic buyers and recommendation costs.
6 Open Questions
- A broader class of influence models than the one examined remains an open direction.Source: §6 · p. 13
- It remains unclear whether the assumptions on C(·) are minimal, and the authors propose removing the assumption that some price yields certain acceptance.Source: §6 · p. 13
- The model treats buyers as non-strategic and assumes they recommend to all friends without cost; modeling strategic payoff-maximizing nodes is left open.Source: §6 · pp. 13–14
8 Appendix
The appendix proves that optimal network pricing is NP-hard by reducing bounded-degree vertex cover to a pricing instance. In the construction, the optimal free-price choices in one layer correspond to a minimum vertex cover.
8.1 Hardness of finding the optimal strategy
- The reduction maps vertices to V1 and edges to V2, joining incident pairs and attaching k = 20d leaf nodes to each V2 node.It uses a four-layer graph with a single initially active node s linked to V1.Source: §8.1 · p. 15
- In an optimal strategy, every V2 node is free, every V3 node is full-price, and each V2 node is adjacent to a free V1 node.The pricing strategy partitions nodes into free and full-price offers.Source: §8.1 · pp. 15–16
- The free V1 nodes form a minimum vertex cover because every V2 node must be adjacent to one of them.The constructed V1–V2 incidence graph represents the bounded-degree vertex-cover instance.Source: §8.1 · pp. 15–16
- Two Coupon Optimal Strategy Problem is NP-Hard.The reduction shows that optimal pricing in this limited scenario can calculate a minimum vertex cover of any bounded-degree graph.Source: §8.1 · p. 16