中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
Approximation algorithms for pricing with negative network externalities

文献类型：期刊论文

作者Cao, Zhigang1; Chen, Xujin1; Hu, Xiaodong1; Wang, Changjun2
刊名JOURNAL OF COMBINATORIAL OPTIMIZATION
出版日期2017-02-01
卷号33期号:2页码:681-712
关键词Pricing Approximation algorithms NP-hardness Social networks Random networks Negative externalities
ISSN号1382-6905
DOI10.1007/s10878-015-9988-1
英文摘要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.
资助项目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记录号WOS:000394241000019
出版者SPRINGER
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/24705]  
专题应用数学研究所
通讯作者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.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。