Beyond $k$-Seeds: Optimizing Product Discounts for Maximum Net Revenue

TL;DR

Researchers from USTC and NTU have tackled the "pure gravy" problem: how to allocate probabilistic discounts to social network users to maximize Net Revenue (Total Profit - Total Cost). They moved beyond the limited "fixed $k$-seeds" model to produce MaxRev1, an algorithm that is both mathematically guaranteed ($\frac{1}{2}(1-ϵ)$ approximation) and orders of magnitude faster than existing baselines.

The Problem at Hand: The "Revenue" Gap

Most viral marketing research treats users as "switches"—if you pay for them, they are 100% activated. In reality:

1. Probabilistic Response: A 10% discount might only have a 20% chance of activating a user.
2. Cost vs. Profit: Marketers don't just want "reach"; they want the maximum difference between the rewards brought by influenced users and the costs of the discounts given.

Mathematically, this changes the game. While standard Influence Maximization is submodular (exhibiting diminishing returns), Revenue Maximization is not. It’s non-monotone and non-submodular, meaning adding more seeds could actually decrease your total revenue if costs outweigh the propagation benefit.

Methodology: The Surrogate Breakthrough

The authors solve this by introducing a Surrogate Optimization Problem (DISA1). They replace the complex expected cost function with a simpler modular function $W(X)$.

The Intuition

The surrogate function implies a counter-intuitive rule: if you offer multiple discounts to one user, you pay for all of them, but only the largest one helps propagation. While this seems "wasteful," the authors prove a critical Surrogate Lemma: Any approximation solution to this simplified surrogate problem preserves its approximation ratio when mapped back to the original complex problem.

The Architecture of Sampling

To compute these values on billion-scale networks, the paper adapts Reverse-Reachable (RR) sets. Unlike standard RR-sets, these are weighted by heterogeneous node rewards and account for the probabilistic activation of the root node.

MaxRev1: Efficiency Through Estimation

While their first algorithm (MaxRev0) is robust, it is "pessimistically" slow because it generates a fixed, massive number of RR-sets to guarantee safety. MaxRev1 is the "optimistic" sibling:

• It generates a few RR-sets first.
• It uses a custom Monte-Carlo "Estimate" algorithm to check if the current solution is "likely good."
• If the solution passes the statistical check, it stops early.

Experimental Battleground

The team tested MaxRev1 against modified versions of BCT and DGIP (the previous SOTA in profit maximization) across massive datasets like Amazon and LiveJournal.

Key Findings:

• Speed: MaxRev1 is a speed demon. On the LiveJournal dataset (69 million edges), MaxRev1 finished while BCT was still churning after 5 hours.
• Revenue: Because MaxRev1 understands the cost-benefit trade-off of discounts better, it consistently produced positive net revenue, whereas baselines sometimes chose seed sets so expensive they resulted in a net loss.

(Performance on LiveJournal: MaxRev1 achieves high revenue while maintaining a near-flat running time compared to exponentially scaling baselines.)

Critical Insight & Summary

The true value of this paper is the theoretical bridging. By finding a submodular surrogate for a non-submodular problem, the authors unlocked the ability to use "Double Greedy" algorithms and RR-sampling on a much more realistic business problem.

Limitations: The model assumes activation probabilities are known beforehand. In a real-world scenario, these would need to be estimated via A/B testing or historical data, which might introduce noise not accounted for in the current $ϵ$-guarantees.

Future Impact: This framework can be extended to multi-product marketing or competitive social networks where two companies are fighting for the same revenue pool using different discount strategies.