Stochastic coupon probing in social networks

CMO Council reports that 71% of internet users in the U.S. were influenced by coupons and discounts when making their purchase decisions. It has also been shown that offering coupons to a small fraction of users may affect the purchase decisions of many other users in a social network. This motivates us to study stochastic coupon probing problem in social networks. Assume there is a social network and a set of coupons. We can offer coupons to some users adaptively and those users who accept the offer will act as seeds and influence their friends in the social network. There are two constraints which are called the inner and outer constraints, respectively. The set of coupons redeemed by users must satisfy inner constraints, and the set of all probed users must satisfy outer constraints. One seeks to develop a coupon probing policy that achieves the maximum influence while satisfying both inner and outer constraints. Our main result is a constant approximation policy for the stochastic coupon probing problem for any monotone submodular utility function.