文章基本信息

标题：Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
本地全文：下载
作者：Georgios Amanatidis ; Evangelos Markakis ; Krzysztof Sornat 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：9:1-9:13
DOI：10.4230/LIPIcs.MFCS.2016.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity aversion, i.e., prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al., by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions of the model of Alon et al., regarding the allowed set of prices.
关键词：inequity aversion; social networks; revenue maximization