KMS Of Academy of mathematics and systems sciences, CAS
Approximation algorithms for pricing with negative network externalities | |
Cao, Zhigang1; Chen, Xujin1; Hu, Xiaodong1; Wang, Changjun2 | |
2017-02-01 | |
发表期刊 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
ISSN | 1382-6905 |
卷号 | 33期号:2页码:681-712 |
摘要 | We study the problems of pricing an indivisible product to consumers who are embedded in a given social network. The goal is to maximize the revenue of the seller by the so-called iterative pricing that offers consumers a sequence of prices over time. The consumers are assumed to be impatient in that they 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 two factors: a fixed consumer-specified intrinsic value and a variable externality that is exerted from the consumer's neighbors in a linear way. We focus on the scenario of negative externalities, which captures many interesting situations, but is much less understood in comparison with its positive externality counterpart. Assuming complete information about the network, consumers' intrinsic values, and the negative externalities, we prove that it is NP-hard to find an optimal iterative pricing, even for unweighted tree networks with uniform intrinsic values. Complementary to the hardness result, we design a 2-approximation algorithm for general weighted networks with (possibly) nonuniform intrinsic values. We show that, as an approximation to optimal iterative pricing, single pricing works fairly well for many interesting cases, such as forests, ErdAs-R,nyi networks and Barabasi-Albert networks, although its worst-case performance can be arbitrarily bad in general networks. |
关键词 | Pricing Approximation algorithms NP-hardness Social networks Random networks Negative externalities |
DOI | 10.1007/s10878-015-9988-1 |
语种 | 英语 |
资助项目 | NNSF of China[11531014] ; NNSF of China[11222109] ; NNSF of China[11471326] ; CAS Program for Cross & Cooperative Team of Science & Technology Innovation |
WOS研究方向 | Computer Science ; Mathematics |
WOS类目 | Computer Science, Interdisciplinary Applications ; Mathematics, Applied |
WOS记录号 | WOS:000394241000019 |
出版者 | SPRINGER |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/24706 |
专题 | 应用数学研究所 |
通讯作者 | Wang, Changjun |
作者单位 | 1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China |
推荐引用方式 GB/T 7714 | Cao, Zhigang,Chen, Xujin,Hu, Xiaodong,et al. Approximation algorithms for pricing with negative network externalities[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2017,33(2):681-712. |
APA | Cao, Zhigang,Chen, Xujin,Hu, Xiaodong,&Wang, Changjun.(2017).Approximation algorithms for pricing with negative network externalities.JOURNAL OF COMBINATORIAL OPTIMIZATION,33(2),681-712. |
MLA | Cao, Zhigang,et al."Approximation algorithms for pricing with negative network externalities".JOURNAL OF COMBINATORIAL OPTIMIZATION 33.2(2017):681-712. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论