NP-Hardness and Approximation Algorithms for Iterative Pricing on Social Networks with Externalities

We study how a monopolist seller should price an indivisible product iteratively to the consumers who are connected by a known link-weighted directed social network. For two consumers u and v, there is an arc directed from u to v if and only if v is a fashion leader of u. Assuming complete information about the network, the seller offers consumers a sequence of prices over time and the goal is to obtain the maximum revenue. We assume that the consumers buy the product as soon as the seller posts a price not greater than their valuations of the product. The product's value for a consumer is determined by three factors: a fixed consumer specified intrinsic value and a variable positive (resp. negative) externality that is exerted from the consumer's out(resp. in)-neighbours. The setting of positive externality is that the influence of fashion leaders on a consumer is the total weight of links from herself to her fashion leaders who have owned the product, and more fashion leaders of a consumer owning the product will increase the influence (external value) on the consumer. And the setting of negative externalities is that the product's value of showing off for a consumer is the total weight of links from her followers who do not own the product to herself, and more followers of a consumer owning the product will decrease this external value for the consumer. We confirm that finding an optimal iterative pricing is NP-hard even for acyclic networks with maximum total degree 3 and with all intrinsic values zero. We design a greedy algorithm which achieves (n-1) approximation for networks with all intrinsic values zero and show that the approximation ratio n-1 is tight. Complementary to the hardness result, we design a (1.8 + epsilon)-approximation algorithm for Barabasi-Albert networks.