Research Repository

Inequity aversion pricing over social networks: Approximation algorithms and hardness results

Amanatidis, Georgios and Fulla, Peter and Markakis, Evangelos and Sornat, Krzysztof (2021) 'Inequity aversion pricing over social networks: Approximation algorithms and hardness results.' Theoretical Computer Science, 871. pp. 62-78. ISSN 0304-3975

Inequity_Aversion_Problem__TCS_j_version_(1).pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (491kB) | Preview
1606.06664v3.pdf - Submitted Version

Download (322kB) | Preview


We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i.e., it captures the fact that prices offered to neighboring nodes should not differ significantly. We first provide approximation algorithms for a natural class of instances, where the total revenue is the sum 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 instance, to settings where the seller will only consider a fixed number of discount types or special offers. To complement our positive results, we resolve one of the open questions posed in [2] 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 large, or even when the number of allowed distinct prices is as small as three. Finally, we study extensions of the model regarding the demand type of the clients.

Item Type: Article
Additional Information: A preliminary conference version of this work appeared in MFCS 2016
Uncontrolled Keywords: Revenue maximization; Inequity aversion; Social networks; Pricing; Approximation algorithms
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 26 Nov 2021 14:41
Last Modified: 26 Apr 2022 01:00

Actions (login required)

View Item View Item