Title: Toward Optimal Coupon Allocation in Social Networks: An Approximate Submodular Optimization Approach,
Abstract: 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 (called seed users)
may affect the purchase decisions of many other users in a social network. This
motivates us to study the optimal coupon allocation problem, and our objective
is to allocate coupons to a set of users so as to maximize the expected
cascade. Different from existing studies on influence maximizaton (IM), our
framework allows a general utility function and a more complex set of
constraints. In particular, we formulate our problem as an approximate
submodular maximization problem subject to matroid and knapsack constraints.
Existing techniques relying on the submodularity of the utility function, such
as greedy algorithm, can not work directly on a non-submodular function. We use
$\epsilon$ to measure the difference between our function and its closest
submodular function and propose a novel approximate algorithm with
approximation ratio $\beta(\epsilon)$ with $\lim_{\epsilon\rightarrow
0}\beta(\epsilon)=1-1/e$. This is the best approximation guarantee for
approximate submodular maximization subject to a partition matroid and knapsack
constraints, our results apply to a broad range of optimization problems that
can be formulated as an approximate submodular maximization problem.