Multi-Grade Revenue Maximization for Promotional and Competitive Viral Marketing in Social Networks

In this paper, we address the problem of revenue maximization (RM) for multi-grade products in social networks by considering pricing, seed selection, and coupon distribution. Previous works on RM often focus on a single product and neglect the use of coupons for promotion. We propose a new optimization problem, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Revenue Maximization of Multi-Grade Product(RMMGP)</i>, to simultaneously determine pricing, seed selection, and coupon distribution for multi-grade products with both promotional and competitive relationships between grades in order to maximize revenue through viral marketing. We prove the hardness and inapproximability of RMMGP and show that the revenue function is not monotone or submodular. To solve RMMGP, we design an approximation algorithm, namely <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Data-Dependent Revenue Maximization (DDRM)</i>, and propose the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Pricing-Seeding-Coupon allocation (PriSCa)</i> algorithm, which uses the concepts of Worth Receiving Probability, Pricing-Promotion Alternating Framework, and Independent/Holistic Customer-Grade Determinant sets. Our experiments on real social networks, using valuation distributions from Amazon.com, demonstrate that PriSCa and DDRM achieve on average 1.5 times higher revenue than state-of-the-art approaches. Additionally, PriSCa is efficient and scalable on large datasets.