Stochastic Coupon Probing in Social Networks

Shaojie Tang

Abstract

This paper investigates the "Stochastic Coupon Probing" problem, where a marketer adaptively offers coupons to social network users to maximize brand influence under budget and user fatigue constraints. We propose a randomized policy, stoch-CP, which balances low-value and high-value coupon strategies. Our theoretical analysis proves that this policy achieves a constant approximation ratio of the optimal expected influence, even with correlated user responses and complex constraints.

Introduction

Traditional Influence Maximization (IM) often oversimplifies user activation, assuming that selected "seed" nodes are automatically activated. In practice, users typically require incentives, such as coupons, to promote a product. Furthermore, real-world marketing is inherently stochastic and adaptive: costs are only incurred upon coupon redemption, and a user's rejection of a high-value offer often implies rejection of lower-value ones.

This work addresses the Stochastic Coupon Probing problem, which incorporates:

  1. Inner Constraints: A hard budget ($B$) on the total value of redeemed coupons.
  2. Outer Constraints: A limit ($K$) on the number of times a specific user can be probed to prevent marketing fatigue.
  3. Rational User Behavior: Correlated realizations where rejection of a discount suggests a lower probability of accepting smaller discounts.

Problem Formulation and Notation

To navigate the complexity of adaptive probing with correlated outcomes, we define a formal notation for the ground sets, decision matrices, and action spaces involved in the optimization process.

Table 1: Summary of notations and their meanings used in the stochastic coupon probing framework.

The goal is to select a sequence of actions from the action space $S \triangleq \mathcal{V} \times \Psi$ to maximize the expected influence cascade $I(\mathcal{U})$ while staying within the budget $B$.

Methodology

The proposed stoch-CP policy is a randomized algorithm that chooses between two specialized sub-algorithms with equal probability, ensuring robustness across different budget scenarios.

ALG I: The Low-Value Specialist

This algorithm targets coupons with values $\le B/2$. It employs a Continuous Greedy process to solve a relaxed version of the influence maximization problem. The resulting fractional solution is then transformed into a discrete sequence of actions using Contention Resolution techniques. A key technical simplification proven in the paper is that restricting the policy to "consecutive probing" (probing the same user in successive rounds) does not significantly degrade the approximation ratio, making the optimization more tractable.

ALG II: The High-Value Specialist

Focusing on high-value coupons, this algorithm uses a simple greedy ordering. It sorts users by their individual potential influence and probes them sequentially with the most valuable available coupons. This ensures that the policy captures "big wins" that might be missed by the more granular approach of ALG I.

Theoretical Results

The primary contribution of this work is the mathematical proof that the stoch-CP policy achieves a constant approximation ratio. For the standard model, the policy is guaranteed to achieve at least $\frac{(1-1/e)(1-\beta)(1-2\beta)\beta}{2}$ of the maximum possible expected influence, where $\beta$ is a tuning parameter.

The framework is further extended to accommodate a distribution budget ($W$), which limits the total number of unique users contacted. The modified E-stoch-CP algorithm maintains a constant approximation ratio even under these nested constraints.

Discussion and Future Work

While the constant approximation ratio is a significant theoretical milestone, the practical performance may vary based on the choice of $\beta$. Additionally, the computational complexity of the Continuous Greedy step—involving linear programming and expectation estimation—presents a challenge for scaling to massive social networks with millions of nodes.

Future research may explore more dynamic user thresholds or the application of this framework to other stochastic optimization problems characterized by correlated realizations and complex, nested constraints.

Summary updated

BibTeX
@inproceedings{tang2018stochastic,
  author = {Shaojie Tang},
  title = {{Stochastic Coupon Probing in Social Networks}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2018},
  doi = {10.1145/3269206.3271771},
}
Figure